## 1 Introduction and Related Work  
Approximate string matching (ASM) is an important problem that arises in applications related to text searching, pattern recognition, signal processing, and computational biology, to name a few. The problem consists in locating all the occurrences \(O\) of a given pattern string \(P\), of size \(m\), in a larger text string \(T\), of size \(u\), where the distance between \(P\) and \(O\) is less than a given threshold \(k\). We focus on the edit distance, that is, the minimum number of character insertions, deletions, and substitutions of single characters to convert one string into the other. The classical sequential search solution runs in \(O(um)\) worst-case time (see [1]). An optimal average-case algorithm requires \(O(u(k+\log_{\sigma}m)/m)\) time [2; 3], where \(\sigma\) is the size of the alphabet \(\Sigma\). Those good average-case algorithms are called _filtration_ algorithms: they traverse the text fast while checking for a simple necessary condition, and only when this condition holds do they verify the text area using a classical ASM algorithm. For long texts, however, sequential searching might be impractical as it must scan all the text. To avoid the scanning we use an _index_[4; 5], which is a data structure built on the text. There exist indexes specifically devoted to ASM [6; 7; 8; 9] (see [5] for an overview). Most are oriented to worst-case performance, and experiment a space-time barrier: They require either exponential time (in \(m\) or \(k\)), or exponential index space (_e.g.,_\(O(u\log^{k}u)\) integers). This renders them impractical in many applications. Another choice is to reuse an index designed for exact searching, all of which are linear-space (_i.e._\(O(u)\) integers), and try to do ASM over it. Indexes such as suffix trees [10], suffix arrays [11], or based on so-called \(q\)-grams or \(q\)-samples [4], have been used for ASM. There exist several algorithms, based on suffix trees or arrays, which focus on worst-case performance [12; 13; 14]. They suffer from the same space-time barrier, achieving a search time independent of \(u\) but exponential in \(m\) or \(k\). Essentially, they backtrack on the suffix tree or array, simulating the sequential search over all the text suffixes, and take advantage of the factoring of similar substrings achieved by suffix trees or arrays. Indexes based on \(q\)-grams or \(q\)-samples are appealing because they require less space than suffix trees or arrays. The algorithms on those indexes do not offer worst-case guarantees, but perform well on average when the _error level_\(\alpha=k/m\) is low enough, say \(O(1/\log_{\sigma}u)\). Those indexes basically simulate a sequential filtration algorithm, such that the \"necessary condition\" checked involves exact matching of pattern substrings, and as such can be verified with any exact-searching index. Such filtration indexes, _e.g.,_[15; 16], cease to be useful for moderate \(\alpha\) levels that are still of interest in applications. The most successful approach, in practice, is in between backtracking and exact-matching filtration, and is called _hybrid_ indexing. The index determines the text positions to verify using an approximate-matching condition over pattern pieces. Those positions are determined using backtracking, whose time is exponential in the length of the string or the number of errors. Yet, it is applied over short pattern pieces and allowing few errors, so that the exponential cost is controlled. Indexes of this kind offer average-case guarantees of the form \(O(mn^{\lambda})\) for some \(0<\lambda<1\), and work well for higher error levels. They have been implemented over \(q\)-gram indexes [17], suffix arrays [18], and \(q\)-sample indexes [19]. Yet, many of those linear-space indexes are very large anyway. For example, suffix arrays require 4 times the text size and suffix trees require at the very least 10 times [20]. In recent years a new and extremely successful class of indexes has emerged.