Analysis of Algorithms and Data Structures for Text Indexing
Moritz G. Maaß · 2006
Large amounts of textual data like document collections, DNA sequence data, or the Internet call for fast look-up methods that avoid searching the whole corpus. This is often accomplished using tree-based data structures for text indexing such as tries, PATRICIA trees, or suffix trees. We present and analyze improved algorithms and index data structures for exact and error-tolerant search. Affix trees are a data structure for exact indexing. They are a generalization of suffix trees, allowing a bidirectional search by extending a pattern to the left and to the right during retrieval. We present an algorithm that constructs affix trees on-line in both directions, i.e., by augmenting the underlying string in both directions. An amortized analysis yields that the algorithm has a linear-time worst-case complexity. A space efficient method for error-tolerant searching in a dictionary for a pattern allowing some mismatches can be implemented with a trie or a PATRICIA tree. For a given mismatch probability q and a given maximum of allowed mismatches d, we study the average-case complexity of the number of comparisons for searching in a trie with n strings over an alphabet of size s. Using methods from complex analysis, we derive a sublinear behavior for d s n. For constant d, we can distinguish three cases depending upon q. For example, the search complexity for the Hamming distance is s(s-1) d / (d+1)! (log s n) d+1 + O( log d n ). To enable an even more efficient search, we utilize an index of a limited d-neighborhood of the text corpus. We show how the index can be used for various search problems requiring error-tolerant look-up. An average-case analysis proves that the index size is O(n log d n) while the look-up time is optimal in the worst-case with respect to the pattern size and the number of reported occurrences. It is possible to modify the data structure so that its size is bounded in the worst-case while the bound on the look-up time becomes average-case.