TCS -TR-A-10-42

TCS Technical Report

Substring Indices Using Sequence BDDs

by

Shuhei Denzumi, Hiroki Arimura, and Shin-ichi
MinatoDivision of Computer Science
Report Series A
April 14, 2010

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Building Substring Indices Using Sequence BDDs
Shuhei Denzumi

Hiroki Arimura

Shin-ichi Minato

Division of Computer Science
Hokkaido University
Sapporo 060-0814, Japan

Division of Computer Science
Hokkaido University
Sapporo 060-0814, Japan

Division of Computer Science
Hokkaido University
Sapporo 060-0814, Japan

April 14, 2010

(Abstract) There is a demand for eﬃcientindexed-substring data structures, which can store
all substrings of a given text. Suﬃx trees andDirected Acyclic Word Graphs (DAWGs) are examples of substring indices, but they lack operations for manipulating sets of strings. The Sequence Binary Decision Diagram (SeqBDD) data
structure proposed by E. Loekito, J. Bailey, and J.
Pei (KAIS, 2009) is a new type of Binary Decision
Diagram (BDD), and represents sets of sequences.
This study focuses mainly on two issues: (a) compact substring indices based on SeqBDD, calledSuﬃx Decision Diagrams (SuﬃxDDs), which makeit possible to represent the set of all substrings eﬃciently via various operations inherited from Zerosuppressed Binary Decision Diagrams (ZDDs), and(b) methods for building SuﬃxDD, beginning with
an empty string and updating iteratively whenevera new letter is read. This paper presents an efﬁcient algorithm for constructing a SuﬃxDD for agiven text, together with a proof of correctness andsome notes about BDD families, and discusses why
the new data structure appears to have advantages
over existing substring indices. An upper bound on
the running time is also obtained. It is hoped that
presenting this data structure to a wider audienceat this time will help to promote useful discussionof the important issues.

1

lem of determining if P occurs in T . This problem
was well known long ago, and is as important today
for manipulating large-scale data such as Internetbased data.
Substring indices are eﬃcient data structures forstoring all the substrings of a given text. DAWG
[2] is such a data structure, representing all thesubstrings contained in a text of length n. For apattern of length m, DAWG can solve the problem
in O(m log |Σ|+occ) time, where |Σ| and occ denotethe alphabet size and the number of occurrences of
P in T , respectively. We can obtain DAWG in O(n)time by simulating Ukkonen’s online algorithm forconstructing a suﬃx tree [12].
In this paper, we present a method for applying SeqBDDs to substring indices. SeqBDDs [7]is a new ZDD-based data structure recently proposed by E. Loekito, J. Bailey, and J. Pei. Thisdata structure is a new type of BDD. BDDs [3]are widely used for representing and manipulating
Boolean functions inside a computer, and ZDDs
[8, 10], a special type of BDDs, are suitable forhandling large-scale sets of combinations. SeqBDDs are string indices based on ZDDs, they areable to enumerate large sets of sequences implicitly, and use a variety of eﬃcient operations. Families of BDDs are compact representations of discrete structures, with rich collections of operations.
The extension of SeqBDD to substring indices is an
open issue, and we would like to devise an eﬃcient
substring index structure based on SeqBDD.

Introduction

The development of information networks has
raised the necessity for data mining to discover usage patterns from massive online data. For a given
text T and pattern P , string matching is the prob-

In the remainder of this paper, Chapter 2 formulates a convenient notational framework anddiscusses BDD families. This treatment is essentially self-contained, assuming no prior knowledge
1

2

Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minatoof BDDs. Chapter 3 presents two construction
procedures for SuﬃxDD, one being a simple technique and the other a more eﬃcient implementation, together with some theorems that describe
the virtues of the method. Some computational
experiments are recorded in Chapter 4, with Chapter 5 concluding the paper and mentioning several
future directions for related work.

2

Preliminaries

2.1

Basic string deﬁnitions

