In this paper, we show that the LZ77 factorization of a text T ∈ Σn can be computed in O(R log n) bits of working space and O(n log R) time, R being the number of runs in the Burrows-Wheeler transform of T (reversed). For (extremely) repetitive inputs, the working space can be as low as O(log n) bits: exponentially smaller than the text itself. Hence, our result finds important applications in the construction of repetition-aware self-indexes and in the compression of repetitive text collections within small working space.

Computing LZ77 in Run-Compressed Space

POLICRITI, Alberto;PREZZA, Nicola
2016-01-01

Abstract

In this paper, we show that the LZ77 factorization of a text T ∈ Σn can be computed in O(R log n) bits of working space and O(n log R) time, R being the number of runs in the Burrows-Wheeler transform of T (reversed). For (extremely) repetitive inputs, the working space can be as low as O(log n) bits: exponentially smaller than the text itself. Hence, our result finds important applications in the construction of repetition-aware self-indexes and in the compression of repetitive text collections within small working space.
2016
978-1-5090-1853-6
978-1-5090-1853-6
File in questo prodotto:
File Dimensione Formato  
rle-lz77.pdf

accesso aperto

Descrizione: Pre-print articolo
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 250.33 kB
Formato Adobe PDF
250.33 kB Adobe PDF Visualizza/Apri
conference-proceeding.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 303.14 kB
Formato Adobe PDF
303.14 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1098488
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 5
social impact