Adaptive Source Coding
Stefan Höt · 2019
This chapter considers algorithms that can perform compression for sources when the statistics is unknown. These types of algorithms are often called universal source coding algorithms. In many cases when the source statistics is unknown, it is possible to use adaptive versions of the source coding algorithms. The chapter describes an adaptive, or dynamic, version of Huffman coding where the statistics for the current symbol is estimated from the past symbols of the sequence. The idea of the Lempel-Ziv algorithm is to use the latest part of the previous letters from the source sequence as a dictionary and use as a codeword for the position and length of the repetition. In GZIP, the deflate algorithm is wrapped in a header, with information like time and file system, and a tailing cyclic redundancy check (CRC). The ZIP format is a bit more general and can be a container for multiple files.