Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:virginia:chapter4 [2012/03/06 15:04] – [Section 7: Clustering] lovellv | courses:cs211:winter2012:journals:virginia:chapter4 [2012/03/06 16:01] (current) – [Section 8: Huffman Codes and Data Compression] lovellv |
|---|
| ===== Section 8: Huffman Codes and Data Compression ===== | ===== Section 8: Huffman Codes and Data Compression ===== |
| |
| | We also use greedy algorithms to help with encoding, the process of mapping symbols (letters, for example) to bits. There are many possible ways to encode our alphabet. We want to find some optimal encoding by taking advantage of the non-uniformity of the alphabet, so that the average number of bits per letter (ABL) is as small as possible. We also want an encoding that does not require spaces or other separators between letters, that is, we want a prefix code, an encoding where no letter is a prefix of another. |
| |
| | We will represent a prefix code using a binary tree, where each letter is a leaf node and the path to a letter is its encoding. The length of an encoding is the depth of that letter in the tree, so we are interested in minimizing the weighted averages of the depth of the leaves. Given a set of letter frequencies, we can find this optimal prefix code using Huffman's Algorithm (p 172). In this algorithm, we begin at the bottom of the tree, assigning the letters with lowest frequency as siblings and creating a meta-letter as their parent that has frequency equal to the sum of their frequencies. We then recursively repeat this process until the tree is complete. This algorithm as O(nlogn) run time when using a priority queue on an alphabet of n characters. |
| | |
| | Readability: 7 |
| |
| |
| |
| |
