Compact Complete Inverted Filesfor Texts and Directed Acyclic Graphs
Based on Sequence Binary Decision Diagrams
Shuhei Denzumi1 , Koji Tsuda2,3 , Hiroki Arimura1 , and Shin-ichi Minato1,3
1

Graduate School of IST, Hokkaido University, Sapporo, JapanAIST Computational Biology Research Center, Tokyo, Japan
3
JST ERATO MINATO Discrete Structure Manipulation System Project, Sapporo, Japan{denzumi, arim, minato}@ist.hokudai.ac.jp, koji.tsuda@aist.go.jp
2

Abstract. A complete inverted file is an abstract data type that provides functions
for text retrieval. Using it, we can retrieve frequencies and occurrences of strings forgiven texts. There have been various complete inverted files for texts. However, complete inverted files for graphs have not been studied. In this paper, we define complete
inverted files based on sequence binary decision diagrams (SDD) for directed acyclic
graphs (DAG). Directed acyclic graphs are given as sequence binary decision diagrams.
We propose new complete inverted files called PosFSDD and PosFSDDdag for a text
and a DAG, respectively. We also present algorithms to construct them and to retrieve
occurrence information from them. Computational experiments are executed to show
the efficiency of PosFSDDs.

1

Introduction

Recent emergence of massive text and sequence data has increased the importanceof string processing technologies. In particular, complete inverted files for efficient
text retrieval and analysis has attracted much attention in many applications suchas bioinformatics, natural language processing, and sequence mining. A complete inverted file for a text w is a data structure that stores all factors of w allowing threefunctions; find, freq, and locations. In many real applications, indices that store occurrence information are highly required. Sequence binary decision diagrams (sequence
BDDs or SDDs, for short) are compact representation for manipulating sets of strings,
proposed by Loekito, et al. [7]. In this paper, we consider the problem of constructing a complete inverted file on SDD framework. We define complete inverted files
on SDDs, named PosFSDD (See Fig. 2), and propose an algorithm to construct a
PosFSDD from an input text. We also define a complete inverted file for a directed
acyclic graph (DAG) and present an efficient construction algorithm to construct a
PosFSDDdag from an input DAG, which is given as an SDD. There is research on
construction factor automata from automata [10]. On the other hand, complete inverted files for graphs have not been studied. We can construct complete inverted files
for multiple texts by concatenating them on existing data structures. However, thosemethods cannot deal with very large number of strings such that DAGs can representby sharing its subgraphs. For example, regular expressions without infinite loop andhuman genomes with many replacements can be represented much more compactly
by DAGs than by explicit representations. We also show some experimental results forreal data. Our method will be useful for wide variety of pattern matching applications
and sequence mining.
Shuhei Denzumi, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato: Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence
Binary Decision Diagrams, pp. 157–167.
Proceedings of PSC 2013, Jan Holub and Jan Žd’árek (Eds.), ISBN 978-80-01-05330-0 c Czech Technical University in Prague, Czech Republic

158

Proceedings of the Prague Stringology Conference 2013

b

a
a

b

b

b

B{1} cc

B{2}c

B{0,1,2,3,4,5}

B{0,1,2,3,4,5}

B{4}

B{5}

1
0

B{2, 4}

1

B{2}

1

B{3, 5}010B

B{3, 5}B{2, 4}

B{3}

1

1

1

0

0

c
c

b

B{3}

c

c

B{4}

⊥

Figure 1. An SDD forthe language {ǫ, aaa,
aab, aac, ab, ac, b, bcc, c,ccc}. Circles denote nonterminals. Squares denote terminals. The 0terminal ⊥ and 0-edges
coming to ⊥ are omitted.

bB{5} A. The factor part

0

1

{1}

0

1

0

⊥

a

a

B. The position part

Figure 2. An example of a complete inverted file based on SDD, PosFSDD, for w = abcbc. The 0-terminal ⊥ is omitted. All 0-edges comingto ⊥ and ⊤ are indicated by a small black dot and white dot on theright side, respectively.

2

Preliminaries

2.1

Strings and string sets

