
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Constructing the Suffix Tree of a Tree with a Large Alphabet
Tetsuo SHIBUYA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E86A
No.5
pp.10611066 Publication Date: 2003/05/01 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: algorithm, suffix tree, common suffix tree, integer alphabet, tree pattern matching,
Full Text: PDF>>
Summary:
The problem of constructing the suffix tree of a tree is a generalization of the problem of constructing the suffix tree of a string. It has many applications, such as in minimizing the size of sequential transducers and in tree pattern matching. The bestknown algorithm for this problem is Breslauer's O(nlog Σ) time algorithm where n is the size of the CStree and Σ is the alphabet size, which requires O(nlog n) time if Σ is large. We improve this bound by giving an optimal linear time algorithm for integer alphabets. We also describe a new data structure, the Bsuffix tree, which enables efficient query for patterns of completely balanced kary trees from a kary tree or forest. We also propose an optimal O(n) algorithm for constructing the Bsuffix tree for integer alphabets.

