论文标题
空间有效的RLZ-TO-LZ77转换
Space-efficient RLZ-to-LZ77 conversion
论文作者
论文摘要
考虑一个文本$ t [1..n] $由参考序列$ r = t [1 .. \ ell] $前缀。我们展示了如何给定$ r $和$ z'$ - 短语相对Lempel-Ziv parse $ t [\ ell + 1..n] $的$ t [\ ell + 1..n] $，对于$ r $，我们可以构建$ n \，\ mathrm {polylog}（polylog}（polylog}（n）$ o（n）$ o（n）$ o（n）$ o（n）$ o（$ o（el）$ o（el e el + z'），我们可以构建$ t $ $ t $的lz77 parse。
Consider a text $T [1..n]$ prefixed by a reference sequence $R = T [1..\ell]$. We show how, given $R$ and the $z'$-phrase relative Lempel-Ziv parse of $T [\ell + 1..n]$ with respect to $R$, we can build the LZ77 parse of $T$ in $n\,\mathrm{polylog} (n)$ time and $O (\ell + z')$ total space.
