Efficient implementation of lazy suffix trees

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

Download
OA
Journal Article | Published | English
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 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.
Publishing Year
ISSN
eISSN
PUB-ID

Cite this

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.
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.
Main File(s)
Access Level
OA Open Access

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