6.001/Recitation 10

Rob Speer

More Huffman encoding

What we've got so far is an abstraction for binary trees. Here it is as viewed from outside the abstraction barrier:

(make-tree symbols freq left right)
(symbols tree)
(freq tree)
(left-child tree)
(right-child tree)

We've also got ordered sets:

(adjoin-set item set)
(get-first set)
(drop-first set)

We still need:

• A procedure that counts the frequencies of symbols in a text.
• A procedure that creates an initial set of leaves out of these frequencies.
• Procedures that can walk down the Huffman tree to encode and decode text.

Here are some things to generate Huffman trees for, and then encode:

1. Words with lots of A's
   • Alphabet: (A B C D E F G H)
   • Text: (B A C A D A E A F A B B A A A G A H)
2. 50's rock songs
   • Alphabet: (a boom get job na sha yip wa)
   • Text:

(get a job
 sha na na na na na na na na
 get a job
 sha na na na na na na na na
 wah yip yip yip yip yip yip yip yip yip
 sha boom)