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

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.
String Processing and Information Retrieval 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings
File in questo prodotto:
File Dimensione Formato  
lz77.pdf

non disponibili

Dimensione 268.23 kB
Formato Adobe PDF
268.23 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA 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/10278/3729832
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 11
social impact