TCS -TR-A-11-53

TCS Technical Report

Eﬃcient Algorithms on Sequence Binary Decision
Diagrams for Manipulating Sets of Strings
by

Shuhei Denzumi, Ryo Yoshinaka, Shin-ichi Minato,and Hiroki Arimura

Division of Computer Science
Report Series A
April 30, 2011

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

arim@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7680+81-011-706-7680

Eﬃcient Algorithms on Sequence Binary
Decision Diagrams for Manipulating Sets ofStrings
Shuhei Denzumi1 , Ryo Yoshinaka2 , Shin-ichi Minato1,2 , and Hiroki Arimura1
1)

2)

Graduate School of IST, Hokkaido University, Japan
ERATO MINATO Discrete Structure Manipulation System Project, JST, Japan{denzumi,ry,minato,arim}@ist.hokudai.ac.jp

Abstract. We consider sequence binary decision diagrams (sequence
BDD or SDD, for short), which are compact representation for manipulating sets of strings, proposed by (Loekito, et al., Knowl. Inf. Syst.,
24(2), 235-268, 2009). An SDD resembles to an acyclic DFA in binary
form with diﬀerent reduction rules from one for DFAs. In this paper, westudy the power of SDDs for storing and manipulating sets of strings
on shared and reduced SDDs. Particularly, we ﬁrst give the characterization of minimal SDDs as reduced SDDs. Then, we present simple andeﬃcient algorithms for various problems related to reduced and shared
SDDs: on-the-ﬂy and oﬀ-line minimization, dynamic string set construction, and factor SDD construction. Finally, we run experiments on real
data sets that show the eﬃciency and usefulness of SDDs in large-scale
string processing.

1

Introduction

Backgrounds. Recent emergence of massive text and sequence data has increased the importance of string processing technologies. In particular, compact string index data structures for storing, ﬁltering, and manipulating setsof strings [3, 7, 9, 13, 16, 21] have attracted much attention in many applications
such as bioinfomratics, natural language processing, event stream processing,and sequence mining. Sequence binary decision diagrams (sequence BDDs or
SDDs, for short) are compact representation for manipulating sets of strings,
proposed by Loekito, et al. [15]. Roughly speaking, an SDD is a node-labelled
DAG in binary form that resembles to an acyclic DFA (ADFA) [9, 21] but with
diﬀerent reduction rule from one for ADFAs, where equivalent siblings as well
as children can be shared. From this diﬀerence, minimal SDDs can be slightly
smaller than the equivalent minimal ADFAs, and the implementation of minimization and other set manipulation procedures can be much more simpliﬁed
and made easy, as it will be shown in this paper later. In the paper [15], theframework of shared and reduced SDDs are shown to be useful in string processing applications. However, the theoretical analysis need further investigation.
Main results. In this paper, we study basic properties and eﬃcient algorithms for shared and reduced SDDs as follows. First, we study on-the-ﬂy andoﬀ-line minimization of SDDs. Particularly, we present the characterization ofminimal SDDs as reduced SDDs (Theorem 1), the correctness of Getnode procedure for the on-the-ﬂy minimization in SDD, the time complexity of a linear-time
oﬀ-line minimization procedure Reduce (Corollary 3). Next, we present eﬃcientalgorithms for related problems: We show an incremental construction algorithmwith insert, delete, and switch operations for an SDD from a string set, and shows
its linear-time complexity in dynamic setting (Theorem 4 and Corollary 5). We
present a practical algorithm RecFSDD for constructing a factor SDD from an
input SDD, which is a simple recursive procedure based on tabling and binary
set operation, and ran in almost linear time in our experiments. Finally, we run
experiments on real data sets that show the usefulness of SDDs in large-scale
string processing.
In summary, the SDD is a compact index structure, which is conceptuallysimple, having clear semantics, easy to implement, and extensible to various purposes. Moreover, the above results demonstrate that the framework of shared andreduced SDD environment is a practical choice for large-scale string applications
utilizing the power of node-sharing, on-the-ﬂy minimization, and built-in set
operations, inherited from ADFAs and BDDs (See below for BDDs).
Related works. There have been a number of studies on the use of minimal
ADFAs as compacted string indexes [9, 21] and as compacted factor indexes [3,7, 13, 16, 21]. In the former line of researches, there are a number of works on
oﬀ-line algorithms for state minimization and Boolean set operations [12]. For
example, Daciuk et al. [9] presented a linear-time incremental algorithm forconstructing a minimal ADFA from a string set. Mohri et al. [21] studied theconstruction of factor automata (FA) and factor transducers from an ADFA andshowed a non-trivial upperbound of the size and the construction time for FA.
Apart from well-known linear time algorithms [7, 26] for suﬃx trees (STs) andFAs (or DAWGs) based-on suﬃx links, there is a line of researches on practical
top-down algorithms, such as wotd [11], for constructing factor indexes [11, 21,24] similar to our RecFSDD. Although they have non-linear time complexity,
some of their advantages are reported that they are conceptually simple [11],run fast in practice [11, 21], and have good I/O complexity [24].
On the other hand, logic design community has developed compact storage and manipulation techniques for combinatorial structures [5, 14, 17, 18, 27]
in the form of BDDs (binary decision diagrams) for Boolean functions, invented
by Bryant [5] in 80s, and its variant ZDDs (zero-suppressed BDDs) for combinatorial sets, proposed by Minato [18] in 90s. Hence, it is an interesting idea
to add new functionality to string indexes based on BDDs and ZDDs. Recently,
Loekito, et al. [15] discovered that ZDDs with node-sharing and zero-suppress
rules resemble to ADFAs [21] in binary form, when the ordering constraint on
1-children is removed, and then, they proposed the sequence BDDs (SDDs) [15]as an alternative to ASFA. In [15], they presented the basic framework of shared
and reduced SDDs and studied eﬃcient algorithms for set operations ∪ and \,with application to a sequence mining problem, while further study is required