Let Σ be a ﬁnite alphabet and Σ∗ be the set of
all strings over Σ. We denote the length of stringx ∈ Σ∗ by |x|. The string whose length is 0 isdenoted by ϵ and called the empty string, that is|ϵ| = 0. The concatenation of two strings x1 andx2 ∈ Σ∗ is denoted by x1 · x2 , also written simply
as x1 x2 if no confusion occurs.
Strings x, y, and z are said to be the preﬁx ,substring, and suﬃx of the string w = xyz, respectively. The ith symbol of a string w is denoted by
w[i], and the substring of w that begins at position
i and ends at position j is denoted by w[i . . . j]. For
convenience, we let w[i . . . j] = ϵ for j < i. We also
denote by P ref ix(w) the set of all preﬁxes of thestring w ∈ Σ∗ , and denote by Substring(w) the setof all substrings of w ∈ Σ∗ . The reversal of a stringw = w[1 . . . |w|] is deﬁned by wR = w[|w|] · · · w[1].

2.2

BDDs

A BDD [3] is a directed-graph representation of a
Boolean function, as illustrated in Figure 2(b). It
is derived by reducing the binary tree graph representing a recursive Shannon’s expansion, as shownin Figure 2(a). The following reduction rules yielda BDD, which can eﬃciently represent the Booleanfunction (see [4] for details).
• Delete all redundant nodes whose two edges
point to the same node (see Figure 1(a)).
• Share all equivalent subgraphs (see Figure1(b)).

0

x

jump

1

f

f

(a) Node deletion.

xx

x share

01

0 1

0 1

f0

f1

f0

f1

(b) Node sharing.

Figure 1: BDD reduction rule

BDDs provide canonical forms for Boolean functions when the variable order is ﬁxed. Most research on BDDs is based on the above reduction
rules. 1
As shown in Figure 3, a set of multiple BDDs
can be shared with each other under the same variable ordering. In this way, we can handle a number of Boolean functions simultaneously in the one
memory space.
Using Bryant’s algorithm [3], we can eﬃciently
construct a BDD for the result of a binary logic
operation (i.e. AND, OR, XOR), given a pair ofoperand BDDs. This algorithm is based on hashtable techniques, and the computation time is almost linear with data size, unless the data overﬂows
the main memory (see [9] for details).

2.3

ZDDs

A ZDD [8, 10] is a special type of BDD for theeﬃcient manipulation of sets of combinations [11].
An example is shown in Figure 4.
With a ZDD, we do not delete the nodes whose
two edges point to the same node, which was required under the original rule. Instead, we delete
all nodes whose 1-edge points directly to the 0terminal node, and jump through to the 0-edge’s
destination, as shown in Figure 5.
1
In general, the term BDD includes graphs that do not
fix the order of variables or that are not canonical, but wedeal only with those graphs that follow the above reduction
rules in this paper.

3

Substring Indices Using Sequence BDDs

F1 = a ∧ b
F2 = a ⊕b

F
0

0
0
1

c

b

a 1

1

1

0

0

1

0

c

1

0

0

1

c

b

F3 = b
1

1

0

0

1

c

F4 = a ∨ b
11F1(a) Binary Decision Tree.
F

0

a 1
0

1

c

a 1

b

0

0

1

b 1

0

0

F2

F3

a 1

F4

0

a
1

b

0

1 0

0

1

1
(b) BDD

Figure 2: Binary tree and BDD for F = (a ∧ b) ∨ c

Figure 3: Shared multiple BDDs

When no equivalent nodes exist in a ZDD, whichis the worst case, the ZDD structure explicitly
stores all combinations of all items, in addition tousing an explicit linear linked-list data structure.
An example is shown in Figure 6. Note that theorder of ZDD size never exceeds that of the explicit
representation.

SeqBDDs, as follows, we can manipulate sets of sequences eﬃciently.

It is known that binary operations can be executed eﬃciently in almost linear computation timeand in a single memory space matching the numberof nodes of the ZDD. This feature depends on using
a technique that avoids redundant computation byusing a hash table to store and make available priorcomputation results.
In the past, an approach was reported that applied ZDD to the sequence data-mining ﬁeld [5].
Figure 7 shows an example of a ZDD representing a set of sequences. However, the research did
not demonstrate the performance required for application to practical-scale problems. This was attributed to the fact that the ZDDs were not optimized for sets of sequences. In fact, if we use

2.4

SeqBDDs

