Compact recognizers of episode sequences.
Given two strings X=a1...an and P=b1...bm over an alphabet , the problem of testing whether P occurs as a subsequence of X is trivially solved in linear time. It is also known that a simple O (n log ||) time preprocessing of X makes it easy to decide subsequently, for any P and in at most |P| log || character comparisons, whether P is a subsequence of X. These problems become more complicated if one asks instead whether P occurs as a subsequence of some substring Y of X of bounded length. This paper presents an automaton built on the textstring X and capable of identifying all distinct minimal substrings Y of X having P as a subsequence. By a substring Y being minimal with respect to P, it is meant that P is not a subsequence of any proper substring of Y. For every minimal substring Y, the automaton recognizes the occurrence of P having the lexicographically smallest sequence of symbol positions in Y. It is not difficult to realize such an automaton in time and space O (n2) for a text of n characters. One result of this paper consists of bringing those bounds down to linear or O (n log n), respectively, depending on whether the alphabet is bounded or of arbitrary size, thereby matching the corresponding complexities of automata constructions for offline exact string searching. Having built the automaton, the search for all lexicographically earliest occurrences of P in X is carried out in time O (i=1mroccii) or O (n+i=1mroccii log n), depending on whether the alphabet is fixed or arbitrary, where rocci is the number of distinct minimal substrings of X having b1...bi as a subsequence (note that each such substring may occur many times in X but is counted only once in the bound). All log factors appearing in the above bounds can be further reduced to log log by resorting to known integer-handling data structures.
Introduction
We consider the problem of detecting occurrences of a pattern string as a subsequence of a substring
of bounded length of a larger text string. Variants of this problem arise in numerous applications,
ranging from information retrieval and data mining (see, e.g., [10]) to molecular sequence analysis
(see, e.g., [12]) and intrusion and misuse detection in a computer system (see, e.g., [9]).
Recall that given a pattern
say that P occurs as a subsequence of X iff there exist indices 1 - such that
a
this case we also say that the substring
a
of X is a realization of P beginning at position i 1 and ending at position i m in X. We reserve the
term occurrence for the sequence i 1 . It is trivial to compute, in time linear in jXj, whether
occurs as a subsequence of X. Alternatively, a simple O(nj\Sigmaj) time preprocessing of X makes
it easy to decide subsequently for any P , and in at most jP j character comparisons, whether P
is a subsequence of X. For this, all that is needed is a pointer leading, for every position of X
and every alphabet symbol, to the closest position occupied by that symbol, as exemplified in Fig.
1. Slightly more complicated arrangements, such as developed in [2], can accommodate within
preprocessing time O(n log j\Sigmaj) and space linear in X also the case of an arbitrary alphabet size,
though introducing an extra log j\Sigmaj cost factor in the search for P . We refer also to [3] for additional
discussion of subsequence searching.
a
a
a
a
a
a
a
a
a
a

Figure

