Compression is prediction

Compression and language modeling share a fundamental objective: reducing data size by identifying and leveraging patterns and redundancies. In this piece, we explore the core concepts of data compression and draw parallels with language modeling. There exist numerous methods to shrink data, ranging from minification to more advanced techniques.

Minification, for instance, eliminates unnecessary characters in code, but true compression hinges on exploiting redundancy. Consider the string "AAAAAAAAABBBBCCDAAADDDDDDDDD," which contains an abundance of repetitive characters. By encoding the string as "A9B4C2D1A3D9," we achieve a 57 percent reduction in size, going from 28 characters to 12 characters.

This is just one example of a compression technique called run-length encoding. Modern compression tools employ a trio of components: transforms, models, and entropy coders. While transforms and models deserve attention, our focus lies in entropy coders. Arithmetic coding serves as a prime illustration of how improved probabilities contribute to more efficient compression.

By representing an entire dataset with a single number, arithmetic coding can achieve remarkable compression ratios. To demonstrate, let's encode the string "ABABAAC" using arithmetic coding. First, we determine the probabilities of each symbol (character) based on their frequency in the string, yielding 0.571 for "A," 0.286 for "B," and 0.143 for "C."

Next, we divide the range from 0 to 1 into segments corresponding to each symbol's probability. As we process each symbol in the string, we progressively narrow down the range, ultimately arriving at a compact range that encodes the entire message. This compact representation requires fewer bits than the original string, exemplifying the power of arithmetic coding in data compression.