A SeqBDD is a ZDD that has removed the ordering
constraint only for 1-edges with ordered 0-edges,
and for which a letter is allowed to occur multiple
times in a path. SeqBDD semantics are such thata path in a SeqBDD represents a string, for which
the nodes are arranged in order of the positionsof their respective variables in the string. Morespeciﬁcally, the top node corresponds to the headof the string, and the successive nodes take 1-edges
corresponding to the following letters, respectively.
A SeqBDD node N = node(x, N1 , N0 ) denotes aninternal node labeled by letter X, and N1 (or N0 )denotes its 1-edge (or 0-edge). The letter of node
N has a lower order (appears earlier in the variable
ordering) than the letter of N0 . We denote the total
number of descendant nodes of node N , including
N itself, by |N |. Let x be a letter and P and Q be
two sets of strings. In SeqBDD, a 0-terminal node4

Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato

C(abc):

C(abcd):abc Cabcd C

000
001
010
011
100
C(abc)
101
110
a 111
1

0

b

0 1

b
1

0

1

b

b

0 1

0

1

0
1
1
0
0
C(abcd)
0
0
0 a

1 0

c 0

c

1 0
1

BDD

1

0

f
C(abcd)

0

x

jump

1

0

f

Figure 5: ZDD reduction ruleC(abc)

0

0

0

0
0

d

0000 00001 10010 10011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 0

a

1

b 1

ZDD

1

Figure 4: Example of ZDD eﬀect

encodes the empty set (emptyset), and a 1-terminal
node encodes the set of empty string (ϵ). Figure
8 shows an example. For clarity, we omit the 0terminal nodes from the illustrations in this paper.
(A solid line represents a 1-edge and a dotted line
represents a 0-edge).
We deﬁne an operation P .push(x) that appends
x to the head of every sequence in P , and an operation P ∪ Q that returns the set of sequences
occurring in either P or Q.
Definition 1 A
SeqBDDnode
N=node(x, N1 , N0 ) represents a set of sequences
S such that S = Sx̄ ∪ Sx .push(x), where Sx is theset of sequences that begin with element x (withthe head elements being removed), and Sx̄ is theset of sequences that do not begin with x. Node N1
represents set Sx , and node N0 represents set Sx̄ .
Table 1 shows most of the primitive operationsfor SeqBDDs. In these operations, ∅, 1, P.top,
and P.push(x) are executed in constant time, withthe others being almost linear with the size of thegraph. We can describe a variety of processing operations on sets of combinations by composition ofthese primitive operations.
These are natural extensions to ZDDs, as usedin Loekito et.al ’s paper [7]. The size of the output is at most |P ||Q| because this is the number ofdistinctly diﬀerent calls of binary operations that
can arise. To keep a lid on the computation, we
can remember what we have done before by hashing. Previously solved cases thereby become terminal ones. Therefore, the running time will be
O(|P ||Q|) in the worst possible case. However, therunning time is practically linear with the SeqBDD
representation for almost all operations.
First, we show the SeqBDDs’ union operation ∪in Figure 10. Recursions always terminate when asuﬃciently simple case arises. The terminal cases
are P ∪ ∅ = P , ∅ ∪ Q = Q, and P ∪ Q = P when
P = Q.
If P is a 0-terminal, i.e. P is empty, the output
comprises all sequences in Q. Similarly, if Q is a
0-terminal, P is returned as output.
If P equals Q, i.e. P and Q comprise the same
sequences, then the output also comprises all sequences in P .
If both P and Q are internal nodes, we compare
the letters of both x and y. Suppose x = y. Then,because x is the smallest letter among the head
letters of all strings in P and Q, x should be theletter of the output node. The 1-edge of the output
node should contain all sequences that begin withx, with the 0-edge of the output node containing

5

Substring Indices Using Sequence BDDs

{abcd, bc, cde}

0

0

a 1

b 1

c 1

{aabac, baba, aaca, bbac}
a1

b
c

c

b3

0

d

a4

d

c5

e
0

