TCS -TR-A-06-16

TCS Technical Report

N-gram Analysis Based on Zero-suppressed BDDs

byR. Kurai, S. Minato, and T. Zeugmann

Division of Computer Science
Report Series A
June 17, 2006

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

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

N-gram Analysis Based on Zero-suppressed BDDs∗
Ryutaro Kurai, Shin-ichi Minato, and Thomas Zeugmann
Division of Computer Science
Hokkaido University
N-14, W-9
Sapporo 060-0814, Japan{ryu,minato,thomas}@mx-alg.ist.hokudai.ac.jp

Abstract
In present paper, we propose a new method of n-gram analysis using ZBDDs (Zero-suppressed BDDs). ZBDDs are known as a compact representationof combinatorial item sets. Here, we newly apply the ZBDD-based techniques
for efficiently handling sets of sequences. Using the algebraic operations definedover ZBDDs, such as union, intersection, difference, etc., we can execute various processings and/or analyses for large-scale sequence data. We conducted
experiments for generating n-gram statistical data for given real document files,
and the obtained results show the potentiality of the ZBDD-based method forthe sequence database analysis.

1. Introduction
One of the important data model that has been used for text analysis are n-grams(cf., e.g., [2], [7], [8], [9]). Recently, n-grams have been used not only for text analysis
but also for text indexing in some search engines [1]. If we can compactly represent
n-gram data and efficiently manipulate them, it will greatly facilitate text database
analysis and machine learning applications.
In this paper, we propose a method of n-gram computation with a new sequence
data structure based on Zero-suppressed BDDs. BDDs (Binary Decision Diagrams)
are graph-based representations of Boolean functions, now widely used in system design and verification. Zero-suppressed BDDs (ZBDDs) are a special type of BDDs
that are suitable for handling large-scale sets of combinations. Using ZBDDs, we canimplicitly enumerate combinatorial item set data and efficiently compute set operations over the ZBDDs. For n-gram computations, we need to manipulate sets of∗This paper has been presented at the 4th Workshop on Learning with Logics and Logics for
Learning (LLLL 2006), The Tower Hall Funabori, Tokyo, June 5-6, 2006

1

2

R. Kurai, S. Minato, and T. Zeugmann“sequences,” which is a more complicated data model than sets of “combinations.” In
this paper, we present a method of manipulating sets of sequences using ZBDDs andgenerate efficiently n-gram data for given sequence databases. We have implemented a
prototype system and show experimental results to evaluate our new n-gram analysis
method.

2. ZBDDs and Item Set Manipulation
Within this section, we briefly describe the basic techniques of ZBDDs for representing sets of combinations efficiently.
2.1. Sets of Combinations and their Representation
A set of combinations consists of the elements each of which is a combination of anumber of items. There are 2n combinations that can be chosen from n items, so wenhave 22 variations of sets of combinations. For example, for a domain of five items
a, b, c, d, e, we can express examples of sets of combinations as:{ab, e}, {abc, cde, bd, acde, e}, {1, cd}, ∅. Here “1” denotes a combination of null items,
and “∅” means the empty set. Sets of combinations are one of the basic data structures
for handling combinatorial problems. They often appear in real-life problems, such as
combinations of switching devices, sets of faults, paths in the networks, etc., and ofcourse, it can be used for representing frequent itemset data.
a
0
0
0
0
1
1
1
1

b
0
0
1
1
0
0
1
1

c
0
1
0
1
0
1
0
1

F
0
1
0
1
0
0
1
1

→c

As a Boolean function:
F = ab + ac

→ bc
As a set of combinations:
F = {ab, abc, bc, c}
→ ab
→ abc

Figure 1: Correspondence of Boolean functions and sets of combinations.

A set of combinations can be mapped into Boolean space of n input variables. For
example, Fig. 1 shows the truth table of the Boolean function (ab + ac), but it also
represents the set of combinations {ab, abc, bc, c}. Such Boolean functions are called
characteristic functions for the sets of combinations. Using BDD manipulation forcharacteristic functions, we can implicitly represent and manipulate large-scale setsof combinations. In addition, we can enjoy more efficient manipulation using “Zerosuppressed BDDs” (ZBDD) (cf. [4]), which are a special type of BDDs optimized forhandling sets of combinations.