1: Recognizer for the subsequences of abaababaabaababa, shown here without explicit labels
on forward "skip" links
These problems become more complicated if one asks instead whether X contains a realization
Y of P of bounded length, since the earliest occurrence of P as a subsequence of X is not guaranteed
to be a solution. In this case, one would need to apply the above scheme to all suffixes of X or find
some other way to detect the minimal realizations Y of P in X, where a realization is minimal if no
substring of Y is a realization of P . Algorithms for the so-called episode matching problem, which
consists of finding the earliest occurrences of P in all minimal realizations of P in X have been
given previously in [7]. An occurrence i 1 of P in a realization Y is an earliest occurrence
if the string lexicographically smallest with respect to any other possible occurrence
of P in Y . The algorithms in [7] perform within roughly O(nm) time, without resorting to any
auxiliary structure or index based on the structure of the text.
In some applications of exact string searching, the text string is preprocessed in such a way
that any subsequent query regarding pattern occurrence takes time proportional to the size of the
pattern rather than that of the text. Notable among these constructions are those resulting in
structures such as subword trees and graphs (refer to, e.g., [1, 6]). Notice that the answer to the
typical query is now only whether or not the pattern appears in the text. If one wanted to locate
all the occurrences as well, then the time would become O(jwj denotes the total
number of occurrences. These kinds of searches may be considered as on line with respect to the
pattern, in the sense that preprocessing of the pattern is not allowed, but are off-line in terms of
the ability to preprocess the text. In general, setting up efficient structures of this kind for non
exact matches seems quite hard: sometimes a small selection of options is faced, that represent
various compromises among a few space and time parameters. In [11, 5], the idea of limiting the
search only to distinct substrings of the text is applied to perform approximate string matching
with suffix trees.
This paper addresses the construction of an automaton, based on the textstring X and suitable
for identifying, for any given P , the set of all distinct minimal realizations of P in X. Specifically,
the automaton recognizes, for each such realization Y , the earliest occurrence of P in Y . The
preceding discussion suggests that it is not difficult to realize such an automaton in time and space
a text of n characters. The main result of the paper consists of bringing those bounds
down to linear or or O(n log n), depending on the assumption on alphabet size, thus matching the
cost of preprocessing in off-line exact string searching with subword graphs. Our construction can
be used, in particular, in cases in which the symbols of P are affected by individual "expiration
deadlines", expressed, e.g., in terms of positions of X that might elapse at most before next symbol
(or, alternatively, the entire occurrence of pattern P ) must be matched.
The paper is organized as follows. In next section, we review the basic structure of Directed
Acyclic Word Graphs and outline an extension of it that constitutes a first, quadratic space realization
of our automaton. A more compact implementation of the automaton is addressed in the
following section. Such an implementation requires linear space but only in the case of a finite
alphabet. The case of general alphabets is addressed in the last section, and it results in a trade-off
between seach time and space.
2 DAWGs and Skip-edge DAWGs
Our main concern in this section is to show how the text X can be preprocessed in a such a way,
that a subsequent search for the earliest occurrences in X of all prefixes of any given P is carried
out in time bounded by the size of the output rather than that of the input. Our solution rests on
an adaptation of the partial minimal automaton recognizing all subwords of a word, also known
as the DAWG (Directed Acyclic Word Graph) [4] associated with that word. Let W be the set of
all subwords of the text X, and P i m) be the ith prefix of P . Our modified graph can
be built in time and space quadratic or linear in the length of the input, depending on whether
the size of the input alphabet is arbitrary or bounded by a constant, respectively, and it can be
searched for the earliest occurrences in all rocc i distinct realizations of P m) in time
O(
Here a realization of P m) is any minimal substring of X having
quence. Note that a realization of P i is a substring that may occur many times in X but is counted
only once in our bound.
We begin our discussion by recalling the structure of the DAWG for string First,
we consider the following partial deterministic finite automaton recognizing all subwords of X.
Given two words X and Y , the end-set of Y in X is the set endpos X (Y for some
Two strings W and Y are equivalent on X if endpos X (W
The equivalence relation instituted in this way is denoted by jX and partitions the set of all strings
over \Sigma into equivalence classes. It is convenient to assume henceforth that our text string X is
fixed, so that the equivalence class with respect to jX of any word W can be denoted simply by
is the set of all strings that have occurrences in X terminating at the same set of
positions as W . Correspondingly, the finite automaton A recognizing all substrings of X will have
one state for each of the equivalence classes of subwords of X under jX . Specifically:
1. The start state of A is [ffl], where ffl is the empty word;
2. For any state [W ] and any symbol a 2 \Sigma, there is a transition edge leading to state [Wa];
3. The state corresponding to all strings that are not substrings of W , is the only nonaccepting
state, all other states are accepting states.
Deleting from A above the nonaccepting state and all of its incoming arcs yields the DAWG
associated with X. As an example, the DAWG for abbbaabaa is reported in Figure 2.
a
a
a
a
a
a a a aa a

Figure

2: An example DAWG
We refer to, e.g., [4, 6], for the construction of a DAWG. Here we recall some basic properties
of this structure. This is clearly a directed acyclic graph with one sink and one source, where every
state lies on a path from the source to the sink. Moreover, the following two properties hold [4, 6].
Property 1 For any word X, the sequence of labels on each distinct path from the source to the
sink of the DAWG of X represents one distinct suffix of X.
Property 2 For any word X, the DAWG of X has a number of states Q such that jXj
a number of edges E such that jXj -
Recalling the basic structure of a subsequence detector such as the one of Fig. 1, it is immediate
to see how the DAWG of X may be adapted to recognize all earliest occurrences of any given pattern
P as a subsequence of X. Essentially, we need to endow every node ff with a number of "downward
failure links" or skip-edges. Each such link will be associated with a specific alphabet symbol, and
the role of a link leaving ff with label a will be to enable the transition to a descendant of ff on
a nontrivial (i.e., with at least two original edges) path labeled by a string in which symbol a
occurs only as a suffix. Formally, a skip link labeled a is set from the node ff associated with the
equivalence class [W ] to any other node fi, associated with some class [WV a] such that V 6= ffl and
a does not appear in V . Thus, a skip-edge labeled a is issued from ff to each one of its closest
descendants other than children where an original incoming edge labeled a already exists. As an
example, Figure 3 displays a partially augmented version of the DAWG of Figure 2, with skip-edges
added only from the source and its two adjacent nodes. We will use the words full skip-edge DAWG
to refer to the structure that would result from adding skip-edges to all nodes of the DAWG. Clearly,
the role of skip-edges is to serve as shortcuts in the search. However, these edges also introduce
"nondeterminism" in our automaton, in particular, now more than one path from the source may
be labebed with a prefix of P . The following theorem is used to summarize the discussion.
Theorem 1 For any string X of n symbols, the full skip-edge DAWG of X can be built in O(n 2 j\Sigmaj)
time and space, and it can be searched for all rocc i earliest realizations of prefixes of any pattern
of m symbols in time
O(
Proof. Having built the DAWG in time O(n log j\Sigmaj) by one of the existing methods, the augmentation
itself is easily carried out in O(n 2 j\Sigmaj) time and space, e.g., by adaptation of a depth-first visit
of the DAWG, as follows. First, when the sink is first reached, it gets assigned NIL skip-edges for
all alphabet symbols; next, every time we backtrack to a node ff from some other node fi, the label
of arc (ff; fi) and the skip-edges defined at fi are used to identify and issue (additional) skip-edges
from ff. The bound follows from the fact that for every node and symbol, skip-edges might have
to be directed to \Theta(n) other nodes.
The time bound on searches is subtended by an immediate consequence of Property 1. Namely,
we have that P occurs as a subsequence of X beginning at some specific position i of X if and only
if the following two conditions hold: (1) there is a path - labeled P from the source to some node ff
of the full skip-edge DAWG of X, and (2) it is possible to replace each skip-edge in - with a chain
of original edges in such a way that the resulting path from the source to ff is labeled by consecutive
symbols of X beginning with position i. Therefore, the search for P is trivially performed, e.g.,
as a depth-first visit of all longest paths in the full skip-edge DAWG that start at the source and
are labeled by some prefix of P . (Incidentally, the depth of the search may be suitably bounded
by taking into account the length of P , and lengths of the shunted paths.) Each edge is traversed
precisely once, and to each time we backtrack from a node corresponds a prefix of P which cannot
be continued along the path being explored, whence the claimed time bound for searches. 2
The search-time bound of Theorem 1 is actually not tight, an even tighter one being represented
by the total number of distinct nodes traversed. In practice, this may be expected to be proportional
to some small power of the length of P . Consideration of symbol durations may also be added to the
construction phase, thereby further reducing the number of skip-edges issued. The main problem,
however, is that storing a full skip-edge DAWG would take an unrealistic \Theta(n 2 ) worst-case space
even when the alphabet size is a constant (cf. Fig. 3). The remainder of our discussion is devoted
to improving on this space requirement.
a
a
a
a
a
a
a
a
a
a a
a
a a a a

Figure

3: Adding skip-edges from the source and its two adjacent nodes
Compact skip-edge DAWGs
Observe that by Property 1 each node of the DAWG of X can be mapped to a position i in X in
such a way that some path (say, to fix the ideas, the longest one) from that node to the sink is
labeled precisely by the suffix a i a i+1 :::a n of X. As is easy to check, such a mapping assignment can
be carried out during the construction of the DAWG at no extra cost. Observe also that there is
always a path labeled X in the DAWG of X. This path will be called the backbone of the DAWG.
Let the depth of a node - in the DAWG be the length of the longest word W on a path from the
source to -. We have then that, by the definition of a DAWG, every other path from the source to
- is labeled by one of the consecutive suffixes of W down to a certain minimum length (these are
the words in the equivalence class [W ] that occur in X only as suffixes of W ). It also follows that,
considering the set of immediate predecessors of - on these paths, their depths must be mutually
different and each smaller than jW j. Finally, the depths of the backbone nodes must be given by
the consecutive integers from 0 (for the source) to n (for the sink).
In order to describe how skip links are issued on the DAWG, we resort to a slightly extended
version of a spanning tree of the DAWG (see Fig. 4). The extension consists simply of replicating
the nodes of the DAWG that are adjacent to the leaves of the spanning tree, so as to bring into
the final structure also the edges connecting those nodes (any of these edges would be classified as
either a "cross edge" or a "descendant edge" in the depth-first visit of the DAWG resulting in our
tree). We stipulate that the duplicates of node - are created in such a way, that this will leave -
connected to the immediate predecessor - of - with the property that the depth of - in the DAWG
equals the depth of - minus 1. Note that such a node - must exist for each - except the source.
Note also that our spanning tree must contain a directed path that corresponds precisely to the
backbone of the DAWG.
Let T be the resulting structure. Clearly, T has the same number of edges of the DAWG.
Moreover, each node of the DAWG is represented in T at most once for every incoming edge.
Therefore, the size of T is linear in jXj. We use the more convenient structure of T to describe
how to set skip-edges and other auxiliary links. In actuality, edges are set on the DAWG.
Since the introduction of a skip-edge for every node and symbol would be too costly, we will
endow with such edges only a fraction of the nodes. Specifically, our policy will result in a linear
number of skip-edges being issued overall. From any node not endowed with a skip-edge on some
desired symbol, the corresponding transition will be performed by first gaining access to a suitable
node where such a skip-edge is available, and then by following that edge. In order to gain access
from any node to its appropriate "surrogate" skip-edge, we need to resort to two additional families
of auxiliary edges, respectively called deferring edges and back edges. The space overhead brought
about by these auxiliary edges will be only O(n \Delta j\Sigmaj), hence linear when \Sigma is finite. The new
edges will be labeled, just like skip-edges, but unlike skip-edges their traversal on a given input
symbol does not consume that symbol. Their full structure and management will be explained in
due course.
We now describe the augmentation of the DAWG. With reference to a generic node fl of T , we
distinguish the following cases.
outdegree 1. Assume that the edge leaving fl is labeled a, and consider
the original path - from fl to a branching node or leaf of T , whichever comes first. For every
first occurrence on - of an edge (j; fi) labeled - a 6= a, direct a skip-edge labeled -
a from fl to
a
a a
a a a a
a
a
a
a

Figure

4: An extended spanning tree T with sample skip-edges
fi. For every symbol of the alphabet not encountered on - set a deferring edge from fl to the
branching node or leaf found at the end of -.
ffl Case 2: Node fl is a branching node. The auxiliary edges to be possibly issued from fl are
determined as follows (see also Fig. 5). Let j be a descendant other than a child of fl in T ,
with an incoming edge labeled a, and let - be the longest ascending original path from j such
that no other edge of - is labeled a. If fl is the highest (i.e., closest to the root) branching
node on -, then perform the following two actions. First, direct a skip-edge labeled a from
fl to j. Next, consider the subtree of T rooted at fl. Any path of T in this tree that does
not lead eventually to an arc labeled a (like the arc leading to node j) must end on a leaf.
To every such leaf, direct from fl a deferring edge labeled a. This second action is always
performed in the special case where fl is the root.
ffl Case 3: Node fl is a leaf. If fl is the sink, nothing is done. Otherwise, let - be the original
DAWG node of which fl is a replica. Back on T , for each symbol a of the alphabet, follow
every distinct path from - until encountering a first occurrence of a or the sink. For every
such path with no intervening branching nodes, direct a skip-edge from the leaf fl to the
node at the end of the path. For every path traversing and proceding past a branching node,
direct a deferring edge from fl to the deepest one among such branching nodes. At the end,
eliminate possible duplicates among the deferring edges that were introduced.

Figures

4 and 5 exemplify skip links for the backbone, the root and one of its children in the
tree T of our example.
a
a
a
a
a
a
a
a
d

Figure

5: A one-symbol transition from a node ff of T to its descendant j is implemented via
three auxiliary-edge traversals: first, through a deferring link to the nearest branch node fi; next
from fi to fl through a back-edge; finally, through the skip-edge from fl to j. To avoid unnecessarily
cluttering the figure, not all edges are shown. Note that the presence of another a-labeled skip-edge
from fl to ffi introduces ambiguity as to which direction to take once the search has reached fl
At this point and as a result of our construction policy, there may be branching nodes that do
not get assigned any skip- or deferring edge. This may cause a search to stall in the middle of a
downward path, for lack of appropriate direction. In order to prevent this problem, back edges are
added to every such branching node, as follows (see Fig. 5). For every branching node fi of T and
every alphabet symbol a such that an a-labeled skip-edge from fi is not defined, an edge labeled
a is directed from fi to the closest ancestor fl of fi from which a skip- or deferring edge labeled a
is defined. We refer to fl as the a-backup of fi, and we denote it by back a (fi). Note that, by our
construction of Case 2, such a backup node exists always. Clearly, our intent is that the effect of
traversing a skip-edge as described in the previous section can now be achieved by traversing a
small sequence of auxiliary edges. In the example of Fig. 5, the transition from node ff to j is
implemented by traversing in succession one deferring edge, one back edge and one skip-edge. This
complication is compensated by the following advantage.
Lemma 1 The total number of auxiliary edges in T , whence also in the augmented DAWG of X,
is O(jXj \Delta j\Sigmaj).
Proof. There is at most one auxiliary edge per alphabet symbol leaving nodes of outdegree 1,
so that we can concentrate on branching nodes and leaves. As for the skip-edges directed from
branching nodes, observe that for any symbol a and any node fi, at most one skip-edge labeled a
may reach fi from some such node, due to the conventions made in Case 2. Indeed, if a skip-edge
labeled a is set from some branching node ff to another node fi, then by construction no branching
node on the path from ff to fi can be issued an a-labeled skip-edge. Also by construction, either ff
is the root or else there must be an edge labeled a on the path from the closest branching ancestor
of ff to ff itself. Hence, no skip-edge labeled a could possibly be set from a branching ancestor of
ff to a node in the subtree of T rooted at ff. A similar argument holds for deferring edges directed
towards every leaf of T . Indeed, by the mechanics of Case 2, if a deferring edge labeled a is set
from a branching node ff to a leaf fi, then there is no original edge labeled a on the path from ff
to fi. Again, either ff is the root or else there must be an original edge labeled a on the path from
the closest branching ancestor of ff to ff itself, so that no deferring edge labeled a may be issued
from a branching ancestor of ff to a node in the subtree of T rooted at ff.
Considering now the leaves, observe first that at most one skip-edge per symbol may be directed
from a leaf to a node. To get a global bound on all deferring edges set from leaves, consider the
compact trie of all suffixes of X. This trie has O(n) leaves and arcs, and every branching node of
T can be mapped in a distinct branching node in the trie (indeed, T can be obtained figuratively
by pruning the non-compact version of the trie). We will map each one of the deferring edges set
from a leaf fl into an arc of the trie, and in such a way that each arc of the trie is charged at
most one such deferring edge per alphabet symbol. To see this mapping, let W be the word from
the root of T to fl, and let W a be the extension of W that completes one of the paths
ending in a first occurrence of a after crossing some branching nodes in the DAWG. The deferring
edge relative to W 0 is charged to the edge of the trie where W 0 ends. Observe that, for any other
extension a of W appearing in X and such that a has no occurrence in V 0 , V and V 0
must diverge. In other words, W 00 must have a path in the trie that diverges from that of W 0 , and
thus will charge an arc of the trie different from the one charged by W 0 . Moreover, since no prefix
of W ends on a leaf of T , then no ancestor of fl can produce the same charges. In conclusion, for
each leaf of T and symbol of \Sigma a distinct arc of the trie is charged, whence the total number of
auxiliary edges of this kind per symbol is bounded by the length of X. 2
has a realization Y in X beginning with a i and ending with a j if and only if there is
a sequence oe of arcs in T with the following properties: (i) the concatenation of consecutive labels
on the original and skip-edges of oe spells out P ; (ii) any original or skip-edge of oe is followed by
a sequence containing at most two deferring edges and at most one back edge; (iii) there is a path
labeled in the DAWG from the source to the node which is
reached by the last arc of oe.
Proof. The proof is by induction on the length m of the pattern. Let assume that P has
a realization Y in X as stated. By the definition of T , there must be an original arc corresponding
to . The node reached by this arc satisfies trivially points (i \Gamma iii). For m ? 1,
assume that the claim holds for all patterns of lengths and that we have matched
the prefix of P down to some node ff of T while maintaining (i \Gamma iii). Hence,
for some index f ! j, there is a path from the root of T to ff labeled Y and such
that Y f is a realization of Pm\Gamma1 .
Given that P has a realization Y , then there must be a path in the DAWG labeled a f+1 :::a j
and originating at the node represented in T by ff. The path itself has an image in T , perhaps
fragmented in a sequence of segments. Considering this image, the claim is then easily checked if
the last symbol b m of P is consumed through either an original arc or a defined skip-edge leaving ff
and shunting the path labeled a f+1 :::a j . Assuming that neither type of edge is defined at ff, then
by construction there must be a deferring edge labeled a leading through a path labeled by
a prefix a f+1 :::a k of a f+1 either to a branching node, call it fi, or to some leaf -.
In this second case, we have either a defined skip-edge leading to the final node, which would
conclude the argument, or one more deferring edge that will take from - to a branching node.
Considering such a branching node, it must be the image in T of some node of the DAWG on the
path from ff labeled a k+1 :::a j . Hence from this moment on we can reset our reasoning and assume
to be in the same case as if we were on a branching node fi, except for the fact that we would now
start with the "handicap" of having already consumed up to two deferring edges.
Assume then that we are on a branching node fi, possibly having already traversed one or two
deferring edges, and with some suffix of a k+1 :::a j , (f still to be matched. Clearly, if fi has
a defined a-labeled skip- or original edges, this concludes the argument. Thus, the only remaining
cases of interest occur when no a-labeled skip- or original edge is defined from fi. In such an event,
the link to back a (fi) is traversed instead, as depicted in Fig. 5.
Let j be any of the descendants of fi such that j is connected to fi through a nontrivial original
path - of T in which symbol a appears precisely as a suffix and there is no a-labeled original edge
from fi to j. We claim that there is a skip-edge labeled a from fl to j. In fact, by our selection
of -, there is no other edge labeled a on the path from fi to the parent node of j. Assuming one
such edge existed on the path from fl to fi, then fi itself or a branching ancestor of fi other than
would have a-labeled skip-edges defined, thereby contradicting that back a
we choose j to be the node at the end of the path originating from fi and labeled by the suffix of
a k+1 :::a j that remains at this point to be consumed, we have that a skip-edge labeled a must exist
from fl to j. Traversal of this edge achieves propagation of points (i \Gamma iii) from
to P within the transitions of at most two deferring edge, one back edge and one skip-edge.
The proof of the converse is straightforward and thus is omitted. 2
Based on Lemma 2, a search for the realizations of a pattern in the augmented DAWG of X
may be carried out along the lines of a bounded-depth visit of a directed graph. The elementary
downward step in a search consists of following an original edge or a skip-edge, depending on which
one is found. The details are then obvious whenever such an edge actually exists. The problem
that we need to examine in detail is that for any symbol a there may be more than one skip- or
deferring edge labeled a leaving a node like the node fl of Fig. 5, with some such edges leading to
descendants of fl that are not simultaneously descendants of ff. In Fig. 5, an instance of such a
situation is represented by node ffi.
We assume that all auxiliary (i.e., skip- or deferring) edges leaving a node fl under the same
label a are arranged in a list dedicated to a, sorted, say, according to the left-to-right order
of the descendants of fl. Thus, in particular, any descendants of the node ff of our example that are
reachable by an a-labeled auxiliary edge from fl are found as consecutive entries in the auxiliary
edge list of fl associated with symbol a. This list or part of it will be traversed left to right in our
search, as follows naturally from the structure of a depth-first visit of a graph. The convention is
also made that the back-edge from fi to fl points directly to the auxiliary edge associated with the
leftmost descendant of fi. During a search, the beginning of the sublist at fl relative to descendants
of fi is immediately accessed from fi in this way, and the skip- and deferring edges in that sublist are
scanned sequentially while the subtree of T rooted at fi is being explored. The following theorem
summarizes the discussion.
Theorem 2 The compact skip-edge DAWG associated with X supports the search for all earliest
occurrences of a pattern in X in time
O(
where rocc i is the number of distinct realizations in X of the prefix P of P .
As already noted, a realization is a substring that may occur many times in X but is counted
only once in our bound. It is not difficult to modify the DAWG augmentation highlighted in the
previous section so as to build the compact variant described here. Again, the core paradigm
is a bottom-up computation on T , except that this time lists of skip- and deferring edges may
be assigned to branching nodes only on a temporary basis: whenever, climbing back towards the
root from some node fi, an ancestor branching node ff is encountered before any intervening edges
labeled a, then the a-labeled skip- and deferring edge lists of fi are surrendered to ff, and fi is
simultaneously appended to a list Back of branching nodes awaiting back edges. As soon as
(because of an intervening original edge labeled a or having reached the root) the a-labeled lists are
permanently assigned to some node ff, appropriate back-edges are also directed from every node in
the list Back, and Back itself is disposed of. A similar process governs the introduction of skip-
and deferring edges from leaves. Recall that a leaf of T is in fact a replica of a same "confluence
node" of the DAWG. This not only shows that it is possible to compute this class of auxiliary edges
bottom-up, but also suggests that for a group of leaves replicating a same node of the DAWG it
suffices to issue the edges at the node of T that is the image of that DAWG node and let the replicas
simply point to it. Note that, as long as we insist on reasoning in terms of T , these deferring edges
from leaves must be suitably marked, lest they be confused with those issued at branching nodes
and play havoc with the search as described in Lemma 2.
The overall process takes time and space linear in the structure at the outset, which is linear
in jXj for fixed alphabets. Symbol durations may be taken into account both during construction
as well as in the searches, possibly resulting in additional savings. The details are tedious but
straightforward and are left to the reader.
4 Generalizing to unbounded alphabets
When the alphabet size j\Sigmaj is not a constant independent of the length n of X, we face the choice
of implementing the (original) adjacency list of a node of the DAWG as either a linear list or
a balanced tree. The first option leaves space unaffected but introduces slowdown by a linear
multiplicative factor in worst-case searches. The second introduces some linear number of extra
nodes but now the overhead of a search is only a multiplicative factor O(log j\Sigmaj). Below, we assume
this second choice is made. Rather straightforward adaptations to the structure discussed in the
previous section would lead to a statement similar to Theorem 2, except for an O(log j\Sigmaj) factor
in the time bound. Here, however, we are more interested in the fact that when the alphabet size
is no longer a constant Lemma 1 collapses, as the number of auxiliary edges needed in the DAWG
may become quadratic. In this Section, we show that a transducer supporting search time
can in fact be built within O(n log n) time and linear space.
The idea is of course to forfeit many skip-edges and other auxiliary edges and pay for this
sparsification with a log j\Sigmaj overhead on some elementary transitions. We explain first how this
can work on the original array in which X is stored. We resort to a global table Close, defined as
follows [2].
contains the smallest position larger
than j where there is an occurrence of s p , the pth symbol of the alphabet.
Thus, Close is regarded as subdivided into blocks of size j\Sigmaj the entries of which are cyclically
assigned to the different symbols of the alphabet. It is trivial to compute Close from X, in linear
time. Let now closest(i; p) be the closest instance of s p to the right of position i (if there is no such
occurrence set closest(i; 1). The following property holds.
Lemma 3 Given the table Close and the sorted list of occurrences of s p , closest(i; p) can be
computed for any p in O(log j\Sigmaj) time.
We refer to [2] for a proof of Lemma 3. The main idea is that two accesses of the form
must either identify the desired
occurrence or else will define an interval of at most j\Sigmaj entries in the occurrence list of s p , within
which the desired occurrence can be found by binary search, hence in O(log j\Sigmaj) time. Note that
the symbols of X can be partitioned into individual symbol-occurrence lists in O(n log j\Sigmaj) overall
time, and that those lists occupy linear space collectively.
The above construction enables us immediately to get rid of all skip-edges issued inside each
chain of unary nodes present in T . A key element in making this latter fact possible is the cir-
cumstance, already remarked, that we can map every path to the sink of the DAWG, hence also
every such maximal chain, to a substring of a suffix (hence, to an interval of positions) of X. In
fact, once such an interval is identified, an application of closest will tell how far down along the
chain one should go. Along these lines, we only need to show how a downward transition on T
is performed following the identification made by closest of the node that we want to reach: we
may either scan the chain sequentially or search through it logarithmically. The first option results
in adding to the overall time complexity a term linear in n, the second requires additional ad-hoc
auxiliary links at the rate of at most 2 log n per node, of which log n point upward and at most as
many point downwards. The overhead introduced by the second option is O(log n) per transition,
which absorbs the O(log possibly charged by closest. The same scheme can be adapted
to get rid of skip-edges directed from the leaves.
We still face a potential of \Theta(j\Sigmaj) deferring edges per chain node, and as many backup edges
per branching node. These edges are easy to accommodate: all deferring edges from a node point
to a same branching node and can thus coalesce into a single "downward failure link". As for the
backup edges, recall that by definition, on a path - between fi and back a (fi) there can be no
edge labeled a, but such an edge must exist on the path from the closest branching ancestor of fl
to fl. Let trivially each node of T be given as a label the starting position of the earliest suffix of
whose path passes through that node. Then, we can use the table closest on array X to find
the distance of this arc from j, climb to it on T using at most log n auxiliary upward links, and
finally reach fl through the downward failure link. Considering now the deferring edges that lead
to leaves, these edges can be entirely suppressed at the cost of visiting the subtrees of T involved
at search time: this introduces work linear overall, since, e.g., in a breadth-first search it suffices to
visit each subtree once.
Finally, we consider the collection of all deferring edges that originate at an arbitrary leaf. Recall
that when a deferring edge labeled a is set from a leaf fl to a branching node fi, this is done with the
intent of making accessible during searches a final target node j that is found along a unary chain
connecting fi to its closest branching descendant (or leaf) -. Specifically, j is the node at the end
of the first edge labeled a on the chain connecting fi to -. In analogy with what discussed earlier,
j can be reached in logarithmic time from -, through an application of closest. The problem is
thus how to be prepared to reach nodes such as -, during searches, without dedicating one separate
deferring edge to every such node.
In the terms of the discussion of Lemma 1, the idea could be again to coalesce in a same deferring
edge all of those deferring edges from fl that would be charged to a same arc of the suffix trie of
X, and let closest discern at search time among the individual symbols present on that arc. In the
specific case we are considering, this trie arc would be one that maps, in the DAWG, to the path
connecting fi to -. However, this time this is not enough, since not every symbol of \Sigma is guaranteed
to appear in every DAWG chain or trie arc. We must go one step further and coalesce all of the at
most j\Sigmaj edges reaching down along a given path of the trie into the deepest one among those edges.
The intent is that, during a search, the table closest will be used to climb back to the appropriate
depth and symbol. We need to show that this is done consistently, i.e., that a connected path
supporting this climb is guaranteed to exist in T .
Let W be the word associated with fl and W shortest extensions of W such that V
contains at least one instance of every symbol of \Sigma and W 0 ends at a branching node of the suffix
trie. Let -
W and -
respectively, the longest words in the equivalence classes [W ] and [W 0 ],
and recall that fl is a replica of the node of T corresponding to -
W . Clearly, there must be a path
in the DAWG connecting the node of [W ] to that of [W 0 ] and labeled V . Moreover, the DAWG
node corresponding to [W 0 ] must be a branching node, because such is the corresponding node in
the trie. By our construction of T , such a branching node must exist also in this tree, and it must
be connected to the root through a path labeled -
is a suffix of -
connected path
labeled V exists in T as claimed.
We conclude by pointing out that all log factors appearing in our claims can be reduced to
log log at the expense of some additional bookkeeping, by deploying data structures especially
suited for storing integers in a known range [8]. It is also likely that the log n factors could be made
to disappear entirely by resort to amortized finger searches such as, e.g., in [2].
5 Conclusion
We have described a data structure suitable for reporting occurrence of a pattern string as a
constrained subsequence of another string. Since the full-fledged data structure would be too bulky
in practical allocations, a more compact, "sparse" version was built where space saving is traded
in exchange for some overhead on search time. Both of these parameters are perhaps susceptible of
further improvement. In particular, it is not clear that the bounds attained for fixed alphabet sizes
cannot be extended without penalty to the case of an unrestricted alphabet. Non-trivial estimates
or bounds on the terms rocc i that appear in our complexities may shed more light on the expected
or worst case performance of a search. Finally, little is known about indices that would return, in
time linear in the pattern size, whether or not any given pattern occurs as an episode subsequence
of the textstring.
6

Acknowledgements

We are indebted to the Referees for their thorough scrutiny of the original version of this paper
and for their many valuable comments.



--R

Pattern Matching Algorithms
The Longest Common Subsequence Problem Revisited

The Smallest Automaton Recognizing the Subwords of a Text
Fast Approximate Matchings Using Suffix Trees
Algorithms

A Priority Queue in which Initialization and Queue Operations Take O(log log n) Time
A Pattern-Matching Model for Instrusion Detection
Discovering Frequent Episodes in Sequences
Approximate String Matching with Suffix Trees
Introduction to Computational Biology
--TR
Searching subsequences
Text algorithms
Pattern matching algorithms
Discovery of Frequent Episodes in Event Sequences
Approximate String-Matching over Suffix Trees
Episode Matching

--CTR
Zdenk Tronek, Episode directed acyclic subsequence graph, Nordic Journal of Computing, v.11 n.1, p.35-40, Spring 2004
Abhijit Chattaraj , Laxmi Parida, An inexact-suffix-tree-based algorithm for detecting extensible patterns, Theoretical Computer Science, v.335 n.1, p.3-14, 20 May 2005
Robert Gwadera , Mikhail J. Atallah , Wojciech Szpankowski, Reliable detection of episodes in event sequences, Knowledge and Information Systems, v.7 n.4, p.415-437, May 2005
Philippe Flajolet , Wojciech Szpankowski , Brigitte Valle, Hidden word statistics, Journal of the ACM (JACM), v.53 n.1, p.147-183, January 2006
compact subsequence automation;DAWG;skip-link;subsequence and episode searching;algorithms;suffix automation;skip-edge DAWG;forward failure function;pattern matching