the remaining sequences. Suppose x is smaller2
than y. Then x is smaller than the head of all
sequences in Q. Therefore, the output node shouldhave letter x, and all sequences that begin with x
are present in P1 . The remaining output sequences
exist in P0 and Q. Suppose x is bigger than y. Thiscondition is the opposite of the above condition,
since the operation is commutative.
When we construct a substring index in SeqBDD, we can consider a 1-terminal node as a 0terminal node, since no 0-terminal node appears
when computing ∪. In this way, the ∪ operation
can be twice as fast. In addition, we can deﬁne theoperations ∩ and \, which compute the intersection and diﬀerence sets, respectively, by recursivealgorithms. These procedures are almost the same
as for ∪. The only diﬀerences are that we change
the output in the terminal cases and the inputs ofrecursive calls. The remaining algorithms proceedexactly as for ∪.
A 1-terminal node is considered an internal node with abigger letter than all letters in the alphabet.

a2
c3
b3
a4

b2

a3
c4

1

1

Figure 6: Explicit representation by ZDD

2

b1

a2

Figure 7: ZDD representation of a set of sequences
aabac, baba, aaca, bbac

2.5

Online substring-index construction
problem

A Substring index for a text T is a data structurethat stores the set of all substrings of T and has
the following operations:• Index construction P ← create(T ): Returnthe index that represents the set of all substrings of T ∈ Σ∗ .
• Membership determination P.member(w):For a given string w ∈ Σ∗ , determine whether“w ∈ Substring(T )” is true.
For a given online text T = T [1 . . . n], the online
substring-index construction problem is expressed
as follows. For each i = 1, . . . , n, construct thesubstring index Si of Ti = T [1..i], where Si is built
incrementally from Si−1 and T [i].

6Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato

rootaTable 1: Primitive SeqBDD operations{aaa, aba, bbc, bc}{bbc, bc} b“1”

a {aa, ba}
b {ba}{bc, c} b“∅”

P .topa {a}P .onset(x)1

P .oﬀset(x)

{c} c
{ }

Figure 8: An example of SeqBDD, and the sets ofsequences that each node represents

3

Algorithms

In this section, we introduce SuﬃxDD, which isa substring index based on SeqBDD, and give aneﬃcient construction algorithm.

3.1

SuﬃxDDLet T ∈ Σ∗ be a text of length n ≥ 0. Then theSuﬃxDD of text T is a SeqBDD constructed for theset of all substrings Substring(T ). Figure 11 shows
an example of SuﬃxDD for aabac. The numberof nodes of SuﬃxDD is linear with respect to thelength of the text T . It is possible to show that
SuﬃxDD is isomorphic to DAWG. From this fact,
we can infer that the number of nodes of SuﬃxDD
is O(n) for a text of length n ≥ 0.

3.2

Naive construction method

Figure 12 shows a straightforward construction algorithm for SuﬃxDD. We ﬁrst build a SeqBDD Ri
that represents only the string Ti = T [1 . . . i] ateach step. Then we update SuﬃxDD by adding all
those suﬃxes of Ti that are not contained in Si at
the time, and the result is set as the new SuﬃxDD.
In this algorithm, a SeqBDD must be built at every
reading of a new letter, to represent all suﬃxes of

P .push(x)
P ∪Q
P ∩Q
P \Q
P .count

Returns empty set.
(0-terminal node)
Returns the set of only theempty string. (1-terminal node)
Returns the letter at theroot node of P .
Selects the subset of sequences thatbegin with letter x, and then removes
x from the head of each sequence.
Selects the subset of sequences that
do not begin with letter x.
Appends x to the head of
every sequence in P .
Returns the union set.
Returns the intersection set.
Returns the diﬀerence set(in P but not in Q).
Counts the number of sequences.

the current text. An example of this construction
process is shown in Figure 13.
For every letter, this algorithm has to build a
rectilinear SeqBDD whose length is the same as
the text already read, and it computes unions at
almost the same time as for the length. Let n be
the length of the text. The computation time of∪ is O(|Σ|n) in this case, and it is repeated O(n2 )times. These considerations lead to the following
lemma.
Lemma 1 The running time of BuildNaive isbounded by O(|Σ|n3 ).

3.3

Eﬃcient construction method

Using the simple algorithm, we build a SeqBDD of
length n and add new suﬃxes one by one whenever a new letter is read. We now give an eﬃcient algorithm for SuﬃxDD construction. It does
not involve bottom-up building or repeating thesame union-operation computations. The idea is toconstruct a SuﬃxDD comprising all reversed substrings, maintaining a SeqBDD that represents all

7

Substring Indices Using Sequence BDDs

$

'

S1

S2