{31}

a 31
a 28

b 29

a 24
a

b 25

20

a

b 30

b 26

21

a

b 12 b 13 b 14 b 15

ab 16 b 17

b

{28}

{29}

a

{24}

b 27

22

{30}

a

a

{20-23}23ab 18 b 19

b {12,14,

{28}

a

b

b

{24}

b

1

2

3

4

5

6

7

8

9

10 11

Trie B1a{26,27}{20-23}a{13,15,
17,19}b

16,18}

1 1 1 1 1 1 1 1 1 1 1{29,30}

b

{25}

b

a{31}

1 {1-11}
Non-reduced SDD B2

{25
-27}

b

{12-19}

1 {1-11}
Reduced SDD B3

Fig. 1. Examples of three index structures on Σ1 = {a, b} for the same string set
S1 = {aaaab, aaab, aabab, aabb, aa, abbab, abbb, ab, bbab, bbb, b}: a trie B1 in the leftmostchild right-sibling form (left), a minimal DFA as a non-reduced SDD B2 (middle), anda reduced SDD B3 (right). In the ﬁgure, solid and dotted arrows indicate the 1- and0-edge and the numbers attached to a node indicate the equivalent nodes in B1 . The
0-terminal 0 and all edges pointing to 0 are omitted in the ﬁgure.

for properties and algorithms of SDDs from the view of automata and algorithm
theories.
Organization of this paper. In Sec. 2, we give basic deﬁnitions on sequence
BDDs. Then, we discuss the on-the-ﬂy minimization in Sec. 3, the dynamic
string set construction in Sec. 4, the factor SDD construction in Sec. 5, andshow experimental results in Sec. 6. Finally, Sec. 7 concludes this paper.

2

Preliminaries

In this section, we give basic deﬁnitions and notations in sets of strings, BDDs,
and SDDs according to [14, 15, 18]. For the deﬁnitions and results not found here,
please consult papers on SDDs [10, 15].
Strings and string sets. Let Σ be an alphabet of symbols with a totalorder ≼Σ on Σ. A string on Σ is a sequence s = s[1] · · · s[n] of letters, where|s| = n is the length and s[i] ∈ Σ (1 ≤ i ≤ n). If s = xyz for some x, y, z ∈ Σ ∗ ,then we say that x is a preﬁx , y is a factor , and z is a suﬃx of s. A string set(or a language)is any ﬁnite S ⊆ Σ ∗ . We denote by |S| = m the cardinality, by∑||S|| = s∈S |s| the total size of S, and by maxlen(S) = max{ |s| | s ∈ S }. For
any x ∈ Σ, we deﬁne x · S = { xy | y ∈ S }. For a string set S, we denote by
Suf (S) the set of all suﬃxes of strings in S.
Sequence BDDs. Let dom and op be countable domains of the nodes andthe operations, resp. A sequence binary decision diagram or a sequence BDD(abbreviated as SDD 1 here) is a DAG B = ⟨Σ, V, τ, r, 0, 1⟩, with the node set
1Note that the abbreviation SeqBDD was used to denote sequence BDD in the original
paper by Loekito et al. [15]. We also note that the abbreviation SDD was also used forthe set decision diagrams [6] and the spectral decision diagrams [25] in logic designcommunity. However, we use the abbreviation for its simplicity if no confusion arises.

V = V (B) ⊆ dom, the root r and two terminal nodes 1 and 0 ∈ V , called
the 1- and 0-terminals. The nodes in VN = V \{0, 1} are called nonterminals.
Each node v ∈ VN of B is labeled by a symbol v.lab ∈ Σ and has the 1- and0-children, denoted by v.1 and v.0, resp., which correspond to the leftmost-childand the right-sibling in a DAG in binary form [1, 14]. Formally, the information
is described by a function τ : VN → Σ × V 2 that assigns the node triple τ (v) =⟨v.top, v.0, v.1⟩ to each v ∈ VN . For a node u, a path π ∈ {0, 1}∗ speciﬁes thenode u.π by u.ε = u and u.πα = (u.π).α for every α = 0, 1. In our shared
SDD environment, the function τ is implemented by a hash table uniqtable, andshared by more than one SDDs in common. We deﬁne the size of B by |B| =|VN | = |V | − 2, the number of non-terminals in B. 2 An SDD B is deterministic,i.e., the siblings of each node has no repeated labels and are ordered from left
to right by symbol order ≺Σ on their labels. B is acyclic if there exists a strict
partial order ≻V on nodes such that for every non-terminal v ∈ VN , v ≻V v.0
and v ≻V v.1 hold. We assume that any SDD B is well-deﬁned meaning that B
is both deterministic and acyclic.
Minimal and Reduced SDDs. For any node v ∈ V , we deﬁne the language
LB (v) of node v of SDD B: (i) LB (0) = ∅; (ii) LB (1) = {ε}; (iii) LB (v) =LB (v.0) ∪ x · LB (v.1) for any v ∈ VN and x = v.top. Equivalently, LB (v) is theset of the strings spelled out by all the paths π from v to the terminal 1 obtainedby concatenating the labels v.lab of the nodes such that π contains both of v andv.1. The language of B is deﬁned by the set L(B) = LB (r). We say that SDD
B is equivalent to SDD B ′ if L(B) = L(B ′ ). An SDD B is said to be minimal if
it has the smallest number of nodes among the equivalent SDDs, i.e., |B| ≤ |B ′ |for any SDD B ′ such that L(B ′ ) = L(B). A reduced SDD is a normal formof SDDs. An SDD B = ⟨Σ, V, τ, r, 0, 1⟩ is said to be reduced if it satisﬁes theconditions 1 and 2 below:
1. For any u, v ∈ VN , τ (u) = τ (v) implies u = v (node-sharing rule).
2. For any v ∈ VN , v.1 ̸= 0 holds (zero-suppress rule).
The above rules say that no distinct non-terminal nodes have the same triple,
and the 1-child of any non-terminal node v is not the 0-terminal.
Example 1. In Fig. 1, we show examples of a trie B1 (left), a minimal DFA B2(middle), and a reduced SDD B3 (right) for the same string set S1 = {aaaab,
aaab, aabab, aabb, aa, abbab, abbb, ab, bbab, bbb, b} on an alphabet Σ = {a, b} allin the form of SDDs, where the set of numbers attached to each node indicate
the equivalent node numbers, and the 0-terminal 0 and all edges pointing to 0
are omitted for convenience. In the ﬁgure, we observe that
– we get the DFA B2 from the trie B1 and the minimal SDD B3 from theDFA B2 by merging a set of equivalent nodes that have the same subgraphto get a smaller structure. For example, we obtain B2 from B1 by merging
2

