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.
Policriti, Alberto; Prezza, Nicola. (2015). Fast online Lempel-Ziv factorization in compressed space. In String Processing and Information Retrieval 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings (pp. 13- 20). Springer. Isbn: 9783319238258. Doi: 10.1007/978-3-319-23826-5_2. http://springerlink.com/content/0302-9743/copyright/2005/.
Fast online Lempel-Ziv factorization in compressed space
PREZZA, Nicola
2015
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 | Dimensione | Formato | |
|---|---|---|---|
|
lz77.pdf
Solo gestori archivio
Descrizione: articolo principale
Tipologia:
Documento in Pre-print
Licenza:
DRM (Digital rights management) non definiti
Dimensione
268.23 kB
Formato
Adobe PDF
|
268.23 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
