Optimal Time Random Access to Grammar-Compressed Strings in Small Space

Patrick Hagge Cording

The random access problem for compressed strings is to build a data structure that efficiently supports accessing the character in position $i$ of a string given in compressed form…