Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:nasona:chapter4 [2018/03/11 20:02] – [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==
+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's algorithm is that you merge the two lowest frequency letters in the algorithm. The bottom-up approach is the optimal approach. The runtime of the algorithm is O(klogk).
 ==The Problem==
-  * A greedy rule is used to shrink the size of the problem instance so that an quivalent smaller problem can then be solved by recursion
+  * A greedy rule is used to shrink the size of the problem instance so that an equivalent smaller problem can then be solved by recursion
   * The global consequences of the initial greedy decision do not become fully apparent until the full recursion is complete
   * Data compression, an area that forms part of the foundation for digital communication
@@ Line 381: / Line 382: @@
 ==Additional Information==
-A concept that was troubling me in the beginning stages of understanding Huffman codes was the concept of the meta-letter that is the parent of leaf nodes. As a read the section after the class, it made more sense. The meta-letter is there because a letter node cannot be there. A letter encoding cannot be an interior node because that means that it is the prefix of another node, which is the point of the Huffman codes. There can be no encoding that is the prefix of another. Moreover, meta-letters are helpful and make more sense in Huffman's optimal bottom up approach anyway.
+A concept that was troubling me in the beginning stages of understanding Huffman codes was the concept of the meta-letter that is the parent of leaf nodes. As a read the section after the class, it made more sense. The meta-letter is there because a letter node cannot be there. A letter encoding cannot be an interior node because that means that it is the prefix of another node, which is the point of the Huffman codes. There can be no encoding that is the prefix of another. Moreover, meta-letters are helpful and make more sense in Huffman's optimal bottom up approach anyway. The first meta-letter joins the two letters of the lowest frequency and that way its like a super letter and now the alphabet has one less letter. This explanation of the purpose of the meta-letter also makes it clear why we would implement the algorithm with a priority queue.
 On a scale of 1 to 10, the readability of this section is a 9. The book explained really well the notation and the concepts behind the Huffman Code. Also, the main part of the code involved binary trees, which we've already seen multiple times in this class, so it was really building off the knowledge we already knew.