Suffix arrays: a new method for on-line string searches

Reviewer: John Sadowsky

The authors present algorithms for constructing and querying a data structure, the suffix array, which was introduced in their earlier paper [1], for use in online searches for strings in a large block of text. The suffix array is closely related to the suffix tree data structure. In both cases, the suffixes of the text are organized into a data structure, either as a search tree or as an array with auxiliary arrays to facilitate searching and comparison tasks. (If the text is A=a 0 a 1 a 2 &ldots;a N-1 , then the suffixes of A are of the form s k =a k a k+1 &ldots;a N-1 .) The primary result of this paper is that the suffix array uses less space for storage than does a suffix tree, and has complexity, in search and construction time and in storage required, that is independent of the size of the underlying alphabet, although these improvements are at the cost of an increase in initial data structure construction time. In particular, a suffix tree for a text A <__?__Pub Caret1>of length N over an alphabet of length S can be built in time O N log S using O N space and can answer queries of the form “Is W (of length P ) a substring of A __?__” in time O P log S . With more complicated auxiliary data, these complexities can be reduced to O N for the construction time and O P for the query, but at an increase in storage complexity to O NS . On the other hand, the suffix array can achieve query complexity of O P+ log N (a potential improvement for large alphabets) at the cost of O N log N for construction. The storage required is 3N integers which, although the same order of magnitude as the suffix tree, in practice amounts to three to five times less storage. The paper is well written, with several innovative algorithms presented so they can be implemented easily. With the aid of a survey paper, such as Apostolico [2] (cited in the bibliography of the paper), a researcher or practitioner could understand and make good use of this work.