S1={aabac, baba}
a

a

b

b

a

S2={aaca, bbac}

a

a

b

a

b

b
c

a

a

b

a

b

Procedure P ∪ Q
Input: P , Q: SeqBDD;
1: case P = 0-terminal node : return Q
2: case Q = 0-terminal node : return P
3: case P = Q : return P
4: If there is a P ∪ Q result, then return it.
5: x ← P .top; y ← Q.top

6: P1 ← P .onset(x); P0 ← P .oﬀset(x)7: Q1 ← Q.onset(y); Q0 ← Q.oﬀset(y)8: case x = y : z ← x; R1 ← P1 ∪ Q1 ; R0 ←P0 ∪ Q0

9: case x < y : z ← x; R1 ← P1 ; R0 ← P0 ∪ Qac

10: case x > y : z ← y; R1 ← Q1 ; R0 ← P ∪ Q0

11: return R1 .push(z) ∪R0%It means making node(z, R1 , R0 ) and return it.

&

Figure 10: Code for constructing P ∪ Q

1(1) The correctness of procedure BuildFast
Figure 9: An example of SeqBDD showing the result of a ∪ operation and its inputs.

preﬁxes of the reversed text, and then updating itby just one union operation.
The procedure can be expressed as shown in
Figure 14. We maintain and update a SeqBDD
R that represents all reversed suﬃxes by appending one node to the old R. To update SuﬃxDDS, we compute the union of S ∪ R once per iteration. Let T and P be the given text and pattern.
Therefore, the SeqBDD represents Substring(T R )in this algorithm. An example is shown in Figure
15, for T = aba. For this SuﬃxDD, the stringmatching problem is to determine whether or not
P R ∈ Substring(T R ).
Let n denote the length of the text. This algorithm makes a new node (O(1)) in one iteration, and computes the union with the existing SufﬁxDD. Note that updating SuﬃxDD takes O(|Σ|n)
time.

Proof
We prove that the variable S comprises
Substring(T ) at each iteration. Let n be the text
length.
(i) If n = 0:
We have T = ϵ, and, because the substrings ofthe empty string are also only empty strings, thenthe 1-terminal node represents it. Therefore, variable S is the SuﬃxDD of the text at the ﬁrst iteration because BuildFast starts with S = 1-terminal
node. It follows that R represents P ref ix(T R ) =1terminal node, for the same reason.
(ii) Suppose that S is the SuﬃxDD of the text
T [1 . . . i]R when n = i(i > 0), and R represents
P ref ix(T [1 . . . i]R ).
R is updated to represent P ref ix([1 . . . i + 1]R )at the time that the i + 1th letter is read in line 5.
The SuﬃxDD of T [1 . . . i + 1]R ] is obtained by theunion in line 6:
Substring(T [1 . . . i]R ) ∪ P ref ix(T [1 . . . i + 1]R )= Substring(T [1 . . . i + 1]R )Theorem 1 BuildFast can be executed in timeO(|Σ|n2 ).

Thevariable

S

is

shown

to

represent%

8Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato

Substring(aabac)
a
a

b

b
a
c
1
Figure 11: Structure for a SuﬃxDD, given an input
aabac

Substring(T [1 . . . i + 1]R ) by the above equality.
The proof is therefore complete by induction.
(2) Running time of algorithm BuildFast
The length of a straight SeqBDD R is i when
the text length is i. Therefore, S ∪ R terminates
after i recursions on a 1-edge in the worst case. The
number of times we traverse 0-edges is at most |Σ|.
Therefore, one ∪ will take O(|Σ|i) for each letter:Σni=1 O(|Σ|i) = O(|Σ|n2 )The BuildFast algorithm can therefore be performed in O(|Σ|n2 ) for a text whose length is n,
and we have proved Theorem 1.

4

Experiments

We implemented the proposed algorithm in the
concurrent programming language Erlang, and performed experiments using artiﬁcial data. We used
an Erlang Term Storage table for storing the nodesof the BDDs. The computer was a 2.67 GHz Corei7
PC running Windows XP SP3, with a 3.25 GB
main memory, of which about 1.5 GB was allocatedto Erlang. We used artiﬁcial data, in which all
letters occurred with equal likelihood, as the test
data. The text strings were generated randomly.
The alphabet size was either 4 or 128, dependingon the experiment.

