Space-efficient RLZ-to-LZ77 conversion
share
Consider a text T [1..n] prefixed by a reference sequence R = T [1..ℓ]. We show how, given R and the z'-phrase relative Lempel-Ziv parse of T [ℓ + 1..n] with respect to R, we can build the LZ77 parse of T in n polylog (n) time and O (ℓ + z') total space.
READ FULL TEXT