Video 7-4: §7.4 Entropy and Huffman codes

0:00 <Untitled Chapter 1>

0:04 in this section about entropy we will have a look at how we can quantify how well huffman coding will work without running it on the text but just by analyzing the text up front and we'll come to statements that are more versatile than just analyzing huffman codes we've seen half main codes are the best possible prefix free character codes but we'll look at other compression methods later on and so yeah huffman codes are the best of this of this specific family uh it's not necessarily the best overall for all sorts of scenarios uh but entropy gives us a way to evaluate how well huffman codes would work on a given text without without trying it out just as an analytical way

0:50 and so let's start uh with the definition um that's just something that falls from the sky without much motivation at this point but i'll try to motivate it give the intuition behind that definition right after the entropy is defined for probabilities so we have here p numbers they're between 0 and 1 and they sum to 1 so it's a probability distribution so what that means is p1 p2 up to pn sums to 1 and also each pi is between zero and one uh that's well as you as you may have seen in other courses uh that's that's probability distribution where we have n possible different outcomes and the entropy is defined for the distribution so it depends on these on these probability ways and it's just this sum so we sum p i times log of p i logarithm to the base of two and a minus in front or this this is the formula i think is it's a little more intuitive so i would like you to keep this one in mind it's p i times log of one over p i

2:10 so why might it make sense to to make this definition well first of all i've just thrown this definition at you and haven't told you what we'll use it for the idea of entropy is to have a measure of information content now what's the information content of a distribution that's a bit unclear maybe what we mean by that is if you draw a random a random sample from that distribution a single random variable that's distributed according to this distribution and then this variable will have one specific value but because it's a random variable you can talk about expected values and so the entropy gets at the question of the expected number of yes no questions you need to answer to nail down the value of this random variable okay so in a sense if you know this this game of of 20 questions where you ask 20 yes no questions and try to nail down a specific thing that your partner thinks about then this is in a sense what the yes no questions in entropy also try to do so let's let's try to see an example

3:23 by what i mean by this suppose we lay out the probabilities so this p1 up to pn i can draw this this unit interval and i can put in the probabilities here so suppose the length of this that's my p1 the length of this is p2 and so on up to pn because they sum to one this has to go up and cover exactly the unit interval and then the outcome of this random variable is selecting one of these intervals so in the in the picture here there's one of these intervals is red and that's the one that this variable actually took now let's try to figure out yes no questions that allow us to find out which of these intervals was selected and so the best thing you can in general do if you start with um with this interval at the at the start you know nothing you know the red interval is somewhere in the unit interval but that's that's all and so you try to ask a question that with one yes no question maximizes the amount you learn so i guess the best and intuitive way of doing this is asking whether the reds whether the the value is left or right of the middle point okay

4:52 so you ask this question it's a yes no or well it's a left right question is it left yes no okay um in this case it's on the right side and so after the answer to that question you asked one question and you learned now the interval is somewhere on the right of the middle point okay and you keep going like this you cut it in half another time with another question and another time and one more time and then if you know that you remember this picture from above if there were these intervals for the pi if you've nailed it down to this to this range uh maybe that's uh that's all we need and then you know the value that's that's a single interval left

5:40 so uh if the probability here is is this distance um the probability of falling into this red range is the the difference between the endpoints and that's 1 over 16. if that is the probability then this value here log of 1 over the probability is 4 because 1 over 16 is 16 and log base 2 of 16 is 4. now how does this match up this number 4 is exactly the number of times we had to cut the unit interval in half before we arrived at that size that's after all all that the logarithm expresses

6:26 and so this quantity that we sum up here is in a way the number of yes no questions you need to make before you get down to this size it's the number of times you have to cut the unit interval in half before you reach a certain size and this is what we define as the information content of that outcome because it took you so many yes no questions to get there and then the entropy is just averaging that over all possible outcomes each pi occurs with probability p i which outcome i occurs with probability p i and it's it took you log of one over pi questions to find that that's the rough intuition uh behind behind entropy okay that's why this term might make some sense but we'll put it into more concrete context with huffman codes on the next slide

7:30 in in general if we have a random value then we ask how many questions do we need to nail down that specific value and here i identified the value with the position of the of the interval so i label the intervals from left to right one two three up to n and then finding out if the random variable is in one of these intervals is the same as finding if its value is is a value i