$'

Procedure BuildNaive
Input: Text string T
1: n ← 1
2: S ← 1-terminal node
3: while(){4:
T [n] ← reads a new letter
5:
n++
6:
Build SeqBDD R thatT [1 . . . n].
7:
do{
8:
OldS ← S
9:S ← R ∪ OldS
10:
R ← R.onset(R.top)11:}while(S ̸= OldS)
12: }represents&%

Figure 12: Naive procedure for construction of a
SuﬃxDD

4.1

Experiments and results

Both SuﬃxDD construction algorithms, BuildNaive
and BuildFast, were implemented for comparison.
The experiments were performed to test the data
structure of SuﬃxDD, using each random text oflength n with a default Σ of {A, B, C, D}. The
following empirical results were obtained.
Experiment 1:
Figure 16 shows the running time for BuildFast.
Figure 17 shows the running time for both methods. Figure 18 is a logarithmic version of Figure
17.
These results suggest that the naive algorithm
runs in O(n2 ) time and the eﬃcient algorithm runsin O(n) time. These results do not contradict
Lemma 1 or Theorem 1, running in better timethan predicted. The eﬃcient method built SufﬁxDD faster than the O(n2 ) running time derived
from analysis of the algorithm. The memorization
technique worked well, which was probably the reason for the overall running time being better than
expected.
Experiment 2: Figure 19 shows the running
time of BuildFast with two random texts, for which|Σ| = 4 and |Σ| = 128, respectively.

Substring Indices Using Sequence BDDs

In both cases, running times seem to be proportional to n. The O(n2 ) running time is derived
from analysis of the algorithm. The SuﬃxDDs for|Σ| = 4 were computed nearly six times faster thanthe SuﬃxDDs for |Σ| = 128.
Experiment 3: Figure 20 shows the number ofnodes in SuﬃxDDs for |Σ| = 4 and |Σ| = 128.
The size of the SuﬃxDD is linearly related to
the length of the text. The SuﬃxDDs for thelarger alphabet were slightly smaller, but the reason is not clear. For example, the number of nodes
for alice29.txt, which comprises 152,089 bytes, is288,759.
Experiment 4: Figure 21 shows the computation times for constructing SeqBDDs that represent the union, intersection, and diﬀerence of two
SuﬃxDDs.
Experiment 5: We generated three random
texts, namely S, T , and U . Text S had P (A) = 0.4
and P (B) = P (C) = P (D) = 0.2, where P (x) is
the probability that letter x is chosen. Text T had
P (A) = 1. Text U had equally likely probabilities.
Figures 22 and 23 show the running time and thenumber of nodes for the SuﬃxDDs of S, T , and U .
Both the running time and the size are smaller
for the texts with stronger bias. The SuﬃxDDs
for T were built 20 times faster than for the othertexts, and the number of nodes was n + 1, i.e., thesmallest size.

5

Conclusion

In this paper, we have discussed SeqBDD, proposed by Loekito et al., and have presented an algorithm that constructs SuﬃxDD using only primitive SeqBDD operations. We described experiments showing that our proposed algorithm isfaster than the simple method, and have foundthat our method leads to a thousand-fold increasein program speed. The results of our study suggest that SuﬃxDD can store all substring sets effectively. Therefore, SuﬃxDD appears to be a valid
method.
In future work, additional static and dynamic
statistics should be gathered, and a more sophisti-

9cated study comparing SuﬃxDD with existing substring indices would be desirable. SuﬃxDD can beapplied eﬀectively to other string problems, and it
would appear to be useful to develop applications
for string searching based on SeqBDD. It would beinteresting to extend SuﬃxDD to allow mismatching. It is clear that there is considerable work yet
to be done on SuﬃxDD.

