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; PREZZA, Nicola. - (2015), pp. 13-20. ((Intervento presentato al convegno 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015 tenutosi a London, UK nel September 1-4, 2015 [10.1007/978-3-319-23826-5_2].

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.
9783319238258
BWT; Compression; Lempel-Ziv; Computer Science (all); Theoretical Computer Science
Fast online Lempel-Ziv factorization in compressed space / POLICRITI, Alberto; PREZZA, Nicola. - (2015), pp. 13-20. ((Intervento presentato al convegno 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015 tenutosi a London, UK nel September 1-4, 2015 [10.1007/978-3-319-23826-5_2].
File in questo prodotto:
File Dimensione Formato  
lz77.pdf

Solo gestori archivio

Descrizione: articolo principale
Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 268.23 kB
Formato Adobe PDF
268.23 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/11385/194097
Citazioni
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 11
social impact