Introduction to Huffman Trees
Hello everyone! 👋
This article is about Huffman Trees, I did this project in university and after ten years or so I wanted to revisit it in order to solidify my understanding and to practice manual coding.
Introduction
The Huffman coding tree is a fundamental data structure in computer science, and it is used for lossless data compression and entropy coding. Huffman coding trees are already used in ZIP, Mp3, Png for compression often not alone but with other data compression algorithms.
Entropy represents the randomness of the data.
Say roooar, it has 6 characters length and there are 3 unique characters, the entropy is low because of the repeating characters, which implies less uncertainty. For 123456, there are 6 characters and 6 unique characters, the entropy is high because the data looks “random”, there is more uncertainty.
Entropy coding aims to encode the low entropy data so that it can be compressed more efficiently. For roooar you will need 6 bytes of data but with assigning codes you can use fewer bytes, for example you could assign the following bits to the letters:
r = 100, o = 0, a = 101
That will yield something like: 100,0,0,0,101,100, which represents roar using only 12 bits, which means that you’ve compressed the word roooar from 6 bytes to 2 bytes. You will need to pad those 12 bits to that you’ll end up with 16 bits, two bytes.
If you want to implement Huffman trees by yourself scroll down to the References section and check out the links. Next I will show and discuss with you my Python based implementation.
Implementing a Compression tool
Let’s walk through a Python tool that compresses data using Huffman coding trees. The full implementation can be found on my Github and self-hosted Gitlab accounts.
https://github.com/dnutiu/huffman-trees
https://gitlab.nuculabs.dev/dnutiu/huffmantrees
Frequency Map
The first step is to create a frequency map, you need to count the number of characters in the source file in order to determine the characters and bytes which occur more often.
In Python, you can create a frequency map by waking through the bytes of the file and counting the occurrences of each byte.
def _build_frequency_map(self, content: bytes) -> dict[int, int]:
"""
Build the frequency map by counting how many times each byte appears in the content.
:param content: The source content bytes.
:return: A frequency map dictionary.
"""
with utils.Timer(name="Build frequency map", logger=self._logger):
frequency_map = defaultdict(lambda: 0)
for byte in content:
frequency_map[byte] += 1
return frequency_mapI think this part is quite straight forward to understand, next we’ll use the frequency map by building the tree.
Building the tree
The strategy is to create a leaf node from each byte and assign it a weight which is equal to it’s frequency. After that we take two items (leaf or internal node) with the minimum weight and build an internal node, to which we assign the weight as a sum of the two nodes we just took.
To build this efficiently we can use a min heap or a min priority queue. If you want to keep it simple you can also put all the leaf nodes in an array, and create a function that returns and removes the item with the minimum weight. You’d use that function recursively to grab two items at a time, build an internal node and put back the internal node in the array, by doing this over and over you’ll end up with a single element in the array, which is the root node.
In my implementation I’ve used a min heal to efficiently search the minimum element and build the tree.
In the following snippet, I’ve included the whole tree source code:
import abc
import heapq
import typing
from functools import total_ordering
class BaseTreeNode(abc.ABC):
"""
Abstract base tree class that models a huffman tree.
"""
def __init__(self, weight: int, is_leaf: bool = False):
self._weight: int = weight
self._is_leaf: bool = is_leaf
def weight(self) -> int:
return self._weight
def is_leaf(self) -> bool:
return self._is_leaf
@total_ordering
class LeafNode(BaseTreeNode):
def __init__(self, byte_element: int, weight: int):
super().__init__(weight, is_leaf=True)
self._element: int = byte_element
def value(self) -> int:
return self._element
def __lt__(self, other):
if not issubclass(other.__class__, BaseTreeNode):
return NotImplemented
return self.weight() < other.weight()
class InternalNode(BaseTreeNode):
def __init__(self, left: BaseTreeNode, right: BaseTreeNode):
weight = left.weight() + right.weight()
super().__init__(weight, is_leaf=False)
self._weight = weight
self._left = left
self._right = right
def left(self):
return self._left
def right(self):
return self._right
def __lt__(self, other):
if not issubclass(other.__class__, BaseTreeNode):
return NotImplemented
return self.weight() < other.weight()
@staticmethod
def from_frequency_map(
frequency_map: dict[int, int],
) -> typing.Optional["InternalNode"]:
"""
Builds the huffman tree from a given frequency map.
:param frequency_map: The frequency map.
:return: An internal node representing the root of the tree.
"""
if not frequency_map:
return None
# Create a heap
binary_heap = []
for item in frequency_map.items():
# push item into the heap by frequency and character
heapq.heappush(binary_heap, LeafNode(byte_element=item[0], weight=item[1]))
# Build the Huffman tree
while len(binary_heap) > 1:
left = heapq.heappop(binary_heap)
right = heapq.heappop(binary_heap)
# internal node by frequency, in order to be traversed
heapq.heappush(binary_heap, InternalNode(left, right))
return binary_heap[0]
Creating the encodings
You will need to traverse the tree in order to build the encoding table or grab the encoding for a single character. In order to avoid duplicate work I’ve decided to traverse the tree once and build the encoding table in one shot.
To traverse the tree you can use a DFS (Depth First Search) algorithm. It work by going in depth to each leaf node. Once you hit the leaf node you save the value to a map and the path taken to get there, if you’ve traversed the tree left you’d usually put a 0 and if you’ve traverse the tree right you can put a 1.
def _build_encoding_table(self):
"""
Builds the encoding table for huffman using a Depth First Search algorithm on the tree.
"""
with utils.Timer(name="Build encoding table", logger=self._logger):
stack = []
root = self._huffman_tree_root
stack.append([root, []])
while len(stack) > 0:
element, encoding = stack.pop()
if element.is_leaf():
self._encoding_table[element.value()] = "".join(encoding)
else:
if (left := element.left()) is not None:
stack.append([left, [*encoding, "0"]])
if (right := element.right()) is not None:
stack.append([right, [*encoding, "1"]])
Writing to the file
Writing to the file is the tricky part, because since you’re encoding each element into a bit sequence you will need to pad the final amount of bits such that it is divisible by 8, and you can only write 8 bits (a byte) at a time. You can’t write 111 for example, you have to write the whole byte with padding 11100000. I’ve used the bitstring Python package to simplify this process and at the end I’ve added the padding manually.
Besides writing the content you need to write the encoding table in the file as well. It will be used to decode the file. To write the encoding table I have used Python’s built-in package pickle but you can use a 3rd party library such as msgpack to convert the object to binary form. You could also write it as a simple string.
I’ve written the encoding table at the beginning and it’s length so that I know that the rest of the bytes are the file’s content.
def _get_encoded_file_contents(self, content: bytes) -> BitArray:
"""
Given unencoded contents it encodes them with huffman codes.
:param content: The raw content bytes.
:return: The encoded content bytes.
"""
with utils.Timer(name="Encode source file", logger=self._logger):
buffer = []
for byte in content:
buffer.append(self._encode_byte(byte))
bit_array = BitArray(bin="".join(buffer))
return bit_array
def _encode_byte(self, byte: int) -> str:
"""
Encode the given byte using the huffman tree.
"""
if byte in self._encoding_table:
return self._encoding_table[byte]
raise Exception(
f"Can't encode byte {byte}. It is not found in the encoding table."
)
def encode(self, file_name: str, destination: str):
"""
Encodes a given file into huffman bytes and writes it to disk..
:param file_name: The path to the file name.
:param destination: The path to the destination file name.
"""
with open(file_name, "rb") as fh:
content = fh.read()
frequency_map = self._build_frequency_map(content)
self._build_huffman_tree(frequency_map)
self._build_encoding_table()
bit_array = BitArray()
encoding_table = pickle.dumps(self._encoding_table)
# 2 bytes unsigned integer for the encoding table length
bit_array.append(pack("<H", len(encoding_table)))
# the whole encoding table pickled
bit_array.append(encoding_table)
# the huffman encoded file contents
encoded_content = self._get_encoded_file_contents(content)
if len(encoded_content) % 8 == 0:
encoded_content_padding_bits = 0
else:
encoded_content_padding_bits = 8 - (len(encoded_content) % 8)
bit_array.append(pack("<B", encoded_content_padding_bits))
bit_array.append(encoded_content)
self._write_to_destination_file(bit_array, destination)
self._logger.info(f"Done encoding {file_name}.")
#...
def _write_to_destination_file(self, content: BitArray, destination: str):
"""
Writes the bytes to the destination file.
:param content: The content bytes.
:param destination: The destination file name
"""
with utils.Timer(name="Write to destination", logger=self._logger):
with open(destination, "wb") as fh:
content.tofile(fh)
self._logger.debug(
f"Wrote {content.len} bits to destination file: {destination}"
)
Decompressing
Decompressing the file is a straight forward step. You can read the encoding table, reverse it, build a map and retrieve the original elements from there, then write the bytes to the output file.
Conclusion
The Huffman project is an interesting project, it touches algorithms, bit manipulations, files, io, and it is used in many real life applications as well, and formats. If you try to compress a PNG with it, it won’t work because compressing it twice doesn’t yield better results.
If you want to implement it yourself, give it a try. Bellow you can find my Python implementation and some reffereces that I’ve used to implement it.
Thanks for reading!
References
https://en.wikipedia.org/wiki/Entropy_(computing)
https://en.wikipedia.org/wiki/Entropy_coding
https://codingchallenges.fyi/challenges/challenge-huffman/
https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/Huffman.html
https://gitlab.nuculabs.dev/dnutiu/huffmantreespy/
https://github.com/dnutiu/huffman-trees