License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.17
URN: urn:nbn:de:0030-drops-73215
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7321/
Go to the corresponding LIPIcs Volume Portal

Policriti, Alberto ; Prezza, Nicola

From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back

pdf-format:
LIPIcs-CPM-2017-17.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{policriti_et_al:LIPIcs:2017:7321,
  author =	{Alberto Policriti and Nicola Prezza},
  title =	{{From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7321},
  URN =		{urn:nbn:de:0030-drops-73215},
  doi =		{10.4230/LIPIcs.CPM.2017.17},
  annote =	{Keywords: Lempel-Ziv, Burrows-Wheeler transform, compressed computation, repetitive text collections}
}

Keywords: Lempel-Ziv, Burrows-Wheeler transform, compressed computation, repetitive text collections
Collection: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 30.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI