EECS 1520 Lecture Notes - Lecture 12: Binary Tree, Huffman Coding

• School: York University
• Department: Electrical Engineering and Computer Science
• Course: EECS 1520
• Professor: Andriy Pavlovych

Document Summary

Coded as: 1011110110111101001100100: this is where you need the prefix property. If we used a fixed-size bit string to represent each character (ex. 8 bits) then the binary form of the original string would be 64 bits: the huffman encoding for that string is 25 bits long, giving a compression ratio of. Input: symbols and their frequency-counts: output: binary-code for each symbol, property: optimum compression-rate with prefix-property. Step 1: sort them in ascending order of frequency. Place them in a sorted queue c d a. Step 2: replace the 2 minimum frequency symbols by one (cid:1688)combined symbol(cid:1689) and place it in a 2nd sorted queue. e b. These two minimums can be selected from either queue. Step 2 continues until only one remains in the queues. Queue 2: label the left-branches 0 branch node root. Step 3: the result is a binary tree leaf. Step 4: the code for each symbol is the binary sequence along the corresponding root-to-leaf path.