A GENERALIZATION OF THE SUFFIX TREE TO SQUARE MATRICES, WITH APPLICATIONS

摘要

We describe a new data structure, the Lsuffix tree, which generalizes McCreight's suffix tree for a string [J. Assoc. Comput. Mach.. 23 (1976), pp. 262-272] to a square matrix. All matrices have entries from a totally ordered alphabet Sigma. Based on the Lsuffix tree, we give efficient algorithms for the static versions of the following dual problems that arise in low-level image processing and visual databases. Two-dimensional pattern retrieval. We have a library of texts S = {TEXT(1)....TEXT(r)}, where TEXT(l) is an n(i) x n(i) matrix, 1 less than or equal to i less than or equal to r. We may preprocess the library, Then, given m x m, m less than or equal to n(i), 1 less than or equal to i less than or equal to r, pattern matrix PAT, we want to find all occurrences of PAT in TEXT, for all TEXT is an element of S. Let t(S) = Sigma(i=l)(r)n(i)(2) be the size of the library. The preprocessing step builds the Lsuffix tree for the matrices in S and then transforms it into an index (a trie defined over Sigma). It takes O(t(S)(log Sigma + log t(S))) time and O(t(S)) space. The index can be queried directly in O(m(2) log Sigma + torocc) time. where totocc is the total number of occurrences of PAT in TEXT, for all TEXT is an element of S. Two-dimensional dictionary marching. We have a dictionary of patterns DC = {PAT(1),..., PAT(J)}, where PAT(i) is of dimension m(i) x m(i), 1 less than or equal to i less than or equal to s. We may preprocess the dictionary. Then, given an n x n text matrix TEXT, we want to search for all occurrences of patterns in the dictionary in the text. Let t(DC) = Sigma(i=l)(s)m(i)(2) be the size of the dictionary and let (t) over bar(DC) be the sum of the m(i)'s. The preprocessing consists of building the Lsuffix tree for the matrices in DC. It takes O(t(DC) log Sigma + (t) over bar(DC) log (t) over bar(DC))) time and O(t(DC)) space. The search step takes O(n(2)(log Sigma + log (t) over bar(DC)) + totocc) time, where totocc is the total number of occurrences of patterns in the text. Both problems have a dynamic version in which the library and the dictionary, respectively, can be updated by insertion or deletion of square matrices in them. In a companion paper we will provide algorithms for the dynamic version. [References: 26]