3

N-gram Analysis Based on Zero-suppressed BDDs

x
0

f

x

Jump

1

0

f

f

(a) Ordinary BDD.

Jump

1

0

f

(b) ZBDD.

Figure 2: Different reduction rules for BDD and ZBDDs.

ZBDDs are based on the reduction rule different from one used in ordinary BDDs.
As illustrated in Fig. 2(a), the ordinary reduction rule deletes the nodes whose twoedges point to the same node. However, in ZBDDs, we do not delete such nodes but
delete another type of nodes whose 1-edge directly points to the 0-terminal node, as
shown in Fig. 2(b).
In ZBDDs, a 0-edge points to the subset (cofactor) of combinations not including
the decision variable x, and a 1-edge points to the subset (cofactor) of combinations
including x. If the 1-edge directly points to the 0-terminal node, it means that theitem x never appears in the set of combinations. The Zero-suppressed reduction ruleautomatically deletes such a node with respect to the irrelevant item x, and thus
ZBDDs more compactly represent sets of combinations than ordinary BDDs do.
The detailed techniques of ZBDD manipulation are described in the articles [4] [5].
A typical ZBDD package supports cofactoring operations to traverse 0-edge or 1-edge,
and binary operations between two sets of combinations, such as union, intersection,and difference. the computation time for each operation is almost linear to the number
of ZBDD nodes related to the operation.
2.2. Item Set Histograms and ZBDD Vectors
A item set histogram is the table for counting the number of appearances of each
item combination in the given database. An example of item set histogram is shownin Fig. 3. This is just a compressed table of the database to combine the same tuples
appearing more than once into one line with the frequency.
Our n-gram data structure is based on the item set histogram representation [6]using ZBDDs. Since ZBDDs are representation of sets of combinations, a simple
ZBDD distinguishes only existence of each combination in the database. In order torepresent the numbers of combination’s appearances, we decompose the number intom-digits of ZBDD vector {F0 , F1 , . . . , Fm−1 } to represent integers up to (2m − 1), as
shown in Fig. 4. Namely, we encode the appearance numbers into binary digital code,
as F0 represents a set of tuples appearing odd times (LSB = 1), F1 represents a setof combinations whose appearance number’s second lowest bit is 1, and similarly wedefine the set of each digit up to Fm−1 .

4

R. Kurai, S. Minato, and T. Zeugmann

Record ID
1
2
3
4
5
6
7
8
9
10
11

Comb.
abc
ab
abc
bc
ab
abc
c
abc
abc
ab
bc

Original Database

Comb.
abc
ab
bc
c

Freq.
5
3
2
1

Item set histogram

Figure 3: Database example and item set histogram.

Comb.

frequency

abc
ab
bc
c

5 (101)3 (011)2 (010)1 (001)F2 F1 F0
1 0 1
0 1 1
0 1 0
0 0 1

F0 = {abc, ab, c}
F1 = {ab, bc}, F2 = {abc}

F2

F1

a

F0

a
1

0

b
0

a

0
1

1
0

0

1
0 b

b

1

1
c
0

0

1

c
0 1
1

Figure 4: ZBDD vector for item set histogram.

In the example of Fig. 4, the item set frequencies are decomposed as: F0 ={abc, ab, c}, F1 = {ab, bc}, F2 = {abc}, and then each digit can be represented bya simple ZBDD. The three ZBDDs share their sub-graphs to one another.
When we construct a ZBDD vector of an item set histogram, the number of ZBDD
nodes in each digit is bounded by the total appearance of items in all combinations.
If there are many partially similar combinations in the database, the sub-graphs of
ZBDDs are shared very well, and a compact representation is obtained. The bitwidth of ZBDD vector is bounded by log Smax , where Smax is the appearance of mostfrequent items.
Once we have generated a ZBDD vector for the item set histogram, various operations can be executed efficiently. Here are the instances of operations used in ourpattern mining algorithm.
• H.factor0(v): Extracts sub-histogram of combinations not including item v.
• H.factor1(v): Extracts sub-histogram of combinations including item v and thendelete v from the combinations. (also considered as the quotient of H/v)

