Huffman Coding & Trees Flashcards
All 5 cards in this deck
What is Huffman coding?
A compression method that gives each character a binary code based on how often it appears: the most frequent characters get the shortest codes.
How do you find a character's Huffman code from a Huffman tree?
Start at the root and follow the branches down to the character, writing down the 0 or 1 on each branch you pass.
Where in a Huffman tree are the most frequent characters found?
Closest to the root, so they have the shortest codes.
Why does Huffman coding usually need fewer bits than 7-bit ASCII?
ASCII uses 7 bits for every character. Huffman coding gives common characters codes shorter than that, so the total number of bits is smaller.
What are the steps to decode a Huffman-coded bit string using a Huffman tree?
e.g. a tree where A = 0, B = 10 and C = 11; decode 01100- Start at the root and follow the branch that matches each bit in turn.
- When you reach a character, write it down and go back to the root.
- 0 → A, 11 → C, 0 → A, 0 → A, giving ACAA.