Video 7-4: §7.3 Huffman codes

0:00 Character frequencies

0:04 in the next subsection we'll look at the first example of a more interesting code and that's Huffman codes I think many of you will have seen some of these um but I want to give everyone a chance to follow on it's it's a very useful technique that has uh has found its way as a one building block into many practical compressed formats and it's also a beautiful algorithm so where do we come from this is still the part about character frequencies so the redundancy will exploit is that some letters are much more frequent than others here's some some graphic way of representing that for English text and

0:44 we'll always encode to Binary here and most can be generalized are a larger coded alphabets but it's hardly hardly in ever used or hardly ever interesting if we fix the coded alphabet to just binary01 we can use just Sigma for the source alphabet because the source alphabet will appear many many times on the slides so I having a shorthand for that is useful the intuition should be clear half man is a variable length code it encodes it gives one code word for each of these letters say if that's your alphabet um and of course we kind of want the frequent characters to have a short code word and the uh because we can't have everything short you have to assign longer codewords to some of the less frequent characters longer than in an ASCII code but how to exactly do that

1:49 to formalize the problem this is what our input will look like and it's pretty much this table in a general sense we're given an alphabet so what are all the symbols that can occur in the text and waits for these symbols that just represent which ones are more important or which ones occur more often we'll be generic so these are just some numbers assigned to the letters but you can think of them as probabilities in a text or relative frequencies in a text

1:56 Huffman coding

2:19 and the goal is to find a prefix free code that assigns to each of the characters in the alphabet one code word um and it should be a prefix free code so that we can represent it as a try as before and the goal is to minimize this sum which is summing over all the characters in the alphabet that's the length of the code word times the weight that we assign to that character and so if you um the special case and I put this on the slide yeah uh the special case when the weight is the number of occurrences of a character in some Source text then this sum is exactly the

3:04 um the total size of the coded text right each character W uh each character C occurs W of c times in the source text so you will have to write down its code word WC times and it needs length of e of C bits so we're really asking for uh the best possible character encoding of a given text which is I mean if you think about it it's quite ambitious remember all this uh these hard impossibility results about kolmogorov complexity and these things it looked like not much is possible in the general compression sense and now we're asking for is the completely optimal character code

3:54 but it turns out in this case it is possible and the key is that we're restricting ourselves to individual symbols we encode one symbol at a time and that is a much more restricted uh scenario

4:08 it's even better than that it's not just possible it's also a very simple or simple-minded algorithm in a way some it's called a greedy algorithm where greedy has really a technical meaning in that sense it says the myopic approach to take what currently looks best is actually giving you the globally best solution it's hardly ever true in life and it's also not ever not often true in algorithms but sometimes it is and finding half man codes is one of these or finding the optimal length character codes prefix free codes is one of these examples and so Huffman's algorithm works as follows you have all your characters with their weights now you find two characters with the lowest weight intuitively again these are the least important ones so we can we can assign a longer codeword to those two and what we do is we um we take those two and say okay we don't know what they will at the end being coded to they will be encoded to some correct some string U and then I'll use one more bit to distinguish between a a and b

5:33 so I'll I'll decide for now the code word for a will be some string U and Then followed by zero and for B it's some string used followed by one so I can distinguish the two but I I don't know what U is yet okay but I know that the two can now be treated as one so I create from the two single characters from A and B I create this this box character I've used the same notation before right in uh when we talked about suffix arrays so just imagine this as a new symbol that consists of those two together it's it's just um an imaginary thing if you want and we'll set the weight of this new symbol as the sum of the weights of the original one the whole idea is just we need a way to get to this U and the way we'll get there is to say oh these two characters share their code words up to this point and we already decided what happens after it so we combine them into one character and recurse so we call the same algorithm on the remaining characters but we have made the problem one smaller right this uh we took two characters out and one u in that's still a minus one in

6:48 total so if we keep doing this we will eventually end up with a single character and then we can stop let's talk about how to implement that after the example so here's here's an example um and I'll do it like we will essentially always do it in in this module we'll use as weights the frequencies in a text so we start with the source text lossless it has just these four characters so I'll assume we just need those four and I did the counting for you so these are this is the starting point and now remember what Huffman's algorithm did it said try to find two characters that have minimal frequency so in this case uh that should be these two they're both of minimal frequency one in this case and then I lump them together now graphically you can nicely represent this as a little code try and the other ones can also be seen as simple code tries they're just single leaves so there's not much much to them but once we combine those two these are the ones with the minimal leaves then we decide one is the zero child one is the one child and we create some internal node we don't know the path to the root from this yet

