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.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Autor
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
Titel des Konferenzbandes
Algorithm Engineering. 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings
Band
1668
Seite
30-42
Konferenz
3rd International Workshop, WAE’99
Konferenzort
London, UK
Konferenzdatum
1999-07-19 – 1999-07-21
ISSN
PUB-ID

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. doi:10.1007/3-540-48318-7_5
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.