NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

---

There are simple examples of Huffman codes, where there are two structurally distinct Huffman trees for the same set of symbols and frequencies. Because the Huffman code is optimal, these codes must have the same average code length.

Here is one simple example: a:9, b:5, c:4, d:3, and e:3. There are clearly two distinct ways to construct the tree, resulting in Huffman codes for the symbols with a different set of lengths for the codewords. In both cases the average code length is 2.25 bits per symbol.

Here are two different sets of lengths:

   +---a: 0.3750, 0 (step 4)
   |   
---+---@: 1.0000, 
   |           
   |       +---e: 0.1250, 100 (step 1)
   |       |   
   |   +---+---@: 0.2500, 10 (step 3)
   |   |   |   
   |   |   +---d: 0.1250, 101 (step 1)
   |   |   
   +---+---@: 0.6250, 1 (step 4)
       |       
       |   +---c: 0.1667, 110 (step 2)
       |   |   
       +---+---@: 0.3750, 11 (step 3)
           |   
           +---b: 0.2083, 111 (step 2)
               
Entry 0. Symbol: a, Weight: 0.3750, Representation: 0
Entry 1. Symbol: d, Weight: 0.1250, Representation: 101
Entry 2. Symbol: b, Weight: 0.2083, Representation: 111
Entry 3. Symbol: e, Weight: 0.1250, Representation: 100
Entry 4. Symbol: c, Weight: 0.1667, Representation: 110

Entropy: 2.1829, Ave. Code Length: 2.25

       +---c: 0.1667, 00 (step 2)
       |   
   +---+---@: 0.3750, 0 (step 4)
   |   |   
   |   +---b: 0.2083, 01 (step 2)
   |   
---+---@: 1.0000, 
   |           
   |       +---e: 0.1250, 100 (step 1)
   |       |   
   |   +---+---@: 0.2500, 10 (step 3)
   |   |   |   
   |   |   +---d: 0.1250, 101 (step 1)
   |   |   
   +---+---@: 0.6250, 1 (step 4)
       |   
       +---a: 0.3750, 11 (step 3)
           
Entry 0. Symbol: a, Weight: 0.3750, Representation: 11
Entry 1. Symbol: b, Weight: 0.2083, Representation: 01
Entry 2. Symbol: c, Weight: 0.1667, Representation: 00
Entry 3. Symbol: d, Weight: 0.1250, Representation: 101
Entry 4. Symbol: e, Weight: 0.1250, Representation: 100

Entropy: 2.1829, Ave. Code Length: 2.25