Name
Title | ||
|---|---|---|
Linearized Suffix Tree: an Efficient Index Data Structure with the Capabilities of Suffix Trees and Suffix Arrays |
Abstract | ||
|---|---|---|
Suffix trees and suffix arrays are fundamental full-text index data structures to solve problems occurring in string processing.
Since suffix trees and suffix arrays have different capabilities, some problems are solved more efficiently using suffix trees
and others are solved more efficiently using suffix arrays. We consider efficient index data structures with the capabilities
of both suffix trees and suffix arrays without requiring much space. When the size of an alphabet is small, enhanced suffix
arrays are such index data structures. However, when the size of an alphabet is large, enhanced suffix arrays lose the power
of suffix trees. Pattern searching in an enhanced suffix array takes O(m|Σ|) time while pattern searching in a suffix tree takes O(mlog |Σ|) time where m is the length of a pattern and Σ is an alphabet.
In this paper, we present linearized suffix trees which are efficient index data structures with the capabilities of both suffix trees and suffix arrays even when the size
of an alphabet is large. A linearized suffix tree has all the functionalities of the enhanced suffix array and supports the
pattern search in O(mlog |Σ|) time. In a different point of view, it can be considered a practical implementation of the suffix tree supporting
O(mlog |Σ|)-time pattern search.
In addition, we also present two efficient algorithms for computing suffix links on the enhanced suffix array and the linearized
suffix tree. These are the first algorithms that run in O(n) time without using the range minima query. Our experimental results show that our algorithms are faster than the previous
algorithms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00453-007-9061-2 | Algorithmica |
Keywords | Field | DocType |
Suffix trees,Suffix arrays,Index data structures,String algorithms | Data structure,Discrete mathematics,Suffix,String processing,Suffix tree,Mathematics | Journal |
Volume | Issue | ISSN |
52 | 3 | 0178-4617 |
Citations | PageRank | References |
5 | 0.47 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dong Kyue Kim | 1 | 226 | 22.59 |
| Minhwan Kim | 2 | 23 | 5.83 |
| Heejin Park | 3 | 235 | 21.63 |