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.
On the bit-complexity of Lempel-Ziv compression
Venturini R
2013
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
prod_277160-doc_78146.pdf
solo utenti autorizzati
Descrizione: ON THE BIT-COMPLEXITY OF LEMPEL-ZIV COMPRESSION
Tipologia:
Versione Editoriale (PDF)
Dimensione
441.91 kB
Formato
Adobe PDF
|
441.91 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
prod_277160-doc_78188.pdf
solo utenti autorizzati
Descrizione: ON THE BIT-COMPLEXITY OF LEMPEL-ZIV COMPRESSION
Tipologia:
Versione Editoriale (PDF)
Dimensione
598.81 kB
Formato
Adobe PDF
|
598.81 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.