N-gram Analysis Based on Zero-suppressed BDDs

5

• v · H: Attaches an item v on each combination in the histogram F .
• H1 + H2 : Generates a new item set histogram with sum of the frequencies ofcorresponding tuples.
• H.tuplecount: The number of tuples appearing at least once.
These operations can be composed as a sequence of ZBDD operations. The result
is also compactly represented by a ZBDD vector. The computation time is boundedby roughly linear to total ZBDD sizes. The detailed techniques of ZBDD vector
manipulation are described in the articles [6].

3. ZBDD-Based Representation for Sets of Sequences
Next we explain, in some more detail, our method of generating n-gram data
representations using ZBDDs.
3.1. Sets of Sequences and Sets of CombinationsFirst, we describe the way to extend the representation of sets of combinations tosets of sequences. In our method, we define an item for each symbol (or character)used in each position of sequences. Namely, the item represents not only a symbol
but also its position in the sequence. An example is given below.
Sequences
AABC
CABC

Combinations
a1 a2 b 3 c 4c 1 a2 b 3 c 4

a1
c1

a2
b3
c4

0

1

Figure 5: ZBDDs example which expresses sets of sequences.
In the combination for the sequence “AABC,” the item a1 represents the symbol“A” at the first (leftmost) position. Similarly, c4 express the symbol “C” at the6

R. Kurai, S. Minato, and T. Zeugmann

4th position. In our method, if the same symbol appears at the different positions,
we treat them as different items. For example, the sequence “AABC” includes thesame symbol ”A” at the first and second positions, but we treat them as a1 anda2 , i.e., as different items. After such an assignment of items, a set of sequences
can be represented by a set of combinations. Then, the set of combinations can be
represented by a ZBDD. Figure 5 shows an example of ZBDD representing the set ofsequences { AABC, CABC }. In this way, the sets of sequences are decomposed tosets of combinations, and they can be manipulated by ZBDD-techniques.
3.2. n-gram Representation
An n-gram data is a histogram of all possible subsequences of the length n included
in a given sequences. As described in Section 2, we can compute item set histogramsby using ZBDD vectors. So, the ZBDD-based representation for sets of sequences canbe extended to the sequence histograms by using ZBDD vectors.
3.3. Binary Coding of Symbols
In our method, we use a number of items for the respective positions in the sequences. The number is the product of the number of symbols |Σ| and the sequencelength m. If we apply this method for a language using not so many symbols such as
gene sequence data, the number of items would be feasible. However, for a languagethat has many symbols such as Japanese Kanji, too many items would be required.
To address this problem, we propose a method of using binary coding to save thenumber of items.
When we assume the three symbols A, B and C for each position, we may use the2-bit binary coding shown in the following table.
Symbols
A
B
C

Items
ak
bk
ck

Binary code (x1k x0k ) Encoded combinations
01
x0k
10
x1k
11
x1k x0k

Using this encoding, we can express the sequences ”AABC” and ”CABC” by thefollowing table, and the resulting ZBDD is shown in Fig. 6.
Sequences
AABC
CABC

Encoded combinations
x01 x02 x13 x14 x04
x11 x01 x02 x13 x14 x04

We may use ASCII code for this purpose. ASCII code expresses conventional western characters with 8bit vectors. We treat one bit as one item. One can distinguishat most 255 symbols with a combination of eight items for each position. Examples
are shown below.

7

N-gram Analysis Based on Zero-suppressed BDDs
x11
x01
x02
x13
x14
x04
0

1

Figure 6: ZBDDs example which expresses sets of sequences.

Symbols
a
b
c
z
A

ASCII
Binary code(x7 x6 x5 x4 x3 x2 x1 x0 )Encoded(decimal)combinations
97
98
99
122
65

