How Huffman Trees Work - Computerphile

There's no better way than to check something really simple and show you how you [would] derive it using Huffman tree techniques I'm going to Construct a tree from the probabilities, and I'm going to go up And I'll hope I don't run out of space all these probabilities add up to one Order them starting with the highest at the left and they lowest at the right you can do the way around if you like So long as you're consistent about it [now]. There's no problem here, because they're all a quarter they're ordered already the huffman algorithm Then says group in twos from the right Successively by going through this, I hope it'll be clear what I mean starting at the right take the lowest two probabilities that you can see so I group these together as the branches of a tree Computer scientists always draw their trees nearly always upside down the leaves if you like the base of the trees down here But the actual root where it springs from is up at the top if you group a quarter and a quarter together That gives a combined probability of a half that node these two probabilities Have been coped with in some sense you're now left with 2/3 probability situation take the lowest two probabilities, you can see if there's any [ambiguity] about which you should choose then choose the rightmost set of probabilities. Well here. There's no problem So the next stage for the two lowest probabilities is to group those together and make a 1/2 combined probability They're done the next stage, so this is almost going like recursively back up the tree is to say [R] But we now group these together [the] half and the half we've now reassured ourselves that all the probabilities Here when grouped together and added up come to 1.0 And we'll be in deep [trouble] if they didn't that is your huffman tree with those probabilities The next thing you do this is great fun is to decorate the tree. I now want to from this Workout what the [correct] code the minimal code should be for a given state start to get the root of the tree? I always Annotate the left going Branch with [zero] and the right going bra with a 1 you can do it the other way around Uniformly throughout if you want to it will come to a side different looking huffman code But it will have just the same properties as the one I'm going to derive when you come to this node And you say I'm now going to descend to the left again the rule is you add a zero of what you've already got seen it with zero zero How about this state? You come down on a zero, but then you go to the right? Every time you go to the right you add one to what you've already got We've already got a 0 out of 1 and here. We are look it works for the rest Go down to the right with a 1 then go down to the left Every time you go down to the left add a zero to what you've got there. We are 1 Down to the right had a 1 that's that one So there we are what huffman basically said in 1952 when he did this? was [that] this was the [method] of getting a compact code in other words the best you could [possibly] do for those probabilities and I think David Hoffman's. Thesis is famous for only being about 12 pages long I think many of us would love to write a thesis saying Here is an unsolved problem. I've done it. Please give me a phd. Yes. It's only 12 pages long but to be fair to To those who are examining him. It's easy enough to prove that it works for something like this which [is] so easy because they are all exact negative powers of [2] The harder thing is to prove that it still gives the best possible compromise even when the probabilities don't work in your favor I have to sort of sound a word of warning here Let me do the San Francisco [entropy] on the San Francisco page if I can find space to squeeze it in If you remember the entropy is the sum over all the [weather] states They typically see in textbooks things looking like this from the first weather to the fourth Weather situation take the sum over p. I log to the Base 2 1 over p I that of course come down to being the sum over Minus p. I log p I is equally valid so what we do for the entropy is we take the weighted sum [of] The probability of the state happening times the log of the probability of it happening And we've discovered in the entropy in compression video the entropy Overall is two bits Of course it is [it's] exact power of two all the weather states are the same But then we worked out [to] the average length of the code and the average length of the code is two bits Yeah, they all occur with probability or quarter, but they're all two bits long so the average Length of [the] message [you] set is also two bits. This is so simple and so straightforward That's the efficiency Which is measured as h? Over L in this particular case is 2 over 2 2 bits for Entry [2] bits there is length which is equal to 100% You can hit the entropy limit with this weather system Encoded in this way because these probabilities are all negative powers of 2 for those of you. Who've encountered Entropy in Physics or chemistry take great care? information theorists call Entropy h don't do that in your chemistry exam in chemistry h is reserved for the amount of heat in a system, and Certainly [remembering] back to my chemistry days. I think they use the symbol s for entropy so don't get confused Shannon used h for antifreeze, so I will what about if we have? Whether states or some system where these probabilities are [not]? Exact powers of two we'll look at a fishing trip. Let's say That we want a system with probabilities of one third one third One nine One Nine one Ninth this person with a pretty good set of fishing kit and a good selection of fish to catch Actually at the end of the day ends up that one third of his [or] her catch is called another one third is sea bass one ninth proportion of the catch is tuna one ninth is a baby shark and We got a bit stuck for inspiration here Barracuda, whether you could get them all from the same boat. I don't know but let's say this person wants to Transmit back in the shortest possible Toad What the predominant catches that he's got so he wants to signal whether he's you know? He's got a good lot of Cod today Or is it bass or is it whatever first thing always is check your probabilities add up that except to three thirds Which is one here we go Huffman tree. We're still going to use log to the base 2 from the right take the pair of lowest probabilities You can see and those are these [1/9] So that makes two ninths cross out the ones you've coped with You've now got one third one third one ninth to ninth the two lowest probabilities. You can still see are [two] [ninths] and [1/9] which is going to combine to make a 1/3? next stage The two lowest probabilities you can see well you've got a third a third a third we have coped with [that] We've coped with that if you get a choice of either that pair or that pair of thirds [it] doesn't matter which actually you'll get slightly different codes But with similar properties one third and this [one] [third] Gets combined into two thirds and the final stage you can all see is dead easy We triumphantly We do add up to a total probability of [1.0] Now comes the fun bit of writing down the huffman codes for this in binary. You're descending left. So that's a [0] You're going right? So that's a 1 you. Come down on this one So that's a 1 and then a 0 this arm gets 1 1 but then you come [down] here That's going to be 1 1 0 therefore this arm coming down here is 1 1 1 this one is 1 1 [0] and that One is 1 1 so those are your huffman codes when you take? h as the sum of your this is now from State number 1 1 2 3 4 5 state number [1] is I've caught card [stay] number 2 is of Court [bath] Up to five of your minus p. I log to the base 2 of p I You are going to find to your dismay that The Entropy comes out to being [2] point 1 1 3 bits I've looked this up on my calculator if any of you aren't sure how to take Log the base to other third then We must keep ganging up on brady to do a number file on powers of number bases and logarithms The average length when you work it out is 2 point 2 to 2 bits so the efficiency is equal to 1 over the other two point 1 1 3 over 2 point 2 2 2 is equal to 95 Point one percent efficient Not bad, not bad but not nearly as good as the weather stays why why is because these things are not exact negative powers of 2 With these things being exact negative powers of three I can confidently Predict that if only we could calculate entropy in trace so so long as your properties of your line Were such that errors were relatively infrequent?

Channel: Computerphile

Views: 240,814

Keywords: computers, computerphile, Huffman Coding (Algorithm), Huffman Tree, coding, computer science, Professor Brailsford

Id: umTbivyJoiI

Length: 11min 7sec (667 seconds)

Published: Fri Oct 18 2013