SICP 2.3.4

This week: Huffman encoding!

Conversational notes

• When is Huffman encoding optimal?
• history
• variable frequency, responsive codes...
• 2.3.4 (Pg 223): "The algorithm does not always specify a unique tree" -- how could it? What advantages would there be?
• long message blows stack?
• snacks

On Exercise 2.72

If we assume that a message has the same character frequencies as the corpus, Dann's version of encode-symbol is faster than Andrey's.

Example: n = 5. Characters: 1, 2, 3, 4, 5; frequencies: 1, 2, 4, 8, 16. Let's take a test message with one 1, two 2s, four 3s, eight 4s, and sixteen 5s. In total: N = 31 characters.

Andrey's encode-symbol: (n+1)N = 6 * 31 = 186. Dann's encode-symbol: 116 + 68 + 94 + 102 + 8*1 = 128.

Further Readings

• Finite State Entropy coding [blog].