A Space-Economical Suffix Tree Construction Algorithm

Journal of the ACM - Tập 23 Số 2 - Trang 262-272 - 1976
Edward M. McCreight1
1XEROX Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA

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

10.1145/360980.360995

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

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 23 Số 2

262-272

Thông tin tác giả