TY  - JOUR
AB  - 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.
DA  - 2003
DO  - 10.1002/spe.535
KW  - space-efficient implementation
KW  - string matching
KW  - suffix tree
KW  - lazy
KW  - evaluation
LA  - eng
IS  - 11
M2  - 1035
PY  - 2003
SN  - 0038-0644
SP  - 1035-1049
T2  - SOFTWARE-PRACTICE & EXPERIENCE
TI  - Efficient implementation of lazy suffix trees
UR  - https://nbn-resolving.org/urn:nbn:de:0070-pub-16103977
Y2  - 2024-11-22T03:55:59
ER  -