Let Σ = {a, b, . . .} be a countable alphabet of symbols, for which the equality =Σ
and a strict total order ≺Σ , such that a ≺Σ b ≺Σ · · · , are defined on Σ. We often
omit the subscript Σ if no confusion arises. A string on Σ of length n ≥ 0 is asequence s = a1 · · · an of symbols, where |s| = n is called the length of s and for every
i = 1, . . . , n, s[i] = ai ∈ Σ is called the i-th symbol of s for 1 ≤ i ≤ |s|.
Let ǫ be the empty string of length zero, and Σ ∗ be the set of all possibly empty
finite strings. For strings x = a1 · · · am and y = b1 · · · bn , we define the concatenationof x and y by x·y = xy = a1 · · · am b1 · · · bn . For any symbol α ∈ Σ, let α·L = {α}·L ={ αx | x ∈ L }. We denote the reversed string of x by xR = x[|x|] · · · x[1]. For a strings, if s = xyz for x, y, z ∈ Σ ∗ , then we call x, y, and z a prefix , a factor , and a suffix
of s, respectively. The sets of prefixes, factors, and suffixes of a string s are denotedby Prefix (s), Factor (s), and Suffix (s), respectively. Given a set S of strings, let thesets of prefixes, factors, and suffixes of the strings in S be denoted by PREFIX (S),
FACTOR(S), and SUFFIX (S), respectively.
For any x ∈ Factor (w), eposw (x) denotes the set of all positions in w immediately
following the occurrences of x and bposw (x) denotes the set of all positions immediately preceding occurrences of x. We denote binary representation of an integer i
by binstr(i) ∈ {0 , 1 }∗ where the leading 0 s are omitted. Therefore, binstr(0) = ǫ. If
0 , 1 ∈ Σ, a ≺ 0 ≺ 1 for any symbol a ∈ Σ.
2.2

Finite Automata

We presume a basic knowledge of the automata theory. For comprehensive introduction to it, see [5,11] for example. A (partial) deterministic finite automaton DFA isrepresented by a quintuple A = hΣ, Γ, δ, q0 , F i, where Σ is the input alphabet, Γ isthe state set, δ is the partial transition function from Γ × Σ to Γ , q0 ∈ Γ is theinitial state and F ⊆ Γ is the set of acceptance states. The partial function δ can be

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

159

regarded as a subset δ ⊆ Γ ×Σ ×Γ . We define the size of a DFA A, denoted by |A|,as the number of labeled edges in A, i.e., |A| = |δ|.
The set of strings that lead the automaton A from a state q to an acceptancestate is denoted by LA (q). The language L(A) accepted by A is LA (q0 ). We say that
ADFAs A and A′ are equivalent if L(A) = L(A′ ). A minimal DFA has no state q suchthat LA (q) = ∅ and no distinct states q ′ and q ′′ such that LA (q ′ ) = LA (q ′′ ). Since
we are concerned with finite languages, all DFAs discussed in this section are acyclic
DFAs (ADFA, for short).
2.3

Sequence binary decision diagrams

