Contributo in atti di convegno, 2009, ENG

On the bit-complexity of Lempel-Ziv compression

Ferragina P.; Nitto I.; Venturini R.

Department of Computer Science, Università di Pisa, Pisa, Italy; Department of Computer Science, Università di Pisa, Pisa, Italy; CNR-ISTI, Pisa, Italy

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-complexity of LZ-based compressors, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space. These theoretical results will be sustained by some experiments that will compare our novel LZ-based compressors against the most popular compression tools (like gzip, bzip2) and state-of-the-art compressors (like the booster of [14, 13]).

Symposium on Discrete Algorithms, pp. 768–777, New York, 4-6 January 2009

Keywords

Analysis of Algorithms and Problem Complexity, Compression

CNR authors

Venturini Rossano

CNR institutes

ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"

ID: 91925

Year: 2009

Type: Contributo in atti di convegno

Last update: 2018-02-14 14:36:53.000

External links

OAI-PMH: Dublin Core

OAI-PMH: Mods

OAI-PMH: RDF

URL: http://www.siam.org/meetings/da09/

External IDs

CNR OAI-PMH: oai:it.cnr:prodotti:91925