## 6 Hierarchical Approximate String Matching  
### Bidirectional Compressed Indexes  
Our final algorithm can be implemented over any bidirectional index. This means that, from the index point corresponding to a text substring \(T[i..j]\) we can efficiently move to that of \(T[i..j+1]\) but also to that of \(T[i-1..j]\). Although classical text indexes are not usually bidirectional, the compressed indexes that simulate suffix arrays are. For example, FM-indexes [24, 31] offer a so-called LF mapping operation, which moves from the suffix array position \(k\) such that \(A[k]=i\), to the position \(k^{\prime}\) such that \(A[k^{\prime}]=i-1\). Compressed suffix arrays [29, 30, 32], instead, offer function \(\psi\), which moves to a \(k^{\prime}\) such that \(A[k^{\prime}]=i+1\), thus \(\psi\) is the inverse of LF. Both kinds of compressed indexes can implement the inverse of their basic functionality, and hence are bidirectional (see [53] for the case of LF). The existing compressed suffix trees [33, 34, 35] build complete suffix tree functionality on top of a compressed suffix array, and hence are bidirectional as well. To fix ideas, let us focus in the so-called _fully compressed suffix trees_ (FCSTs) [35], which build on top of an FM-index [24, 31] and require \(uH_{k}+o(u\log\sigma)\) bits, although any other combination would essentially fit. The LF mapping of FM-indexes allow FCSTs implement Weiner links [10]: \(\textsc{WeinerLink}(v,a)\), for node \(v\) and letter \(a\) gives the suffix tree node \(v^{\prime}\) with path-label \(a.v[0..]\), and it is the key to move from a \(v\) representing \(T[i..j]\) to a \(v^{\prime}\) representing \(T[i-1..j]\), that is, to bidirectionality. The other direction, that is, from \(T[i..j]\) to \(T[i..j+1]\), is supported just by moving to a child of \(v\). FCSTs support all of the usual suffix tree navigation operations, including suffix links (via \(\psi\)) and lowest common ancestors (\(\textsc{LCA}(v,v^{\prime})\)). Our algorithm will carry out a hybrid search by backtracking on the compressed suffix tree in order to find the approximate occurrences of pattern pieces, yet it will proceed in a slightly more sophisticated fashion. Instead of extending \(O^{\prime}\) only in one direction, to the right, we will use a bidirectional search. [PERSON] _et al._[48] obtained the surprising result that it is possible to compute \(ed(A,cB)\) from \(ed(A,B)\), also in time \(O(k)\). The resulting algorithm is very sophisticated and the reader should consult the original paper. For our purposes all we need are the following observations. (1) The extension is not restricted to \(B\), _i.e._ we can also extend \(ed(A,B)\) to \(ed(cA,B)\). (2) The number of errors does not have to be fixed, _i.e._ we can extend a computation with \(k\) errors to a computation on \(k+1\) errors in \(O(k+1)\) time. (3) Finally, the data structure they use are two doubly linked lists organized in a grid. This means that if we compute \(ed(A,cB)\) from \(ed(A,B)\) we can revert back to the \(ed(A,B)\) state by simply keeping a rollback log of which pointers to revert, which requires \(O(k)\) computer words (It should be possible to extend their algorithm to support this directly, but if that is not the case we can still use the rollback log idea). For our algorithm this idea suffices since the states we need to visit are always organized in a stack. Thus we never need to compute a sequence such as \(ed(A,B)\) to \(ed(A,cB)\) to \(ed(dA,cB)\) to \(ed(dA,B)\). To improve the success rate of the process described above we should start our search from an area of \(P\) that is well preserved. To limit the number of errors we divide the pattern into small pieces. We will use Lemma 2, taking \(A=P\) and \(B=O\), and dividing the errors in a homogeneous fashion, _i.e._ choosing \(k_{i}=\alpha|A_{i}|+\epsilon\), where \(\alpha=k/m\) and \(\epsilon>0\) is a number that can be as small as we want and is only used to guarantee that \(ed(A,B)<\sum_{i=0}^{j}k_{i}\).