In this subsection, we briefly give a formalization of sequence BDDs, introduced by
Loekito, Bailey, and Pei [7], and related concepts for further discussion. Let dom ={u, v, v1 , v2 , . . .} be a countable set, where each element is called a node, and let Σ
be a countable alphabet with which a strict total order ≺Σ is associated. A labeledbinary directed acyclic graph (labeled binary DAG) is a directed acyclic graph (DAG)
in which every node has out-degree either zero (terminal) or two (non-terminal),
where each non-terminal node has a pair of distinguished edges called the 0-edge andthe 1-edge . We call the nodes pointed to by the 0- and 1-edges the 0-child and the
1-child, respectively. We define the subgraph of S rooted at node v by the connected
subgraph of S reachable from v and denote it by S(v).
Roughly speaking, a sequence binary decision diagram [7] on Σ is a node-labeledbinary DAG that encodes an acyclic DFA on Σ in the leftmost child and right-sibling(LCRS , for short) representation (see, e.g., [1,6]), where the 0-child and 1-child of a
non-terminal node correspond to its leftmost child and the right sibling, respectively.
Formally, sequence binary decision diagram is defined as follows.
Definition 1. Let Σ be an alphabet. A sequence binary decision diagram (a sequence
BDD, for short) is a DAG S = hΣ, V, τ, ⊥, ⊤, ri satisfying the following conditions:– V = V (S) ⊆ dom is a finite set of nodes and every node has unique ID,– r ∈ V is a distinguished node called the root of S.
– ⊥ and ⊤ ∈ V are distinguished nodes called the 0- and 1-terminal, respectively.
The nodes in VN = V \{⊥, ⊤} are called non-terminals.
– τ : VN → Σ × V 2 is the function that assigns to each v ∈ VN the triple τ (v) =hv.lab, v.0, v.1i, called the node triple for v. Then, the triple indicates that (i)v.lab ∈ Σ is the label of v, (ii) v.0 ∈ V is the child, called the 0-child, that ispointed to by a 0-edge from v, and (iii) v.1 ∈ V is the child, called the 1-child,that is pointed to by a 1-edge from v.
– S must be acyclic in its 0- and 1-edges, that is, there exists some strict partial
order ≻V on V such that for any v ∈ VN , both of v ≻V v.0 and v ≻V v.1 hold.
– S must be 0-ordered, that is, for every non-terminal node v, if v.0 is a non-terminal
node then v.lab ≺Σ (v.0).lab must hold. This means that siblings are deterministically ordered from left to right by ≺Σ on their labels when S is interpreted as anacyclic DFA in the LCRS representation.
In the figures of this paper, the terminals/nonterminals are denoted by squares/circles,
and the 0/1-edges are denoted by dotted/solid lines.
In the above definition, S is said to be well-defined if it is both acyclic and 0ordered. We define the size |S| of S by the number of non-terminals in S, i.e., |S| =|VN | = |V | − 2. In the rest of this paper, we often abbreviate a sequence BDD as SDD
if no confusion arises.

160

Proceedings of the Prague Stringology Conference 2013

An important class of sequence BDDs is that of reduced sequence BDDs [7], which
is a syntactic normal form of SDDs defined as follows.
Definition 2 (reduced SDD [7]). An sequence BDD is said to be reduced if itsatisfies the following two conditions:– Node-sharing rule: For any non-terminal nodes u, v ∈ VN , τ (u) = τ (v) impliesu = v, i.e., no distinct non-terminal nodes have the same triple.
– Zero-suppress rule: For any non-terminal nodes v ∈ VN , v.1 6= ⊥ holds, i.e., nonon-terminal node has the 0-terminal as its 1-child.
The above two rules were originally introduced by Minato [8] for ZDDs [6]. A
sequence BDD S defines its language L(S) in the following way. The language of asequence BDD S is the language assigned to its root r.
Definition 3 (language). To each node v ∈ V , we inductively assign a language
LS (v) w.r.t. ≻V as follows: (i) LS (⊥) = ∅; (ii) LS (⊤) = {ε}; (iii) LS (v) = LS (v.0) ∪(v.lab) · LS (v.1).
In Fig. 1, we show an example of SDD for the language {ǫ, aaa, aab, aac, ab, ac, b, bcc, c,
ccc}.
In sequence BDD environment, we can create a new subgraph by combining one
or more existing subgraphs in an arbitrary way. As an invariant, all subgraphs aremaintained as minimal. In the environment, We use two hash tables uniqtable andcache, explained below. The first table uniqtable, called the unique node table, assigns
a nonterminal node v = uniqtable(c, v0 , v1 ) to a given triple t = hc, v0 , v1 i of a symbolc and a pair of nodes v0 and v1 . This table is maintained such that it is a function
from all triples t ∈ Σ × V 2 to the nonterminal node v in V such that τ (v) = t. If sucha node does not exist, uniqtable returns null. We define a procedure Getnode(c, v0 , v1 )that returns a node with the triple hc, v0 , v1 i. If there is such a node in V , Getnodereturns it. Otherwise, it creates such a node and returns it. The Getnode checks thetwo reduction rules by using the uniqtable to avoid creating duplicated nodes. The
second table cache, called the operation cache, is used for a user to memorize theinvocation pattern “op(v1 , . . . , vk )” of a user-defined operation op and the associatedreturn value u = op(v1 , . . . , vk ), where each vi , i = 1, . . . , k is an existing node in V .
For two given SDDs P and Q, we can compute a SDD R such that R is thelanguage obtained from primitive set operations, union, intersection and difference, on
the languages L(P ) and L(Q) by recursive algorithms [4]. In addition, concatenationof languages can be computed by Concat in Fig. 3. Using these algorithms, we canconstruct SDDs for sets of strings of exponential size such as regular expressions
without infinite repeats.
2.4