7:03 Huffman's algorithm - Example

8:15 but we'll get there recursively and we assign this this one as weight the sum of the weights of the children okay and now we keep doing the same thing so the next step is again find the ones with minimal weights well it's these two and so again we combine those so we create a tree that has children the two notes from before or the two sub trees from before in the general case what we get is an entire tree here and so here we combine those in the same way one gets the zero child one becomes the one child and we create a new internal node with again some unknown path to that but we'll just leave it as that for now okay one final step there's only these two left so not much choice so we combine those so again you see this was the sub tree from before this was the other sub tree and we just combined them like that and that's the half main code now one thing I skipped was about the implementation uh how would you implement this code using data structures you've already seen so that it runs fast uh the the potentially expensive part is this where you have to find these two characters of minimal weight

9:39 but we've seen exactly the right data structure for that and namely your priority queue if you keep all the characters in a priority queue you can take do extract Min twice that gives you the two characters with currently minimal frequency and then you create this new box character and put it back in the priority queue with the sum of the weight as its priority and that way um you can do this step in

10:13 log Sigma time Sigma is the size of the alphabet it actually gets faster over time but the first time it takes log Sigma um and similar so the insert here

10:27 also takes lock Sigma timing in our priority queues um and so the recursion itself you can unroll that into a loop if you want I think the example showed that quite clearly so you're doing this overall Sigma times until you end up with just a single tree so the total time will be something like Sigma log Sigma

11:09 we also call this final result the half man tree for I guess obvious reasons uh it's just the code try for the Huffman code that the algorithm uh generates anyways and that contains pretty much all we needed we can then use this to compress our source text so if we do this um well I didn't put the table here but you can find this the code word for l is zero one the code word for o is zero zero one and then s gets the shortest it's just the one and so on so you get this coded text from our text loss list and then you can compute the compression ratio as we defined it last time so it's uh eight characters in The Source text and we have four characters

12:10 uh in the source alphabet so that gives you this eight times log four for the size of the source text and if you do the counting here it's 14 bits in the coded text and so you get a slight reduction in space it's not super impressive because the string is so short um but at least it's uh it's shorter than the trivial way to represent it

12:41 Huffman tree-tie breaking

12:47 okay a very important slide for all the application problems on exams and class tests and so on um I have to see if I can put maybe uh okay I'll check this offline the procedure from above is ambiguous in various ways if we have several times if you have ties for what is the lowest weight it's not clear which two we should use and when we combine things there's a symmetry in which one is the left and which one's the right sub tree it all doesn't really matter that much the code will have the same length but it's a different code because if you swap some things in the tree around you swap a zero and a one if you combine things in a different order you get slightly different code words so uh do me the favor and memorize or uh well I always if there's a problem like this on the exam we will always reproduce this box but uh train yourself to um obey these rules so that you always uh get a unique result that makes checking those much much easier and so I'll require you to use that rule when we select two characters for the minimum then if there's ties we'll always break the ties by the alphabetic order so if

14:06 there's ABC and they all have weight one and that's the minimum weight you don't take C and B you take A and B because they're smaller in the alphabet that's the the first one now if you have a whole tree you take the smallest alphabet anywhere in the tree the smallest symbol anywhere in the tree if you have two trees they might be incomparable otherwise but you can always find the one that's earliest in the alphabet second rule is when you combine two trees uh and there is one that has a smaller weight than the other you could put the one with a smaller weight to the left again somewhat natural but you could do it otherwise and for the last case when we have two trees that have the same weight then again you put that that one left that contains the character that's um the smallest in the alphabet

15:07 okay so these three rules make the algorithm ambiguous unambiguous it takes away all the choice and means whenever you have weights you arrive at the same result you've seen how to construct the Huffman tree and the code from that if you want to apply that for compression you need one thing on top of that you somehow need to get the frequencies of the text the character frequencies so the overall encoding has two phases the first pass over the text counts how often each character occurs then we can construct the tree with the algorithm you've seen using our priority queues and all that uh but then we also have to somehow store the Huffman tree or the the code that we get from it because the decoder needs to know what the code was was look well what the code was like to decode and the decoder cannot use the character frequencies because it hasn't decoded the text yet so we have to store the tree in some way now we'll not discuss how to do that in a smart way uh it leads us too far a simple way would be to just write down all the code words for the symbols in alphabetic order it's not the it's not impossible but you also have to