01100001
01100010
01100011
01111010
01000001

x6 x5 x0x6 x5 x1x6 x5 x1 x0
x6 x5 x4 x3 x1
x6 x0

If the probability distribution of the symbols is given, we shall be able to design amore efficient binary coding assignment.

4. Experimental Results
4.1. Generating n-gram Data Based on ZBDDs
For evaluating the feasibility of our method, we executed experiments for generating ZBDDs of the n-grams for a given text data. We used the English plain text data
“Alice in Wonderland.” This text consists of over 3,000 lines and 26,000 words, having
a total of 138KB of plane text. In our experiments, we used a 3.00GHz Pentium 4
Linux PC with 512MB main memory.
The results of generating n-grams for n = 1 to 10 are shown in Table 1. In thistable, the column “ZBDD nodes” shows the total number of nodes in the ZBDD vector
representing the n-gram. “#Sequences” gives the total number of different sequences
contained in the n-gram. “Max frequency” shows the number of appearances of themost popular subsequences in the text. In this experiment, we used the symbol
encoding method with ASCII code, as described in the previous section.

8

R. Kurai, S. Minato, and T. Zeugmann

From the result, we can observe that the size of ZBDDs is almost proportional
to the product of the length n and the number of sequences. The CPU time is also
almost linear in size of the ZBDD.
n ZBDD nodes #Sequences Max frequency Time(sec)
1121
26
13,681
3.17
2
1,428
518
3,813
6.18
3
9,487
4,750
2,402
9.45
4
33,19919,004500
12.96
573,94038,913417
16.73
6129,738
57,510221
22.41
7198,31172,28521130.33
8283,544
82,89111644.02
9388,863
90,247116
63.49
10522,175
95,36658
89.51
Table 1: Experimental results

After generating the ZBDD vector of the n-gram, we can easily retrieve the frequent
sequences by using algebraic operations over ZBDDs. The additional computation
cost is relatively smaller than the cost for generating n-grams. Table 2 shows the top
10 frequent sequences in the 5-gram of “Alice in Wonderland.” The most frequent
sequence is “alice,” and it appears 417 times. The 2nd, 3rd, 4th, and 10th sequences
seems a part of same sequence “he/she said the.” In this experiment, we removed
spaces, special symbols such as question mark, and periods from the text. We onlyused case-independent alphabets and numbers to create n-grams.
4.2. Post Processing for n-gram Data
Rank Sequence
1“alice”
2 “saidt”
3 “aidth”
4 “idthe”
5 “thing”
6 “andth”
7 “dalic”
8 “ofthe”
8 “ndthe”
10 “esaid”

Appearance
417
265
223
220
170
169
163
156
156
133

Table 2: Top 10 subsequences in the 5-gram of “Alice in Wonderland.”N-gram Analysis Based on Zero-suppressed BDDs

Rank Sequence
1“alice”
2 “thing”
2 “saidt”
4“littl”
4“ittle”

9Appearance
201
93
93
85
85

Table 3: Top 5 subsequences in the 5-gram of “First half of Alice in Wonderland.”Rank Sequence
1“alice”
2 “saidt”
3 “idthe”
4 “aidth”
5 “andth”

Appearance
216
172
145
143
103

Table 4: Top 5 subsequences in the 5-gram of “Second half of Alice in Wonderland.”Our ZBDD-based method features the flexible post processing after generating ngram data by using algebraic operations such as intersection, union, difference, andsome numeric operations.
For example, suppose that we want to obtain the subset of n-gram data such thatthe last letter is either “a,” “e,” “i,” “o,” or “u.” In this case, we first generate thefive subsets each of which includes each of the letters at the last position, respectively,
and then we apply union operations to combine all the subsets. These process caneasily be described in a command script of ZBDD operations.
Here we show a good example of applying ZBDD operations after generating ngram data. We prepared a command script to compare the two n-grams. That is, we
compare the first half of the text in “Alice in Wonderland” to the second half of it.
The results are displayed in the three tables below.
The first two tables do not differ much, since the same sequences appear manytimes in the first and second half of the text. Therefore, we also check the histogramof differences of the histogram. As shown in Table 5 below, the sequence “the queen”
appears only in this table. This is caused by the fact that “queen” appears in thestory only in the second half of the text (frequently).

