Random Access to Grammar Compressed Strings

Philip Bille, Gad M. Landau, Rajeev Raman +3

Grammar based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular…