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
Einrichtung
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, Robert, and Kurtz, Stefan. 1997. “From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction”. ALGORITHMICA 19 (3): 331-353.
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
Web of Science
Dieser Datensatz im Web of Science®Suchen in
Google Scholar