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.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.
