## 1 Introduction and Related Work
_Compressed full-text indexes_ use data compression techniques to produce less space-demanding data structures [21]. It turns out that data compression algorithms exploit the internal structure of a string much in the same way indexes do, and therefore it is possible to build a compressed index that takes space proportional to that of the compressed text, offers indexed searching, and replaces the text as it can reproduce any text substring (in which case they are called _self-indexes_). The size of those indexes is measured in terms of the empirical text entropy, \(H_{k}\)[22], which gives a lower bound on the number of bits per symbol achievable by a \(k\)-th order compressor. There are two main families of self-indexes [21]. One is based on Ziv-Lempel compression [23; 24; 25; 26; 27; 28], and the other simulates suffix trees and suffix arrays [24; 29; 30; 31; 32; 33; 34; 35]. Compressed indexes usually require more operations than their classical counterpart, yet they can operate on a smaller/faster memory in the hierarchy. This is particularly noticeable when they can fit in RAM while the classical indexes must operate on disk. In this case their advantages are most striking. A recent survey covers the practical state of the art in compressed self-indexes [36]. Despite their great success, self-indexes have been mainly used for exact searching. Only very recently some indexes taking \(O(u)\) or \(O(u\sqrt{\log u})\)_bits_ have appeared [8; 37; 38]. Those are specifically designed for ASM, focus on worst case, and unfortunately require time exponential in \(k\)[5]. Instead, in this paper we are interested in carrying out ASM over existing compressed full-text self-indexes, and in achieving good practical performance. We start by implementing the exact-match filtration approach over compressed self-indexes. This is the most direct solution because these indexes already provide exact searching. We choose a Ziv-Lempel self-index [25], as this type of index is fast to extract the text areas to be verified, and we optimize the process of extracting those text passages. We also try a suffix-array self-index [24] as these permit efficiently counting the number of occurrences, which allows us to optimize the pattern partitioning. Then we turn our attention to hybrid indexing, which has been very successful on classical indexes. We show how the ideas of hybrid indexing over \(q\)-sample indexes [19] can be carried over Ziv-Lempel indexes, by regarding the text parsing as an irregular variant of the \(q\)-sampling. We obtain novel results about \(q\)-sample indexes that may find applications beyond compressed indexes. Finally, we focus on suffix-tree-based self-indexes. Any ASM algorithm over suffix trees can be adapted to work over compressed ones. However, some adjustments are necessary because accessing the text in a self-index is around two orders of magnitude slower than in plain form. To address this problem we study the hierarchical verification technique [17; 39] and show that it can benefit from _bidirectionality_, that is, by extending edit distance computation from both ends of the string. This is particularly relevant on this type of self-indexes, as they permit moving in the text in either direction. This second index is slower than the Lempel-Ziv-based one, but it takes significantly less space. Both hybrid indexing techniques improve upon the results obtained with the exact-matching approach. The paper has the following structure. In Section 2. we review some basic concepts about ASM, define some notation, and describe our contributions. Section 3. describes our application of exact-matching filters for ASM over self-indexes. Sections 4. and 5. are dedicated to hybrid ASM over Lempel-Ziv compressed indexes. In Section 4. we explain our approach over a general \(q\)-samples index, but we assume the size of the samples is fixed. In Section 5. we tackle the problem of an irregular parsing. Section 6. is dedicated to our second hybrid approach, _i.e._ ASM over compressed suffix trees.