## 5 Using a Lempel-Ziv Self-Index
### Handling Different Lengths  
As explained, the main idea is to use the phrases instead of \(q\)-samples. For this sake Lemma 2 solves the problem of distributing the errors homogeneously across phrases. However, other problems arise especially for long phrases. For example, an occurrence could be completely inside a phrase. In general, backtracking over long phrases is too costly. Even when an occurrence is not completely contained inside a phrase, it is not viable to start searching for an occurrence with too many errors, even if the occurrence is long. This is essentially the argument in favor of filtration and hybrid indexes. Consider our example with \(k=9\), \(A=A_{1}.A_{2}.A_{3}\), \(A_{1}=ab\), \(A_{2}=cdefghijklm\), \(A_{3}=no\), \(k_{1}=k_{3}=0.7\), \(k_{2}=7.7\) and \(B=axbcxdxexfgxhizjkxlxmnxo\). Recall also that we consider \(P=B\) and \(O=A\). It is not viable to search for all the samples \(A^{\prime}\) such that \(ed(A^{\prime},cdxexfgxhizjkxlxm)\leq 7\), by using backtracking. The problem is essentially that, in this way, we allow for all the seven errors to concentrate in the beginning of \(A^{\prime}\), _i.e._ we have to potentially consider for \(\sigma^{7}\) strings. Only a very small fraction of these strings will end up extending to a sample \(A^{\prime}\) that verifies \(ed(A^{\prime},cdxexfgxhizjkxlxm)\leq 7\). To avoid this problem we adopt a hybrid approach. We resort again to \(q\)-samples, this time within phrases. We choose two non-negative integer parameters \(q\) and \(s<q\). We will look for any \(q\)-gram of \(P\) that appears with less than \(s\) errors within any phrase. All phrases spotted along this process must be verified. Still, some phrases not containing any pattern \(q\)-gram with \(<s\) errors can participate in an occurrence of \(P\) (_e.g.,_ if \(\lfloor(m-k-q+1)/q\rfloor\cdot s\leq k\) or if the phrase is shorter than \(q\)). Next we show that those remaining phrases have a certain structure that makes them easy to find. **Lemma 4**: _Let A and B be strings and \(q\) and \(s\) be integers such that \(0\leq s<q\leq|A|\) and for any substrings \(B^{\prime}\) of \(B\) and \(A^{\prime}\) of \(A\) with \(|A^{\prime}|=q\) we have that \(ed(A^{\prime},B^{\prime})\geq s\). Then for every prefix \(A^{\prime}\) of \(A\) there is a substring \(B^{\prime}\) of \(B\) such that \(ed(A^{\prime},B^{\prime})\leq ed(A,B)-s\lfloor(|A|-|A^{\prime}|)/q\rfloor\)._  
This is an application of Lemma 2 and it is important because it gives a good description of the restrictions obtained by the filtration. Apply Lemma 2 with \(A_{1}=A^{\prime}\), \(|A_{j}|<q\) and the remaining \(A_{i}\)'s of size \(q\), _i.e._\(|A_{i}|=q\). Consider \(k_{1}=ed(A,B)-s\lfloor(|A|-|A^{\prime}|)/q\rfloor+\epsilon\) with \(0<\epsilon<1\), \(k_{j}=0\). The remaining \(k_{i}\)'s are equal to \(s\). Note that \(j=\lfloor(|A|-|A^{\prime}|)/q\rfloor+1\) and therefore \(\sum_{i=1}^{j}k_{i}=ed(A,B)+\epsilon-s\lfloor(|A|-|A^{\prime}|)/q\rfloor+s(j-1 )=ed(A,B)+\epsilon-s\lfloor(|A|-|A^{\prime}|)/q\rfloor+s\lfloor(|A|-|A^{ \prime}|)/q\rfloor=ed(A,B)+\epsilon>ed(A,B)\). Therefore we conclude that there is a substring \(B^{\prime}\) of \(B\) and an \(i\) such that \(ed(A_{i},B^{\prime})<k_{i}\). We will prove that it must be \(i=1\). If \(i=j\), then \(ed(A_{j},B^{\prime})<k_{j}=0\), which is impossible. If \(1<i<j\), then \(ed(A_{i},B^{\prime})<k_{i}=s\) with \(|A_{i}|=q\), which contradicts the hypotheses of the lemma. Therefore \(i=1\) and \(ed(A_{1},B^{\prime})=ed(A^{\prime},B^{\prime})<k_{1}=ed(A,B)-s\lfloor(|A|-|A^{ \prime}|)/q\rfloor+\epsilon\), which means that \(ed(A^{\prime},B^{\prime})\leq ed(A,B)-s\lfloor(|A|-|A^{\prime}|)/q\rfloor\). The lemma implies that, if a phrase is close to a substring of \(P\), but none of its \(q\)-grams are sufficiently close to any substring of \(P\), then the errors must be distributed uniformly along the phrase. Therefore we can check the phrase progressively (for increasing prefixes), so that the number of errors permitted grows slowly.