Taking a Look at Compression Algorithms – Moncef Abboud

In case you’re curious about how coding agents work, check out this post where I explore an open-source agent internals.

You can also checkout my deep dive into how LLM inference engines like vLLM work.

Intro

I recently undertook the delusional project of writing my own implementation of a Kafka Broker: MonKafka. Deep into that rabbit hole, I fell into a different one when trying to implement compression for Kafka’s record batches. Kafka supports, as of now, four schemes: GZIP, Snappy, LZ4, and ZSTD. While proceeding with my implementation, I realized I really didn’t know that much about the fascinating topic of compression. I vaguely remembered Huffman trees and some information theory from school, but that was the extent of it. Importing packages and calling friendly APIs felt lacking. So, in the spirit of rabbit holes and indulging, I decided to take a bit of a deep dive to get a better understanding of some of these compression algorithms.

What is compression? We represent data using bytes (1 byte = 8 bits). The more bits we have, the more storage space we need and the longer the transmission time. If we can represent some data with fewer bits, we can save on both storage and time it takes to process or transmit. So compression translates to cost savings and better performance. And at scale, we are talking about millions of $.

There are two major types of compression:

• lossless, where no data is lost and the original data can be perfectly reconstructed. In this post, we’ll focus on that.
• lossy, where data is compressed in such a way that the original data cannot be fully recovered, but a close approximation is sufficient. A well-known example is JPEG, which produces an image close enough to the original, and for many cases, this level of quality is acceptable if it gives a better compression ratio.

So, how do we compress data? There are several techniques, some of which you might be familiar with or have heard of:

**Run-Length Encoding (RLE):**Consecutive identical elements are replaced with a single element and a count (e.g., “AAAAAA” becomes “6A”).**Lempel-Ziv (LZ):**This method uses back-references to previous sequences. For example,This is a nice sweet example of LZ, a nice sweet example of LZ.

becomesThis is a nice sweet example of LZ, <28, 26>.

, where <28, 26> means “go back 28 positions and copy 26 characters.” Lempel and Ziv are a big deal in the compression world and their compression scheme LZ77 (created in 1977) is the ancestor of a host of modern schemes such as DEFLATE (gzip) and Snappy.**Huffman Coding:**A variable-length encoding algorithm, where symbols have different code lengths (e.g., 10, 110, 1110, etc.), assigns shorter codes to more frequent symbols. In English, for instance,e

is the most frequent letter, andz

is one of the least frequent. To save space, we can represente

with a short code, while using a longer code forz

• which won’t be a significant penalty sincez

occurs less often.

These techniques and others are used in the different schemes with great variations in the implementations.

The various compressions schemes try to optimize three metrics: compression ratio, compression speed and decompression speed.

When I started looking into GZIP, it was confusing and frustrating, to say the least. But a lecture by Professor Bill Bird on YouTube not only allowed me to learn so much about the subject and answered all my questions, but it was also very entertaining and fun. I can’t recommend this video and his whole series on compression strongly enough. At some point in the lecture, he was explaining one of the most gnarly pieces of DEFLATE and said:

“…maybe after months and months of working on this scheme with all these bit level hacks they were getting maybe cabin fever or something and um delirium was setting in”

The ‘cabin fever’ comment had me laughing out loud. It came two hours into the intricacies of DEFLATE, and the joke hit the nail on the head!

Anyway, let’s keep going.

Gzip is a file format with a header (10 bytes), footer (8 bytes), and a payload of blocks compressed using the DEFLATE algorithm. It is one of the most famous compression formats in the world. The meat and potatoes of GZIP is DEFLATE.

The DEFLATE algorithm is also used in ZIP,DOCX (Microsoft Word), and PNG (images) files. DEFLATE is everywhere!

The DEFLATE compression algorithm combines LZ77 (technically LZSS, but the RFC refers to it as LZ77) and Huffman encoding:

LZ77: A sliding window algorithm that back-references previous sequences. For example, as mentioned above, “This is a nice sweet example of LZ, a nice sweet example of LZ!” becomes “This is a nice sweet example of LZ, <28, 26>!”, where <28, 26> means “go back 28 positions and copy 26 characters.” We saved quite a bit of characters by replacing them with just two numbers. Imagine doing this multiple times with greater lengths. That is the LZ magic!

Huffman encoding: As explained above, encodes frequent symbol with shorter sequences than less frequent ones, to save space. A simplification of its algorithm is:

• Count the frequencies of symbols.
• Build a binary tree where frequent symbols are closer to the root.
• Traverse the tree to retrieve the symbols.

We create the tree from the bottom-up, combining the least frequent nodes first, ensuring that no path to a leaf overlaps with another. Let’s take a look at an example:

1 2 3 4 5 6 7 8 9 10 11 12

In order of most to least frequent: B, A, C, D. B, the most frequent, has the shorter code, thus allowing for the maximum space saving.

/\ Symbol Code 0 1 ------ ---- / \ A 00 /\ B B 1 0 1 C 011 / \ D 010 A /
0 1 /
D C

Deflate has the following block types:

Type 0 (Uncompressed)- Used when compression provides no benefit, storing data as-is is more efficient. This can be the case for random data or already compressed data.

Type 1 (Fixed Huffman Codes)- Uses predefined, fixed Huffman codes i.e. the tree is known beforehand.

• Simpler than type 2 but doesn’t optimize for our data symbol frequencies e.g. unlike the English alphabet where e

is the most common andz

the least, our data might contain mostlyz

and a static predefined encoding would be penalizing.

Type 2 (Dynamic Huffman Codes)- Builds custom Huffman codes for each block based on symbol frequencies i.e. we account for our data symbol frequencies

• We need to compute these codes and include them in the block header, which adds overhead.

In Deflate, there are two distinct Huffman codes

• Literal and backreference length codes (those are conceptually two different alphabets but merged into a common one)
• Backreference distance codes

The following quotes from the RFC explains it rather well:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

encoded data blocks in the "deflate" format consist of sequences of symbols drawn from three conceptually distinct alphabets: either literal bytes, from the alphabet of byte values (0..255), or <length, backward distance> pairs, where the length is drawn from (3..258) and the distance is drawn from (1..32,768). In fact, the literal and length alphabets are merged into a single alphabet (0..285), where values 0..255 represent literal bytes, the value 256 indicates end-of-block, and values 257..285 represent length codes (possibly in conjunction with extra bits following the symbol code) as follows: Extra Extra Extra Code Bits Length(s) Code Bits Lengths Code Bits Length(s)

---

257 0 3 267 1 15,16 277 4 67-82 258 0 4 268 1 17,18 278 4 83-98 259 0 5 269 2 19-22 279 4 99-114 260 0 6 270 2 23-26 280 4 115-130 261 0 7 271 2 27-30 281 5 131-162 262 0 8 272 2 31-34 282 5 163-194 263 0 9 273 3 35-42 283 5 195-226 264 0 10 274 3 43-50 284 5 227-257 285 0 258 266 1 13,14 276 3 59-66 The extra bits should be interpreted as a machine in