Complete Inverted File

The notion of an inverted file for a textual database is common in the literature on
information retrieval, but precise definitions of this concept vary. We use the following
definition. Given a finite alphabet Σ, and a text word w ∈ Σ ∗ , a complete inverted
file for (Σ, w) is an abstract data type that implements the following functions:– (1) find: Σ ∗ → Factor (w), where find (x) is the longest prefix y of x such thatx ∈ Factor (w) and y occurs in w, that is, x = yz, x, y, z ∈ Σ ∗ , and y is a factor
of a text w.

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

161✬
Global variable: uniqtable, cache: hash tables.

✩

Proc Concat(P, Q: SBDD):
Return: R: SDD;
1: if (P = ⊥ or Q = ⊥) return ⊥;2: else if (P = ⊤) return Q;
3: else if (Q = ⊤) return P ;4: else if ((R ← cache[“Concat(P, Q)”]) exists) return R;
5: else6:hx, P0 , P1 i ← τ (P );7:
R ← Getnode(P.lab, ⊥, Concat(P1 , Q));
8:R ← Union(R, Concat(P0 , Q));9:cache[“Concat(P, Q)”] ← R;
10:
return R;✫✪

Figure 3. An algorithm Concat that constructs the SDD for the language L(P ) · L(Q), for
given SDDs P and Q.

– (2) freq: Factor (w) → N, where freq(x) is the number of times x occurs as a factorof the text w.
– (3) locations: Factor (w) → N∗ , where locations(x) is the set of end positions within
the text in which x occurs.
In this paper, we consider the problem of constructing a complete inverted file fora text w. The function locations(x) returns the SDD that represents set of integers
eposw (x) as set of binary strings in our method. We describe SDDs can implement
complete inverted files compactly.
Example 4. Let w = abaababa be a given text. Then, find (baabbaab) = baab, freq(ba) =3, and locations(ba) = {3, 6, 8}.

3

Position Factor SDD

We begin with a brief look at some aspects of the factor structure of a fixed, arbitrary
word w. In particular, for each factor x of w we will be interested in the set of positionsin w at the ends of occurrences of x. We describe the basic data structure used to
implement a complete inverted file for a text w based on an SDD.
In our method, occurrence positions are represented as a set of binary strings
instead of simple a list of integers. If a factor x occurs at position i, our inverted filestores x · binstr(i). That is, a factor x of w is followed by its occurrence positions in
the complete inverted file. Then, we can know the occurrences of x after traversing thepath corresponding to x. All equivalent subgraphs are online minimized automaticallyby always using Getnode when a node with some triple is needed. Therefore, thesubgraphs which represent binary strings also share their equivalent subgraphs andbecome compact.
Definition 5. Let w be any string. Then, we define two languages.
– Lepos (w) = {x · binstr(k) : x ∈ Factor (w), k ∈ eposw (x)},– Lbpos (w) = {xR · binstr(k) : x ∈ Factor (w), k ∈ bposw (x)}.
Definition 6. The Position Factor SDD (PosFSDD) of w ∈ Σ ∗ is the SDD
F = hΣ ∪ {0, 1}, V, τ, ⊥, ⊤, ri such that L(r) = Lepos .

162

Proceedings of the Prague Stringology Conference 2013

