Huffman coding

Huffman coding uses so-called binary trees to reduce the amount of information in a message.

Let's look at an example with a very basic version of this data "compression" algorithm.

Suppose we have the following text: 

The text consists of a string with 17 characters, which will occupy 17 bytes in memory.

Each of these characters takes up 1 byte and is represented in binary using 8 bits.

For example, the letter A is represented as 01000001, and consequently, its ASCII code is: 1*2^0 + 0*2^2 + ... + 0*2^5 + 1* 2^6 + 0*2^7=65

Let's look at a code snippet to display the text in binary:

We obtain the following string of 136 bits (17 characters with 8 bits each).

The Huffman encoding method is based on the creation of a binary tree. To achieve this, we follow these steps:

1º) We create a list of the characters that make up the text, ordered from highest to lowest frequency.

For this, we use Python's "dictionary" structure:

We obtain the following:

2º) We create the binary tree. To do this, we place the characters ordered from highest to lowest frequency on the right side of the tree, assigning 0 to the left branches and 1 to the right branches according to the following scheme:

This tree assigns each character a numerical combination based on the path from the root to the specific character.

For example, to reach R, we follow 001, and to reach A, we follow 0.

Thus, we obtain the following representation for the characters: 

This table can be obtained as follows:

With all this, we can attempt to "compress" the character string. To do this, we obtain a new binary representation by replacing each character with its corresponding code from the previous table.

We obtain the following binary representation, which lenght is 50 bits.

The original text had a lenght of  136 bits

We observe that to "decompress," we must traverse the "compressed" binary string from left to right. The appearance of a character other than 0 indicates the separation between two characters.