In our implementation of an shared and reduced SDD environment described inSec. 6, |B| = |VN | is actually the number of entries in a node table since terminals 0
and 1 have no associated entries in the table.

all 1-terminals into the node labeled [1-11], the nodes 12, 14, 16, and 18 into
the node labeled [12, 14, 16, 18], and so on.
– Similarly, we obtain B3 from B2 by merging the nodes labeled [12, 14, 16, 18]
and [13, 15, 17, 19] into the node labeled [12-19], the nodes labeled [25] and[26, 27] into the node labeled [25-27], and so on.
– In their sizes, the reduced SDD B3 is smallest having seven nodes, while theminimal ADFA B2 and the trie B1 have 10 and 20 nodes, resp.
– In all structures, the path π1 = 101101 spells out the same string s1 = abbb
on the node sequences v 1 = (31, 28, 29, 26, 22, 17, 8) in B1 , v 2 = (31, 28,
29, [26, 27], [20-23], [13, 15, 17, 19], [1-11]) in B2 , and v 3 = (31, 28, [29, 30],[25-27], [20-23], [12-19], [1-11]) in B3 , where the overlined nodes are the nodes
having 1-edge on π emitting a symbol in s1 .
– We also see that B2 is an SDD representing a minimal DFA, but is not reduced because three pairs of nodes ⟨29, 30⟩, ⟨25, [26, 27]⟩ and ⟨[12, . . .], [13, . . .]⟩violate the node-sharing rule.
Relationship between an ADFA and an SDD. The relationship between
an ADFA and an SDD is summarized as follows. An ADFA (in binary format)
is an SDD without sibling sharing, that is, an SDD satisfying conditions (i)only ﬁrst children have incoming 1-edges and (ii) each node has at most one
incoming 0-edges. For example in Fig. 1, we see that the DFA B2 satisﬁes theabove conditions, while it is not the case for the SDD B3 . Thus, we know that thesize of a minimal SDD B is no more than that of an equivalent minimal ADFA
A, i.e., |B| ≤ |A|. It is shown in [10] that the minimal ADFA A equivalent to an
SDD B is at most |Σ| times larger than B.

3

Reduction and Minimization algorithms

In this section, we show the equivalence of reduced SDDs and minimal SDDs,
and then, present a linear-time reduction algorithm for SDD.
3.1

The minimality of a reduced SDD

Let L ⊆ Σ ∗ is any ﬁnite set of strings. We ﬁrst see that the canonical SDD
for L is deﬁned, in a similar way to the minimal DFA in Myhill-Nerode theorem (e.g.,[12]), as follows. The main diﬀerence from one for DFA is the operation
to derive successors of a state. We deﬁne string sets
– L.1 = { α ∈ Σ ∗ | xα ∈ M, x = top(L) } (onset operation),– L.0 = L \ (x · L.1) (oﬀset operation),where top(L) is top(L) = min≤Σ { x ∈ Σ | xα ∈ L, α ∈ Σ ∗ }, i.e., the ﬁrst letterof the lexicographically smallest string in L if it exists. For any L ̸∈ {∅, {ε}},top(L), L.1, and L.0 are always deﬁned. Now, we build the canonical SDD B∗
for L by taking as its nodes the diﬀerent sets L.π for all π ∈ {0, 1}∗ , as theroot L = L.ε, as the 1-terminal 1 = {ε}, as the 0-terminal 0 = ∅, and with

1- and 0-edges deﬁned for any L ̸= 1, 0, respectively, by (L.π).1 = L.(π.1)
and (L.π).0 = L.(π.0). The nodes 1 and 0 has no out-going edges. Clearly, thecanonical SDD for L is completely determined by L. For any L ⊆ Σ ∗ , let us
deﬁne its index by idx(L) = |L| + maxlen(L) ≥ 0.
Lemma 1. For any L ⊆ Σ ∗ , if L is neither ∅ nor {ε}, then for every α = 0, 1,
L.α is deﬁned, and moreover, idx(L) > idx(L.α) holds.
Proof. The claims are easily shown by induction on idx(L).