The PosFSDD for w = abcbc is given in Figure 2. Note that the SDDs that
represent binary strings play a role analogous to the identification pointers in thecompact DAWG [3].
Theorem 7. Using PosFSDD F = hΣ ∪ {0, 1}, V, τ, ⊥, ⊤, ri for a word w ∈ Σ ∗ ,for any word x ∈ Σ ∗ , y = find (x) can be determined in time O(|Σ||x|). For anyx ∈ Factor (w), freq(x) can be determined in time O(|Σ||x|) if Card(r) is alreadyexecuted at least once.
Proof. To implement find, we begin at the root r and trace a path corresponding to
the letters of x as long as possible. This “search path” is determined and continues
until the longest prefix y of x in Factor (w) has been found. To implement freq, wenote that freq(x) = |{z : xz ∈ Lepos (w)}| = |eposw (x)| for any x ∈ Factor (w).
The algorithm Card computes the cardinality of the language that each SDD node
represents and stores each result in cache [6]. So, freq(x) can be obtained by following
the procedure of find and then returning the result of Card of the node stored in thecache. Card(r) is executed in linear time to the input SDD size. Since this node
represents the language M = {z : xz ∈ Lepos (w)}, we can obtain the node that
represents {b : b ∈ M, b ∈ {0 , 1 }∗ } by traversing 0-edges until getting a node labeledby 0 or 1. Clearly all queries are O(|Σ||x|).
⊓⊔
Our algorithm to construct PosFSDD is described in Fig. 4. The union operationis computed in O(|P ||Q|) time for two SDDs P and Q [4]. In fig. 5, we shows thealgorithm BinSDD(k) that constructs an SDD that represents a binary representationof a natural number k. That is, L(BinSDD(k)) is {binstr(k)}. We can also construct
an SDD for Lbpos with some modification of BuildPosFSDD. That is swapping |w|
with 0 in line 1 and line 5, and changing the for loop in line 2 from descending order|w|, . . . , 1 to ascending order 1, . . . , |w|.
For a given text w and its factor x, it takes O(freq(x) log w) time to computeoccurrence list of x after obtaining the SDD for locations(x), because occurrences are
represented as binary strings and every node has just one label. On the other hand,
there are advantages due to SDD representation, especially when freq(x) is large. A listof integers in ordinary representation requires O(f req(x)) space and time to examine
all positions. By sharing structures, these positions can be represented compactlyin our method. As a result, execution times for various operations are improved.
For example, for given two factors x and y, finding the positions that both occur
within l symbols is computed with some modifications. At first, we construct SDD′
for Lepos (w) = {x · binstr(k + j) : x ∈ Factor (w), k ∈ eposw (x), 0 ≤ j ≤ l}. Next,
obtain the SDDs for locations(x) and locations(y). Then, the positions we want arecomputed by the intersection operation of these two SDDs.

4

Position FSDD for SDD

We now show our algorithm that constructs a complete inverted file for a directed
acyclic graph given as an SDD. First we note that the complete inverted file for an
SDD S is defined as follows. In our method, we use node identifiers (IDs) instead of
positions for ordinary texts, and factors correspond to paths in the input SDD.
Given an SDD S, a complete inverted file for S for it is an abstract data type that
implements the following functions:Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

163✬
Global variable: uniqtable, cache: hash tables.

✩

Proc BuildPosFSDD(w: string):
Return: F : PosFSDD;
1: P|w| ← BinSDD(|w|), F|w| ← P|w| ;2: for i = |w|, . . . , 1
3:
Pi−1 ← Getnode(w[i], BinSDD(i − 1), Pi );4:
Fi−1 ← Union(Fi , Pi );5: return F0 ;✫✪✬Global variable: uniqtable, cache: hash tables.

✩

Proc BinSDD(k: natural number):
Return: B: SDD such that L(B) = {binstr(k)};1: return BinSDD0(k, ⌊log2 (k + 1)⌋);
Proc BinSDD0(k, l: natural number):
Return: B: SDD that L(B) = {l length binary string of k};
2: if (l = 0) return ⊤;3: else if (B ← cache[“BinSDD(k, l)”] exists) return B;
4: else5:
if (k&(1 << l) 6= 0) B ← Getnode(1 , ⊥, BinSDD0(k&((1 << l) − 1), l − 1));6:else B ← Getnode(0 , ⊥, BinSDD0(k&((1 << l) − 1), l − 1));
7:
cache[“BinSDD(k, l)”] ← B;
8: return B;✫✪✬
Global variable: uniqtable, cache: hash tables.

