TY - JOUR

T1 - Suffix Trays and Suffix Trists

T2 - Structures for Faster Text Indexing

AU - Cole, Richard

AU - Kopelowitz, Tsvi

AU - Lewenstein, Moshe

N1 - Funding Information:
Cole’s work was supported in part by NSF grant CCF-1217989. Lewenstein’s research was supported by a BSF grant (#2010437) and a GIF grant (#1147/2011).
Publisher Copyright:
© 2014, Springer Science+Business Media New York.

PY - 2015/6/1

Y1 - 2015/6/1

N2 - Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially sized alphabets. However, when it comes to answering queries with worst-case deterministic time bounds, the prior does so in O(mlog|Σ|) time, where m is the query size, |Σ| is the alphabet size, and the latter does so in O(m+logn) time, where n is the text size. If one wants to output all appearances of the query, an additive cost of O(occ) time is sufficient, where occ is the size of the output. Notice that it is possible to obtain a worst case, deterministic query time of O(m) but at the cost of super-linear construction time or space usage.We propose a novel way of combining the two into, what we call, a suffix tray. The space and construction time remain linear and the query time improves to O(m+log|Σ|) for integer alphabets from a linear range, i.e. Σ⊂{1,…,cn}, for an arbitrary constant c. The construction and query are deterministic. Here also an additive O(occ) time is sufficient if one desires to output all appearances of the query.We also consider the online version of indexing, where the text arrives online, one character at a time, and indexing queries are answered in tandem. In this variant we create a cross between a suffix tree and a suffix list (a dynamic variant of suffix array) to be called a suffix trist; it supports queries in O(m+log|Σ|) time. The suffix trist also uses linear space. Furthermore, if there exists an online construction for a linear-space suffix tree such that the cost of adding a character is worst-case deterministic f(n,|Σ|) (n is the size of the current text), then one can further update the suffix trist in O(f(n,|Σ|)+log|Σ|) time. The best currently known worst-case deterministic bound for f(n,|Σ|) is O(logn) time.

AB - Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially sized alphabets. However, when it comes to answering queries with worst-case deterministic time bounds, the prior does so in O(mlog|Σ|) time, where m is the query size, |Σ| is the alphabet size, and the latter does so in O(m+logn) time, where n is the text size. If one wants to output all appearances of the query, an additive cost of O(occ) time is sufficient, where occ is the size of the output. Notice that it is possible to obtain a worst case, deterministic query time of O(m) but at the cost of super-linear construction time or space usage.We propose a novel way of combining the two into, what we call, a suffix tray. The space and construction time remain linear and the query time improves to O(m+log|Σ|) for integer alphabets from a linear range, i.e. Σ⊂{1,…,cn}, for an arbitrary constant c. The construction and query are deterministic. Here also an additive O(occ) time is sufficient if one desires to output all appearances of the query.We also consider the online version of indexing, where the text arrives online, one character at a time, and indexing queries are answered in tandem. In this variant we create a cross between a suffix tree and a suffix list (a dynamic variant of suffix array) to be called a suffix trist; it supports queries in O(m+log|Σ|) time. The suffix trist also uses linear space. Furthermore, if there exists an online construction for a linear-space suffix tree such that the cost of adding a character is worst-case deterministic f(n,|Σ|) (n is the size of the current text), then one can further update the suffix trist in O(f(n,|Σ|)+log|Σ|) time. The best currently known worst-case deterministic bound for f(n,|Σ|) is O(logn) time.

KW - Data structures

KW - Indexing

KW - Pattern matching

UR - http://www.scopus.com/inward/record.url?scp=84929061223&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84929061223&partnerID=8YFLogxK

U2 - 10.1007/s00453-013-9860-6

DO - 10.1007/s00453-013-9860-6

M3 - Article

AN - SCOPUS:84929061223

SN - 0178-4617

VL - 72

SP - 450

EP - 466

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -