Let T be a text of length n on an alphabet Σ of size σ, and let H0 be the zero-order empirical entropy of T. We show that the LZ77 factorization of T can be computed in nH0+o(nlogσ)+O(σlogn) bits of working space with an online algorithm running in O(nlogn) time. Previous space-efficient online solutions either work in compact space and O(nlogn) time, or in succinct space and O(nlog3n) time.
Fast online Lempel-Ziv factorization in compressed space
POLICRITI, Alberto;
2015-01-01
Abstract
Let T be a text of length n on an alphabet Σ of size σ, and let H0 be the zero-order empirical entropy of T. We show that the LZ77 factorization of T can be computed in nH0+o(nlogσ)+O(σlogn) bits of working space with an online algorithm running in O(nlogn) time. Previous space-efficient online solutions either work in compact space and O(nlogn) time, or in succinct space and O(nlog3n) time.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Policriti-Prezza2015_Chapter_FastOnlineLempel-ZivFactorizat.pdf
non disponibili
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non pubblico
Dimensione
185.42 kB
Formato
Adobe PDF
|
185.42 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
lz77.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
268.23 kB
Formato
Adobe PDF
|
268.23 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