⊓⊔Lemma 2. The canonical SDD B∗ for any L ⊆ Σ ∗ is well deﬁned.
Proof. The deteminicity is obvious. Let us deﬁne idx(L) = |L| + maxlen(L) ≥ 0.
From Lemma 1, we see that there is no arbitrary long chain of nodes L1 , L2 , . . .
in B∗ following either 0- or 1-edges such that idx(L1 ) > idx(L2 ) > · · · . Thisshows the acyclicity of B∗ .
⊓⊔We prepare some technical lemmas on the relationship between canonical
SDDs and reduced and non-reduced SDDs.
Lemma 3. Any reduced SDD B is isomorphic to the canonical SDD B∗ for
L(B). More precisely, for any v ∈ VN , we have: (0) v.lab = top(L). (1) LB (v) =∅ iﬀ v = 0. (2) LB (v.1) = LB (v).1 ̸= ∅. (3) LB (v.0) = LB (v).0.
Proof. Recall that LB (v) = x · LB (v.1) ∪ LB (v.0) for any v ∈ VN . (0) Since B isdeterministic and v satisﬁes zero-suppress rule, it is proved. (1) Immediate fromzero-suppress rule. Let v be any non-terminal node v with L = LB (v). From (2)of Lemma 3, we have LB (v.1) ̸= ∅. (2) From zero-suppress rule, LB (v.1) ̸= ∅.
Since x = v.lab is the smallest among its sibling, the claim holds. (3) Since B isdeterministic, we have (x · LB (v.1)) ∩ LB (v.0) = ∅. Thus, the claim follows. ⊓⊔Lemma 4. Let B∗ and B be any SDDs. If B∗ is canonical and L(B∗ ) = L(B),then for any u ∈ V (B∗ ), there is some v ∈ V (B) such that LB∗ (u) = LB (v).
Proof. Let L = L(B∗ ) = L(B). Let u ∈ V (B∗ ) be any node of a canonical SDD
B∗ . Then, we have a path π(u) ∈ {0, 1}∗ in B∗ such that r.π(u) = u. Since B∗
is unique, such a π(u) is unique for each u. We show the claim by induction on
the length m = |π(u)|. (Case 1) The case that |π(u)| = 0 is obvious. (Case 2)
The case that |π(u)| > 0. Then, there exists the unique parent p of u such thatu = p.α for some α ∈ {0, 1}. Because B∗ is canonical, p is non-terminal and
LB∗ (p) is neither ∅ nor {ε}. Clearly, π(p) < π(u). By inductive hypothesis, there
exists some q ∈ V (B) with LB∗ (p) = LB (q). It is possible that the node q has an
empty 0-child. However, we can show that there exists some younger sibling q̃ ofq such that LB (q̃) = LB (q) and q̃.1 ̸= 0 by following 0-edges from q. Otherwise,
we ﬁnally reach either 1 or 0. From this observation, let q̃ be a non-terminal
node of B which is a descendant of q and satisﬁes that LB (q̃) = LB (q) andq̃.1 ̸= 0. If LB∗ (p) = LB (q̃) and q̃.1 ̸= 0, we have that LB∗ (p.1) = LB (q̃.1) andLB∗ (p.0) = LB (q̃.0). Thus, LB∗ (p.α) = LB (q̃.α) holds, and the lemma is proved.
Combining the above arguments, we show the lemma.
⊓⊔Now, we have the main theorem of this section.
Theorem 1 (characterization of minimal SDDs). For any SDD B withthe language L = L(B), the following (1)–(3) are equivalent each other.
(1) B is a reduced SDD.
(2) B is a canonical SDD for L up to isomorphism.
(3) B is a minimal SDD.
Proof. [(1) ⇒ (2)]: Suppose that B is reduced. Let B∗ be the canonical SDD
for L. From Lemma 3, if we take ϕ(v) = LB (v), we see that ϕ : V (B) → V (B∗ )satisﬁes that ϕ(1) = {ε}, ϕ(0) = ∅, ϕ(r) = L, and for any v ∈ V (B), ϕ(v.α) =ϕ(v).α holds for every α = 1, 0. From Lemma 3 and the fact that the states of B∗
are the diﬀerent languages, we see that ϕ is actually a bijection between V (B)and V (B∗ ). This shows the claim (End of (1) ⇒ (2)).
[(2) ⇒ (3)]: Suppose without loss of generality that B is the canonical SDD
B∗ for L. Obviously, all nodes of B∗ have mutually distinct languages. By contradiction, suppose that there exists some SDD B ′ such that L(B) = L(B ′ ) and|B ′ | < |B|. From Lemma 4, there exists some mapping ϕ : V (B) → V (B ′ ) suchthat LB (u) = LB ′ (ϕ(u)) holds for any u ∈ V (B). By pigeonhole principle, we
see that ϕ must be injective; Otherwise, there exist some distinct pair of nodes,
u1 , u2 ∈ V (B) (u1 ̸= u2 ), such that ϕ(u1 ) = ϕ(u2 ), and thus, LB (u1 ) = LB (u2 );The contradiction is derived. Hence, the claim is proved. (End of (2) ⇒ (3)).
[(3) ⇒ (1)]: We show that if B is not reduced then B is not minimal. Supposethat B is not a reduced SDD. Then, (i) If B violates the node-sharing rule, thenthere are distinct nodes u1 , u2 ∈ VV (u1 ̸= u2 ) such that τ (u1 ) = τ (u2 ). Then,we identify u1 and u2 . (ii) If B violates the zero-suppress rule, then there is a
non-terminal u ∈ VV such that u.1 = 0, and we replace u with u.0. Then, theresulting reduced SDD B ′ is equivalent to B and has a strictly smaller than B,
and thus, B is not minimal. (End of (3) ⇒ (1)). Combining the above arguments,
the theorem is proved.
⊓
⊔

3.2

On-the-ﬂy and oﬀ-line minimization

