A Space-Economical Suffix Tree Construction Algorithm
Tóm tắt
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.
Từ khóa
Tài liệu tham khảo
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 . 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.
KIMBALL , R B . A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh , Pa. , April 1974 . KIMBALL, R B. A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh, Pa., April 1974.
KNUTH , D.E. The Art of Computer Programmzng, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass , 1973 , Ch. 6 . 3 , pp. 490 - 493 . KNUTH, D.E. The Art of Computer Programmzng, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass, 1973, Ch. 6.3, pp. 490-493.
KSUTH , D.E Pattern matching in strings. Unpub. lecture notes , Trondheim , Norway , May 1973 . KSUTH, D.E Pattern matching in strings. Unpub. lecture notes, Trondheim, Norway, May 1973.
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 . 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.
PRATT , V R . Applications of the Weiner repetition finder. Unpub. paper , Cambridge , Mass ., May 1973 ; rev Oct. 1973 PRATT, V R. Applications of the Weiner repetition finder. Unpub. paper, Cambridge, Mass., May 1973; rev Oct. 1973
WEINER , P. Linear pattern matching algorlthms . Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory , pp. 1 - 11 . 10.1109/SWAT. 1973 .13 WEINER, P. Linear pattern matching algorlthms. Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 1-11. 10.1109/SWAT.1973.13