Video 5-3: §5.3 Huffman codes

0:02 in the next subsection we'll look at Huffman codes this will provide the kind of final ultimate solution for character codes uh so let's uh recap again why we think these might be useful the goal was to find for each character in an alphabet some encoding or code words and we'll restrict our attention to binary code words here so that the overall text is stored with uh the shortest amount of bits um in this section because we have well because I'll write Sigma s many many times I'll abbreviate it as as Sigma and that's fine because the coded alphabet is fixed anyways to be binary if you look at many types of data and in this case um English English language text you can count how often each letter occurs now this one's maybe a little bit of a is cheating a little bit because it treats the capital and lowercase letters the same um but you get a similar picture if you take more letters into account or more more symbols uh you have some some letters that are much more frequent than others and these also don't vary a lot in different texts but they might vary a little bit if the text is not super long okay so the inition should be as in

1:28 the morse code by the way that letters at the beginning of this table that are occurring so often should have a short code word whereas those at the end that only occur so randomly so so rarely it's fine if they have a longer code word because we won't use them as

1:49 often now halfman coding is uh is formalizing or abstracting this idea as follows um it's an it's the algorithmic problem where we given some alphabet and we're also given weights for each of the letters so think of it as this table but the weights are just arbitrary numbers for now any any uh positive numbers non non- negative numbers and the goal is to find some codes some code words for these letters but we want them to be prefix free to not have this ambiguity problem that I've uh shown you last time so we'd like to find a code try that has all the letters from six at the leaves and that minimizes this quantity which is summing over all the letters in the alphabet the length of the code word right remember e assigns the code word to each letter so that's the length of the code word for

2:58 C and this is just the weight of that letter so we it's a weighted a weighted sum of uh the code word lengths and that's what we would try to

3:16 minimize um why that so why is that the right thing to look at uh let's use this notation I think it only occurs on this slide um if you have a string I'll write these bars and then as a subscript a character that's the number of occurrences of this character in the string it's a convenient notation you find that find that in other places too now if we set our weights for the alphabet to be precisely this the number of occurrences of that letter in the string then this sum is exactly the total length of the coded text is that clear so you uh the coded text consists of the code word for the first letter code word for the second letter code word for the third letter and so on uh but for summing up the lengths the order doesn't matter it's just is a matter of how often do we have each code word how often do we have it well as often as this character occurs in the source text so that's precisely the sum so what halfman coding is is asking for really is the best possible characteriz encoding or at least prefix free character wise encoding I should probably smuggle this in here

4:34 as we'll see later in this section it's actually uh also close to best possible in a more General sense if you see this first time now again some of you will have seen this before right um but if you see this for the first time and phrase like this it sounds really ambitious the best possible code do we have any chance of finding this quickly and amazingly for for halfman for halfman's uh problem this is a a big yes and in a sense the reason why it's possible is that the problem allows a greedy approach uh where we very very shortsightedly optimize what the next step is but it turns out that gives you an optimal solution in in this case that's not often the case most problems are not so tame and nice as this but the problem of finding uh character encoding is is such a problem so here's Huffman's algorithm um for constructing such a code we start by finding two characters with the lowest weight okay I'll have an example um one or two slides away we find two characters with the lowest weights uh it could be it could be Tai so maybe it's not unique but we'll come back to that uh and we'll try to make those um we'll try to make

5:58 progress by deciding the code word for these two letters but we leave much of it open we only say that one of the characters gets a code word u yet to be determined But Then followed by a zero and the other one gets the same code word followed by a one okay and U is not known yet but we'll um recursively find that in the end what we do then is we treat a and b now as a single unit I'll draw this uh like this so we we have a box around the two characters but it's it's really just a nice notation uh it's a new letter that hasn't occurred in the alphabet before that we now add instead of A and B so we make the alphabet one smaller by squishing these two characters together and treating them as a single entity because we need a weighted alphabet for halfman's algorithm we have to decide what the weight of this new letter is and it's just the sum of the weights of the these these two letters we combine now we have a new instance of the same problem the same alphabet except for A and B which are gone and this new letter AB which is added and they all have a weight so I can apply

