The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of A . 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 size , . Motivated by applications in Image Compression , Giancarlo and Guaiana  considered the on-line version of the two-dimensional suffix tree and presented an O(n2 log2 n)-time algorithm, which we refer to as GG. That algorithm is a nontrivial generalization of Ukkonen’s on-line algorithm for standard suffix trees . The main contribution in this paper is an O(logn) factor improvement in the time complexity of the GG algorithm, making it optimal for unbounded alphabets . 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 O(logn) 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 trees . Specifically, here we provide a version of that algorithm which takes linear time and works on-line and concurrently over a set of strings.
|Publication status||Published - 2007|
All Science Journal Classification (ASJC) codes
- General Computer Science
- Computer Science Applications
- Applied Mathematics