Efficient implementation of lazy suffix trees

Giegerich R, Kurtz S, Stoye J (1999)
In: Proc. of WAE 1999. LNCS, 1668. 30-42.

Conference Paper | Published | English

No fulltext has been uploaded

Author
Abstract
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.
Publishing Year
Conference
WAE 1999
Location
London, UK
ISSN
PUB-ID

Cite this

Giegerich R, Kurtz S, Stoye J. Efficient implementation of lazy suffix trees. In: Proc. of WAE 1999. LNCS. Vol 1668. 1999: 30-42.
Giegerich, R., Kurtz, S., & Stoye, J. (1999). Efficient implementation of lazy suffix trees. Proc. of WAE 1999, 1668, 30-42.
Giegerich, R., Kurtz, S., and Stoye, J. (1999). “Efficient implementation of lazy suffix trees” in Proc. of WAE 1999 LNCS, vol. 1668, 30-42.
Giegerich, R., Kurtz, S., & Stoye, J., 1999. Efficient implementation of lazy suffix trees. In Proc. of WAE 1999. LNCS. no.1668 pp. 30-42.
R. Giegerich, S. Kurtz, and J. Stoye, “Efficient implementation of lazy suffix trees”, Proc. of WAE 1999, LNCS, vol. 1668, 1999, pp.30-42.
Giegerich, R., Kurtz, S., Stoye, J.: Efficient implementation of lazy suffix trees. Proc. of WAE 1999. LNCS. 1668, p. 30-42. (1999).
Giegerich, Robert, Kurtz, Stefan, and Stoye, Jens. “Efficient implementation of lazy suffix trees”. Proc. of WAE 1999. 1999.Vol. 1668. LNCS. 30-42.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar