Plenary lecture 7: improving dictionary based data compression by using previous knowledge and interaction
Bruno Carpentieri · AMERICAN-MATH'10 Proceedings of the 2010 American conference on Applied mathematics · 2010
Data Compression is crucial for the transmission and storage of digital data. The theoretical background of the data compression techniques is strong and well established. It dates back to the seminal work of Shannon who, more than half a century ago, gave precise limits on the performance of any lossless compression algorithm: this limit is the entropy of the source we want to compress. Today state of the art lossless compressors are efficient. While it is not possible to prove that they always achieve the entropy limit, their effective performances for specific types of data, like text or continuous images, are very close to this limit. One option we have to increase compression is to use the knowledge of similar messages from the same source that the two transmitting sides have compressed in the past and to design algorithms that efficiently compress and decompress given this previous knowledge. By doing this in the fundamental source coding theorem we can substitute entropy with conditional entropy and we have a new theoretical limit that allows for better compression. Moreover, if we assume the possibility of interaction between the compressor and the decompressor then we can exploit the previous knowledge they both have of the source. The price we might accept to pay is a very low possibility of communication errors. In this talk we review recent work that applies previous knowledge and interactive approaches to data compression and discuss this possibility.