7:57 but no matter what the the values really are you can always draw the probabilities as these intervals in the unit interval so uh it seems at least from this intuition that we would like to encode a value i if it has probability p i using log of 1 over p i bits because that was the number of yes no questions we used before um okay so far i can only appeal to your intuition that maybe this makes sense but at least it already is clear that this is not quite possible because log of 1 over p i might be some real number definitely not necessarily integral and so it's a little tough to see how we can spend how we can create code words with length one and a half

8:55 this sounds if you if you think of specific code words there's no binary string of length one and a half but um you can sometimes achieve this on average if you don't have a fixed code word but you have the option to to average things out then you can sometimes indeed achieve this it's something that we won't cover but there's um there's a method called arithmetic coding that is uh huffman on steroids i don't know it allows you to do this to code things with a fractional number of bits uh but yeah we'll we'll leave it with huffman so in huffman coding we cannot do this so it seems like as long as we have a huffman code we have to somehow round up

9:13 Arithmetic Coding

9:43 and that's um [Music] that's also what we see in this result so let's let's parse this step by step we have some alphabet sigma again so we have characters one up to sigma or a1 up to a sigma and they have some weight again think of the weights of as as relative probability relative frequencies or probabilities

10:09 and we have a huffman code so that's the code from from last time i showed you how to do how to compute that one and remember l of the code that was this expected codeword length so l of e oh don't do this to me again

10:41 and what do we sum up the weight of the character times the length of the code word that was the definition of this of this l and now this this theorem says i can look at an entropy so h this calligraphic h is well used to denote entropy as defined here uh now we take the relative weights okay so these are exactly the weights but we divide by their sum and if the weights are probability this probabilities then the sum will be one and this is just the entropy of the probabilities then but in general it's convenient to allow weights so that we can just put in frequencies

11:28 take the relative weights i compute their entropy and it turns out that this is a very tight bound for how well huffman will do how how well the huffman code works for these weights the code is at least uses at least as many bits on average than h it turns out h is a lower bound you can't possibly beat that and h plus one is an upper bound and that comes essentially from the fact of this rounding if the entropy tells you please use 1.1 bits you can't really do that you have to round it up and if you do that rounding up all the time you essentially lose this plus one we'll we'll see that in the proof is the is the statement clear so you compute a huffman code for a given uh an alphabet with some weights and this theorem tells you quite precisely how long on average a code word will be if you take a random character then the expected length of its code word will be between h and h 1.

12:45 uh let's let's sketch at least how we can prove this and there's two parts the first statement is the lower bound that l of e is bigger than h and we will prove this not for a huffman code e but pre really for for any prefix free code because the statement is true for any any prefix free code um if we have a prefix recode e then we can choose weights that again is just the definition but uh it has an intuition as well behind it so the q i are defined as two to the minus the length of that code word and that comes from the idea that each bit you spend in the code words is something like a question left or right and so whenever you spend a bit you should cut down the probability in half and so these qi are exactly defined so that every every bit cuts things in half there's something called crafts inequality that shows that if you do this you get to at most one um and the intuition is if you draw the try for this code remember the code try

13:40 Crafts Inequality

14:04 looked always like this we have zero one more edges zero one and maybe then here in the leaves you have the characters okay remember coach rice huffman codes etc um it was important that the the characters are only the leaves the alphabet symbols are only in the leaves

14:30 and what this says is if you assign a weight of one to the root um and then assign half of that weight to its children and half of that weight to their children

14:50 and half of their their weight to their i think it's clear if you go down one step the the weight on one level is always summing to one it started with one and then you exactly split it in half so the sum is still one and that keeps going and what you can also show is if you take any um cut through this tree

15:21 that doesn't contain two nodes where one is an ancestor of the other then they also sum to at most one because you cover at most one level just shifting things up and down uh the idea here is you could pretend that these go down one more level and then they go all to one eighth okay then no one can read this

15:51 if you go down to the level of the deepest leaf you will have a power of two and that is the number of leaves on that level and those sum to exactly one if you combine two of these into the one one over four their sum is still the same and so uh if this tree is is full if you don't leave out any notes you will actually sum to exactly one and you can leave out some leaves that you sum to at most one all the crafts inequality says sum is at most one

16:24 Gibbs Inequality

