O(n2 log n) Time On-Line Construction of Two-Dimensional Suffiz Trees
The two-dimensional suffix tree of an n×n square matrix A is a compacted trie that represents all square submatrices of A 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 size 9, 15. Motivated by applications in Image Compression 18, Giancarlo and Guaiana 12 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 non-trivial generalization of Ukkonens on-line algorithm for standard suffix trees 19. The main contribution in this paper is an O(log n) factor improvement in the time complexity of the GG algorithm, making it optimal for unbounded alphabets 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 O(log 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: Weiners algorithm for the construction of standard suffix trees 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.
Joong Chae Na Raffaele Giancarlo Kunsoo Park
School of Computer Science and Engineering, Seoul National University, Korea Dipartimento di Matematica ed Applicazioni, Universita di Palermo, Italy
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
273-282
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）