At the top of Fig. 2, we show the node allocation procedure Getnode for on-theﬂy minimization of SDDs as well as the hash tables uniqtable : Σ × dom2 →dom that corresponds to τ for node-sharing, and cache : op × dom∗ → domthat stores invocation patterns of user-deﬁned operations for avoiding redundant
computation. In all results in this paper, we assume that these hash tables areglobal variables, and a look-up for a hash table takes O(1) time; We have to
add additional O(log n) term if we use balanced binary tree dictionary [1]. In
the shared and reduced SDD environment [15] studied here, we use write-only
construction, similar to [11], such that any new SDD is constructed by adding a
new node on the top of already constructed SDDs using a call of Getnode given
existing nodes as its arguments. The next lemma say that on-the-ﬂy constructionof SDDs is correct under condition below.

'$Global variable: uniqtable, cache: hash tables for triples and operations.
Proc Getnode(x: letter, P0 , P1 : SDD):
1: if (P1 = 0) return P0 ; /* zero-suppress rule */2: else if ((R ← uniqtable[⟨x, P0 , P1 ⟩]) exists) return R; /* node-sharing rule */3: else4:
R ← a new node with τ (R) = ⟨x, P0 , P1 ⟩;5:
uniqtable[⟨x, P0 , P1 ⟩] ← R;
6:
return R;
Algorithm Reduce(P : possibly non-reduced SDD):
1: if (P = 1 or P = 0) return P ;2: else if ((R ← cache[“Reduce(P )”]) exists) return R;
3: else4:
R ← Getnode(x, Reduce(P.0), Reduce(P.1));
5:
cache[“Reduce(P )”] ← R;
6:
return R;&

Fig. 2. An algorithm for computing the reduced version of a seqBDD

Lemma 5 (correctness of on-the-ﬂy reduction). Let B be any reduced SDD
and ⟨x, v0 , v1 ⟩ ∈ Σ × dom2 be any triple with x ≺Σ v0 .top. Then, if we invoke
v = Getnode(x, v0 , v1 ) and add the result v to V , then the resulting SDD B ′obtained from B is well-deﬁned and reduced, too.
In Fig. 2, we show our oﬀ-line reduction algorithm Reduce using Getnode thatcomputes the reduced version red(B) from an input SDD B.
Theorem 2 (reduction). The algorithm Reduce of Fig. 2 computes a reduced
SDD red(B) equivalent to B in O(n) time and space in the input size n = |B|.
Proof. For the equivalence of the language of B and red(B), the node-sharing
and zero-suppress rules at Lines 1 and 2 in Getnode does not change the language.
Lemma 5 ensures that the resulting SDD B is kept reduced after adding newnodes returned by Getnode. For time complexity, we see that the use of cache issuﬃcient to ensure the linear-time complexity by avoiding the duplicated call of
Reduce.
⊓⊔From Theorem 2 and Theorem 1, we have the complexity of the minimization
problem for SDDs using the algorithm Reduce.
Corollary 3 (complexity of oﬀ-line minimization) For any SDD B, theminimal SDD equivalent to B is linear time and space computable in n = |B|.

%

'

$

Global variable: uniqtable, cache: hash tables for triples and operations.
Algorithm Meld⋄ (P, Q: possibly non-reduced SDDs):
Output: The reduced SDD for the melding P ⋄ Q given F⋄ : {0, 1}2 → {0, 1};
1: if (P = 0 or Q = 0 or P = Q)
2:
if (F⋄ [sign(P ), sign(Q)] = 0) return 0; /* See text for F⋄ . */3:else if P ̸= 0 return P ;4:else if Q ̸= 0 return Q;
5: else if (F⋄ [0, 1] = F⋄ [1, 0] and P > Q) return Meld⋄ (Q, P );6: else if ((R ← cache[“Meld ⋄ (P, Q)”]) exists) return R;
7: else8:x ← P.lab; y ← Q.lab;
9:
if (x ≺Σ y) R ← Getnode(x, Meld⋄ (P.0, Q), Meld⋄ (P.1, 0));10:else if (x ≻Σ y) R ← Getnode(y, Meld⋄ (P, Q.0), Meld⋄ (0, Q.1));
11:else if (x = y) R ← Getnode(x, Meld⋄ (P.0, Q.0), Meld⋄ (P.1, Q.1));
12:
cache[“Meld ⋄ (P, Q)”] ← R;
13:
return R;&%

Fig. 3. An algorithm Meld⋄ for built-in binary set operations ⋄ ∈ {∪, ∩, \, ⊕}.

4

A linear-time dynamic construction algorithm

This section studies the dynamic construction problem for SDDs in the shared
and reduced SDD environment. First, we prepare built-in binary operations for∗∗∗
SDDs. Let ⋄ ∈ {∪, ∩, \, ⊕} be the names of set operations ⋄ : 2Σ ×2Σ → 2Σ . We
deﬁne F⋄ : {0, 1}2 → {0, 1} by F∪ [x, y] = x∨y, F∩ [x, y] = x∧y, F\ [x, y] = x∧¬y,and F⊕ [x, y] = x ⊕ y (exclusive-or), In Fig. 3, we give the algorithm Meld⋄ thatcomputes the reduced SDD R for the set L(R) = L(P ) ⋄ L(Q) of two SDDs givenF⋄ [5, 10, 14, 15], where sign(P ) is 0 if P = ∅ and 1 otherwise. The Meld⋄ (P, Q)
runs in O(|P | · |Q|) and also in O(|R|) in the worst case. See the paper [10] forthe details.
For any SDD B with S = L(B) and any string s, add(B, s), delete(B, s),
and switch(B, s), resp., build and return the reduced SDD B ′ for the string setsS ∪ {s}, S\{s}, and S ⊕ {s} = (S\{s}) ∪ ({s}\S). The dynamic construction
problem for SDDs is the problem of constructing a sequence of SDDs (Bi )ki=0 (k ≥0) as follows. The inputs are an SDD B0 = 0, an empty hash table τ = uniqtable,
and a sequence s1 , . . . , sk ∈ Σ ∗ of k ≥ 1 strings. For every i ≥ 1, we apply one ofthe operations α ∈ {add, delete, switch} to compute Bi = α(Bi−1 , si ). In Fig. 4,
we present the algorithms for these operations. Given a string s, MakeString,
the algorithm ﬁrst builds a reduced SDD for s in linear-time, and then apply αusing algorithm Meld⋄ in linear-time without touching all but O(n) nodes though
Meld⋄ requires quadratic time in general [10]. This claim is formally veriﬁed asfollows.

