Efficient implementation of lazy suffix trees

Giegerich R, Kurtz S, Stoye J (2003)
SOFTWARE-PRACTICE & EXPERIENCE 33(11): 1035-1049.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA
Autor*in
Abstract / Bemerkung
We present an efficient implementation of a write-only top-down construction for suffix trees. Our implementation is based on a new, space-efficient representation of suffix trees that requires only 12 bytes per input character in the worst case, and 8.5 bytes per input character on average for a collection of files of different type. We show how to efficiently implement the lazy evaluation of suffix trees such that a subtree is evaluated only when it is traversed for the first time. Our experiments show that for the problem of searching many exact patterns in a fixed input string, the lazy top-down construction is often faster and more space efficient than other methods. Copyright (C) 2003 John Wiley Sons, Ltd.
Stichworte
space-efficient implementation; string matching; suffix tree; lazy; evaluation
Erscheinungsjahr
2003
Zeitschriftentitel
SOFTWARE-PRACTICE & EXPERIENCE
Band
33
Ausgabe
11
Seite(n)
1035-1049
ISSN
0038-0644
eISSN
1097-024X
Page URI
https://pub.uni-bielefeld.de/record/1610397

Zitieren

Giegerich R, Kurtz S, Stoye J. Efficient implementation of lazy suffix trees. SOFTWARE-PRACTICE & EXPERIENCE. 2003;33(11):1035-1049.
Giegerich, R., Kurtz, S., & Stoye, J. (2003). Efficient implementation of lazy suffix trees. SOFTWARE-PRACTICE & EXPERIENCE, 33(11), 1035-1049. doi:10.1002/spe.535
Giegerich, R., Kurtz, S., and Stoye, J. (2003). Efficient implementation of lazy suffix trees. SOFTWARE-PRACTICE & EXPERIENCE 33, 1035-1049.
Giegerich, R., Kurtz, S., & Stoye, J., 2003. Efficient implementation of lazy suffix trees. SOFTWARE-PRACTICE & EXPERIENCE, 33(11), p 1035-1049.
R. Giegerich, S. Kurtz, and J. Stoye, “Efficient implementation of lazy suffix trees”, SOFTWARE-PRACTICE & EXPERIENCE, vol. 33, 2003, pp. 1035-1049.
Giegerich, R., Kurtz, S., Stoye, J.: Efficient implementation of lazy suffix trees. SOFTWARE-PRACTICE & EXPERIENCE. 33, 1035-1049 (2003).
Giegerich, Robert, Kurtz, Stefan, and Stoye, Jens. “Efficient implementation of lazy suffix trees”. SOFTWARE-PRACTICE & EXPERIENCE 33.11 (2003): 1035-1049.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T08:48:03Z
MD5 Prüfsumme
e2f7a0fb0094966b3c761f0e08df0a72