7:14 the same algorithm recursively on this smaller alphabet and because you know I'm taking two characters out adding one in I'm getting smaller So eventually I will terminate um I guess there should be

7:34 when I only have two letters left then I just decide that I give the first letter the zero and this the other one the one arbitrarily uh and continue when I come back from this recursive call I will have constructed a code try for all the symbols in my new alphabet in in particular including this AB squish together and that is the code word that I use for my U so I unpack this U and then I know what the code word for A and B would have

8:17 been from this description it's maybe not clear how to best implement this but it's uh it's easy to uh to do it with a priority que so uh uh greetings from unit two all the way back we looked at that in detail how to implement a priority queue um and if you if you use that here you can say we insert the characters at the beginning into the cube with the weight as their key then this first step can be realized by doing two delete Min calls that always gives me the character with the smallest weight and then um I can insert this new character AB squish together with the new weight um and we'll analyze in a second how how fast that is but let's see an example first to make it concrete here's a small text um the first step will be to find the alphabet all the letters that occur in the text and their frequencies these are given here right you just count um if you if you do this on paper manually you can you can visualize the algorithm by constructing these code tries step by step uh what I described here doesn't really tell you how to handle the tries but if you implement it in a computer it's it's easy to uh it's most

9:42 convenient to build the trees uh the code tries as actual trees with um objects and pointers to the children and that's what with this um illustration here we'll we simulate a bit so we start by having four tries one for each character and they're all boring trivial tries where there's a single leaf and no uh no code words at all because in each of these there's only a single uh letter so what is uh Huffman's algorithm do it finds two leaves or two um two symbols of lowest weight that's those two right and then it combines those two um into this squish together character if you do that at the level of trees these two are the same as before and this one okay let me go back so it's E and O that come together and they form this little this little code try like

10:49 that and notice that the weight is the sum of the weights that's exactly as the algorithm told us to do um and you see uh this last step that we've done here is essentially what what we described here you should have this u in front and then split off as another zero and another one added you can think of this happening when you take this tree and make it part of a bigger tree then you prepend something to all the code words all right but what's the next step we again find the two symbols so here we would have EO squished together as one symbol and L as the other and they both have smallest weights so we combine those two now into again a try that has these two so it's the try for the old symbol for the EO and the try for L which was just this uh the single leaf okay and we just keep going like this now in this example because it's so small that's already the end there's only two things left to combine um so we would do that uh by the way if you you want to represent the entire tree here has now become one symbol and if you just recursively apply my boxing construction

12:08 you can write this fairly concisely it's uh I I like to do it like that on paper because it's very little to write has all the information so it's one one big symbol that consists of the pair where the first is again a pair so you have these nested boxes all right if we do one more step of combining then we have one try containing everything if you want you can again draw the boxes diagram

12:43 instead and note how you can go from the boxes to the tree and back if you want you'll practice exactly that in the tutorials in in a slightly bigger example because PR in parenthesis that's kind of a nice question one could ask in various assessments so it's good to practice that one all

13:06 right if you want to know the actual code wordss you have to try so you can just read those off following the say for example the the code for L right you start reading from the root 0 one so that's the code word but U all the information is basically given in the in the

13:29 try now how well uh did this work for our text for this tiny example first of all if we encode lless then we get this uh so we can double check L was 01 right that's how it starts then we have o 001 0

13:52 01 then we have two s's they all both get represented with just a single one so these are very short which makes sense because s was the most frequent character now you can you can compute the compression ratio of just the coded text uh if you count the length here it's 14 bits whereas the you remember the compression ratio was dividing by length of the source text Times log of the alphabet size and that here works out to 16 so it's it's a compression ratio of 88%

14:33 little caveat is we would have to store the code as well because we're in this in the static world uh and so um I Didn't Do It on the slides because it makes it makes the method look look like it doesn't work it's an expansion in this case because I don't think you can store the code in two bits but that's of course a tiny example of text that's why it doesn't work so well

