Video 5-4: §5.4 Entropy and Huffman codes

0:03 in the next sub SE section we'll talk about entropy is a somewhat um misl well misunderstood notion poor entropy has too few friends but you can't really talk about compression without talking about this this notion of information content uh and the context of Huffman codes makes it very concrete I think uh so let's let's dive a little bit into this the formal definition of entrop p is is given here uh what you have as as the input is a probability distribution yeah discrete probability distribution where you have n possible

0:48 outcomes any uh anything we should discuss in the plenum if not let's discuss entropy so we have something random a random variable that has n possible outcomes here just the the numbers one up to n and they have different probabilities and the meaning is the outcome to have value I is happening with probability Pi then we can Define this this mysterious Mo notion of entropy as as as this often denoted by H and it's it's this sum or a bit I think this is the the better one to keep in mind because it has uh more intuitive meaning that I'll come to but now it's just the definition okay uh so what can we say about this if we have n suchar

1:37 probabilities it's always at most uh log n and it's at least zero because this is or you can figure out p i are all between zero and one so because these are probabilities right um then of course Pi is in 01 some real

2:04 number um you achieve the maximal entropy of all the equal they're all one over n that gives the maximal entropy but okay I don't want to bore you with a list of of properties of this notion before we discussed why it's

2:30 useful the way why we uh why we studied this in the compression chapter is that entropy is a measure of information in a distribution so it's a bit awkward to talk about information in some random process but think of it as as this um you're hiding an interval somewhere on the unit interval so you pick some uh some little interval that lies somewhere and my task is to ask yes no questions as in this in in this game 20 questions to nail down what interval you've picked okay so what what could I do um to uh find your interval initially I don't know where it is um all I have is that it's somewhere in the unit interval so my my uh area of uncertainty or the area of possibilities is the entire unit interval and then I'm going to ask you a question namely is your point that you pick from your interval is that to the left or to the right of the one half mark and because you're you're picking something from this red thing in your case but I don't know um but you say it's to the right okay so with one question I have cut my area of uncertainty in half and of course I'll just keep doing this if I ask you again

3:53 the middle of of this range 3/4 Mark and you'll say okay it's left of that so so I'll reduce it to that part another time you say it's to the right of 58 and so on and then okay at this point we'll uh we'll stop the game and say okay you you found my range uh all the numbers I've chosen are from this range and I needed four questions for that so the the the way to think about it is if your interval has a specific length that's what counts for the number of questions you need the interval here was lying was the the interval between 116th up to 3/4 and the length is 1 over 16 and because that's a negative power of two you can um nicely write it as log of 1 / p is 4 log of 1 over 16 is log of 16 that's four so all the all the logarithms here are base two it's a computer science class right uh also here these are all base to maybe it's worth writing down

5:05 again good so in a way this this term that pops up here also is the term that pops up here and you can work out that this doesn't work just in this example I gave you um it works for other other intervals as

5:25 well so the way to intuitively think about entropy is it's how often do you have to cut your your unit interval in half before you found this this red interval and the answer is log of 1 over pi times now I've chosen nice numbers here so that it works out precisely and without any any fudging um in general because we can do this with randomization you can still achieve it uh but maybe not with such a simple strategy but the the the notion to keep in mind is it's the expected number of of these yes no questions that you need to nail down a random value from that distribution okay that's that's what entropy uh intuitively means what does that have to do with uh information content uh there's nothing random in a string right which're is starting with a text we will come back to that uh but first let's let's look at um the connection to halfman codes if I have uh an alphabet and probabilities so I'm not looking at a fixed text for the moment I'm looking at encoding one symbol at a time and the symbols are chosen randomly but with given probabilities for example you roll a dice each time you want to uh send some you want to have a next letter and

6:51 whatever comes up is your letter uniform between one and six if I have that situation I would like to send the letter I the outcome I of my random Choice with prob with uh which happens with probability Pi I would like to send that using log 1 over Pi bits because that's what the entropy tells you you should need you shouldn't use more than log of one over Pi yes no questions each yes no questions can be stored as one bit so that's the number of bits you'd like to use uh but of course that can be problematic because this is a continuous function it need not be an integer might be a any number like 1.5 so if we want a code word of that length good luck that won't work uh we can still do that in some average sense but that's um that's beyond the today beyond the section

7:52 here so um if you start with an alphabet Sigma and probabilities for the letters and remember we defined halfman codes for any weighted alphabet but probabilities are fine weights they just additionally happen to sum to one so I can apply halfman's algorithm on this alphabet with the probabilities as weights then I get a code u a code try out which has a certain expected code word length L of e and then I can prove that this lies between the entropy and entropy plus one so I have very precise sandwiches sandwich bound for how long the expected Cod word length in this case is for the halfman code in terms of this entropy of the probabilities that we start

