Differences

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

--- courses:cs211:winter2018:journals:shermanc:chapter4 [2018/03/06 04:21] – shermanc
+++ courses:cs211:winter2018:journals:shermanc:chapter4 [2018/03/20 21:30] (current) – shermanc
@@ Line 71: / Line 71: @@
 This section was actually pretty interesting and extremely short, so 8/10.
+===== 4.8: Huffman Codes and Data Compression =====
+The whole deal with Huffman Codes was that they were a way to find how to encode symbols using bits.  So, the book discussed how to go about coding them and then, in turn, decoding them.
+The goal is to produce a "labeled binary tree in which the leaves are as close to the root as possible."  This is because this gives us an average leaf depth.  What we end up doing is constructing a prefix code for a given alphabet.  We pick out the two letters that occur least frequently and assign them as variables.  Then we make a new alphabet excluding these letters, but replacing them with a new letter that occurs the amount of both least-occurring letters combined.  Then we recursively construct a prefix code on this new alphabet.  The way we get a prefix for the original alphabet is by taking the given tree from our newest alphabet and take the letter we replaced the least-occurring letters with, and give it two children: the original least-occurring letters.  This final tree will give us our desired prefix code as defined as a //Huffman code//.
+This algorithm runs in O(k<sup>2</sup>), because it first does a full scan over an alphabet of size k and then proceeds to iterate k-1 times over the alphabet.  If we use a priority queue, however, we can get it to run in O(klogk) time, as the priority queue allows for insertions and extractions of O(logk).
+This was a very interesting section, talking about encoding and the uses for it.  Also, the reason why the algorithm works and how to use it was interesting too, so I give it a 9/10.