Space-conscious compression

Travis Gagie, Giovanni Manzini

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

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.

Lingua originaleInglese
Titolo della pubblicazione ospiteMathematical Foundations of Computer Science 2007 - 32nd International Symposium, MFCS 2007, Proceedings
EditoreSpringer Verlag
Pagine206-217
Numero di pagine12
ISBN (stampa)9783540744559
DOI
Stato di pubblicazionePubblicato - 2007
Pubblicato esternamente
Evento32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007 - Cesky Krumlov, Czech Republic
Durata: 26 ago 200731 ago 2007

Serie di pubblicazioni

NomeLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4708 LNCS
ISSN (stampa)0302-9743
ISSN (elettronico)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007
Paese/TerritorioCzech Republic
CittàCesky Krumlov
Periodo26/08/0731/08/07

Fingerprint

Entra nei temi di ricerca di 'Space-conscious compression'. Insieme formano una fingerprint unica.

Cita questo