ESP-index: A compressed index based on edit-sensitive parsing
We propose ESP-index, a self-index based on edit-sensitive parsing. Given a string S, ESP tree is equivalent to a CFG deriving just S, which can be represented as a restricted DAG G. Finding pattern P in S is reduced to embedding the parsing tree of P into G. Adopting several succinct data structures, G  is decomposed into two bit strings and a single array, requiring ( 1 + ? ) n log n + 4 n + o ( n ) bits of space, where n is the number of variables of G  and 0<?<1 0 < ? < 1 . The counting time for the occurrences of P in S  is in O ( ( 1 / ? ) ( m log n + occ c log m log u ) log ? u ) , where m=|P| m = | P | , u=|S| u = | S | , and occc occ c is the number of the occurrences of a maximal common subtree in ESP trees of P and S . With the additional array of n log u bits of space, our index supports the locating and extracting. Locating time is the same as counting time and extracting time for any substring of length m  is O ( ( 1 / ? ) ( m + log u ) ) .
edit-sensitive parsing self-index succinct data structure grammar-based compression