✩

Proc AppendID(P : SDD):
Return: R: SDD such that L(R) = {x · binstr(P.ID) : x ∈ F ACT OR(L(Q)),
P is a SDD node reachable from root via the path corresponding to x
and traversing 0-edges};
1: if (P = ⊥) return BinSDD(0);2: else if (P = ⊤) return BinSDD(1);3: else if (R ← cache[“AppendID(P )”] exists) return R;
4: else5:hx, P0 , P1 i ← τ (P );6:
R ← Union(Getnode(x, AppendID(P0 ), AppendID(P1 )), BinSDD(P.id));7:
cache[“AppendID(P )”] ← R;
8: return R;✫✪

Figure 4. An algorithm BuildPosFSDD for constructing the PosFSDD of an input stringw.

Figure 5. An algorithm BinSDD for constructing the SDD for {binstr(k)}. Bitwise AND
operation and bit left shift operaton are denoted by & and <<, respectively.

Figure 6. An algorithm AppendID for constructing the SDD with node IDs by binary
strings.

– (1) find: Σ ∗ → FACTOR(L(S)), where find (x) is the longest prefix y of x suchthat x ∈ FACTOR(L(S)) and y occurs in L(S), that is, y is a factor of a stringin L(S).

164

Proceedings of the Prague Stringology Conference 2013✬
Global variable: uniqtable, cache: hash tables.

✩

Proc BuildPosFSDDdag(S: SDD):
Return: F : Position FSDDdag for S;
1: return BuildPosFSDDdag0(AppendID(S));
Proc BuildPosFSDDdag0(P : SDD):
Return: G: SDD such that L(G) = {z : z ∈ SUFFIX (L(P )), z ∈ Σ + ·{0 , 1 }∗ };1: if (P = ⊥ or P = ⊤) return P ;2: else if (G ← cache[“BuildPosFSDDdag(P )”] exists) return G;
3: else4:hx, P0 , P1 i ← τ (P );5:
if (x ∈ {0 , 1 }) return P ;6:
G ← BuildPosFSDDdag0(P0 ) ∪ BuildPosFSDDdag0(P1 ) ∪ Getnode(x, ⊥, P1 ) ;7:cache[“BuildPosFSDDdag(P )”] ← G;
8: return G;✫✪

Figure 7. An algorithm constructs the PosFSDDdag for the input SDD S. Union operations
are denoted by ∪.
a
9

a

a

8

b

6

b

B{0,1,2,3,4,5,6,7,8,9}ac

B{0,1,3,5}bc

B{0,2,5,6,7,8}

4

c

a
b

7

c

5

a

B{0,1,5}

B{0,1,2,3,4,5,6,7,8,9}

B{0,2,5,6,7,8}1
0B{0,2}

1

0

1

B{0,1,5} B{0,1,3,5} B{0,2,5,7}

1

3

1

1

1

0

0

0

0
1

0

1

B{1}

a

b

c

B{0,2,5,7}

0

0

1

0

1

2

b
1

0

⊥

⊥

Figure 8.
An
SDD for {aaab,aac, abc, bab}.
Node IDs are
given on the sideof each nodes.

B{0,2}
B{1}A. The factor part

⊥

a

b

B. The position part

Figure 9. An example of a complete inverted file based on SDD, PosFSDDdag,
for the SDD in Fig. 8. The 0-terminal ⊥ is omitted. All 0-edges incoming to⊥ and ⊤ are indicated by a small black dot and white dot on the right side ofa node, respectively.

