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
No fulltext has been uploaded. References only!
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
3rd International Workshop, WAE’99
Location
London, UK
Conference Date
1999-07-19 – 1999-07-21
ISSN
PUB-ID

Cite this

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.
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