From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction

Giegerich R, Kurtz S (1997)
ALGORITHMICA 19(3): 331-353.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Giegerich, RobertUniBi; Kurtz, Stefan
Abstract / Bemerkung
We review the linear-time suffix tree constructions by Weiner, McCreight, and Ukkonen. We use the terminology of the most recent algorithm, Ukkonen's on-line construction, to explain its historic predecessors. This reveals relationships much closer than one would expect, since the three algorithms are based on rather different intuitive ideas. Moreover, it completely explains the differences between these algorithms in terms of simplicity, efficiency, and implementation complexity.
Stichworte
program transformation; on-line string matching; text processing; algorithm; suffix trees; linear-time
Erscheinungsjahr
1997
Zeitschriftentitel
ALGORITHMICA
Band
19
Ausgabe
3
Seite(n)
331-353
ISSN
0178-4617
Page URI
https://pub.uni-bielefeld.de/record/1627522

Zitieren

Giegerich R, Kurtz S. From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction. ALGORITHMICA. 1997;19(3):331-353.
Giegerich, R., & Kurtz, S. (1997). From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction. ALGORITHMICA, 19(3), 331-353. https://doi.org/10.1007/PL00009177
Giegerich, R., and Kurtz, S. (1997). From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction. ALGORITHMICA 19, 331-353.
Giegerich, R., & Kurtz, S., 1997. From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction. ALGORITHMICA, 19(3), p 331-353.
R. Giegerich and S. Kurtz, “From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction”, ALGORITHMICA, vol. 19, 1997, pp. 331-353.
Giegerich, R., Kurtz, S.: From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction. ALGORITHMICA. 19, 331-353 (1997).
Giegerich, Robert, and Kurtz, Stefan. “From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction”. ALGORITHMICA 19.3 (1997): 331-353.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar