6533b7ddfe1ef96bd12747ae

RESEARCH PRODUCT

On-line construction of two-dimensional suffix trees

subject

description

We present a new technique, which we refer to as implicit updates, based on which we obtain: (a) an algorithm for the on-line construction of the Lsuffix tree of an n x n matrix A — this data structure, described in [13], is the two-dimensional analog of the suffix tree of a string; (b) simple algorithms implementing primitive operations for LZ1-type on-dine lossless image compression methods. Those methods, recently introduced by Storer [35], are generalizations of LZl-type compression methods for strings (see also [24, 31]). For the problem in (a), we get nearly an order of magnitude improvement over algorithms that can be derived from known techniques [13]. For the problem in (b), we do not get an asymptotic speed-up with respect to what can be done with known techniques, e.g. [13, 28], but a major simplification in the implementation of the primitive operations. To the best of our knowledge, our technique is the first one that effectively addresses problems related to the on-line construction of two-dimensional suffix trees.