View publication
| Title | Self-Indexed Text Compression using Straight-Line Programs |
| Authors | Francisco Claude, Gonzalo Navarro |
| Publication date | 2009 |
| Abstract | Straight-line programs (SLPs) offer powerful text compression by representing a text T[1,u] in terms of a restricted context-free grammar of n rules, so that T can be recovered in O(u) time. However, the problem of operating the grammar in compressed form has not been studied much. We present a grammar representation whose size is of the same order of that of a plain SLP representation, and can answer other queries apart from expanding nonterminals. This can be of independent interest. We then extend it to achieve the first grammar representation able of extracting text substrings, and of searching the text for patterns, in time o(n). We also give byproducts on representing binary relations. |
| Pages | 235-246 |
| Conference name | International Symposium on Mathematical Foundations of Computer Science |
| Publisher | Springer-Verlag (Berlin/Heidelberg, Germany) |
| Reference URL |
|