OK we're going to talk about Huffman encoding over here.
This is a binary tree that we're going to build with the huffman encoding the huffman encoding is a
way to optimally compress your data.
Let's say that we have some data a appears 30 times and it appears 25 years 20 years 17 years 15 times
as appears 12 times g appears that's a g g appears.
OK I'm not making it any better but that's a g g appears 10 times h seven times I appears four times
etc. because we have all these letters we have 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 letters.
We would need four bits to do this.
We would need four bits in order to do this so we have four bits that could be in a can be a B This
can be a C this could be the cetera we have.
Yeah.
So that could be that.
Now that means that 30 times do I need those four bits 25 times I need four bits for me 20 times I need
the four bits for C 17 times I need the four bits for D etc..
So whatever that total is of 30 times for plus 25 times for 20 times for 17 times for whatever that
total is that's a lot.
So the question is do you have an easier way or a clearer way or better way more to compress the data
set.
So we do as we build this tree.
We started the.
We take the smallest two numbers that we can find and we are 1 in 1 and add and together they get it.
Now I have two over here.
All right.
So what's available this 2 is available right there.
Also this to this to this three etc..
So I could take this to an ADD the end or the end to that too.
Or I could just take the end and them at an end and am and add them together I chose the Emina and add
them together so I get two into it to get four.
Now I have the four the two.
And over here over three four four etc..
So and the two lowest so out of the to the 4 and the threes I'm going to add the two to the three.
So I make the three over here with the ally and together I get five.
Now I have a five in a four and they have 4 4 4.
So I'm going to have to add the force together.
I can either add these two together or I could add this K over here.
I chose to add the J and the K together.
So you have Jane K as 4 over here you can see that this is.
This is my four over there that's a 4.
So foreign forces.
So now I have 8 four and five and I have another four.
The smallest to do it.
Pick this for added over here so I get the I the is for and for his eight.
Now I have eight in eight and five.
So I have to go for my smallest ones or what's the next smallest one.
I have 8 8 5 but over here I'm seven in 10.
Seven is the next smallest one.
So add that to my smallest one so 7 and 5 becomes 12.
So now I have 12 8 8 and 10 and 12 and 12.
So the smallest ones over here I could add the 10 in the 12 over here or I could add the 10 to 12.
Because those 8 8 became 16 over here because they were the smallest.
In other words when I had 12 8 8 and 10 they and the 8 are the two smallest they become 16.
So my nephew is 16 12 10 and 12.
I decided to add a 10 and 12 together to get 22.
Now the 10 of the 12 becomes 22 and I have a 22 12 and 16.
The next one free is a B which is 15 because it's the next smallest.
I had that here I have 22 27 and 16.
The next one free.
I have a 17 22 27 16 16 and 17 and together to get 73.
The next option I have is a 22 27 33.
What are.
And that and a 20:25 etc. the two smallest are the 20 and the 22.
So I add those together.
I get 44 the next smallest would be the 25 and the 27 I get 52.
The next most would be that 33 and the 30 you get 63.
Then you add these together because those are the two smallest of those to get to get 159.
Now what we're going to do here is we're going to say this is a binary tree.
So let's put zero in one for each possible path that you can take.
So for each possible path I'm just going to label them 0 and 1 0 1 0 1 0 1 0 1.
Doesn't matter where are you going or just doing 0 1.
Because it's a binary tree.
So either side is going to now be taken care of 0 1 0 1.
Now what I'm going to do is I'm going to trace and remember those were four bits before but I'm going
to do is I'm going to trace how to get to each letter in order to get to a.
It's 1 1.
So I say 1 1 in order to get to B.
Where's my b.
It's right here it's 0 1 1 0 1 1.
In order to get to see it 0 0 0 0 0 0 in order to get to D it's 1 0 1 1 0 1 he is 0 1 0 1 0 1 0 1 that
are ones three right then.
So it's clear
a half is 0 0 1 1 0 0 1 1.
OK.
Now I'm just going to stop there but you can keep going and finding all the letters for instance 0 0
1 0 0 0 1 0 etc..
But let's notice that before now you're going to get some letters that need to be pretty big.
For instance P is 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0.
So those are going to be pretty big down here.
But notice that everything above here is less than four bits.
So the aid which appears 30 times and that be it should be has 25 times the C which is 20 times in a
D which is 17.
Those are all less than 4 bits.
And that's important because a which appears 30 times is only two bits which means this that is betting
four bets on each.
I am only spending Two-Bits.
So you can see that I now have 30 times two and twenty five times three and twenty times three and 17
times three.
All of which are much less than they used to be.
And then the.
Is this 15 times four.
But that's actually the same as it used to be at some point is going to become greater but there's not
a big deal because like the P-E which instead of being four as one two three four five six seven bits
it doesn't matter that it's seven bits because only appears once.
So I'm saving so much up here on the Abian Two-Bits and this is ok once it appears seven bits that what
you're going to do is you're going to get in coding as just saying a is being one ones that have 0 0
0 0 or whatever it is.
So now we can send the message in it's going to be unique in this way because you can see that is one
one.
There's nothing else that has a one and there's going to be nothing else that has a 1 and a 1 after
it because it is unique.
So to be able to tell what it is in the message.
So this is how you do the huffman tree and the huffman tree for the huffman encoding and we'll do another
example another video.