Let's build a compressor from scratch

In today's digital age, compression is an essential tool that allows us to efficiently store and transmit data. At its core, compression involves rewriting data in a way that conveys the same information using fewer bytes. To illustrate this concept, let's consider an example involving an array of 8 booleans. Two approaches can be used to store this data: one in JSON format and another in binary format.

While both formats are equivalent, the binary representation is significantly more space-efficient, requiring only a fraction of the bytes.

To create a custom compressor, we can write a program that transforms the JSON format into the binary format. Similarly, a decompressor can be written to reverse this process, restoring the original data from the compressed version. While this compression method is specific to boolean arrays and might not seem particularly useful, there are more sophisticated algorithms that support compression of arbitrary data types.

One such algorithm is DEFLATE, which is employed by the popular gzip tool. DEFLATE applies two key techniques to compress data: Huffman coding and LZ77. Of these, Huffman coding is the more intriguing and effective method. To understand Huffman coding better, I recommend using an interactive playground where you can input text to observe how the algorithm assigns bit sequences to each byte based on their frequency. This visual demonstration can help you grasp the core idea behind Huffman encoding.

Once you've grasped the concept of compression, the process becomes relatively straightforward. The compressor you've just read about exists and is available for anyone to use. Although it may not be as effective as gzip, the simplicity of the compression method allows it to be implemented in just 580 lines of dependency-free Rust code, resulting in a surprisingly good reduction in file size.

Despite its limitations, compressing a book from 622 KB to 366 KB demonstrates the magic of compression. This post serves as a testament to the fact that, after years of struggle, the author has finally mastered the art of compression. The inspiration for this endeavor came from David MacKay, whose enthusiasm for information theory was contagious and made learning about the subject a joy.

Understanding the limitations of compression is crucial, as compressing data beyond a certain point would render it useless. This concept is elegantly explained in a video by 3blue1brown, which provides a deeper mathematical perspective on the subject. To delve further into the fascinating world of data compression, I encourage you to explore the works of David MacKay and the resources he has shared, as they offer a captivating journey into the realm of information theory.