15:04 now the uh the algorithm I've shown you is highly ambiguous in that um in several places in the algorithm you have arbitrary choice now think about this for a compression method if the encoder decides to do one arbitrary choice and the decoder decides another arbitrary choice they will end up with different codes and then the whole decoding will break down so we have to break the ties um wherever there's ambiguity uh the main things where this happens is when you choose characters you find the two of minimal weight but what if there are five that have all equal weight and all minimal then you could choose from those and when you combine trees the halfman code doesn't care which one goes left and which one goes right it's symmetric and either choice would be fine so U for this for this unit will'll always follow this tiebreaking rules um and let me at least read through them so I highly recommend to practice those for the tutorials uh when you solve the example there um because this is this is one of the places where students in the past often lost marks on the exam very unnecessarily in a way they they were able to compute the right halfman code but they didn't follow the right typew

16:24 breaking rules and then lost part part marks for that so the rules are as follows and they're somewhat arbitrary but we have to decide on some Rule and so these are just as good as any when we select two characters and there's there's ties we always use the smallest uh letters first according to the alphabetic order of the of the letters uh we'll always have some some letters where this is clear uh now if you have a whole tree or a whole code TR of several symbols then the one that has the smallest leaf in it wins okay so if you have a set of characters in in these uh the smallest letter in the box is is the one that determines it now um second rule when you combine trees there's these two options if they have different values then the lighter one goes on the left that's that part okay so if you combine two things and they have different weight the low lighter lighter one goes to the left and when you combine two sub trees with equal value then you use the smallest letter again all right uh let me illustrate this on on this one um there weren't any um so there were only two things left so there wasn't any ambiguity which ones to pick

17:56 uh but which of the two trees to put left um is is one of those ties they have the same weight so we're not taking the the second rule instead we're looking at the third Rule and the earliest letter in the alphabet here is e so that sube goes left that's why it ended up over here okay H in this case all of the type braks are of that type I wanted to keep the example simple but the tutorial example will have uh the full nastiness that can

18:38 happen uh whenever I pose a question that features these tiebreaking rules the question in the exam would repeat the tiebreaking rules so you don't have to learn those by heart I just want you to be able to follow them strictly because that's needed for the decoding all right well let's zoom out again so we found this algorithm that computes a nice code try uh how do we use this overall for a compression algorithm and it turns out you need two passes for half man's code at least in the simple form the first pass is you just go through the The Source text and count how often each character occurs once you've done that you can apply Huffman's algorithm that we've just discussed and that gives you the code words now we also have to store the code in general uh we'll omit the details here because the story is actually longer at that point um I don't want to get into it so

19:43 it's you can you can first compute a canonical Huffman tree if you do this in practice and those you can store with fewer bits so you wouldn't literally use the trees that you come up with I don't want to get into this though it's not adding to the the section if you want you can read up uh on Wikipedia has a good article on canonical Huff trees if I remember correctly and then there's a second pass where we use the code that we've just the code that we just computed and stored to store all the characters in the text that's the only part that we'll do in detail if you want to decode what you encoded uh you have to first get the code uh again won't go into detail how to do that because there that leads us too far uh but once we have the code we can decode the source text by just reading through the coded text and traversing through the try at the same time whenever we find a symbol by reaching a leaf we report that it's the same as we've done in the last

20:47 section uh something that happens often in compression is that the decoding is simpler is maybe um maybe intuitively clear because the encoding step has to do all the hard work the heavy lifting of finding uh patterns in the input that allow compression whereas the decoding has just to read and follow the

21:17 script so far for the algorithm uh now I'd like to show you a bit of the analysis of the algorithm um which also gives us gives us the the more interesting statements about this type of code and the first theorem is is this one um which says indeed Huffman's algorithm is the best possible such prefix free code so if we're given our alphabet and some weights these are fixed then halfman's algorithm computes a certain set of code words and they indeed minimize this quantity I said at the beginning that's what we want but I didn't really explain whether that's true or why that's true and so we'll we'll abbreviate this um L of e is is this sum it's the same sum that we've discussed before and so the claim is this is the minimal uh expected code word length among all prefix free codes for that weighted

