Suffix Trays and Suffix Trists: Structures for Faster Text Indexing

摘要

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|I |) pound time, where m is the query size, |I | pound 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.