## 6 Hierarchical Approximate String Matching
### Indexed Hierarchical Verification  
We modify the verification phase, after filtration, in two ways: (1) We will perform it over the FCST instead of over \(T\), to factor out possibly repeated computations. (2) We use hierarchical instead of direct verification, which also provides a strategy to approximate the optimal point. The idea of hierarchical verification is to gradually extend the error level instead of jumping directly to \(k\). This is obtained by iterating Lemma 2. This technique was shown to be extremely efficient for the sequential approach [52]. We use the following lemma. **Lemma 9**: _Let A and B be strings, \(A=A_{0}.A_{1}\ldots A_{j}\), for strings \(A_{i}\) and some \(j+1=2^{h}\geq 1\). Let \(k_{i}\in\mathbb{R}\) such that \(ed(A,B)<\sum_{i=0}^{j}k_{i}\). For some fixed \(0\leq i\leq j\), define \(A^{\prime}_{i^{\prime}}=A_{2^{i^{\prime}}\lfloor i/2^{i^{\prime}}\rfloor} \ldots A_{2^{i^{\prime}}(1+\lfloor i/2^{i^{\prime}}\rfloor)-1}\), for any \(0\leq i^{\prime}\leq h\), as the hierarchical upward path from \(A_{i}\) to \(A\), and define accordingly \(k^{\prime}_{i^{\prime}}=\sum_{i^{\prime}\prime=2^{i^{\prime}}\lfloor i/2^{i^{ \prime}}\rfloor}^{2^{\prime}\left(1+\lfloor i/2^{i^{\prime}}\rfloor\right)-1} k_{i^{\prime\prime}}\) as the error level corresponding to each \(A^{\prime}_{i^{\prime}}\). Then there are strings \(B_{0}\sqsubseteq...\sqsubseteq B_{h}=B\) and an \(i\) such that for any \(0\leq i^{\prime}\leq h\) we have \(ed(A^{\prime}_{i^{\prime}},B_{i^{\prime}})<k^{\prime}_{i^{\prime}}\). Moreover, for each \(i^{\prime}\), if \(A^{\prime}_{i^{\prime}}\) is a prefix(suffix) of \(A^{\prime}_{i^{\prime}+1}\) then \(B_{i^{\prime}}\) is a prefix(suffix) of \(B_{i^{\prime}+1}\)._  
* For \(i^{\prime}=h\) the lemma is trivial because \(ed(A^{\prime}_{h},B_{h})<k^{\prime}_{h}\) reduces to \(ed(A,B)<\sum_{i=1}^{j}k_{i}\). To obtain the result for \(i^{\prime}=h-1\), consider the partition of \(A\) into two strings, \(A^{left}=A_{0}...A_{2^{i^{\prime}}-1}\) and \(A^{right}=A_{2^{i^{\prime}}}...A_{2^{i^{\prime}+1}-1}\) (depending on \(i\), either \(A^{\prime}_{h-1}=A^{left}\) or \(A^{\prime}_{h-1}=A^{right}\)), and its edit distance matrix to \(B\) achieving edit distance \(ed(A,B)<\sum_{i=1}^{j}k_{i}=k^{left}+k^{right}\), for \(k^{left}=\sum_{i^{\prime}\prime=0}^{2^{i^{\prime}}-1}k_{i^{\prime\prime}}\) and \(k^{right}=\sum_{i^{\prime\prime}=2^{i^{\prime}+1}-1}^{2^{i^{\prime}+1}-1}k_{i ^{\prime\prime}}\). Then there must be a partition \(B=B^{left}.B^{right}\) such that \(ed(A^{left},B^{left})<k^{left}\) or \(ed(A^{right},B^{right})<k^{right}\). Thus \(B_{h-1}=B^{left}\) if \(A^{\prime}_{h-1}=A^{left}\) (note \(k_{h-1}=k^{left}\) in this case), and otherwise \(B_{h-1}=B^{right}\). To obtain the result for \(i^{\prime}=h-2\) we repeat the process from \(A^{\prime}_{h-1}\), \(B_{h-1}\), and \(k_{h-1}\). Figure 7 gives a schematic representation of Lemma 9. Consider our running example with \(k=2\) and \(P=abccba\). Instead of applying Lemma 9 we will instead iterate Lemma 2, which is actually the way we compute the partition in practice. We divide \(P=A=abc.cba\) into pieces of size \(3\) and therefore we have \(k^{\prime}_{0}=k^{\prime}_{1}=3\times(2/6)+\epsilon=1+\epsilon\), which in practice means \(1\) error per piece. Now we divide these pieces as \(ab.c.cb.a\) and we have \(k_{0}=k_{2}=2\times(2/6)+\epsilon\) and \(k_{1}=k_{3}=1\times(2/6)+\epsilon\), which means \(0\) errors for all the pieces. Notice that we can refine our method by adding \(\epsilon\) to only one \(k_{i}\), as we did in Section 2.2.. Hence we can choose \(k_{0}=k_{2}=2/3\) and \(k_{1}=1/3+\epsilon\) and \(k_{3}=1/3\) (and thus \(k^{\prime}_{0}=1+\epsilon\) and \(k^{\prime}_{1}=1\)). Notice that in our example the occurrence \(abbba\) verifies this Lemma because \(ed(ab,ab)<2/3\) and \(ed(abb,abc)<(2/3)+(1/3)+\epsilon\), where \(ab\) and \(abc\) are substrings of \(P\). This lemma is used to reduce the cost of verifying an occurrence.