Huffman encoding saves space by giving frequent characters shorter bit patterns and representing the codes as a prefix-free tree. section 6.3
Read a character’s code by starting at the tree’s top: write 0 when moving left and 1 when moving right. Because every character appears at the bottom, one code cannot be confused with the beginning of another. section 6.3
A code for “g”
Following the path Right, Right, Left, Left, Right, Right produces 110011 for “g”. In the worked message, compression reduces 4,171 bits to 522 bytes, with another 25 bytes needed to send the tree. section 6.3
Practice Huffman encoding by working from frequencies to codes and back again:
- Count character frequencies in an excerpt, assign them to the Huffman codes, and encode the passage through “more lightly.” section 6.6
- Decode a supplied frequency table and encoded message. section 6.6
Figure 6.9 Our code table as a tree
Use the tree view to follow paths, read bit codes, and see why the characters occupy separate leaves. section 6.3
