The Lempel-Ziv factorization (LZ77) and the Run-Length encoded Burrows-Wheeler Transform (RLBWT) are two important tools in text compression and indexing, being their sizes z and r closely related to the amount of text self-repetitiveness. In this paper we consider the problem of converting the two representations into each other within a working space proportional to the input and the output. Let n be the text length. We show that RLBWT can be converted to LZ77 in O(n log r) time and O(r) words of working space. Conversely, we provide an algorithm to convert LZ77 to RLBWT in O(n(log r + log z)) time and O(r+z) words of working space. Note that r and z can be constant if the text is highly repetitive, and our algorithms can operate with (up to) exponentially less space than naive solutions based on full decompression.
展开▼
机译：Lempel-Ziv分解（LZ77）和Run-Length编码的Burrows-Wheeler变换（RLBWT）是文本压缩和索引编制中的两个重要工具，它们的大小z和r与文本自重复性的数量密切相关。在本文中，我们考虑在与输入和输出成比例的工作空间内将两种表示形式相互转换的问题。令n为文字长度。我们证明，RLBWT可以在O（n log r）时间和O（r）个工作空间中转换为LZ77。相反，我们提供了一种算法，可以在O（n（log r + log z））时间和O（r + z）个工作空间字中将LZ77转换为RLBWT。请注意，如果文本是高度重复的，则r和z可以是常数，并且与基于完全解压缩的朴素解决方案相比，我们的算法可以（最大）以指数方式减少空间。
展开▼
