Space-efficient conversions from SLPs
share
Given a straight-line program with g rules for a text T [1..n], we can build the z-phrase the LZ77 parse of T in O (g) space and either n polylog (n) time with high probability or O (g z log^2 n) time deterministically. We can also build a locally consistent grammar of optimal size g' = O(δlogn/δ) in O(nlog n) expected time and O(g+g') space.
READ FULL TEXT