Efficient implementation of lazy suffix trees

Giegerich R, Kurtz S, Stoye J (1999)
In: Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings. LNCS, 1668. 30-42.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
DOI
Autor*in
Giegerich, RobertUniBi; Kurtz, Stefan; Stoye, JensUniBi
Einrichtung
Technische Fakultät > AG Praktische Informatik
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 which 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 not before 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.
Erscheinungsjahr
1999
Titel des Konferenzbandes
Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings
Serien- oder Zeitschriftentitel
LNCS
Band
1668
Seite(n)
30-42
Konferenz
3rd International Workshop, WAE’99
Konferenzort
London, UK
Konferenzdatum
1999-07-19 – 1999-07-21
ISSN
0302-9743
Page URI
https://pub.uni-bielefeld.de/record/1620435

Zitieren

Giegerich R, Kurtz S, Stoye J. Efficient implementation of lazy suffix trees. In: Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings. LNCS. Vol 1668. 1999: 30-42.
Giegerich, R., Kurtz, S., & Stoye, J. (1999). Efficient implementation of lazy suffix trees. Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings, LNCS, 1668, 30-42. https://doi.org/10.1007/3-540-48318-7_5
Giegerich, Robert, Kurtz, Stefan, and Stoye, Jens. 1999. “Efficient implementation of lazy suffix trees”. In Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings, 1668:30-42. LNCS.
Giegerich, R., Kurtz, S., and Stoye, J. (1999). “Efficient implementation of lazy suffix trees” in Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings LNCS, vol. 1668, 30-42.
Giegerich, R., Kurtz, S., & Stoye, J., 1999. Efficient implementation of lazy suffix trees. In Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings. LNCS. no.1668 pp. 30-42.
R. Giegerich, S. Kurtz, and J. Stoye, “Efficient implementation of lazy suffix trees”, Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings, LNCS, vol. 1668, 1999, pp.30-42.
Giegerich, R., Kurtz, S., Stoye, J.: Efficient implementation of lazy suffix trees. Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings. LNCS. 1668, p. 30-42. (1999).
Giegerich, Robert, Kurtz, Stefan, and Stoye, Jens. “Efficient implementation of lazy suffix trees”. Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings. 1999.Vol. 1668. LNCS. 30-42.
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Suchen in

Google Scholar