Huffman Encoding & Python Implementation

An old but efficient compression technique with Python Implementation

Huffman Encoding is a Lossless Compression Algorithm used to compress the data. It is an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper “A Method for the Construction of Minimum-Redundancy Codes”. [1]

As it can be understood from being a “Compression Technique”, the aim is to encode the same data in a way that takes up less space. Accordingly, when a data is encoded with Huffman Coding, we get a unique code for each symbol in the data. For example the string “ABC” occupies 3 bytes without any compression. Let’s assume while the character A is given the code 00, the character B is given the code 01, the character C is given the code 10 as the result of encoding. To store the same data, we would only need to use 6 bits instead of 3 bytes. Before examining the working principle of Huffman Encoding, I hope what I mean by compression is better understood !

The Algorithm

Huffman Encoding is an algorithm which uses frequency (or probability) feature of symbols and a binary tree structure. It consists of the following 3 steps:

• Probability Calculation & Ordering the Symbols
• Binary Tree Transformation
• Assigning Codes to the Symbols