Setup
Register for the lab using grinch: https://grinch.caltech.edu/register. For this assignment, DO NOT BOTHER cloning the repository. The button
at the bottom of this page will automatically submit your answers, and gitlab will check them for you.
Part 1: The HuffmanNode class
Consider the following HuffmanNode class which represents a dictionary which maps binary strings to characters:
L0: private static HuffmanNode {
L1: public final Character value;
L2: public Map<Boolean, HuffmanNode> children;
L3: public HuffmanNode() {}
L4: public HuffmanNode(char value) {
L5: this.value = value;
L6: }
L7: }
Fundamentally, any decompression algorithm takes a stream (or String) of bits and turns them back into a series of actual characters.
Huffman decompression achieves this by constructing a tree (technically, a trie) where the leaves of the tree represent specific characters,
and the path (i.e., left is 0 and right is 1) we took from the root to get to the leaf node is the binary string that represents that character.
For example, if we have the following Huffman Tree, where o represents an internal node with no value:
o
/ \
c o
/ \
a b
It could be represented as HuffmanNodes as follows:
HuffmanNode(value=null, children={
false=HuffmanNode(value='c', children={}),
true=HuffmanNode(value=null, children={
false=HuffmanNode(value='a', children={}),
true=HuffmanNode(value='b', children={})
})
})
Note that the children map only ever has false and true as keys (which represent 0 and 1, respectively). Furthermore, leaf nodes (i.e., the ones
which character values) have an empty children map.
Fundamentally, you can think of Huffman trees as TrieMaps with binary strings as keys and characters as values.
Part 2: Getting the Whole Dictionary
L00: _______ Set<String> getDictionary() {
L01: Set<String> result = new HashSet<>();
L02: List<String> acc = new ArrayList<>();
L03: getDictionary(this.root, result, acc);
L04: return result;
L05: }
L06: _______ Set<String> getDictionary(HuffmanNode node, Set<String> result, List<String> acc) {
L07: if (node == null || node.children.isEmpty()) {
L08: result.add(String.join("", acc));
L09: }
L10: else {
L11: acc.add("0")
L12: getDictionary(node.children.get(false), result, acc);
L13: acc.add("1")
L14: getDictionary(node.children.get(true), result, acc);
L15: }
L16: return result;
L17: }
Part 3: Huffman Decompression
L01: public static String decompress(HuffmanNode node, String bits) {
L02: String result = "";
L03: while (!bits.isEmpty()) {
L04: result += nextCharacter(node, bits);
L05: }
L06: return result;
L07: }
L08: public static char nextCharacter(HuffmanNode node, String bits) {
L09: if (node == null || node.children.isEmpty()) {
L10: return node.value;
L11: }
L12: else {
L13: if (bits.substring(0, 1) == "0") {
L14: nextCharacter(node.get(false), bits.substring(1));
L15: }
L16: else {
L17: nextCharacter(node.get(false), bits.substring(1));
L18: }
L19: }
L20: }