View publication
| Title | Improved Grammar-Based Compressed Indexes |
| Authors | Francisco Claude, Gonzalo Navarro |
| Publication date | 2012 |
| Abstract | We introduce the first grammar-compressed representation of a sequence that supports searches in time that depends only logarithmically on the size of the grammar. Given a text T[1..u] that is represented by a (context-free) grammar of n (terminal and nonterminal) symbols and size N (measured as the sum of the lengths of the right hands of the rules), a basic grammar-based representation of T takes N lg n bits of space. Our representation requires 2N lg n + N lg u + eps n lg n + o(N lg n) bits of space, for any 0<eps<=1. It can find the positions of the occ occurrences of a pattern of length m in T in O((m^2/eps) lg (lg u / lg n) + (m+occ) lg n) time, and extract any substring of length l of T in time O(l+h lg(N/h)), where h is the height of the grammar tree. |
| Downloaded | 6 times |
| Pages | 180-192 |
| Conference name | International Symposium on String Processing and Information Retrieval |
| Publisher | Springer-Verlag (Berlin/Heidelberg, Germany) |
|
|
| Reference URL |
|