– (2) freq: FACTOR(L(S)) → N, where freq(x) is the number of nodes reachable bypaths corresponding to x that begins from any nodes in S.
– (3) locations: FACTOR(L(S)) → N∗ , where locations(x) is the set of IDs of nodes
in S to which paths lead that corresponding to x.
In our method, the set of node IDs that locations returns is represented by an SDD
for the set of binary strings of the IDs.
Let S be an SDD. For any x ∈ F ACT OR(L(S)), enodeS (x) denotes the set of all
IDs of nodes in S following the paths corresponding to x and traversing some 0-edges,
bnodeS (x) denotes the set of all IDs of nodes in S which represent a language M suchthat x ∈ P REF IX(M ).
Definition 8. We define Lenode (S) = {x · binstr(i) : x ∈ FACTOR(L(S)), i ∈enodeS (x)}, and Lbnode (S) = {xR · binstr(i) : x ∈ FACTOR(L(S)), i ∈ bnodeS (x)}.
The PosFSDDdag for S is the SDD G such that L(G) = Lenode (S).

165

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams
PosFSDD size

PosFSDD construction time

175

15000000E.coliE.coli150

bible.txt

125bible.txt
Computation time (s)Output PosFSDD size

12500000
10000000
world192.txt
7500000
5000000

world192.txt
100

2500000

75
50
25

0

0
0

250000500000
Input text size (byte)

75000001000000

Figure 10. SDD size of PosFSDD with increasing length of input string.

7500001000000

PosFSDDdag construction time5

Ecoli150

Ecoli150
4
Computation time (s)4000000
Output PosFSDDdag size

500000
Input text size (byte)

Figure 11. Computation time of BuildPosFSDD with increasing length of input string.

PosFSDDdag size

5000000

250000Ecoli500
3000000
BibleAll
2000000

1000000

Ecoli500
3
BibleAll
2

1

0

0
0

5000001000000

1500000

0

Input SDD size

Figure 12. SDD size of PosFSDDdag with increasing input SDD size.

5000001000000

1500000

Input SDD size

Figure 13. Computation time of BuildPosFSDDdag with increasing input SDD size.

The PosFSDDdag for an SDD S such that L(S) = {aaab, aac, abc, bab} is given in
Fig. 9, and Fig. 8 shows the input SDD.
Theorem 9. Using PosFSDDdag G, for any word x ∈ Σ ∗ , y = find (x) can be determined in time O(|Σ||x|). For any x ∈ FACTOR(L(S)) can be determined in timeO(|Σ||x|).
Proof. We can implement find, freq and locations as in PosFSDD for a text.

⊓⊔

Fig. 7 shows an algorithm to build the PosFSDDdag for an SDD S. The algorithm
in Fig. 6 is used for prepocessing of PosFSDDdag. The basic action of the algorithm
for an SDD S is to construct the PosFSDDdag for each node recursively, synchronizedwith the depth-first traversal of S. We can construct reversed version of the PosFSDDdag. It allows for the computation of the exact number of paths corresponding
to queries. It also allows for returning the node IDs at which the paths begin. Suchan SDD is constructed by executing BuildPosFSDDdag after appliying the algorithm
that construct an SDD for reversed L(S), which is proposed by Aoki et al. [2].
First, we append SDDs for node IDs to the input by AppendID. Next, we constructreversed SDD of it, but we do not reverse the SDDs that represent node IDs as binary
strings. Then, we can construct the SDD for Lbnode (S) by execute BuildPosFSDDdag0
on the obtained SDD.

5

Experimental Results

Setting: In the experiments, we used the following data sets. As real data sets, weused E.coli, bible.txt, and world192.txt obtained from the Canterbury corpus1 .
1

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

166

Proceedings of the Prague Stringology Conference 2013