References[1] S.B. Akers,“Binary decision diagrams,”
IEEE Trans. Comput., Vol. C-27, No. 6, pp.
509–516, 1978.
[2] A. Blumer, J. Blumer, A. Ehrenfeucht,
D. Haussler, and R. McConnell, “Linear sizeﬁnite automata for the set of all subwords of aword: an outline of results,” Bull. Europ. Assoc. Theoret. Comput. Sci., 21, pp. 12–20,
1983.
[3] R.E. Bryant, “Graph-based algorithms for
Boolean function manipulation,”
IEEE
Trans. Comput., Vol. C-35, No. 8, pp. 677–
691, 1986.
[4] D.E. Knuth, “The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks &Techniques and Binary Decision Diagrams,”
Addison-Wesley, 2009.
[5] R. Kurai, S. Minato, and T. Zeugmann,“N-Gram analysis based on zero-suppressed
BDDs,” In T. Washio, et al. editors, “New
Frontiers in Artiﬁcial Intelligence, Joint JSAI2006 Workshop, Post-Proceedings”, LNAI
4384, pp. 289–300, Springer, Feb. 2007.
[6] C.Y. Lee, “Representation of switching circuits by binary-decision programs,”
Bell
Syst. Tech. J., Vol. 38, pp. 985–999, 1959.
[7] E. Loekito, J. Bailey, and J. Pei, “A binary decision diagram based approach for mining frequent subsequences,” Knowledge andInformation Systems, doi:10.1007/s10115-0090252-9, 2009.

10

Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato[8] S. Minato, “Zero-suppressed BDDs for set manipulation in combinatorial problems,” Proc.
30th ACM/IEEE Design Automation Conf.
(DAC-93), pp. 272–277, 1993.
[9] S. Minato, “Binary Decision Diagrams andApplications for VLSI CAD,” Kluwer Academic Publishers, November 1996.
[10] S. Minato, “Zero-suppressed BDDs and theirapplications,” Int. J. Software Tools for Technology Transfer (STTT), Vol. 3, No. 2, pp.
156–170, Springer, May 2001.
[11] S. Minato and H. Arimura “Frequent patternmining and knowledge indexing based on Zerosuppressed BDDSs,” The 5th international
workshop on knowledge discovery in inductive
databases (KDID’2006), pp. 83–94.

read T[1] = a{a}Substring( )

a

1

1

read T[2] = b
{b}

a
1

Substring(T[1 … 2])

a

a

b

→

b

b

1

1

{bab}
and
{ba}
a

Substring(T[1 … 3])

Substring(T[1 … 2])[12] E. Ukkonen “Constructing suﬃx trees on-line
in linear time,” IFIP’92, pp. 484–492, 1992.

→

and {ab}Substring(T[1])read T[3] = a

Substring(T[1])

a

b

→ b

a

a

1

1

b

Figure 13: Processing of aba in BuildNaive'$

Procedure BuildFast
Input: Text string T
1: R ← 1-terminal node
2: S ← 1-terminal node
3: while(){4:x ← read a letter
5:
R ← R.push(x) ∪ 1-terminal node
%make node(x, S, 1-terminal node), andlet it be the new S
6:
S ← S∪R
7: }&Figure 14: Eﬃcient code for constructing a SufﬁxDD%

11

Substring Indices Using Sequence BDDs

read T[1] = a

Prefix(T[1]R)Substring( R)

a

1

1

Substring(T[1]R)→a1

read T[2] = b
Substring(T[1 … 2]R)R
Prefix(T[1 … 2] )appendb nodeb→

Substring(T[1]R)
a
1

a

n

b

Figure 18: Experiment 1: Logarithm of the running time of Figure 17

a1

read T[3] = a
Substring(T[1 … 3]R)Prefix(T[1 … 3]R)
appenda nodea
Substring(T[1 … 2]R)

a

b

→ b

a

a

1

1

b

Figure 15: Processing of aba in BuildFastn

Figure 16: Experiment 1: Empirical running time,for BuildFastn

Figure 17: Experiment 1: Running time to construct a SuﬃxDD, for BuildNaive and BuildFastn

Figure 19: Experiment 2: Empirical running timeof BuildFast, for |Σ| = 4 and |Σ| = 128nFigure 20: Experiment 3: Empirical size of SufﬁxDDs, for |Σ| = 4 and |Σ| = 128nFigure 21: Experiment 4: Empirical computation
times for binary set operations on two SuﬃxDDs

12

Shuhei Denzumi, Hiroki Arimura, and Shin-ichi MinatonFigure 22: Experiment 5: The running time of
BuildFast, for texts with biased probabilitiesnFigure 23: The number of nodes of SuﬃxDD, fortexts with biased probabilities