Construction of Substring Indices Using Sequence BDDs
Shuhei Denzumi, Hiroki Arimura, Shin-ichi Minato · Hokkaido University Collection of Scholarly and Academic Papers (Hokkaido University) · 2011
In sequence data mining, it is a fundamental task to compactly represent large sequence data and process efficiently on computer. There are demands for efficient substring index data structures for storing all substrings of a given text. Suffix trees and DAWGs (Directed Acyclic Word Graph) are examples of substring indices, but lack operations to manipulate sets of strings. The novel data structure Sequence Binary Decision Diagram (SeqBDD) by E. Loekito, J. Bailey, and J. Pei in 2009 is a new type of Binary Decision Diagram (BDD) and represents sets of sequences. This study focuses largely on two issues: (a) compact substring indices based on SeqBDD, called Suffix Decision Diagram (SuffixDD), making it possible to represent the set of all substrings efficiently with various operations inherited from Zero-suppressed Binary Decision Diagram (ZDD); (b) methods to build SuffixDD, beginning with the empty string and repeatedly updated if a new letter is read. This paper presents an efficient algorithm for constructing SuffixDD of a given text only by the primitive SeqBDD operations, together with a proof of correctness and some notes about BDD families, and discusses why the new data structure appears to have an advantage over existing substring indices. Upper bound on the running time is also obtained. It is hoped that proposition of this data structure to a wider audience at this time will help to promote useful discussion of the important issues.