In this paper we give an infinite family of strings for which the length of the Lempel-Ziv’77 parse is a factor Ω(log n/ log log n) smaller than the smallest run-length grammar.

A separation between RLSLPs and LZ77 / Bille, Philip; Gagie, Travis; Gørtz, Inge Li; Prezza, Nicola. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 50:(2018), pp. 36-39. [10.1016/j.jda.2018.09.002]

A separation between RLSLPs and LZ77

Prezza, Nicola
2018

Abstract

In this paper we give an infinite family of strings for which the length of the Lempel-Ziv’77 parse is a factor Ω(log n/ log log n) smaller than the smallest run-length grammar.
Grammar-based compression, Run-length compression SLP, RLSLP, LZ77, Thue–Morse sequence
A separation between RLSLPs and LZ77 / Bille, Philip; Gagie, Travis; Gørtz, Inge Li; Prezza, Nicola. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 50:(2018), pp. 36-39. [10.1016/j.jda.2018.09.002]
File in questo prodotto:
File Dimensione Formato  
separation.pdf

Open Access

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 96.31 kB
Formato Adobe PDF
96.31 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/192330
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 3
social impact