## 8 Conclusions and Future Work  
In this paper we presented two algorithms for ASM in compressed space: an adaptation of the hybrid index for Lempel-Ziv compressed indexes and an hierarchical verification over FCST's.  
We started by addressing the problem of approximate matching with \(q\)-samples indexes, where we described a new approach to this problem. We then adapted our algorithm to the irregular parsing produced by Lempel-Ziv indexes. Our approach was flexible enough to be used as a hybrid index instead of an exact-searching-based filtration index. We implemented our algorithm and compared it with the simple filtration approach built over different compressed indexes, with sequential algorithms, and with a good uncompressed index.  
Our results show that our index provides a good space-time tradeoff, using a small amount of space (at best \(0.9\) times the text size, which is \(5.6\) times less than a classical index) in exchange for searching from \(6.2\) to \(33\) times slower than a classical index, for \(k=1\) to \(3\). This is better than the other compressed approaches for low error levels. This is significant since indexed approaches are most valuable, if compared to sequential approaches, when the error level is low. Therefore our work significantly improves the usability of compressed indexes for approximate matching. A crucial part of our work was our approach for the prefixes/suffixes of \(O\). This approach is in fact not essential for \(q\)-samples indexes, but it can improve previous approaches [19]. For a Lempel-Ziv index it is indeed essential.  
\begin{table}
\begin{tabular}{l|c c c c c c}  & ILZI & Hybrid & LZI & DLZI & FMIIndex & BiFMI \\ \hline English & 55 & 257 & 145 & 178 & 131 & 54 \\ DNA & 45 & 252 & 125 & 158 & 127 & 40 \\ Proteins & 105 & 366 & 217 & 228 & 165 & 63 \\ \end{tabular}
\end{table}
Table 1: Memory peaks, in Megabytes, for the different approaches when \(k=6\).  
Our ILZI implementation can be further improved since we do no secondary filtering, that is, we do not apply any sequential filter over the text context before fully verifying them. We also plan to further explore the idea of associating weights to the letters of \(O\). We will investigate the impact of assigning smaller weights to less frequent letters of \(O\). This should decrease the number of positions to verify and improve the overall performance.  
We also studied the impact of hierarchical verification in ASM. We obtained an automatic hybrid index that uses fully-compressed suffix trees. This a very important result because it is the first algorithm that approximates the performance of the hybrid index automatically and effectively in practice. Our result is also very important because FCSTs require only compressed space, _i.e._\(uH_{k}+O(n\log\sigma)\) bits. Compared with other compressed indexes, our approach was more efficient for low error levels. Although it was less efficient than the ILZI-based algorithm, it requires less space in theory and in practice. In theory, the ILZI requires \(5 uH_{k}+o(n\log\sigma)\) bits, but in practice that is closer to \(3 uH_{k}\), including the sublinear term. On the other hand, a FCST requires \(uH_{k}+o(n\log\sigma)\) bits in theory, but this becomes a bit higher in practice if we consider the sublinear term. Moreover our algorithm can be used as a subroutine in a suffix tree algorithm whereas the ILZI-based algorithm cannot.