OK we're going to do another example of huffman encoding.
You can see I have A B C D etc..
Each of those appears every time in my document this many times.
And I started doing it putting the two smallest ones together I an owl.
Now what I need to do is add the next smallest one through these which 5:07 into I need to get that
5 over there and that's going to be my K and that's going to grow to be 7.
Now I can add this 7 with this or you can add those two together.
I'm going to add those two together.
Not that I have to really doesn't matter which way you go but I'm going to add those two together.
And so I'm going to get Jay and I that becomes 14.
Now I have eight nine and seven over here so the 7 and 8 are going to go together.
So I'll get that 8 over there and I have the H and therefore I have 15.
Now I have 9 11 14 9 and the 11 are going to go together because those are the two small ones.
So I have nine and 11 and the 9 is the G and the 11 is the F and then I put those together.
I get 20.
Now I have 20 14 15 21 etc. the two smallest over here are these two out of what's available so that's
29.
So I do those then the two small is out of Elberta to add the 21.
So over here to the.
And to have the UP WITH THE over here that's going to be 21 with the.
So that makes it 41 so I've 29 41 and I have a 22 and 25.
Well this 29 is too big.
And to those who I did the sum up to 20 to 25.
So and the 22 and 25 together.
So I get 22 is my D and 25 is my C.
Add those together.
I get forty seven now I need to add the next lowest two together.
I have 22 29 41 47 50s so the two smallest would be these two the 29 and 41.
So that would be 670.
So the 29 and 41 is 70.
And then what I have is 47.
And this baby is going to be added on to there because that's this next small town so that's my baby
and I have that and that's 99
then 99 70 and 55 so that means a 55 is going to be added over there and that's a and then we're just
going to add everything up together after that at the end because those are going to be my two smallest.
So that's one to five and that's two to four.
So here's my chart.
Now what I do is I give it a cut.
I go back and forth doing the zeros and ones a binary tree.
So you only have two options for each one.
Just putting zero one on each side.
As we go 0 1 0 1 0 0 1 0 1.
Now what we do is we have we go to a 1 1.
Now let's get to B and 0 1.
Let's get to see it at 0 0 1 0 0 1 D.
This is my Deats over there that 0 0 0 He he has 1 0 1 0 1 0 1 0 EF 1 0 1 1 1 1 0 1 1 1 exception.
Now I have 1 2 3 4 5 6 7 8 9 10 11 12 13.
I have 13 numbers that means the most the least I need is 4 bits for each.
You can see up until here I have 4 bits or less and that's great because these big ones like a and b
are only two bits.
These two are three bids.
This one has four.
But until there I have either the same or less here I have more bits than I would otherwise have but
there's only nine eight seven five and less than that.
While the larger number of times the appears is going to be encoded in many Lespinasse.
So what you can do is you can figure out how many bits you would otherwise have by adding it all up
to get They're multiplying by four.
Figuring out how many bits you have now and then which is which is two times with the five and two times
52 and three times 25 and three times 22 accessory add all those together and then you can see the savings
that you have in terms of running the huffman code.
So that's the idea that you can now encode this in less bits than you otherwise have.