15:22 Encoding with Huffman code

16:36 say how long they are they're slightly smarter ways using the tree structure but we'll never do that in detail so you don't need to worry about that for now I just want to mention if you implement this in practice without anything on top you need to somehow store the tree now and then only in the second pass you do what we've seen on the slide where each character you produce the code word without preparation you can decode by first reading the description of the Huffman code then you know how decoding works and then you start reading from there using the decoded half of my code

17:20 and you may notice that decoding here is is simpler because you do a single pass you don't need counting first and then encoding that's a quite typical thing for many more interesting compression algorithms the decoding is much easier and intuitively speaking I think that's quite obvious uh the encoding has the tough job of you give you're given some text and you have to find patterns redundancies to compress that's the hard task the decoding is just reading the description and producing what what's written there that's pretty much following a script whereas encoding is writing the script from from The Source text so we often need more more effort more time for the encoding part

18:10 Huffman code - Optimality

18:16 let's spend a little thought um again I'll go over this fairly quickly but uh let's talk a little bit about why Hoffman's algorithm is is giving you the best possible code I've so far just just claimed that it does but pointed out that it has this absurdly myopic point of view what it did is that the low weight character the load rate characters should probably get a long code word so let me just take the two with the lowest weight and lump them together and decide that they get the same prefix why on Earth should that be really the best possible way maybe there's a much smarter way it turns out now let's see why so this is um the formal statement says if we have an alphabet and the weight that was the input for Huffman's algorithm then we the outputs of Huffman's algorithm namely these code words give us the minimal expected codeword length so that's the sum over all the characters that we've seen before weight of the character times the length of the code word

19:27 and we can prove this by an induction over the size of the alphabet which essentially follows the structure of the algorithm as well and I only really show the inductive steps so the the basis is you have two characters if you have just two characters there's really nothing else you can do than assigning one the length the code word zero and the other code word one and uh that's the only code so this is the best code it's kind of uh not very interesting but it's it's true that half man produces this code if you started with two two letters but the inductive step we assume we have some alphabet size uh greater two and then um

20:27 we'll start with an an optimal prefix free code that we don't know what it looks like but we know there is one um we can maybe construct it but uh from from a proof perspective we could just assume that it's it's given to us and we'll we'll argue about it because this is a code try just from the structure of the tree there will always be uh two siblings at the largest depth now what this means there's there's some path so there's the height of the tree

21:03 and there's there's some notes that look like this two leaves at the lowest level the reason is just uh it's a complete binary tree we can't have a single leaf at the lowest level uh that just wouldn't be complete you always need some other sibling and that can either go even deeper or it can stop but if that's the lowest level it has to stop and so we have to have some node like this and then there's some X and Y at this depth d

21:40 that may or may not be the two characters that Huffman's algorithm combines in the first step and in particular it could not be but if we have [Music] um

21:59 okay I have different notation for the notes and for the characters in the notes so maybe I should make these a little bigger and write a and b inside

22:14 so what's inside the leaves is the character that's represented there and the node itself is called um X and Y if we have some Leaf that's further up and suppose A or B would have been up here then there would be some other character down there maybe C that has larger weight than a if I keep the rest of the tree the same and swap A and C what would happen in this sum I would move C further up so it gets a smaller weight and I move a Down so I change the sum only by these two terms but the weight of C is larger than the weight of a so I only get a better code if I do that

23:14 so moving to this situation where we have a and b in the lowest that didn't copy only makes the tree better we had that before right that's what this says if I make this change I would only make the tree better but because it was already optimal it has to have the same same cost

23:59 that means I can always put the two smallest weight characters in these adjacent in these sibling leaves at the lowest level without making my code worse and so I might as well combine these two s Huffman's algorithm does so formally if I take any optimal code or the alphabet where I remove a and b and put in this this combined character I get something like this tree on top with the leaf here with a and b if I take that code and unfold It Again by replacing a b with this little cherry tree an internal node and two leaves then I get back a code that has the same as same cost as my e star and so it has to be also an optimal tree

24:55 and that's that concludes the inductive step what we still need to show is that uh Huffman's code finds such a tree but that's by the inductive hypothesis if we go to one smaller I said here let's take an optimal code for this smaller alphabet but we apply it Huffman's code now on the smaller alphabet so by the inductive hypothesis which we prove bottom up we already have the statement for that smaller alphabet so we can apply Huffman's code to find this optimal tree for for Sigma Prime doesn't have a name