TY - GEN
T1 - Space-conscious compression
AU - Gagie, Travis
AU - Manzini, Giovanni
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/38049057885
U2 - 10.1007/978-3-540-74456-6_20
DO - 10.1007/978-3-540-74456-6_20
M3 - Conference contribution
AN - SCOPUS:38049057885
SN - 9783540744559
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 206
EP - 217
BT - Mathematical Foundations of Computer Science 2007 - 32nd International Symposium, MFCS 2007, Proceedings
PB - Springer Verlag
T2 - 32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007
Y2 - 26 August 2007 through 31 August 2007
ER -