Space-efficient RLZ-to-LZ77 conversion

Abstract

Consider a text $T[\mathrm{1..}n]$ prefixed by a reference sequence $R=T[\mathrm{1..}\ell ]$. We show how, given $R$ and the $z^{\prime }$-phrase relative Lempel-Ziv parse of $T[\ell +\mathrm{1..}n]$ with respect to $R$, we can build the LZ77 parse of $T$ in $n\mathrm{polylog}(n)$ time and $O(\ell +z^{\prime })$ total space.