Compression is prediction

In the realm of data compression, compressors and language models share an underlying goal: to make sense of patterns within the data. The fundamental concept revolves around reducing redundancy to shrink the data. Take minification as an example, where code is stripped down to its essentials, eliminating unnecessary whitespace and comments. However, true compression goes beyond minification, focusing on exploiting the inherent redundancy present in the data.

Consider a string consisting of 9 A's, 4 B's, 2 C's, 1 D, followed by 3 more A's and 9 D's. This string contains a high degree of redundancy. A basic method to compress it is run-length encoding, which replaces the repeated characters with a single character followed by the count of its repetitions. For instance, the string becomes "A9B4C2D1A3D9," which is significantly shorter than the original. This reduction in size is achieved by representing the runs of each character, effectively condensing the data.

Modern compression tools employ a variety of techniques, often categorized into three main stages: transforms, models, and entropy coders. While transforms and models play significant roles, they are often intertwined and not used independently. Transforms prepare the data by applying preprocessing steps that make it more amenable to compression, even if they sometimes introduce redundancy.

Models, on the other hand, capture the characteristics of the data by estimating the probabilities of different symbols or units of data, such as letters, numbers, or binary code.

Entropy coders are the final component of compression algorithms. They utilize the probability estimates provided by the models to compress the data efficiently. The most notable entropy coder is arithmetic coding, which represents an entire dataset with a single number. This process involves dividing the range from 0 to 1 into segments proportional to the probabilities of each symbol and progressively narrowing down the range based on the symbols encountered in the data.

Once the final compressed number is obtained, it requires a separate probability model to facilitate the decompression process. By utilizing the same probabilities and starting from the initial range of [0, 1), the decompressor can reconstruct the original data by decoding the symbols one by one. As a result, arithmetic coding demonstrates how effective probability estimation can lead to remarkable data compression, significantly reducing the required storage space or transmission bandwidth.