Grammar-Compressed Indexes with Logarithmic Search Time

04/01/2020
by   Francisco Claude, et al.
0

Let a text T[1..n] be the only string generated by a context-free grammar with g (terminal and nonterminal) symbols, and of size G (measured as the sum of the lengths of the right-hand sides of the rules). Such a grammar, called a grammar-compressed representation of T, can be encoded using essentially G g bits. We introduce the first grammar-compressed index that uses O(G n) bits and can find the occ occurrences of patterns P[1..m] in time O((m^2+occ) G). We implement the index and demonstrate its practicality in comparison with the state of the art, on highly repetitive text collections.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset