Space-Efficient SLP Encoding for $$O(\log N)$$-Time Random Access

Abstract A Straight-Line Program (SLP) $$\mathcal {G}$$ G for a string $$\mathcal {T}$$ T is a context-free grammar (CFG) that derives $$\mathcal {T}$$ T only, which can be considered as a compressed representation of $$\mathcal {T}$$ T . In this paper, we show how to encode $$\mathcal {G}$$ G in $$n \lceil \lg N \rceil + (n + n') \lceil \lg (n+\sigma ) \rceil + 4n - 2n' + o(n)$$ n ⌈ lg N ⌉ + ( n + n ′ ) ⌈ lg ( n + σ ) ⌉ + 4 n - 2 n ′ + o ( n ) bits to support random access queries of extracting $$\mathcal {T}[p..q]$$ T [ p . . q ] in worst-case $$O(\log N + q - p)$$ O ( log N + q - p ) time, where N is the length of $$\mathcal {T}$$ T , $$\sigma $$ σ is the alphabet size, n is the number of variables in $$\mathcal {G}$$ G and $$n' \le n$$ n ′ ≤ n is the number of symmetric centroid paths in the DAG representation for $$\mathcal {G}$$ G . The time complexity is almost optimal because Verbin and Yu [CPM 2013] proved that $$O(\log N)$$ O ( log