Edward M. McCreight
Abstract
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.
- 1 AHO, A V., HoPcaoPr, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Agorithms. Addison-Wesley, Reading, Mass., 1974, Ch 9, pp. 317-361. Google Scholar
- 2 KIMBALL, R B. A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh, Pa., April 1974.Google Scholar
- 3 KNUTH, D.E. The Art of Computer Programmzng, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass, 1973, Ch. 6.3, pp. 490-493. Google Scholar
- 4 KSUTH, D.E Pattern matching in strings. Unpub. lecture notes, Trondheim, Norway, May 1973.Google Scholar
- 5 KNUTH, D.E., MORRIS, J.H. JR., AND PRATT, V.R. Fast pattern matching in strings. Comput. Sei. Rep. STAN-CS-74-440, Stanford U., Stanford, Calif., Aug. 1974.Google Scholar
- 6 PRATT, V R. Applications of the Weiner repetition finder. Unpub. paper, Cambridge, Mass., May 1973; rev Oct. 1973Google Scholar
- 7 WAGNER, R.A. Order-n correction for regular languages. Comm ACM 17, 5 (May 1974), 265-268. Google Scholar
- 8 WEINER, P. Linear pattern matching algorlthms. Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 1-11. Google Scholar
Index Terms
- A Space-Economical Suffix Tree Construction Algorithm
Recommendations
On the sorting-complexity of suffix tree construction
The suffix tree of a string is the fundamental data structure of combinatorial pattern matching. We present a recursive technique for building suffix trees that yields optimal algorithms in different computational models. Sorting is an inherent ...
The suffix binary search tree and suffix AVL tree
Suffix trees and suffix arrays are classical data structures that are used to represent the set of suffixes of a given string, and thereby facilitate the efficient solution of various string processing problems--in particular on-line string searching. ...
A suffix tree or not a suffix tree?
In this paper we study the structure of suffix trees. Given an unlabeled tree on n nodes and suffix links of its internal nodes, we ask the question "Is a suffix tree__ __", i.e., is there a string S whose suffix tree has the same topological structure ...
Comments