Data Compression: Huffman Codes
Read the book chapters first, then make sure you can answer the questions in the notes. Following that, work on some skills-check problems and exercises. Then take the online quizzes.
- Reading
- 17.3
- Skills Check
- 11
- Exercises
- 16, 17, 19, 20, 21, 22, 24, 25, 26, 27, 28
- Quiz
- No quiz today.
17.3
- What is the main goal of data compression? What are some examples?
- Data compression requires variable-length codes. Explain what that is.
- Table 17.9 shows the relative frequencies of letters in the English language. Morse Code, which is a variable-length code, would likely try to assign shorter codes to most frequent letters. Verify this by looking at the Morse Code assignments in spotlight 17.4 (For example, E takes a single more signal, a dot, and T takes a single signal, a dash, and this matches the fact that E and T are the two most frequent letters).
- Describe what delta encodings are, and situations in which they might be effective.
- Describe how the Huffman encoding works. How is the code-tree built?
- Show how to encode and decode using the code-tree.
- Using the frequencies in Figure 17.9, construct a Huffman code for the English language. Then use that code to encode the phrase “HANOVERCOLLEGE”.