16:25 then there's another inequality gibbs inequality that applies here that so this part is gives inequality here i don't want to prove it um but it's a standard result in in probability theory so let's just use that as a block box it says when you have something that sums up to at most one then you can replace in the entropy formula the p is here by the q is there that's gibbs gibbs lemma gibbs inequality

16:54 so we write down the entropy u skips inequality to sum uh over the q i here instead of the pi and this sum is exactly l just written in a different way because here if you plug in what qy is defined like then this one over becomes 2 to the length of the codeword and log base 2 just takes the 2 to the away so what you're left with is the sum of the lengths of the code words times their weights and that's that's the definition of this l okay

17:34 so that's the lower bound and all we used here is that we have a code that is a prefix free code so that we can draw the code try and use craft's inequality

17:44 but it also holds for huffman codes in particular because they're an example of a prefix free code the second part of the statement is this upper bound if you have a huffman code it is never worse than h plus one

17:52 Upper Bound

18:00 for that we do something similar but we will just construct such a code with a similar construction we again define q i's which are similar to probabilities but they're defined by taking 2 to the minus and then this this ideal quantity log of 1 over p but round it up because we can't really deal with fractional bits now if you sum if you if you have a code of that length it's code length it's it's l the expected codeword length is this sum p i times log of 1 over q i that simplifies to this just plugging in same trick as before it's the proper choice of the qi so that log becomes something nice um and here

18:53 not again what we use is that if you take ceiling of some number that's never more than x plus one so if you use that here we have the number is x and then you split the sum you sum up p i times log of 1 over p i that's exactly h by definition and you're left with the plus 1

19:22 and that means what's left is the sum of all the probabilities and that's one that's where the plus one comes from so if we can construct a code where the code words have length log of one over p i rounded up we're good that proves this statement if we can show that huffman codes are never worse than that

19:47 and what we'll do is we construct some code which is not necessarily a huffman code that has these codeword lengths but then we use that huffman codes are the best possible prefix free codes so they can only be better than that code so we construct the code e prime that has exactly these

20:07 log of 1 over q i has exactly these codeword lengths and and we construct this as follows we do this inductively if the alphabet has only two symbols then there's not much you can do you just assign each symbol one bit but in that case if you look at

20:43 um why is that at most one half well the code we use is a single bit so clearly uh the the cost of the code is just one that part that part's clear

21:52 well one of the symbols pi must be at least a half and so um all right now uh yeah this is p i is at most one so one over p i is at least one so log of this uh

22:23 and unless one symbol is exactly never happening which makes no sense so we assume that the pi is strictly less than one so these are at least zero so if you round it up it's at least one

22:48 and so if you take two to the minus this thing that gets at most one half potentially it's smaller and so then log of 1 over q i is at least one if you plug in that that inequality

23:10 good fits together so the the base case is quite easy uh in terms of the code there's not much you can do anyways if you have at least three characters then um we assume that they're that they're sorted by weight so uh a1 and a2 are the least frequent one that's a trick you know from huffman before so we merge those two into one character but now we assign it a new weight which is just twice the weight of the second the second weight so we make the weight a little bigger than what huffman would have used and then recurse as in huffman's code if those two are exactly the same if the frequencies of the lowest least frequent symbols are identical then this does the same as half men but if one of them is slightly smaller then [Music] we know at least this is still summing to one to at most one because it's uh from kraft's inequality again so that means we can uh instead of q1 also use q2 and we still get still getcraft's inequality so there was some slack in in the rounding

24:30 then we use the code that we construct from in from the recursive call there we use the inductive hypothesis to show that this is true this inequality so the the codeword length of this e prime for this for this character is at most one over its weight and the weight was set to 2q to 2q2

24:53 and that you can write as as log of 1 over q2 minus 1 if you pull it out and now if you remember what what huffman did uh if you lump these two characters together and then recurse at the end you have to split them again and add this last bit to distinguish the two characters so that's what we do here uh the code in our the code word in our constructed code e prime for these two symbols a1 and a2 is uh the code from before plus this one distinguishing bit and so the code word for both satisfies this inequality again that we need and that establishes the inductive step so if you take that induction together uh that shows you how to construct this code e prime that achieves um that each code word is bounded by this log of one over qi

25:52 and then we use what i said before so the codeword length the expected codeword length of e prime is this and that's at most the entropy plus one as we've shown above and this is some prefix free code and huffman is the cheapest prefix free code so it's at most at most as expensive as that one