'$Global variable: uniqtable, cache: hash tables for triples and operations.
Proc MakeString(s ∈ Σ ∗ : string):
Output: The reduced SDD Q for a string s;
Q = 1; for (j = |s|, . . . , 1) do Q ← Getnode(s[j], 0, Q); return Q;
Algorithm add(B, s)≡ Meld∪ (B, MakeString(s));
Algorithm delete(B, s) ≡ Meld\ (B, MakeString(s));
Algorithm switch(B, s) ≡ Meld⊕ (B, MakeString(s));&%

Fig. 4. The algorithm MakeString for constructing the reduced SDD Q for s, and thealgorithms add, delete, and switch for dynamically adding, deleting, and switching asingle string s to an SDD B.

Theorem 4 (dynamic construction). For any SDD B and any string s,
Algorithms add, delete, and switch of Fig. 4 correctly work, take O(|s|) time,and moreover, add at most O(|Σ| · |s|) nodes to and delete no nodes from the
input SDD B.
Proof. We give a proof sketch for add. Other cases are proved similarly. The
correctness is obvious from that of Meld∪ and MakeString. Given a string s,
MakeString builds a chain SDD Q in O(|Σ|·m) time. During the computation ofMeld∪ (B, Q) in Fig. 3, we have v.0 = 0 for any node v in Q. Thus, we see thatLines 9, 10, and 11 become equivalent invocations– (i) Getnode(x, Meld⋄ (P.0, Q), P.1),– (ii) Getnode(y, P, Q.1), and– (iii) Getnode(x, P.0, Meld⋄ (P.1, Q.1)),
resp., after constant steps. Calls (i) and (iii) are used for traversing 0- and 1edges, resp., and (ii) for inserting the rest of Q. From this observation, we canshow that add(B, Q) makes O(|Σ| · |Q|) calls of Meld∪ , adds O(|Σ| · |Q|) nodes,
and takes O(|Σ| · |Q|) time.
⊓⊔
Corollary 5 (linear-time dynamic construction) For any input sequenceof strings (si )ki=0 (k ≥ 0), the dynamic construction problem for SDDs is solvable∑kin O(|Σ| · n) total time and adds O(n) nodes, where n = i=1 |si | is the input
size.
Proof. Immediate from Theorem 4.

⊓⊔Corollary 5 generalizes the linear-time complexity of the incremental string
set construction problem for ADFA by [9]. Interestingly, we observe that thatadd precisely simulates the algorithm of [9] in write-only manner. In the casethat only the ﬁnal SDD is needed, we can reclaim memory in O(n) time bydiscarding intermediate SDDs with garbage collection (GC) [14, 15, 18].

