Space-efficient SLP encoding for $O(\log N)$-time random access

A Straight-Line Program (SLP) $G$ for a string $T$ is a context-free grammar (CFG) that derives $T$ only, which can be considered as a compressed representation of $T$. In this paper, we show how to encode $G$ in $n\lceil \lg N\rceil +(n+n^{\mathrm{\prime }})\lceil \lg (n+\sigma )\rceil +4n-2n^{\mathrm{\prime }}+o(n)$ bits to support random access queries of extracting $T[p\mathrm{.}\mathrm{.}q]$ in worst-case $O(\log N+q-p)$ time, where $N$ is the length of $T$, $\sigma$ is the alphabet size, $n$ is the number of variables in $G$ and $n^{\mathrm{\prime }}\le n$ is the number of symmetric centroid paths in the DAG representation for $G$. The time complexity is almost optimal because Verbin and Yu [CPM 2013] proved that $O(\log N)$ term cannot be significantly improved in general with $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)$-space data structures. We also present alternative encodings that achieve the same random access time with $n\lceil \lg N\rceil +n\lceil \lg (n+\sigma )\rceil +5n+n^{\mathrm{\prime }}+o(n)$ or $n\lceil \lg N\rceil +n\lceil \lg (n+\sigma )\rceil +5n-n^{\mathrm{\prime }}+\sigma +o(n+\sigma )$ bits of space.