26:14 all right i think that was a long proof um maybe a bit more than a sketch but i thought it's insightful to show these two things and in particular the lower bound i think is is quite nice and clean uh it shows that no matter what you do with the prefix free code the entropy is essentially the bound that you get you can't improve beyond that

26:43 i have a little question for you to wake up and join in it's a quite tricky one so i'll probably want to discuss the outcomes a bit as well

27:33 many people get a few more miraculous appearance of people we're neither in the room nor on the live stream all right um [Music] let me show the results so there was quite a few votes for all of them

28:13 um several are right um but this one not necessarily what is yield more efficient compression what i mean by that is is kind of what's the the best we can show

28:39 so if you compare huffman coding with any fixed character encoding which means uh like some something like utf-8 or ascii where you fix up front what are the code words that you will use for each character and the lengths of the codewords have to be the same for all the characters because both are prefix free codes remember if you have a set of strings that are all the same length they are prefix free without any further further paying attention so even a fixed character length encoding like we've discussed before is a prefix free code and so huffman is never worse so um it's always better in the sense of less or equal it's never worse maybe that would have been more precise um [Music]

29:41 in terms of the the bound that we can show well what we show what we showed about huffman codes is that the the length of the huffman code is at most the entropy plus one

30:03 and if something i didn't show on the slide but if you sum this up and all the pi are the same then this sum sums up the same term all the time then all the p i have to be one over sigma

30:46 so you have one over sigma summed up sigma times that cancels out and what remains is log of one over sigma so that's the entropy if if all the probabilities are the same it's just log of the number of outcomes

31:23 that's what we can always show the the length of this of this code of this huffman code is at most log sigma plus one and so these bounds um because of that plus one it's not quite clear what happens now because a fixed length character encoding is a code

31:53 strictly more efficient needs this condition though so as long as you as long as you don't have this condition you might be just as well you might do as well with the fixed length code as with the huffman code if you have this condition then there's an additional minus one if the entropy is less than log sigma minus one

32:22 then this plus one cancels and then so uh the uh the best you can hope for with the fixed length encoding would be log sigma per character but you need strictly less with the huffman code it's a little uh little edge case in that question

32:48 Huffman Coding

32:48 let's come back to huffman coding for a second because that's something i only verbally said last time so if we encode with huffman there's several stages uh usually the first stage is you go through the text and you count how often do all the characters occur and then you compute the huffman code for these character frequencies and then in the second stage you go through the text a second time and for each character you replace it with its code word uh the constru the the running time for doing that is a sigma log sigma to construct the code if you use a priority queue to maintain the symbol weights so you maintain a partially built co-try and the symbols can be these lumped together symbols right remember these boxes that i drew around around characters

33:47 and they each have a weight and in each step we take out the two with minimal weight that's why it's two deletements and then we do one insert because we combine them and insert the sum again

34:00 uh that's that's where the um so yet sigma times that operation and if you do a binary heap as you've seen in unit 2 you can implement those in in log sigma time

34:14 if the weights if the characters come already sorted by weight then you can actually do it in linear time with a neat algorithm using two cues um but if the if the characters do not come sorted then you somehow have to sort the weights this to some degree you don't get around them that's the time for finding the huffman code and the second part is easier you just need um to go through the text one more time so you need to visit each character in the text and you replace it with its code for that you can just use a table where you use the character as index and then you get it in this time so time to read the input plus time to write the output that's the best one could hope for there

35:04 in practice there's uh different variations of huffman codes in use some comes from the tie breaking rules some comes from the fact that you don't want to do two passes another thing comes from the fact that while huffman codes are the optimal prefix free code they're not unique you can do different ways and so you can squeeze out a few more bits if you decide upfront how you assign code words but this is this is all around the question how do you encode the huffman code and i promise we skip the details on that

35:41 so overall what do we like and don't like about huffman coding it's an optimal prefix three character code and we always like optimal things because that sounds great but you always have to listen carefully and check what exactly optimal with respect to what so in this case it's the optimal prefix free character encoding and it's very fast for decoding you can use this code try and just traverse then you're linear in the number of of bits in the coded text the two passes can be a bit annoying if you want something if you want to do this suppose you're using this in a network router and you want to encode things as they come through you can't wait oh hold back just please scroll back in time and let me read that again you might need to buffer everything and that can be too too costly and also we have to store the code alongside with the text which means if you're just encoding a short text might actually be a bad idea to use huffman codes