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?