PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Ferragina P., Nitto I., Venturini R. On the bit-complexity of Lempel-Ziv compression. In: Siam Journal on Computing, vol. 42 (4) pp. 1521 - 1541. SIAM, 2013.
 
 
Abstract
(English)
One of the most famous and investigated lossless data-compression schemes is the one introduced by Lempel and Ziv about 30 years ago [38]. 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 e ffectiveness of this compression process, "we are not aware of any parsing scheme that achieves optimality [...] under any constraint on the codewords other than being of equal length" [29, 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 some issues pertaining to the bit-complexity of LZ77-based compressors, the most powerful variant of the LZ-compression scheme, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space
URL: http://epubs.siam.org/doi/abs/10.1137/120869511
DOI: 10.1137/120869511
Subject Data Compression
E.4 CODING AND INFORMATION THEORY


Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional