6533b823fe1ef96bd127dfbd

RESEARCH PRODUCT

O(n 2 log n) Time On-Line Construction of Two-Dimensional Suffix Trees

subject

description

The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of Ai¾?[9]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet sizei¾?[9,15]. Motivated by applications in Image Compressioni¾?[18], Giancarlo and Guaianai¾?[12] considered the on-line version of the two-dimensional suffix tree and presented an On2log2n-time algorithm, which we refer to as GG. That algorithm is a non-trivial generalization of Ukkonen's on-line algorithm for standard suffix trees [19]. The main contribution in this paper is an Olog n factor improvement in the time complexity of the GG algorithm, making it optimal for unbounded alphabetsi¾?[7]. Moreover, the ideas presented here also lead to a major simplification of the GG algorithm. Technically, we are able to preserve most of the structure of the original GG algorithm, by reducing a computational bottleneck to a primitive operation, i.e., comparison of Lcharacters, which is here implemented in constant time rather than Olog n time as in GG. However, preserving that structure comes at a price. Indeed, in order to make everything work, we need a careful reorganization of another fundamental algorithm: Weiner's algorithm for the construction of standard suffix treesi¾?[20]. Specifically, here we provide a version of that algorithm which takes linear time and works on-line and concurrently over a set of strings.