'$Global variable: uniqtable, cache: hash tables.
Proc RecFSDD(P : SDD):
2: if P = 0 or P = 1 return P ;3: else if (F ← cache[“RecF SDD(P )”] exists) return F ;4: else5:
P re(P.1) ← SDD for all preﬁxes of strings in P.1;
6:
F ← Meld∪ (Getnode(x, 1, P re(P.1)),
Meld∪ (RecFSDD(P.0), RecFSDD(P.1));
7:
cache[“RecFSDD(P )”] ← F ;8:return F ;&Fig. 5. A recursive procedure RecFSDD for constructing thefactor SDD of an input SDD.

5

a
14

b
13

a
12

a

b

b

a

10

11

9

3

1

%

Fig. 6. An example ofan FSDD for S2 ={baab}.

A practical algorithm for factor SDD construction

The factor SDD (FSDD), denoted by F SDD(B), for a set S ⊆ Σ ∗ is the
reduced SDD for Fact(S) of all factors of strings in S. The FSDD for an SDD B
is simply the FSDD for L(B). For example, Fig. 6 shows an examle of FSDD for
S2 = {baab}, which stores the set Fact(S2 ) = {ε, a, aa, aab, ab, b, ba, baa, baab} of
all 9 strings with totally 17 letters. Since it is well-known that the size of factor
automata F A(S) for a string set S is linear in ||S|| [3, 7], the size of F SDD(B)is also linear in |B|. (See [10] for the tight upperbound.)Since |B| can be exponentially smaller than ||L(B)||, eﬃcient constructionof FSDD from a given SDD is an interesting problem. In Fig. 5, we presents a
simple recursive algorithm RecFSDD that computes F SDD(B) from an input
SDD B using Meld∪ in write-only manner, where P re(P.1) is can be computedby redirecting all 0-edges pointing to 0 by those to 1 in P.1.
Theorem 6. The algorithm RecFSDD of Fig. 5 computes F SDD(B) from an
input SDD B in O(n3 ) time and space, where n = |B|.
Computation of RecFSDD seems similar to wotd algorithm [11] and othertop-down algorithms [21, 24]. Actually, we observed that applications of Pre andMeld∪ , resp., correspond to ε-edge attachment and determinization in [21]. Experiments in Sec. 6showed that RecFSDD ran in almost linear time on some real
data sets.

6

Experimental Results

Data and methods. In Table 1, we show the summary of our data sets, where
BibleAll and BibleBi are sets of all sentences and all word bi-grams drawn froman English text bible.txt, and Ecoli is a single DNA string in ecoli.txt inTable 1. Outline of data sets
Data
BibleAll
BibleBi
Ecoli

Size (byte)
4,047,392
7,793,268
4,638,690#line#Uniq line Ave line len (byte)
30,38330,129133.2
767,854
154,479
10.1
1
1.0
4,638,690.0

|Σ |
62
27
4

Table 2. Comparison of algorithms for string set construction
Input (Text)
Time (sec)
Output (SDD)
Size (byte) Uniq ratio Size (node) ConstTRIEConstINCConstOTF
BibleAll 4,047,392
0.99
3,099,401
13.5
16.3
2.0
BibleBi 7,793,268
0.20
101,2884503.2 4024.3
5.9
Data

Table 3. Comparison of factor indexes and their construction algorithms on BibleAll
data set consisting of long strings with few duplicates
Algorithm
Data
BibleAllSTRIE NaïveFSDD RecFSDD
ST
Size (Kilo node/cell) 14,284
6,110
6,110
6,093
Memory (Kilo byte) 185,687
183,300
183,300 109,680
Time (sec)
1,142.1
215.3
46.3
4.7

SA
4,047
36,427
1.4

Table 4. Comparison of factor indexes and their construction algorithms on BibleBi
data set consisting of short strings with many duplicates
Algorithm
Data
BibleBiSTRIE NaiveFSDD RecFSDD
ST
Size (Kilo node/cell)
1,315
309
309
8,251
Memory (Kilo byte)
17,0939,270
9,270 148,520
Time (sec)7,297.6
29.8
8.4
7.8

SA
7,793
70,1397.2

Canterbury corpus3 . We implemented our shared and reduced SDD environmenton the top of the SAPPORO BDD package [19] for BDDs and ZDDs written
in C and C++, where each node is encoded in a 32-bit integer and a node
triple occupies approximately 50 to 55 bytes in average including hash entries in
uniqtable. We also used another implementation of SDD environment in functional language Erlang. Experiments were run on a PC (Intel Core i7, 2.67 GHz,
3.25 GB memory, Windows XP SP3). About 1.5 GB of memory was allocatedto the SDD environment in maximum. For string set construction in Section 4,
we implemented the following algorithms: an oﬀ-line algorithm ConstTRIE using reduction of a trie, an incremental algorithm ConstINC that applies Reduce
every time adding a string, the proposed dynamic construction algorithm ConstOTF using on-the-ﬂy minimization. For factor index construction in Sec. 5,
we implemented the following algorithms: a suﬃx trie construction algorithm
STRIE in binary form, two FSDD construction algorithms Naı̈veFSDD and the
proposed RecFSDD, where the former uses direct set construction by ConstOTF
from Fact(S), construction algorithms ST for suﬃx trees [16] and SA for suﬃx3

http://corpus.canterbury.ac.nz/resources/

arrays [2]. The running time for RecFSDD does not include the construction time
for an input SDD.
Exp 1: String set construction. First, Fig. 7, Fig. 8, and Table 2 show
the results. From Fig. 7, we saw that a minimal SDD was 5 to 8 percent smaller
than the equivalent minimal ADFA in binary format. From Fig. 8, we saw thatthe proposed ConstOTF runs in linear-time as expected and was expected tobe scalable. From the comparison of algorithms in Table 2, we saw that the
proposed ConstOTF was much faster than other algorithms.
Exp 2: Factor index construction. From Figures 9 and 10, we observedthat the memory usage and the running time of our algorithm RecFSDD arealmost linear in the input size. Although the current theoretical upper boundof running time is cubic, this empirical result indicates practical eﬃciency of
RecFSDD algorithm. From Tables 3 and 4, RecFSDD algorithm was faster thanNaı̈veFSDD and STRIE algorithms on the set BibleAll of English sentences, andwas competitive to ST and SA, and much faster than Naı̈veFSDD and STRIE on
the set BibleBi of many short, duplicated strings.
For binary set operations, our preliminary experiments showed that it took
less than seconds to take set operations ∪, ∩, and \ of two SDDs with aroundthree to four thousands of nodes each, which are relatively smaller than the running time for set construction and factor SDD construction. Overall, we conclude
that the shared and reduced SDD environment with the above algorithms is apractical choice for storing string sets in large-scale string applications especiallywhen we need ﬂexible manipulation of them.

7

Conclusion

In this paper, we studied sequence BDDs (SDDs) and the associated algorithms
for manipulating sets of strings. Based on the framework of shared and reduced
SDDs, we show that the minimality of reduced sequence BDDs, and presented efﬁcient algorithms for on-the-ﬂy and oﬀ-line minimization, dynamic construction,and factor index construction from SDDs. demonstrating the power of combination of on-the-ﬂy minimization and graph-based string indexes. Analysis of thefactor SDD (FSDD) construction algorithm, development of external memoryalgorithms for FSDD, and real applications of SDDs are interesting future problems. It is another future problem to add to SDDs new functionalities of, e.g.,
detecting positions [4] and counting frequency [20].
Acknowledgements
They would like to thank Takashi Horiyama, Takeru Inoue, Jun Kawahara,
Takuya Kida, Toshiki Saitoh, Yasuyuki Shirai, Kana Shimizu, Yasuo Tabei, Koji
Tsuda, Takeaki Uno, and Thomas Zeugmann for their discussions and valuablecomments. This research was partly supported by MEXT Grant-in-Aid for Scientiﬁc Research (A), 20240014, FY2008–2011, and MEXT/ JSPS Global COE
Program, “Center for Next-Generation Information Technology based on Knowledge Discovery and Knowledge Federation,” FY2007–2011.

Size ratio

Runtime (ConstOTF)

1

BibleAll
0.8

0.9

Time (sec)

SDD size / DFA size

1.0

0.8

BibleAll
BibleAll (Fac)
Ecoli (Fac)

0.7

0.6
0

1,000,000

BibleBi
BibleBi (Fac)

BibleBi
0.6
0.4
0.2
0

2,000,000

01,000,000

2,000,000

Input size (byte)

Input size (byte)

Fig. 7. Ratio between the sizes SDDs
and DFAs in binary format

Fig. 8. Time of the incremental construction algorithm ConstOTF for SDDs

FSDD size

80

Runtime (BuildFSDD)

20

BibleAll

15

BibleBigram

Time (sec)Memory (Mbyte)

BibleAll
60

40

20

BibleBi
10

5

0

0
0

1,000,000

2,000,000

01,000,000

2,000,000

Input size (byte)

Input size (byte)

Fig. 9. The memory usage of FSDDs

Fig. 10. Time of the construction algorithm RecFSDD for FSDDs

References
1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer
Algorithms. Addison-Wesley, 1974.
2. J. L. Bentley, R. Sedgewick, Fast Algorithms for Sorting and Searching Strings,
Proc. SODA’97, SIAM, 360–369, 1997.
3. Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.I.:
The smallest automaton recognizing the subwords of a text, TCS, 40, 31–55, 1985.
4. A. Blumer, J. Blumer, D. Haussler, R. M. McConnell, A. Ehrenfeucht, Complete
inverted ﬁles for eﬃcient text retrieval and analysis, J. ACM, 34(3), 578–595, 1987.
5. Bryant, R.E.: Graph-based algorithms for boolean function manipulation,
IEEE. Trans. Comput., C-35(8), 677–691, 1986.
6. J. M. Couvreur and Y. Thierry-Mieg, Hierarchical decision diagrams to exploit
model structure, Proc. FORTE 2005, LNCS 3731, 443-457, 2005.
7. M., Crochemore, Transducers and repetitions, TCS, 45(1), 63–86, 1986.
8. M. Crochemore, C. Hancart, T. Lecroq, Algorithms on strings, Cambridge University Press, 2007.
9. J. Daciuk, S. Mihov, B.W. Watson, R.E. Watson, Incremental construction ofminimal acyclic ﬁnite-state automata, Computational Linguistics, 26(1), 2000.
10. S. Denzumi, R. Yoshinaka, H. Arimura, S. Minato, Notes on Sequence Binary
Decision Diagrams and Acyclic Automata, manuscript, Hokkaido University, April
2011.

11. R. Giegerich, S. Kurtz, J. Stoye, Eﬃcient implementation of lazy suﬃx trees
Softw. Pract. Exper., 33, 1035–1049, 2003.
12. J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Formal Language Theory,
2nd edition, Addison-Wesley, 2001.
13. S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, and S. Arikawa, Constructionof the CDAWG for a Trie, Proc. Prague Stringology Conf.(PSC 2001), 37-48, 2001.
14. D.E. Knuth, The Art of Computer Programming, vo.4, Fascicle 1, Bitwise Tricks& Techniques; Binary Decision Diagrams, Addison-Wesley, 2009.
15. E. Loekito, J. Bailey, J. Pei, A Binary decision diagram based approach for mining
frequent subsequences, Knowl. Inf. Syst., 24(2), 235-268, 2009.
16. E. M. McCreight, A space-economical suﬃx tree construction algorithm, J. ACM,
23, 262–272, 1976.
17. S. Minato, Binary decision diagrams and applications for VLSI CAD, Kluwer
Academic, 1996.
18. S. Minato, Zero-suppressed BDDs and their applications, International Journal
on Software Tools for Technology Transfer, 3(2), 156-170, Springer, 2001.
19. S. Minato, SAPPORO BDD package, Division of Computer Science, Hokkaido
University, unreleased, 2011.
20. Shin-ichi Minato, Hiroki Arimura, Eﬃcient method of combinatorial item set analysis based on zero-suppressed BDDs, Proc. WIRI’05, IEEE, 4-11, 2005.
21. M. Mohri, P. Moreno, E. Weinstein, Factor automata of automata and applications,
Proc. CIAA 2007, 168-179, 2007.
22. G. Navarro and M. Raﬃnot. Flexible Pattern Matching in Strings: Practical OnLine Search Algorithms for Texts and Biological Sequences. Cambridge, 2002.
23. D. Perrin, Finite Automata, Handbook of Theoretical Computer Science, Volume
B: Formal Models and Semantics, J. van Leeuwen (Eds.), Elsevier and MIT Press,
1–57, 1990.
24. Y. Tian, S. Tata, R. A. Hankins, J. M. Patel, Practical methods for constructing
suﬃx trees, VDLB J., 14(3), 281–299, 2005.
25. M. Thornton and R. Drechsler, Spectral decision diagrams using graph transformations, Proc. DATE’01, IEEE, 713-719, 2001.
26. E. Ukkonen, On-line construction of suﬃx-trees, Algorithmica, 14(3), 249-260,
1995.
27. I. Wegener, Branching programs and binary decision diagrams: theory and applications, SIAM, 2000.