Contents

1 Basics

• Developed by D. Huffman in 1952 [1].
• (Absolute) Optimal performance (in average, better than Shannon-Fano) when a integer number of bits is assigned to each symbol.
• Huffman-based VLC codecs build a binary tree where the symbols are stored in the leafs and the distance of each symbol to the root of the tree is \[\lceil \log _2(p(s))\rceil \].
• After label each binary branch in the tree, the Huffman code-word for the symbol \(s\) is the sequence of bits (labels) that we must use to travel from the root to the \(s\)-leaf.

2 Building Huffman trees

1. Create a list of nodes. Each node stores a symbol and its probability.

2. While the number of nodes in the list > 1:

   1. Extract from the list the 2 nodes with the lowest probability.
   2. Insert in the list a new node (that is the root of a binary tree) whose probability is the sum of the probability of its leafs.

2.1 Example

3 Encoder [2]

1. n := |C|;
2. Q := C;

3. for i := 1 to n-1 do

   1. allocate a new node z
   2. z.left := x := Extract-min(Q);
   3. z.right := y := Extract-min(Q);
   4. z.freq := x.freq + y.freq;
   5. Insert(Q,z);
4. end for
5. return Extract-min(Q); {return the root of the tree}

3.1 Example

String: BACADAEAFABBAAAGAH

OUTPUT: 10001010010110110001101010010000111001111

4 Decoder

1. prob_table := freq //Array with the frequency of occurrence of each char
2. sec := str // Output that we want to rebuild
3. tree := array //A key-value associating array, with each item’s key the node in that subtree and value its current sum probability, according to prob_table
4. code_table := table //An array with length of the how many characters in prob_table, wich maps each code to its corresponding decoded character with each code initialised as empty strings.

5. while more than one node in tree do sub_nodes := key of node with smallest probability in tree sec_sub_nodes = key of := key of node with second smallest propability in tree

   1. for node in sub_nodes do

      1. code_table[node].key := “1” + code_table[node].key;
   2. end for

   3. for node in sec_sub_nodes do

      1. code_table[node].key = “0” + code_table[node].key
   4. end for
   5. tree[sub_nodes + sec_sub_nodes] := tree[sub_nodes] + tree[sec_sub_nodes]
   6. delete tree[sub_nodes]
   7. delete tree[sec_sub_nodes]
6. end while
7. temp := ""
8. result := ""

9. for code in seq do

   1. temp := temp + code

   2. if temp in code_table then

      1. result := result + code_table[temp]
      2. temp := ""
   3. end if
10. end for
11. return result

4.1 Example

5 Limits

• Any Huffman code satisfies that \begin {equation} l\big (c(s)\big ) = \lceil I(s)\rceil , \tag {Eq:Huffman} \end {equation} where \(l\big (c(s)\big )\) is the length of the code-word assigned to the symbol \(s\). This implies that, with each encoded symbol, up to 1 bit of redundant data can be introduced (think about a very frequent – high probability – symbol).
• This is a problem that grows when the size of the alphabet is small. In the extreme case, for binary source alphabets, the Huffman coding does not change the length of the original representation.