On the bit-complexity of Lempel-Ziv compression (Contributo in atti di convegno)

Type
Label
  • On the bit-complexity of Lempel-Ziv compression (Contributo in atti di convegno) (literal)
Anno
  • 2009-01-01T00:00:00+01:00 (literal)
Alternative label
  • Ferragina P.; Nitto I.; Venturini R. (2009)
    On the bit-complexity of Lempel-Ziv compression
    in Symposium on Discrete Algorithms, New York
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Ferragina P.; Nitto I.; Venturini R. (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • In: SODA 2009 - Symposium on Discrete Algorithms (New York, 4-6 January 2009). Proceedings, pp. 768 - 777. ACM/SIAM, 2009. (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto
  • ABSTRACT: One of the most famous and investigated lossless data-compression schemes is the one introduced by Lempel and Ziv about 30 years ago [37]. This compression scheme is known as \"dictionary-based compressor\" and consists of squeezing an input string by replacing some of its substrings with (shorter) codewords which are actually pointers to a dictionary of phrases built as the string is processed. Surprisingly enough, although many fundamental results are nowadays known about the speed and effectiveness of this compression process (see e.g. [23, 28] and references therein), \"we are not aware of any parsing scheme that achieves optimality when the LZ77-dictionary is in use under any constraint on the codewords other than being of equal length\" [28, pag. 159]. Here optimality means to achieve the minimum number of bits in compressing each individual input string, without any assumption on its generating source. In this paper we investigate three issues pertaining to the bit-complex (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Department of Computer Science, Univ. Pisa, CNR-ISTI, Pisa (literal)
Titolo
  • On the bit-complexity of Lempel-Ziv compression (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Insieme di parole chiave di
data.CNR.it