22:26 alphabet the proof is by induction again that's going back to to unit one where we discussed this a bit induction over the size of the alphabet it's natural because the algorithm also follows

22:41 that uh against there's um there's the inductive base that I didn't bother to put on the slide if Sigma is um at most two so I have one or two letters then there's actually just a single code

23:07 there's only one possible value for the expected code word length if Sigma is one then technically it's it's empty because it just don't do anything if it's two then we use one bit for each for each letter and that's obviously the best we can do so in a sense the statement is true for all alphabets of at most two letters that's the inductive basis that's how we get started so the inductive step now that's the part that's spelled out in detail assumes that we have at least three letters um and then studies a bit what this uh optimal what this code looks like we're in a proof so this is not an algorithm I can just wish for the optimal prefix free code so give me some optimal prefix free code e Star as a code try that's part of the proof we know that it exists because there's only a finite amount of different code word or code tries so we can always find one that has minimal expected code word length because that is a try there has to be um a note there have to be two siblings at the largest depth I want to briefly um briefly draw some example just so that this is a bit bit more

24:35 clear suppose this is one one possible code try um it always is a binary tree with these little circles as internal nodes but uh each of those has to have exactly two children so if the maximal level of this try it never goes below this depth d uh then um there must be the last last internal nodes are one level above if there was another internal node at this level we would have a deeper leave right so that can't be and if there's an internal node on this level well it has to have two children and they both have to be leaves because we just argue there are no internal nodes on this last level so I can always find such um an internal node on the second to deepest level that has two leaves as children so I could say this is my X and this is my y okay nobody can read this make it a bit

25:42 bigger if you care very much if you wanted to prove this statement more formally you could do another induction on the size of the tree and argue that this is always the case but we'll we'll take it in this slightly more hand w we Pro by picture

25:56 example so we find the these two leaves okay but we don't know anything about the letters that are in these leaves now what we'll do in this in this code try somewhere in the code try there has to be uh two lowest weight characters so two characters with the smallest W they are somewhere in the in the try they don't necessarily recite in X and Y but I can always swap them so that the A and B now are in in in X and Y okay that moves that moves characters around and changes the code it moves code words around but what it does is it makes the two letters A and B have smallest weight so whatever they're swapped with has uh a larger weight so they were F further up here at some point now I swap them down that means I have a higher weight thing that I swap up and that gets a shorter code word so overall the code only gets better by doing this okay that's the key key qu the key argument here by swapping the lowest weight characters into this deepest level I'm only making the code better now because it it already was an optimal code it can't actually change the quality of the code it'll just be

27:18 another optimal code okay and at this point um Let Me Maybe redraw our picture here so we have now a in this and B here and these are on the deepest level have lowest weight and this is part of the of a tree somehow now what we'll do is uh we'll look at a different alphabet and this is similar to what Huffman's algorithm does we take Sigma we take out the two characters here and we instead put in this uh boxed character so I'll take the same

28:13 picture but now instead of these guys um I replace it with one leaf with our boxed character ab and another box because it's a leaf so I replace it with this now I can apply halfman's algorithm recursively on this smaller alphabet and because it's one character smaller I can use the inductive hypothesis what's the inductive hypothesis it's the statement of the theorem which says ha whatever halfman computes is an optimal code try so once I've done that I have an optimal code try for Sigma Prime and now all I need to do is expand that again going from here to here um expanding this by by one

29:04 step and and the last missing piece here is whatever um whatever optimal uh code I start with my uh e star I can transform into one that has this shape that A and B are on the lowest level and could have been replaced with this ab and then this is an optimal code so that means halfman's algorith them finds an optimal code for the overall Alphabet by forcing those two characters together it doesn't actually sacrifice anything and uh if you felt a bit cheated because the proof doesn't explain exactly how this works that's what inductive proofs often are like um but it's still it's still a valid proof the the trick here really is that you can take any optimal code try for Sigma Prime and you can always do this this expansion of of ab to A and B and that always gives you a try for the original