## 5 Using a Lempel-Ziv Self-Index
### A Hybrid Lempel-Ziv Index  
The following lemma describes how we combine previous results to search using a Lempel-Ziv index. **Lemma 5**: _Let A and B be strings such that \(0<ed(A,B)\leq k\). Let \(A=A_{1}.A_{2}\ldots A_{j}\), for strings \(A_{i}\) and some \(j\geq 1\). Let \(q\), \(s\) and \(v\) be integers such that \(0\leq s<q\leq|A|\) and \(0\leq v<|A|/2\). Then there is a substring \(B^{\prime}\) of \(B\) and an \(i\) such that either:_  
1. _there is a substring_ \(A^{\prime}\) _of_ \(A_{i}\) _with_ \(|A^{\prime}|=q\) _and_ \(ed(A^{\prime},B^{\prime})<s\)_, or_
2. \(ed(A_{i},B^{\prime})<k\cdot|A_{i}|_{v}\) _in which case for any prefix_ \(A^{\prime}\) _of_ \(A_{i}\) _there exists a substring_ \(B^{\prime\prime}\) _of_ \(B^{\prime}\) _such that_ \(ed(A^{\prime},B^{\prime\prime})<k\cdot|A_{i}|_{v}-s\lfloor(|A_{i}|-|A^{\prime}| )/q\rfloor\)_._  
As we have explained, our approach first consists in applying Lemma 2 considering \(k_{i}=k\cdot|A_{i}|_{v}\) for \(0\leq i\leq j\). Observe that, by the definition of \(|A_{i}|_{v}\), we have that \(\sum_{i=1}^{j}k\cdot|A_{i}|_{v}=k(\epsilon+(|A|-2v)/(|A|-2v))=k(\epsilon+1)>k\). Now, we classify the resulting \(A_{i}\) into one of the two classes we defined before. The first class justifies the first condition of this Lemma. If the \(A_{i}\) belongs to the second class, we apply Lemma 4 with the resulting \(k_{i}\). Figure 6 shows a schematic representation of Lemma 5. As before the search runs in two phases. In the first phase we find the phrases whose text context must be verified. In the second phase we verify those text contexts for an approximate occurrence of \(P\). Lemma 5 gives the key to the first phase. We find the relevant phrases via two searches:  
**(1)** We look for any \(q\)-gram contained in a phrase which matches within \(P\) with less than \(s\) errors. We backtrack in the trie of phrases for every \(P[y_{1}..]\), descending in the trie and advancing \(y_{2}\) in \(P[y_{1},y_{2}]\) while computing the DP matrix between the current trie node and \(P[y_{1},y_{2}]\). We look for all trie nodes at depth \(q\) that match some \(P[y_{1},y_{2}]\) with less than \(s\) errors. Since every suffix of a phrase is a phrase in the ILZI, every \(q\)-gram within any phrase can be found starting from the root of the trie of phrases. All the phrases \(Z\) that descend from each \(q\)-gram trie node found must be verified (those are the phrases that start with that \(q\)-gram). We must also spot the phrases suffixed by each such \(Z\). Hence we map each phrase \(Z\) to the trie of reverse phrases and also verify all the descent of the reverse trie nodes. This covers case 1 of Lemma 5. This is precisely the case in our example, since we have that \(q=4\) and \(ed(fghi,P[9..13])=ed(fghi,fgxhi)=1<2=s\). We then determine that the phrase \(cdefghijklm\) contains the string \(fghi\) and locate the occurrence by searching the context around that phrase. **(2)** We look for any phrase \(A_{i}\) matching a portion of \(P\) with less than \(k\cdot|A_{i}|_{v}\) errors. This is done over the trie of phrases. Yet, as we go down in the trie (thus considering longer phrases), we can enforce that the number of errors found up to depth \(d\) must be less than \(k\cdot|A_{i}|_{v}-s\lfloor(|A_{i}|-d)/q\rfloor\). This covers case 2 in Lemma 5, where the equations vary according to the roles described in Section 4.3. (_i.e._ depending on \(i\)):  
**(2.1)**\(1<i<j\), in which case we are considering a phrase contained inside \(O\) that is not a prefix nor a suffix. The formula \(k\cdot|A_{i}|_{v}\) (both for the matching condition and the backtracking limit) can be bounded by \((1+\epsilon)\cdot k\cdot\min(|A_{i}|/(m-k-2v),1)\), which depends on \(|A_{i}|\). Since \(A_{i}\) may correspond to any trie node that descends from the current one, we determine _a priori_ which \(|A_{i}|\leq m-k\) maximizes the backtracking limit. We apply the backtracking for each \(P[y_{1}..]\).