http://www.cnr.it/ontology/cnr/individuo/prodotto/ID83618

Space-conscious compression (Contributo in atti di convegno)

Type

Label

Anno

Alternative label

[1] Manzini G., [2] Gagie T. (2007)
Space-conscious compression
in Int. Symposium on Mathematical Foundations of Computer Science (MFCS '07), Cesky Krumlov, Czech Republic, 26-31 August 2007
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Pagina inizio

Pagina fine

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#volumeInCollana

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali

Note

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

[1] CNR-IIT, Pisa, Italy; [2] Dipartimento di Informatica Università del Piemonte Orientale, Italy (literal)

Titolo

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#isbn

Abstract

Compression is most important when space is in short supply, so compression algorithms are often implemented in limited memory. Most analyses ignore memory constraints as an implementation detail, however, creating a gap between theory and practice. In this paper we consider the effect of memory limitations on compression algorithms. In the first part we assume the memory available is fixed and prove nearly tight upper and lower bounds on how much memory is needed to compress a string close to its k-th order entropy. In the second part we assume the memory available grows (slowly) as more and more characters are read. In this setting we show that the rate of growth of the available memory determines the speed at which the compression ratio approaches the entropy. In particular, we establish a relationship between the rate of growth of the sliding window in the LZ77 algorithm and its convergence rate. (literal)

Editore