Video 7-5: §7.4 Entropy and Huffman codes

0:00 <Untitled Chapter 1>

0:04 in the next section I want to make the second statement about Huffman's algorithm it gives an optimal prefix free code but we can also say how long that code is in more absolute terms and that will involve the information theoretic entropy the the term has a history and it comes from from physics but not nothing of that is is really needed well we just borrow this this at this word the entropy is a simple quantity for us if you have probabilities some numbers that are between 0 and 1 and sum to one the probabilities for some outcome of a random variable say a DI with n sites you can Define the entropy as as this sum the the last one is the one I find more intuitive it's the sum of all possible outcomes and then you take the probability for that outcome Times log of 1 over the probability uh let me motivate a little bit why that might make sense

1:10 um or maybe you could do one one tiny example first if we take a standard die with six sides and suppose that it's fair so we would have all the pi are P1 up to

1:37 P6 they're all one over six then the entropy of this um distribution is this sum but the sum is always summing over the same term so we can replace that by six times and then p i is 1 over 6. and log of 1 over 1 6 is log of 6. and so that cancels out as log base 2 of 6. which is uh something between two and three

2:15 now that's just some definition and some numbers uh the intuition behind this formula is is given by this um yes no question game or 20 Questions game your goal is to guess what is the random outcome of a random variable it can take values between 1 and n and you have to find out someone someone rolls the die and you have to find out by asking yes no questions to that other person what was the number you got and uh because you're smart you do this in the best possible way which is you always ask a question so that zero and one yes or no outcomes are equally likely

3:05 so for example um the outcome that we have is has a probability that lies here so um you you lay out all the pis foreign to one you have an interval that's as long as P1 is

3:29 then comes P2 I don't know maybe a bit longer that's P2 and maybe two more P3 and P4 it always has to work out like this is the probability distribution so it has to sum to one and now may you may know this you can generate a random output from this distribution by taking a uniform random variable in this range and outputting what interval it fell so maybe the random number fell here and then you would say oh that falls into the interval for four so I output 4.

4:09 let's imagine that this is what happened here as well and here's one one outcome that's the interval of Pi and your question is how do you find out that this was the random outcome you don't know it you ask your friend so the first question you ask starts with the entire interval and asks is it in the left or right half that's the best you can do because it's equally likely to be in the left and the right half so with one question you can narrow down the range from the full unit interval to half of that and your friend will tell you which one it is and then you just keep going you cut this in half again cut this in half again cut this in half again until uh your friend has to say or I mean you know you know the picture I drew up here the distribution is known to you so um if you want to find this point it's enough to say oh okay it's contained in this range then you know the output was four because this all entirely contained within this P4 interval

5:22 so at this point you can stop here and you only needed four questions and if you count how many times you have to cut in half before you lie inside this interval you get to essentially this log of 1 over pi there's a bit of rounding involved if it doesn't work out nicely like in this case that you get exactly the boundaries then you may need one or two additional questions you can always get away with one more at most but the entropy says Let's ignore the rounding suppose you can always make your questions work out to have the exact um the exact right place then you would need log of 1 over Pi questions and so the total sum is the expected number of questions you have to ask that's an intuition for the entropy

6:21 now how does that connect to compression and half man codes uh the decoder basically asks the same question the decoder wants to know what's the next letter and it asks you questions of yes or no type am I in the left or in the right half of the Half Men tree that's sitting at the root and you have zero and one and he keeps asking questions until it has narrowed down one leaf that's your that's your letter so it's not so far away from that really

6:59 so what does that have to do with Huffman codes if things work out nicely we would like to encode something with that probability Pi with log of 1 over p i bits but that number may not be an integer so we can't really do that but we can prove the following if we have an alphabet with weights as before the input for Huffman Hoffman computes some code words e they all have integer lengths because they're actual bit strings then this L of e the expected codeword length the average weighted over the weights for the characters it lies always between the entropy and the entropy plus one and so it's it's very narrowly uh sandwiched between these two bounds and the entropy is um if you define characters to have probabilities so you take the weights and normalize them by the sum

8:05 um I don't want to prove this formally but I want to give you the key ingredients and this is something often done in undergraduate classes the first bound is you can't beat the entropy so the what halfman spits out is is at least as good as the engine is at least as costly as the entropy says

8:27 um and the the key for that is to use crafts inequality which means whenever you have a code try then if you sum up [Music] um the these numbers the length of the code word as a negative exponent of two which is the depth in the tree if you want that's the length of the code word then that sum is is equal to one in a in a in a proper code try so for example in this one

9:08 you would start with one at the top level then you cut it in half if you go one level down you split the one once if you go to the next level you split it in force and one of the force is staying here so you have one quarter weight that's used on this on this rightmost leaf and you go one level further down now you're at eighths you cut it in half again and so we have one eight four times here if you sum that up uh you should get to um one if you add the other leaf that I forgot there's another quarter if you always make the three full so there's no gaps like this one had a gap that's not good if you add that in two times a fourth and four eighths that's one that's craft inequality and the second Gibbs inequality is uh an analytic property of the entropy if you take this formula for the entropy and replace this Pi with any other numbers that sum to at most one then you make this sum bigger for that you'll just have to believe me for now it's it's simple to prove with just um uh [Music] um the slope of the logarithm logarithm is is a concave function

10:30 if you insert what we know now this is the entropy and this turns out to be exactly the code length of the the QI are the code lengths in the half main code so if you um insert this here you see it's just canceling the two the log and the two to the minus cancel then you get back to the sum for the half man code so that's that's that part halfman codes are never better than the entropy and the other part is they're never worse than the entropy plus one for that you you do something that Half Men could do so you take log of 1 over Pi which is the ideal length but it could be in an any real number so you round it up and you can show that there's a code that has these lengths as the code word lengths if you do that you end up with at most the entropy plus one because rounding up gives you at most plus one and you can construct the code for this um basically using using this procedure I think I'll skip the details here because we're we're a bit short on time and we don't build on this later so if you're curious why that that's true uh you can read the details up

10:59 Entropy and Huffman codes [2]

11:55 we won't really need it what I wanted to take from this so though is the the meaning of this theorem earlier for the attendance code I don't know if if you still voted let's let's wait for 35 at least

14:26 there we go um okay it works so I think in a way the third answer is not quite correct but uh this is a trick question in the sense that it depends how you exactly interpret the question

14:45 um let me go back to where I can write the first one is not wrong in the sense that we're we've just had this proof that half man computes the best possible prefix free code it turns out that any fixed length code is also a prefix free obviously because if they're all the same length nothing can be a proper prefix of anything else so half man codes are always better than the prefix free code in terms of the expected codeword length so if if you mean by more efficient compression the expected codeword length then Huffman's Huffman codes are never worse than any fixed length code in the same interpretation if the entropy of of the character distribution is less than log Sigma minus one then even after adding the plus one which was the the best bound we could prove we're still strictly better if you're in this range where the entropy is just strictly less than log Sigma you may be better or you may not depending on where on the scale the the expected codeword length could be between H and H plus one if you're closer to the h plus one part but H is just slightly less than log Sigma you're not really no you're not doing really much better now in a way

14:50 Clicker Question

16:15 yeah if you look at this more closely the fixed length codes would all would also not achieve log Sigma but log Sigma rounded up and whenever log Sigma rounded up is close to log Sigma also half man would be close to that all right um in a way there's not too many wrong answers uh but that's maybe something I didn't point out the entropy is at most log Sigma that's just because um now it's not not completely obvious I this this sum that the entropy has uh is a song with with the concave function and so it's maximized when all the arguments are the same so the entropy is maximal if the distribution is uniform and then the we see we've seen the example with the fair die where you had six outcomes and the entropy was log of six and the entropy is never bigger than that but it could be close to zero

17:29 if the entropy is very close to log Sigma then Huffman codes won't help you that much if the entropy is much much smaller say for example like this then you definitely save with a Half Men code

17:43 Huffman coding - Discussion

17:46 all right um putting that all together so what we've seen before already the in the discussion of the code Sigma log Sigma is the implementation with the priority queue where we use a heap binary Heap and more precisely we have to build that initially from all the alphabet symbols and then for all iterations we use two delete mins and one insert now there's some a useful special case if the alphabet is already sorted by weight for some reason or because you've made it so once you have that you can actually do do it faster you can do it in linear time using just two cues it's a cute little algorithm to figure out uh just leave it with that comment

18:40 once you have the Half Men code or the code try constructed the time for encoding the text is essentially just as long as you need to read the text you have to read every symbol and then you have to write the output but you can prepare this this codeword table so that each character is a constant time lookup

19:06 um the key algorithm is is like I presented but there's many variations you can use the type breaking rules is one where you can go in different directions uh the way how you get the weights can be different you can as we did you just count exactly how often each character occurs um there's there's cheaper ways where you just try to do to to Guess that and there's ways uh where you're adapting so you say you just keep counting but you already encode the character at that point so at each step you use different ways you use the weights up to that point and you can have with a different algorithm much more complicated than the simple one we've seen you can keep the Huffman tree up to date while you work work your way through the text

20:01 what's good about Huffman coding we had an optimality statement is always great it's the best possible but it's the best possible in some specific sense I stressed this many times in this module whenever someone says optimal be a bit careful what exactly that means so here it's the best possible prefix free character code but it's very fast and so that can be very convenient one downside is that it needs these two passes over the text in the version that we've discussed um and another downside that also refers to this last slido question if you factor into this that for a half main code you have to also tell the other side what code you used it's not so clear uh if it's a big win only for the for long enough texts

20:54 why for the fixed length period of code you also have to tell the other side which ones you're using but it's a downside of Huffman codes you have to tell the decoder what the code looks like