Studying Huffman Coding

Huffman Coding is a lossless compression algorithm.

Example text: ffffcdabdfdeeebcc

First, count how often each character appears:

f:4 c:3 d:3 e:3 b:2 a:1

Then repeatedly merge the least frequent characters into a binary tree until one final tree remains.

Each character gets a binary code:

• Left = 0
• Right = 1

More frequent characters receive shorter codes, reducing the total file size.

A key rule: no code can start with another code.
If f = 1, then 100 cannot be another character, so decoding stays unambiguous.

Time complexity: O(n log n)

Image: GeeksforGeeks
Video: Computerphile – Huffman Coding