Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:nasona:chapter4 [2018/03/11 20:24] – [4.8 Huffman Codes] nasona | courses:cs211:winter2018:journals:nasona:chapter4 [2018/03/11 22:01] (current) – [4.8 Huffman Codes] nasona | ||
|---|---|---|---|
| Line 303: | Line 303: | ||
| ==Summary== | ==Summary== | ||
| + | We want to map encodings to letters so that no encoding is the prefix of another in order to avoid ambiguity. A prefix code that minimizes the average bits per letter is optimal. In other words, more frequently used letters should have shorter encodings in order to compress the data. A brute force algorithm is infeasible because the search space is so large and so variable. We will use a full binary tree to represent prefix codes all letters encoded will be leaf nodes to avoid any encoding being the prefix of another. Meta-letters will be interior nodes (parents to letters). The greedy aspect of Huffman' | ||
| ==The Problem== | ==The Problem== | ||
| - | * A greedy rule is used to shrink the size of the problem instance so that an quivalent | + | * A greedy rule is used to shrink the size of the problem instance so that an equivalent |
| * The global consequences of the initial greedy decision do not become fully apparent until the full recursion is complete | * The global consequences of the initial greedy decision do not become fully apparent until the full recursion is complete | ||
| * Data compression, | * Data compression, | ||
