Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:shannon:chapter4 [2014/03/03 20:34] – [Section 4.8: Huffman Codes and Data Compression] nollets | courses:cs211:winter2014:journals:shannon:chapter4 [2014/03/03 21:10] (current) – [Section 4.8: Huffman Codes and Data Compression] nollets | ||
|---|---|---|---|
| Line 62: | Line 62: | ||
| This section also looks at optimal prefix codes which have the smallest average number of bits required per letter. | This section also looks at optimal prefix codes which have the smallest average number of bits required per letter. | ||
| The algorithm to create the optimal prefix code can be used multiple ways. We can start with the encoding first, and create a binary tree from it. Each time a path to a leaf branches left, we write down a zero and each time a path to a leaf branches right, we write down a one. We can also start with a binary tree and from it deduce the encoding. | The algorithm to create the optimal prefix code can be used multiple ways. We can start with the encoding first, and create a binary tree from it. Each time a path to a leaf branches left, we write down a zero and each time a path to a leaf branches right, we write down a one. We can also start with a binary tree and from it deduce the encoding. | ||
| + | We say that a binary tree is full if every internal node has two children. | ||
| + | When we finally look at creating the algorithm we look at a bottom up approach as opposed to the top down approach which has to use the brute-force algorithm as opposed to the optimal one. The algorithm, discussed on page 172 of the text, starts by placing all of the letters, with their frequencies in some order. Then you match the two letters with the lowest frequencies with each other under a meta letterwith the frequncy equal to the sum of the two letters frequencies. You then repeat this process until allot the nodes are matched up and the frequency of the meta letter is one. This algorithm is called Huffaman' | ||
| + | Prefix codes have some drawbacks including an inability to change as more text is added and that you cannot use partial bits. However, we choose prefix codes as a trade off between the power of compression and the computational cost. | ||
| + | |||
| + | This was a little confusing to reAd, but the explanations in class were very helpful. | ||
| + | I would give this section a 8/10 as I never thought of this problem and I think it is pretty cool that they have created a solution to it! | ||
