TCS-TR-A-11-51

Date: Mon Mar 28 04:51:00 2011

Title: Sparse and Truncated Suffix Trees on Variable-Length Codes

Authors: Takashi Uemura and Hiroki Arimura

Contact:

First name: Hiroki
Last name: Arimura
Address: Graduate School of Infomration Science and Technology, Hokkaido University Kita 14, Nishi 9, Kita-ku, Sapporo, 060-0814 Japan
Email: arim@ist.hokudai.ac.jp

Abstract. The sparse suffix trees (SST), introduced by (Karkkainen and Ukkonen, COCOON 1996), is the suffix tree for a subset of all suffixes of an input text T of length n. In this paper, we study a special case that an input string is a sequence of codewords drawn from a regular prefix code Delta \subseteq Sigma^+ recognized by a finite automaton, and index points locate on the code boundaries. In this case, we present an online algorithm that constructs the sparse suffix tree for an input string t on any variable-length regular prefix code, called the code suffix tree (CST), in O(n + m) time and O(k) additional space for a fixed base alphabet \Sigma, where m is the size of an automaton for \Delta. Furthermore, we present a modified algorithm for k-truncated version of code suffix trees that runs in the same time and space complexities. Hence, these results generalize the previous results (Inenaga and Takeda, CPM 2006 for word suffix trees and (Na, Apostolico, Iliopoulos, and Park, Theor.~Comp.~Sci., 304, 2003) for truncated suffix trees on arbitrary variable-length regular prefix codes.