8:51 with to prove this we have to prove the the two inequalities this one and this one we'll do this this one first so whatever comes out the expected Cod word length is at least the entropy that's kind of alluding to what I said intuitively before the entropy is this uh best possible number of questions then halfman's code shouldn't beat that shouldn't be able to get better than that the formal proof would work like this um whatever prefix free code we have so we don't even use that this is a Huffman code we just use any prefix free code we can say that induces some weights on the Alphabet by using the code word length so we take the length of the code word for AI but then we take two to the minus that length so the longer the code word the smaller the probability to see that letter okay which makes sense halfman gives shorter code words to more frequent characters um now there's a a thing called crafts inequality which says if you have any prefix free code and you take its code words and do this kind of Weights then these weights sum to at most one and the the reason is very simple so

10:18 for for crafts inequality suppose you have any kind of um code try what it says if I take all those leaves and I assign them weights depending on their depth so these are depth two so it's a quarter this one as well this one's front further down so it's 1 over8 and these are even one further down 1 over 16 and the claim is if I sum up these numbers it's at most one now you can check this in the example fine it will be exactly one but why is this is this is true in general well you can go level by level you start at level one we have a weight one to distribute from the root downwards and we say 1/2 goes here one2 goes here so at this level I have 1/2 on each of the internal nodes or leaves if I have some and you keep repeating this process now in each step you're going to at most double the number of nodes that are still alive and some of them consume this but you'll always have exactly this this length left to assign to each leaf that you meet along the way but you started with one so you never make you never uh create weights from anywhere you just

11:44 pass them down that's why the sum keeps um at most one all right you can uh look at the proper proof on Wikipedia if that was too quick so we have some weights for these letters and and they're summing to at most one the second step is Gibs inequality which is is really just this middle part when you have one probability distribution so some pis that sum to one and some Q's that sum to at most one then this is the entropy right this the same term that we had before summing over all letters Pi log of 1 over Pi then if you take the same term but you replace inside the log the P by the Q you only make this whole thing bigger that skips

12:36 inequality and the proof is fairly boring it's just a an an analytic arithmetic proof of using using the derivatives and so on is uh it's not insightful so I'll I'll skip it and that's all we need so we start with our entropy write it as the sum use Gibs inequality with which relies on on this inequality from crafts inequality and that is exactly the expected Cod word length because these Qi are negative powers of two so if you um if you wanted to spell this out one over Qi well this one is log of 1 / 2us e of AI

13:26 length one over and two to the minus cancels right so it's log of two to the length of e of AI and now log into the power of cancels right

13:44 so we're left with this and that sum sum of Pi times the length of the code word that was the definition of the expected code word length so it's it's basically all falling in place that was that part we still have to prove the upper bound so we now know every prefix recode uh has expected code with length at least the entropy that's also true for Huffman because it's one prefix free code the other direction is only true for Huffman's code um but we'll we'll show we'll show it in an indirect way again so we now have to show that uh whatever Huffman's code looks like its expected code word length is never more than entropy plus one what we'll do for that is we we'll construct a totally different code but it will be a prefix free code and then at the very end we'll use that Huffman's code is an optimal prefix free code so it must be at least as good as that code that we

14:52 constructed how do we do this um we start again with setting our qis but this time we start with the probabilities so um you can you can interpret this as rounding the pis to powers of two negative powers of two right we take 1 over pi and the log of that that's rounded up and then 2 to the minus of that so that

15:23 is is roughly again Pi but it's rounded to the nearest uh what is it smaller ative power of two right it's it's rounded to the it's rounded up but then it's a minus in

15:50 front Okay um now if we insert this into our computation um if we pretend we had code words of those lengths that would be the this L of e and if you simplify that it turns out to come out at H + one why do we have the plus one well because we we round up the log here so that's at most log of 1 over Pi I + 1 and then you can pull the one out of the sum this the pi sum to one that's where this plus one comes from

16:30 so what we have to show is that there is a prefix free code e Prime where the code word lengths are the qis or at least they're upper bounded by this that's enough okay let's reorder the characters so that life is convenient so that the the ones with the smallest Q come first let's just renaming and then we'll construct this code by induction if we have just two letters then we'll assign a single bit there's only one such code we'll assign a single bit to the two characters because these are sorted the Q

