f.fritze

Conventional computer codes give each letter the same storage space - the common 'E' consumes as much as the rare 'K'.

The Huffman algorithm chooses a smarter way: frequent characters get very short codes, rare a little longer. Thus, the amount of data shrinks without any loss of information.

How to create an elegant Huffman tree from character frequencies step by step, let's look directly at the example word: KAFFEPAUSE.

The classic approach: The block code (fixed length code)

With the traditional block code, each character is assigned a binary code of equal length. The creation can be displayed wonderfully as a uniform decision tree:

1. count characters: The word COFFEE BREAK consists of 11 letters, but uses only 7 different characters (K, A, F, E, P, U, S).
2. Set Bits: To clearly distinguish 7 different characters, we need a 3-bit code (2^3 = 8 combinations). In the graph, this corresponds to a tree with exactly 3 levels.
3. Assign Paths: Each branch to the left stands for a 0, to the right for a 1. Each letter is at the end of an exactly 3 step long path.

Code table (block code)

Since the tree is exactly 3 levels deep, each character receives a 3-bit code:

The coded text for KAFFEEPAUSE

Translated letter by letter:

Total binary code:
000001010010011011100001101110011

Length: 11 letters ⋅ 3 bits = 33 bits

The problem with this:

Although the E occurs three times and K only once, both consume exactly 3 bits. In addition, the eighth combination (the empty circle at the bottom right) remains completely unused.

Some codes may be shorter: The flex code

In the block code, all characters have three digits. Although this is clear, it is not absolutely necessary: As soon as the path 11 is reached, we already know that only the character 'S' can be meant. The additional branching would therefore be superfluous.

The flex code now requires 32 bits instead of 33 bits for the block code. This is only a small difference - but the principle is crucial: not every character has to be given the same amount of space.

Why do we need the Huffman algorithm?

We have already seen with the flex code: codes may be of different lengths. In order to save even more storage space, it would make sense in our example to move the frequently occurring 'E' further up in the tree. Finally, it appears three times in the word, while about 'K', 'P', 'U' and ‚S‚ only occur once each.

This is exactly where the Huffman algorithm helps: It systematically creates a space-saving, clearly readable code tree from the frequencies of the characters. Frequent characters end up as high as possible in the tree and receive short codes; rare characters get longer codes.

Frequency analysis

For the word 'KAFFEEPAUSE', it is first determined how often each letter occurs: 'E' appears three times, 'A' and 'F' twice each, 'K', 'P', 'U' and 'S' once each. These frequencies form the basis for the Huffman tree.

Explanation of the procedure

Thus, a new node with the frequency 2 arises from the two individual nodes.

Subsequently, the two remaining characters are connected with the frequency 1, i.e. U and S:

1+1=2

Now there are no single nodes with the frequency 1. What remains are four nodes with the frequency 2 – the subtrees KP, US and the individual characters A and F – and the node E with the frequency 3.

This creates a larger subtree with the frequency of 4. After that, A and F are combined:

2+2=4

This means that the Huffman tree is complete. The number 11 at the root corresponds to the total number of all characters in the word.

How the codes are created

Subsequently, each edge of the tree is assigned a binary digit, for example the 0 on the left and the 1 on the right. The code of a character results from the path from the root to its leaf.

At equal frequencies, there are several equivalent possibilities for which nodes are connected to each other. Therefore, different Huffman trees can arise. It is crucial that in each step the two nodes are combined with the smallest frequencies.

Code board for "KAFFEEPAUSE"

The codes are read from the Huffman tree: The path from the root to a character corresponds to its code. Each edge is labeled with a 0 or 1.

It is important that each path is unambiguous and that frequent characters receive as short codes as possible.

With code board, the word KAFFEPAUSE is encoded as follows:

The complete bit sequence is:

Without separators, the result is:

For control: The individual codes must be read by the Huffman tree during decoding, as the code words are different in lengths.

Final conclusion

The Huffman algorithm shows how data can be displayed in a space-saving manner by a clever arrangement of codes of different lengths.

If you then read the path from the root to each character, a unique code is created for each character. In this way, the word can be encoded without loss of information and decoded again later. The Huffman algorithm thus combines frequency analysis, tree structure and efficient data compression.