Competitive file compression

Motivation

The compression task was one of the projects I enjoyed most during my degree because it combined algorithms, low-level data representation, experimentation and competition.

The assignment provided three published test files: rogets_thesaurus.txt, count_monti_cristo.txt and ecoli.fasta. Submissions were also evaluated against a hidden file and the combined result determined our position on a live leaderboard containing roughly 700 students.

That competitive feedback changed how I approached the project. Producing a valid compressor was only the first milestone. Every new result gave me a reason to revisit the algorithm, challenge an earlier assumption and search for another improvement.

Developing the Algorithm

My first attempt combined LZ77-style back-references with Huffman coding. The design quickly became difficult to reason about, particularly around representing matches and storing the Huffman codebook, so I discarded much of it and restarted with a simpler format.

The rebuilt version represented either a literal byte or a repeated sequence pointing back into previously decoded data. This gave me a working compressor and decompressor early in the process. I also added a recovery check that decompressed every result and compared its MD5 checksum with the original file, allowing me to experiment without silently producing invalid output.

The first working implementation searched every possible position inside a sliding window. It was correct, but the search became increasingly expensive as I increased the window size. I replaced that exhaustive search with a prefix index that mapped short byte sequences to the positions where they had previously appeared. The compressor could then evaluate only positions beginning with the same prefix as the current input.

That change made larger search windows practical. I expanded the window from hundreds of bytes to more than 100,000 while continuing to tune the prefix length and maximum match size. A longer prefix reduced the number of candidates that needed to be checked, but could miss shorter useful repetitions. A larger window could find distant matches, but required more bits whenever a distance was encoded.

The largest redesign introduced canonical Huffman coding. The LZ77 stage first produced a sequence of literal and match-length symbols, then assigned shorter codes to the symbols that appeared most frequently. Match distances remained fixed-width values following their corresponding length symbols. Because the codes were canonical, the decompressor could reconstruct the codebook from each symbol and its code length rather than storing the complete tree.

Once the format was working, I focused on implementation overhead. Repeatedly appending individual bits through the supplied bit-vector abstraction made large experiments slow, so I replaced that path with an integer buffer that shifted codes into place and flushed them into a bytearray in larger blocks.

The final stage was repeated measurement and tuning. I adjusted the prefix size, search window, maximum match length and field widths against all three published files, then checked whether the combined result improved. Several late commits were specifically aimed at recovering leaderboard positions after another student moved ahead of me.

What I Learned

The most important lesson was that compression performance depends on the interaction between every part of the format.

A larger search window may find longer repetitions, but it also increases the number of bits needed to encode every distance. A longer prefix makes match searching faster, but narrows the set of candidates. A more expressive codebook can reduce the encoded data while adding metadata to the beginning of every file.

The biggest improvements did not come from continuing to polish my first design. They came from recognizing when an approach had reached its limit and being willing to replace it. I restarted the initial implementation, introduced an indexed search strategy, redesigned the encoding around canonical Huffman codes and changed the bit-packing implementation when it became a bottleneck.

The live leaderboard made those trade-offs immediately visible. An idea that appeared theoretically better could still reduce my score when tested against varied data. Reaching second place taught me to treat optimization as an iterative process of forming a hypothesis, measuring it honestly and refining the complete system rather than one isolated component.