17:15 um uh q1 at least is is at most one2 and so well ah they're all at most one half because they're off this form I was I was struggling to see why in general but because um what whatever probabilities you R you start with um they're all between zero and one and so if you round down to the next negative power of two then one2 is the biggest you can have so that's correct um and if you calculate that that's uh one over at most one half so this is um at least log of two which is one and that is the length of the code wordss so we've shown this part is true for two characters okay the uh Cod word lengths are at most log of 1/ Qi for both of those that's the inductive basis for the inductive step we look at more more letters at least three now similar to halfman but um slightly different next step we we take the two with a smallest weight these are these are these two right they're sorted A1 and A2 have smallest weight I'll replace them by their boxed variant again and assign it not the sum of the weights but something different two times the larger weight so that sounds sounds strange but um that's what you

19:04 have to do if you if you take the lengths of the code words they both get the the the length of what comes down plus one bit each all right there's two cases if the two Q's were the same anyways then this is exactly what Huffman's algorithm would have done otherwise q1 is the unique smallest value and that means we can ALS so bump it up to Q2 and it still sums to at most one and the reason for that is um again a little picture proof if you allow me um all of the q's are powers of two so we might have one one one2 maybe uh then there is a few one over8

19:53 and maybe um okay now I'm not drawing this nicely this should be like this so I have I have that one and this and this and this and then maybe the smallest is is just 1 over 16 so if I start with from 0o to one the entire length I might have used up 1 12 and then 1 over8 1 over8 1 over8 these are my q's and then 1 over 16 so the situation we're we're we're saying here is q1 is the smallest and it's the unique smallest there's no other equal value then no matter how I choose the others if they sum to one before with this Q I can double q1 and it still fits in this in this uh strip because the only way how it can be smaller than the previous one is it's cut at least in half so I can double it back in I half the space for it if I had the space before I have the space after so what this means is we can we can use this this uh double the larger value instead of this taking the sum and it's still a valid probability in this in the same sense and of course these um 2 * Q2 again has this shape of being a negative

21:16 power of two which wouldn't have been true of the sum then we apply recursively algorithm to the smaller alphabet weighted alphabet so we get some some code word back that satisfy this by the inductive hypothesis that's spelled out here and uh so what does that mean here the new Q for this box letter is 2 * Q2 and the factor two in the log just gets pulled out as a minus one factor

21:51 one2 what does that mean for our final code so we construct the code words for A1 and A2 as the code word for the Box letter plus an additional bit at the end for the 01 distinction so they're just one longer and that means they're both bounded by their respective

22:10 qes all right that's the end of the induction that means we've proven this we found a code where each code word is bounded by this thing and uh as we've calculated up here the expected code word length of a Huffman code is better than any code Cod any prefix fre codes expected codeb length so it's at most L of e Prime expected codeb length of this code and this codee's expected code word length is upper bounded by by this sum so that's just sum over the pi log of 1 over Pi but we've shown the length of length of these sorry that's sum of Pi length of the code words

22:59 and then we upper bound this using our result to that and that was upper bounded as H+ one that's a bit of a lengthy calculation in Pro uh I understand um apart from this little step in between that I waved my hands a bit about we've been fairly formal um and it's it's a nice constructive proof as well because it's it's not just a statement about about this uh about these quantities because it gives you a concrete code as well um maybe constructing it on an example is is helpful let's wrap up this part with a little bit of uh interactivity we've had very little of that today

23:49 um this is not specific to The Last Theorem this is zooming out overall so the entire thing um and you're you're asked to read carefully again what I mean by a fixed length character encoding is just something like aski you're you're given the same number of bits for every

25:24 all right we eventually had 130 people on the attendance code so there's a bit of a a gap still certainly none of them will have just locked the attendance code and then switched

25:48 up I think we have a record number of people streaming or or using the live stream today so the room's not so bad guys it's quite cozy and nice but yeah I get the rain was not fun

26:14 par I know um I don't get to choose the rooms um to be frank I mean I didn't get much to say much of a say in this I'm not I'm not a fond of the South Campus one uh but we'll we'll we'll be there tomorrow right

26:31 so yeah exactly yeah yeah that will stay uh okay it's so 100 people voted uh we can continue moaning about the rain and and the rooms later uh let me show you results allowed several

26:52 answers so it's a bit of it's a bit of a trick one so the the third one I'll I'll comment on it um again like you you keep doing this you keep changing your answers you're only you're only cheating yourself um I don't so first of all it's all on record so I can go back and see what the distribution was it's just not so convenient right and secondly you'll not be you'll not be marked for um uh for the right answer just for playing along but um yeah if it makes you

