@inproceedings{a601944f492449efbdfd0de6b2c4fd86,
title = "From LZ77 to the run-length encoded burrows-wheeler transform, and back",
abstract = "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.",
keywords = "Burrows-Wheeler transform, Compressed computation, Lempel-Ziv, Repetitive text collections",
author = "Alberto Policriti and Nicola Prezza",
year = "2017",
doi = "10.4230/LIPIcs.CPM.2017.17",
language = "English",
volume = "78",
series = "Leibniz International Proceedings in Informatics",
publisher = "Schlo{\ss} Dagstuhl",
editor = "K. Juha and Jakub Radozewski and Wojciech Rytter",
booktitle = "Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching",
note = "28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017 ; Conference date: 04-07-2017 Through 06-07-2017",
}