Space-efficient RLZ-to-LZ77 conversion

11/23/2022

∙

by   Travis Gagie, et al.

∙

0

∙

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.