From these data sets, we obtained the following derived data sets: BibleAll is theset of all lines drawn from bible.txt. Ecoli150 and Ecoli500 are the set of factors
drawn from E.coli by cutting the whole sequence at every 150-th or 500-th letter,
respectively. We made subsets of these data sets by randomly taking l lines varying
l = 10, 30, 100, . . . for BibleAll, Ecoli150, and Ecoli500.
We implemented our shared and reduced SDD environment on the top of the
SAPPORO BDD package [9] for BDDs and ZDDs written in C and C++, where eachnode is encoded in a 64-bit integer and a node triple occupies approximately 50 to 55
bytes on average including hash entries in uniqtable. We performed experiments on amachine that consists of eight quad-core 3.1 GHz Intel Xeon CPU E7-8837 SE processors (i.e, 32 CPU cores in total) and 1 TB DDR2 memory shared among cores. For
PosFSDD and PosFSDDdag construction, we implemented BinSDD, BuildPosFSDD,
AppendID, and BuildPosFSDDdag.
Experiment 1: PosFSDD construction. First, Fig. 10, and Fig. 11 show theresults. From Fig. 10, we see that PosFSDDs are almost O(n log n) size for n length
text. The number of nodes are between 12n to 15n. As is illustrated in Fig. 11, theproposed BuildPosFSDD runs in O(n log n).
Experiment 2: PosFSDDdag construction. Fig. 12 demonstrates that the
PosFSDDdags are close to linear in the size of the input SDDs. The number of nodes
are almost twice as that of the input SDD. As can be seen from Fig.13, BuildPosFSDDdag runs in almost O(N log N ) time for N sized input SDDs, practically.

6

Conclusions

We proposed PosFSDD that is a complete inverted file for a text based on SDD. We
also defined complete inverted files for directed acyclic graphs and implemented it
as PosFSDDdag. They allow all queries to be solved in O(|Σ||x|) time for n sized
input. We gave algorithms that construct PosFSDD and PosFSDDdag. From the experimental results, their sizes are compact and our algorithms BuildPosFSDD and
BuildPosFSDDdag run in almost O(n log n) time. The exact size bound of PosFSDD
and the exact time complexity of our algorithms are not obvious. To propose more
efficient algorithms is our future work. Position restricted search with PosFSDD isalso a challenging problem.

References
1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman: The Design and Analysis of Computer
Algorithms, Addison-Wesley, 1974.
2. H. Aoki, S. Yamashita, and S. Minato: An efficient algorithm for constructing a sequencebinary decision diagram representing a set of reversed sequences, in Proceedings of the 2011
IEEE International Conference on Granular Computing (GrC’2011), IEEE, 2011, pp. 54–59.
3. A. Blumer, J. Blumer, D. Haussler, R. M. McConnell, and A. Ehrenfeucht: Complete inverted files for efficient text retrieval and analysis. J. ACM, 34(3) 1987, pp. 578–595.
4. S. Denzumi, R. Yoshinaka, H. Arimura, and S. Minato: Notes on sequence binary decision diagrams: Relationship to acyclic automata and complexities of binary set operations, inProceedings of the Prague Stringology Conference 2011 (PSC’11), J. Holub and J. Žďárek, eds.,
Czech Technical University in Prague, 2011, pp. 147–161.
5. J. E. Hopcroft, R. Motwani, and J. D. Ullman: Introduction to Automata Theory,
Languages, and Computation, Addison-Wesley, 3rd. ed., 2006.
6. D. E. Knuth: The Art of Computer Programming, volume 4, fascicle 1, Bitwise Tricks &Techniques; Binary Decision Diagrams, Addison-Wesley, 2009.

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

167

7. E. Loekito, J. Bailey, and J. Pei: A binary decision diagram based approach for mining
frequent subsequences. Knowledge and Information Systems, 24(2) 2010, pp. 235–268.
8. S. Minato: Zero-suppressed BDDs and their applications. Software Tools for Technology
Transfer, 3(2) 2001, pp. 156–170.
9. S. Minato: SAPPORO BDD package. Division of Computer Science, Hokkaido University,
2011, unreleased.
10. M. Mohri, P. Moreno, and E. Weinstein: Factor automata of automata and applications,in Proceedings of the 12th International Conference on Implementation and Application ofAutomata (CIAA’07), LNCS 4783, Springer, 2007, pp. 168–179.
11. D. Perrin: Finite automata, in Handbook of Theoretical Computer Science,, J. van Leuwen,ed., vol. B. Formal Models and Semantics, Elsevier, 1990, pp. 1–57.