Premium
Efficient implementation of lazy suffix trees
Author(s) -
Giegerich R.,
Kurtz S.,
Stoye J.
Publication year - 2003
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.535
Subject(s) - generalized suffix tree , suffix tree , suffix , byte , computer science , character (mathematics) , string (physics) , tree (set theory) , representation (politics) , compressed suffix array , theoretical computer science , data structure , mathematics , programming language , combinatorics , linguistics , philosophy , geometry , politics , political science , law , mathematical physics
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 © 2003 John Wiley & Sons, Ltd.