5. Conclusions
In the present paper, we have proposed a new method to represent sequences in setsof item sets, i.e., by using ZBDDs. To demonstrate the efficiency of this method, we
have performed a preliminary experiment of generating an n-gram set for a given text
file. The experimental result shows that we can construct the ZBDD-based n-gram

10

R. Kurai, S. Minato, and T. Zeugmann

Rank Sequence
1 “saidt”
2 “idthe”
3 “queen”
4 “thequ”
5 “heque”
5 “equee”
5 “urtle”

Appearance
79
70
68
65
65
65
65

Table 5: Top 5 subsequences in the 5-gram of “Difference between First half andSecond half of Alice in Wonderland.”data structure in a feasible computation time and memory space.
Though we restricted ourselves within this paper to generate n-gram statistical
data for a given real document file, i.e., “Alice in Wonderland,” ZBDDs can also
be used to perform more advanced calculations. For example, we may also apply
our method to represent a text dictionary and to perform quickly dictionary search
operations.
It should be noted that our new method can also be applied to analyze and tomanipulate DNA data or some semi- structured data such as linguistic data annotatedby NLP tools (e.g., [3]). This will be done in the future.

References[1] B. Hoffmeister and T. Zeugmann: Text Mining Using Markov Chains of Variable
Length, In (K.P. Jantke, A. Lunzer, N. Spyratos, Y. Tanaka, eds), Federation
over the Web, International Workshop, Dagstuhl Castle, Germany, May 2005,
Revised Selected Papers, Lecture Notes in Artificial Intelligence Vol. 3847, pp. 1–
24, Springer, Feb. 2006.
[2] P. Jokinen, E. Ukkonen: Two algorithms for approximate string matching instatic texts, In Mathematical Foundations of Computer Science 1991, 16th International Symposium, MFCS’91, Kazimierz Dolny, Poland, September 9-13, 1991,
Proceedings, Lecture Notes in Computer Science Vol. 520, 240-248, SpringerVerlag 1991.
[3] T. Kudo, K. Yamamoto, Y. Tsuboi, Y. Matsumoto: Text mining using linguistic
information, IPSJ SIG-NLP NL-148, (in Japanese), pp. 65–72, 2002.
[4] S. Minato: Zero-suppressed BDDs for set manipulation in combinatorial problems, In Proc. 30th Design Automation Conference (DAC-93), pp. 272–277, ACM
Press, June 1993.

N-gram Analysis Based on Zero-suppressed BDDs

11[5] S. Minato: Zero-suppressed BDDs and their applications, International Journal
on Software Tools for Technology Transfer (STTT), 3(2):156–170, Springer, May
2001.
[6] S. Minato: VSOP (Valued-Sum-of-Products) Calculator for Knowledge Processing Based on Zero-Suppressed BDDs, In (K.P. Jantke, A. Lunzer, N. Spyratos,
Y. Tanaka, eds), Federation over the Web, International Workshop, Dagstuhl
Castle, Germany, May 2005, Revised Selected Papers, Lecture Notes in Artificial
Intelligence Vol. 3847, pp. 40-58, Springer, Feb. 2006.
[7] M. Nagano, and S. Mori: A new method of N-gram statistics for large numberof n and automatic extraction of words and phrases from large text data ofJapanese, In Proc. 15th conference on Computational linguistics, Vol. 1, pp. 611–
615, Association for Computational Linguistics, Morristown, NJ, USA, 1994.
[8] Y. Tsuboi: Mining frequent substrings, Technical Report of IEICE, NLC2003-47,
2003 (in Japanese).
[9] E. Ukkonen: Approximate string-matching with q-grams and maximal matches,
Theoretical Computer Science, 92(1):191–211, 1992.