## 2 Basics and Contribution Overview
### Our Contributions  
Reducing to exact matching of pattern pieces.One can use _any_ compressed self-index to implement a filtration ASM method that relies on looking for exact occurrences of pattern substrings, as this is what all self-indexes provide. This is our approach in Section 3.. We first use a Lempel-Ziv index [25]. The Lempel-Ziv index works well because it is faster to extract the text to verify (recall that in self-indexes the text is not directly available). The specific structure of the Lempel-Ziv index used allows several interesting optimizations, such as factoring out the work of several text extractions. This is possible only when the occurrences span a single Ziv-Lempel phrase. We also use a compressed suffix array [24], as it permits fast counting of the number of occurrences of any substring. This allows us to quickly find the best partition \(A=A_{1}.A_{2}\ldots A_{k+1}\) so that the number of text verifications is minimized. Hybrid indexing on Ziv-Lempel indexes.In Sections 4. and 5. we turn our attention to hybrid indexing, which is more complex but promises handling higher error levels \(\alpha\) more efficiently. We still stick to a Ziv-Lempel index, as it allows fast extracting of text contexts. Considering the complications of Ziv-Lempel indexes when occurrences span more than one phrase, we pay special attention to this problem. A good choice to handle this turns out to be another Ziv-Lempel index [28], whose suffix-tree-like structure is useful for this approximate searching. Mimicking \(q\)-sample indexes is particularly useful for our goals. A Lempel-Ziv parsing can be regarded as an irregular sampling of the text, and therefore our goal, in principle, is to adapt the techniques of the approximate \(q\)-samples index [19] to an irregular parsing (thus we must stick to the interpretation \(B=P\), recall Section 2.2.). As desired, we would not need to consider occurrences spanning more than one phrase. Moreover, the trie of phrases stored by all Lempel-Ziv self-indexes is the exact analogous of the trie of \(q\)-samples. Thus we can search without requiring further structures. The irregular parsing poses several challenges. There is no way to ensure that there will be a minimum number \(j\) of phrases contained in an occurrence. Occurrences could even be fully contained in a phrase! We develop several tools to face those challenges. (1) We give a new variant of Lemma 1 that distributes the errors in a convenient way when the samples are of varying length. (2) We introduce a new filtration technique where the samples that overlap the occurrence (not only those contained in the occurrence) can be considered. This is of interest even for classical \(q\)-sample indexes. (3) We search for \(q\)-samples within long phrases to detect occurrences even if they are within a phrase. This technique also includes novel insights. Hybrid indexing on compressed suffix trees.Finally, in Section 6. we explore the impact of _hierarchical verification_ on hybrid searching, using a compressed suffix tree instead of a Lempel-Ziv index. Hierarchical verification means that an area that needs to be verified is not immediately checked with the maximum number of errors; instead the error threshold is raised gradually. This technique was originally proposed for a hybrid index [17] and later extended and used for a sequential algorithm [39]. However, these approaches used hierarchical verification directly over the text \(T\), meaning that none of the repeated computation was factorized. We investigate precisely how to do this computation over the index, thus allowing us to avoid repeated computation. A key ingredient to achieve our goal is _bidirectionality_, that is, the ability of extending the distance computation to the left or to the right of the matched part. Algorithms for computing edit distance are typically unidirectional, computing from left to right, because they are based on dynamic programming or automata. Interestingly this computation was made bidirectional more than 10 years ago [48].