27:37 happy all right um so I put always uh because in a way a fixed length character encoding is a prefix free code right if I if everything's of the same length nothing is a prefix of something else uh and so any such fixed length encoding is one prefix recode and halfman always gives you something that's at least as good right so if you interpret more efficient as lesser equal then you could say always because it's an optimal prefix free code if you're more strict and uh you interpret more efficient as strictly more efficient has to be strictly better than than this not just equally good uh then the right condition would be well the a sufficient condition is this um sometimes this condition is enough but maybe not always uh for [Music] example uh for example a stupid example would be just two letters there's only one code signing zero and one but the entropy could be slightly less than one uh but it won't be less than zero right um and you get similar situations if Sigma is close to or is a power of two and the entropy is just below that it might be that the Huffman code is the same as using fix length carting codings whereas if this condition is satisfied

29:16 if your entropy is log Sigma minus one then halfman definitely gives you a strictly better result all right guys I just want to make sure you don't miss the second part so um even in case you've seen this before uh this is something that's not not always discussed I want to come back to a single text so we're in the compression chapter and I talked at length about entropy as this probability of a pro this property of a probability distribution but there's nothing random in a string we're just given one string but there's a notion that ties these two things together and makes it um makes it round again uh we can we can take a fixed string and Define something like probabilities by taking the the relative frequencies so you count how often each letter occurs and divide by the length of the string if we if we do that for some for some text um and use our halfman coded um length of the the the coded text what do we get well we can reorder as I said before we sum up all of all the characters how often does each character occur how long is the code word for that character and I can rewrite that as n * this sum and that sum is close to uh the

30:48 entropy but it has this term so uh I mean I've just smuggled out this Factor n here and then I have a p I here the the probabilities I've defined even though there's nothing random so I can say the compressed text size is n times this expected code word length Okay that's essentially just by definition um but then using the theorem that we spent um some time proving we can say that this this length of the coded text is bounded between an entropy and an entropy plus one time n well the entropy is is this is the entropy of these probabilities okay it was a bit long long-winded but um this notion is called the empirical entropy of a string and that term I want you to remember uh because that's that's a useful notion if you're given just a string um coming back to korov complexity uh We've we've already said okay how how much can you compress a given string it's an somewhat unknowable task because you can't compute it color complexity the ultimate compression would be the shortest program producing that string but we can't compute that so what other measures of this string can we Define so that we can compress it but things that are a bit simpler a bit more

32:16 handle U more easy to handle than this color complexity and one option is to look at the empirical entropy which is a measure of how much are the characters random and how much are they predictable and uh that gives you a very precise quantitative notion for this for this intuition but all that it is is you take the relative frequencies of the characters and then the entropy

32:48 thereof all right let's let's wrap up the discussion of Half Men um we've never analyzed the running time of the of the algorithm and it's an algorithms class so uh can't leave you in that state of sin so how much does it take to construct construct a Huffman code um we can use the priority que as I as I mentioned earlier so we build the priority queue by insert by starting with all the letters and their initial weights and then for each letter we have two delete mins and one insert if you remember back from unit 2 we can do both of these operations in log Sigma time log size of the of the priority Q which is at most Sigma here so that gives us this order L Sigma log Sigma overall time it's fairly fast even if the algorithm is even if the alphabet is somewhat big we can actually do it faster if the characters come already in sorted order sorted by weight um there's a lovely algorithm using two cues instead of a priority CU so two standard cues first in first out the overall time to encode a text with the halfman code once that code is already done that's linear in the size of the input and output so I have to

34:09 read each letter in the input and I have to produce the coded text so I have to write each bit in the output but that's pretty much it that's uh achievable in that time okay on on the Practical applications of this Huffman is is a building block of most compression methods that are used just because it's it's super fast has this nice guarantees in isolation it's maybe a little limited but um uh it's it's a useful building block uh there's a few things that become relevant there if you want to squeeze the last number of bits I mentioned um how you can use canonical Huffman codes to deal with these typ braing rules and so on um but we'll leave it with that it has nice theoretical guarantees and remember this is a class about the Eternal truths of algorithms so I like that it's also very fast for the decoding part at least uh a slight disadvantage is that it needs two passes over the input the way I described it and there's no easy way around this uh there's a more complicated variant of Huffman codes I just want to mention that you don't think it's impossible but we won't cover it where you can read through the text and you always keep

35:27 the the number of character occurrences up to this point is what you built the Huffman code on but there's a smart way to do that without recomputing the halfman code each time then you can do it in one pass uh but it's not used that much because it's overall slower the the more serious disadvantage is that we have to store the code alongside the text and so there's a certain minimal size of the text before this becomes useful uh that's one of the things that we'll work around um in the next