ProjectsCompression Tool
A command-line tool that compresses a file with Huffman coding and decompresses it back to an exact copy. Building it teaches why data whose symbols appear unevenly fits in fewer bits, how a greedy algorithm builds the best prefix-free code for those counts, and how to design a binary file format that packs bits into bytes and carries everything needed to decode it.
From Coding Challenges #3 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 8 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Step 1 builds the frequency table, and every later saving comes from how uneven it is. The final check, a smaller file, only holds because text is far from random.
Covers: the frequency table as a model of the data · information content of one symbol · entropy as the lower bound · why no compressor shrinks every input · the limit of whole-bit codes
Data Compression Explained (Matt Mahoney): Information theory ↗ · Entropy (information theory) (Wikipedia) ↗ · A Mathematical Theory of Communication (Claude Shannon, 1948) ↗
Step 3 turns the tree into a code table, and step 7 can only decode the packed bits because no code is the start of another.
Covers: fixed-length versus variable-length codes · the prefix property · codes as paths to the leaves of a binary tree · the Kraft inequality · decoding by walking the tree
Prefix code (Wikipedia) ↗ · Kraft-McMillan inequality (Wikipedia) ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 5.5 Data Compression ↗
Step 2 builds this tree from the counts, and step 6 must rebuild exactly the same one from the header.
Covers: joining the two rarest trees · the priority queue and the binary heap · why the greedy choice is optimal · tie-breaking and the same tree on both sides · cost as the alphabet grows
OpenDSA: Huffman Coding Trees ↗ · Data Compression Explained (Matt Mahoney): Huffman coding ↗ · Algorithms, 4th edition (Sedgewick and Wayne): 2.4 Priority Queues ↗
Step 5 asks you to pack the codes into bytes, and step 7 has to unpack them and stop before the padding.
Covers: files hold whole bytes only · collecting bits in a buffer · the order of bits inside a byte · padding the last byte · telling padding from data
RFC 1951 (DEFLATE), section 3.1.1: Packing into bytes ↗ · Bit numbering (Wikipedia) ↗
Step 4 designs the header and step 6 reads it back. The challenge leaves the format open, so every decision here is yours.
Covers: storing the model in a header · writing a tree as a walk · where the header ends · where the data ends · magic number and version · canonical codes and header size
RFC 1952: GZIP file format specification ↗ · Canonical Huffman code (Wikipedia) ↗ · List of file signatures (Wikipedia) ↗
Step 1 asks you to count characters, which forces this choice, and step 4 has to write whichever kind of symbol you chose into the header.
Covers: a file is a sequence of bytes · text encodings such as UTF-8 · choosing the alphabet of symbols · text mode and line endings · files that aren't text
The Absolute Minimum Every Software Developer Must Know About Unicode (Joel Spolsky) ↗ · UTF-8 (Wikipedia) ↗ · Newline (Wikipedia) ↗
Step 7 ends with the round trip check, and step 2 is where the empty and one-symbol inputs first need a decision.
Covers: the round trip as a property to test · the empty file · one distinct symbol · every byte value present · inputs that grow · very long codes
What is property-based testing? (Hypothesis) ↗ · RFC 1951 (DEFLATE), section 3.2.7: Compression with dynamic Huffman codes ↗ · Data Compression Explained (Matt Mahoney): No universal compression ↗
Step 1 reads the whole input to count it, and step 5 reads it again to encode it. The challenge's introduction stresses that buffer sizes decide how fast a tool like this runs.
Covers: two passes, count then encode · reading in fixed-size blocks · memory that doesn't grow with the file · the cost of one read per byte · flushing buffered output · input that can be read only once
read(2), Linux manual page ↗ · The GNU C Library: Stream Buffering ↗ · Adaptive Huffman coding (Wikipedia) ↗
What you'll build · 8 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project and download the challenge's test data, the text of a long novel.
Works whenYour program runs and can open the test file.
Take a file name, report an error if the file can't be read, and otherwise count how many times each symbol occurs in it.
Works whenThe counts for the two letters the challenge names match its figures for the test text, and unit tests on small prepared inputs pass.
Concepts: symbol frequencies and entropy · bytes versus characters · streaming the input in two passes
Build the binary tree from the counts by joining the two lightest trees again and again until one is left.
Works whenUnit tests built from the OpenDSA examples pass: each symbol ends up at the expected depth, or at least the total of count times depth matches when ties allow another shape.
Concepts: building the tree greedily with a priority queue · the lossless round trip and its edge cases
Walk the tree to give each symbol its code, one bit for each turn left or right on the way from the root to its leaf.
Works whenThe codes agree with the OpenDSA examples, no code is the start of another, and a more frequent symbol never gets a longer code than a rarer one.
Concepts: prefix-free codes and unambiguous decoding · symbol frequencies and entropy
Decide how the user picks compress or decompress, add an option for the output file name, and start the output with a header holding what decoding needs, the tree or the counts, in a form where a reader can tell where the header ends.
Works whenViewed with a hex dump tool such as xxd, the output starts with the header exactly as you designed it, and nothing outside the header is needed to find its end.
Concepts: A self-describing file format · bytes versus characters
Replace each symbol of the input with its code, pack the bits into bytes and append them after the header.
Works whenThe output for the test text is clearly smaller than the input, and its size is the header plus the total number of code bits divided by 8, rounded up to a whole byte.
Concepts: bit packing and the last byte · streaming the input in two passes
When decompressing, read the header and rebuild the tree and the code table from it.
Works whenFor the same input, the rebuilt code table matches the one the compressor used, symbol for symbol.
Concepts: A self-describing file format · building the tree greedily with a priority queue
Read the packed bits after the header, decode them with the tree, stop at the real end of the data, and write the result to the output file.
Works whenCompressing the test text gives a smaller file, and decompressing that gives a file identical to the original, byte for byte.
Concepts: prefix-free codes and unambiguous decoding · bit packing and the last byte · the lossless round trip and its edge cases