Project 3: Huffman Encoding and Decoding
CSC 2001 – Data Structures
1 Overview
In this project you will implement a program to compress and decompress text using Huffman coding, a method of lossless data compression – the original file can be reconstructed perfectly from the compressed version. Each character is assigned a variable-length code made up of ‘0’s and ‘1’s. The length of a character’s code depends on how frequently it occurs: more frequent characters get shorter codes.
The core idea is a binary tree in which each leaf node represents a character and its frequency count. The Huffman code for a character is the unique path from the root of the tree to that character’s leaf, where each ‘left’ branch contributes a ‘0’ bit and each ‘right’ branch contributes a ‘1’ bit. Because the number of bits needed to encode a character is the length of the path from the root, characters that occur frequently should end up less deep in the tree than characters that occur rarely.
The key problem, then, is constructing such a tree from the frequency of occurrence of the characters in a file. A detailed worked example of building a Huffman tree by hand is provided in Appendix A at the end of this document – read through it before you start coding.
You will implement both directions of this process: encoding (compressing a text file into a Huffman-coded file) and decoding (reconstructing the original text file from a Huffman-coded file). Both directions share the same tree-building logic, so you’ll build that once and use it for both.
1.1 General requirements, which apply to everything below:
Provide test cases for every function specified below, using exactly the function/method names given.
Use descriptive names for any additional helper functions or data structures you introduce.
Every function should be documented with a clear purpose statement (what it does, its parameters, and its return value).
You should track your work sessions, and record them in a text file called "process-journal.txt", to be submitted with your assignment. This journal should record every session in which you worked on the project, and include a summary of the work done during that session.
2 Project 3 Template available here:
3 Data Definition: the Huffman Tree Node
A Huffman tree is a binary tree made up of nodes and leaves. A node stores a character (as its integer ASCII value), an occurrence count for that character, and references to its left and right subtrees. Do not remove or rename the fields specified in the starter code. A leaf contains an ASCII value and a count, but no left or right child. No ‘null‘s should be required (or allowed!) for this tree.
For an internal node (one created by combining two smaller subtrees), the character and count fields are still filled in, following the rules described in the next section – this is what makes it possible to break ties consistently while building the tree.
4 Building the Huffman Tree
Because the resulting code depends on the order in which the left and right branches are taken from the root to a leaf, it’s essential to follow a consistent rule for how the tree is built. This requires an ordering on Huffman nodes.
4.1 Ordering nodes: comesBefore
Implement a method a.comesBefore(b) for two Huffman (sub)trees that returns true if tree a comes before tree b. Tree a comes before tree b if the occurrence count of a is smaller than that of b. If the occurrence counts are equal, break the tie using the ASCII value of the character: the smaller ASCII value comes first. For example, if ’d’ and ’k’ occur the same number of times in the file, ’d’ comes before ’k’, since the ASCII value of ’d’ is smaller.
4.2 Combining two nodes: combine
Implement a function a.combine(b) that creates and returns a new internal Huffman node with a and b as its two children. The child for which comesBefore is true is placed on the left; the other child goes on the right. The new node’s occurrence count is the sum of a’s and b’s counts, and its character value is the minimum of a’s and b’s character values (this is what lets later comparisons involving this internal node break ties correctly).
4.3 Choosing a data structure to hold the nodes
Before you write createHuffTree, you need somewhere to keep track of the “not yet combined into the final tree” nodes, ordered from smallest to largest occurrence count so you can always get at the two smallest. This project intentionally does not tell you which data structure to use for that – you get to choose, as long as it lets you always retrieve and remove the node with the minimum occurrence count.
Two reasonable options:
• An ordered list, kept sorted by comesBefore as you insert nodes, so the minimum is always at the front.
• A priority queue backed by a min-heap, where the minimum is always at the root.
Before you start coding, think through the trade-offs:
How expensive is it to pull out the minimum node with each approach? How expensive is it to add a newly-combined internal node back in?
Does the cost of building the initial collection of leaf nodes differ between the two approaches?
Roughly how many times will you remove-the-minimum and add-a-node over the course of building a tree with ‘n’ unique characters? How does that interact with the per-operation cost of each data structure?
If two nodes have equal occurrence counts, does your chosen data structure make it easy or awkward to break the tie the way comesBefore specifies?
4.4 Assembling the tree: createHuffTree
Implement a function createHuffTree(freqList) that takes the list/array of character occurrence counts (as produced by cntFreq, described below) and returns the root node of the resulting Huffman tree.
Start by creating a leaf node for every character with a non-zero count, and use enqueue to place each one into your chosen collection.
While the collection holds more than one node: remove the two smallest nodes with dequeue, connect them with combine to form a new internal node, and use enqueue to place that new node back into the collection.
Continue until exactly one node remains in the collection – that node is the root of the completed Huffman tree. Return it.
Special case: if freqList has no non-zero counts (the input file was empty), createHuffTree should return null (or None, per your language).
Special case: if freqList has exactly one non-zero count (the input file has only one unique character), createHuffTree should return a single node containing that character and its count, with no children.
5 Building the Character Code Table
With the Huffman tree built, implement createCode(root), which traverses the tree and produces the actual Huffman code for every character. The result is a 256-entry table (array/list), indexed by a character’s integer ASCII value, where each entry holds that character’s code as a string of ’0’s and ’1’s. Characters that never appear in the file should have an empty string at their index.
Traverse the tree from the root to each leaf, appending a ’0’ each time you go left and a ’1’ each time you go right; the accumulated string when you reach a leaf is that character’s code.
Special case: if root is itself a leaf (the single-unique-character case described above), there’s no left/right branch to build a code out of. Leave that character’s entry as the empty string, same as a character that never appears – this case is handled entirely by the header in huffmanEncode/huffmanDecode, not by a generated code.
6 Counting Character Frequencies
Implement cntFreq(filename), which opens the text file named filename and counts how often each character occurs in it. Use a 256-entry table (array/list) indexed by ASCII value for the counts, initialized to zero, since input files are assumed to contain only 8-bit characters. Return this table. For example, for a file containing:
ddddddddddddddddccccccccbbbbaaff
the counts at positions 97–103 (ASCII ’a’ through ’g’) would be [2, 4, 8, 16, 0, 2, 0].
7 Encoding a File
7.1 The header: createHeader
Implement createHeader(freqList), which takes the frequency table produced by cntFreq and returns a header string listing each character’s ASCII value and its count, separated by single spaces, for every character with a non-zero count. For example, for the text "aaabbbbcc", createHeader returns "97 3 98 4 99 2".
7.2 Writing the encoded file: huffmanEncode
Implement huffmanEncode(inFile, outFile) (use this exact name), which reads the text in inFile and writes to outFile:
A header line (from createHeader), terminated with a newline;
The Huffman-encoded text, using the codes from createCode.
If outFile already exists, its old contents should be replaced. Handle the special cases called out above – an empty input file, and an input file with only one unique character.
Note: writing each character’s code as literal ’0’/’1’ characters will actually make the output file larger than the input, not smaller – even though each code represents a sequence of bits, writing them as text characters uses a full byte per bit. Producing a genuinely smaller file would require packing the bits, which is outside the scope of this assignment.
8 Decoding a File
Decoding reverses the process: given a file in the format written by huffmanEncode (a header line followed by a line of ’0’/’1’ characters), reconstruct the original text.
8.1 Recreating the tree: parseHeader
Since decoding happens independently of encoding, you first need to recreate the same Huffman tree that was used to encode the file, using only the header stored in the encoded file. Implement parseHeader(headerString), which takes a header string (in the format produced by createHeader) and returns a 256-entry frequency table in the same format returned by cntFreq. For example, the header "97 3 98 4 99 2" corresponds to a table where positions 97–99 hold 3, 4, 2. Once you have this frequency table, pass it to the same createHuffTree function you already wrote to rebuild the identical tree that was used during encoding.
8.2 Walking the tree: huffmanDecode
Implement huffmanDecode(encodedFile, decodeFile) (use this exact name), which reads the encoded file encodedFile and writes the decoded text to decodeFile. After recreating the tree from the header, walk the tree once for every bit of the encoded text: start at the root, go left on a ’0’ and right on a ’1’. Whenever you reach a leaf node, emit its character to the output and restart the walk at the root. Continue until every bit has been consumed.
If encodedFile does not exist, this should raise the same “file not found” error your language normally raises for a missing file. If decodeFile already exists, its old contents should be replaced. Special case: if the recreated tree is a single leaf (the single-unique-character case), there’s no encoded line of ’0’/’1’ characters to walk in the first place – recall that huffmanEncode writes only a header for this case. The header alone already tells you the character and how many times it occurred, so just write that character out that many times.
9 Testing
Write thorough tests for every function listed above, using the exact names specified. Starter test files and sample text/solution files are provided – use them as your starting point, and add your own as you go. It’s fine to comment out or skip tests for functionality you haven’t implemented yet while you’re still working through the assignment.
Be sure your tests cover edge cases, including:
An input file with only one unique character, e.g. "aaaaa" – the output file should contain only the header line, e.g. "97 5", with no second line of code bits at all: a single-node tree has no left/right branches to encode a character with, so there is no code to write. On decode, the character and its count come entirely from the header.
An empty input file – encoding it should produce an empty output file.
An input file that does not exist – this should raise a file-not-found error rather than failing silently or crashing unexpectedly.
10 Implementation Notes
Watch out for text editors or copy/paste silently adding a trailing newline character to your test files – if present, that newline becomes part of the Huffman tree and will show up in your generated codes. Newlines are also represented differently across operating systems: Windows uses \r\n (0x0D 0x0A), while Unix/Mac use \n (0x0A) alone. When writing output files, be deliberate about which newline byte(s) you write so your output matches the provided solution files exactly regardless of platform.
A hex editor is useful for verifying why two files that look identical in a normal text editor are actually different at the byte level – this is often the culprit when a test “almost” passes.
Your output files are graded byte-for-byte. Write newlines as \n (not \r\n, println, or System.lineSeparator()). The starter repository includes a .gitattributes file that stops Git from converting the sample files’ line endings on Windows - keep it in your repository.
11 Submission
You must upload to Gradescope:
Your Huffman implementation, containing all of the functions specified above (cntFreq, comesBefore, combine, enqueue, dequeue, createHuffTree, createCode, createHeader, huffmanEncode, parseHeader, and huffmanDecode) along with any helper functions you added.
Your test file(s), containing the test cases used while developing and verifying your program.
Any additional text files needed for your test cases.
Summary of files to submit
File names are case-sensitive and must match exactly. Do not submit compiled .class files or generated output files (such as file1_out.txt or file1_decode.txt).
Huffman.java
HuffmanTree.java
HuffmanNode.java
HuffmanLeaf.java
HuffmanTest.java
process-journal.txt
... other test data files that you use.
12 Appendix A: Worked Example
The attached pages walk through building a Huffman tree by hand for the text "abcd abc ab a", then using that tree to encode and decode it. The walkthrough illustrates each step using a sorted list as the collection of not-yet-combined nodes, since that makes it easiest to see “the two smallest nodes” at a glance on paper. If you choose a min-heap priority queue instead, the sequence of dequeue/enqueue operations - and the final tree, codes, encoded string, and decoded output - are identical; only the internal mechanics of how the minimum is tracked differs. Use this example to check your own tree, codes, and encoded/decoded strings against, regardless of which collection you implement.