Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:ahmadh:ch4 [2018/03/11 06:46] – ahmadh | courses:cs211:winter2018:journals:ahmadh:ch4 [2018/03/11 06:49] (current) – [4.8.3 Comments] ahmadh |
|---|
| |
| This algorithm is referred to as Huffman's Algorithm, and the prefix code it generates is called a Huffman Code. With the most basic implementation, identifying the lowest-frequency letters can be done in a single scan of the alphabet, in time O(k), and so summing this over the k - 1 iterations gives O(k^2) time. However, this time can be improved upon. We can maintain the alphabet S in a priority queue, using each letter’s frequency as its key. In each iteration we just extract the minimum twice (this gives us the two lowest-frequency letters), and then we insert a new letter whose key is the sum of these two minimum frequencies. Our priority queue now contains a representation of the alphabet that we need for the next iteration. We can make each insertion and extraction of the minimum run in time O(log k); hence, each iteration--which performs just three of these operations--takes time O(log k). Summing over all k iterations, we get a total running time of O(k log k). | This algorithm is referred to as Huffman's Algorithm, and the prefix code it generates is called a Huffman Code. With the most basic implementation, identifying the lowest-frequency letters can be done in a single scan of the alphabet, in time O(k), and so summing this over the k - 1 iterations gives O(k^2) time. However, this time can be improved upon. We can maintain the alphabet S in a priority queue, using each letter’s frequency as its key. In each iteration we just extract the minimum twice (this gives us the two lowest-frequency letters), and then we insert a new letter whose key is the sum of these two minimum frequencies. Our priority queue now contains a representation of the alphabet that we need for the next iteration. We can make each insertion and extraction of the minimum run in time O(log k); hence, each iteration--which performs just three of these operations--takes time O(log k). Summing over all k iterations, we get a total running time of O(k log k). |
| | |
| | ==== 4.8.3 Comments ==== |
| | |
| | I feel like it is safe to say that this was by far the most interesting section that I remember reading in the book. I am not sure why, but the problem seemed really practical/important to me, and I can totally see how big of a deal this algorithm was when it came out. The idea of encoding the most frequent letters using fewer bits seems like a no brainer. The section attracted and then kept my attention //throughout// the reading--and that is a first. 10/10. :) |
