Space-efficient conversions from SLPs

Abstract

We give algorithms that, given a straight-line program (SLP) with $g$ rules that generates (only) a text $T[\mathrm{1..}n]$, builds within $O(g)$ space the Lempel-Ziv (LZ) parse of $T$ (of $z$ phrases) in time $O(n{\log }^{2}n)$ or in time $O(gz{\log }^2(n/z))$. We also show how to build a locally consistent grammar (LCG) of optimal size $g_{lc}=O(\delta \log \frac{n}{\delta })$ from the SLP within $O(g+g_{lc})$ space and in $O(n\log g)$ time, where $\delta$ is the substring complexity measure of $T$. Finally, we show how to build the LZ parse of $T$ from such a LCG within $O(g_{lc})$ space and in time $O(z{\log }^{2}n{\log }^2(n/z))$. All our results hold with high probability.