So we're going to talk now about Huffman codes.
OK so there's a couple topics that come up when we're trying to do something that's called data compression.
What happens is that if we have a message and we were to try and send its And let's say each letter
is you know for bits or something like that you know this is a that's b.
We'll call that A B C etc..
You know this is a zero or whatever it is.
Now the problem is that we have to send each of these is going to be the same size as the next one.
Even though Z may only occur once but it's still going to be the same size as everybody else.
As far as the letters go so the issue is that we need to send information but we don't really need to
have z be the same size as a cause maybe a occurs many times but.
But Z doesn't occur as many.
So we seem to be wasting bits because if we have let's say we have a b c d f right.
And each of them is maybe 8 long and we have one two and maybe we have four of these and three of these
and 12 of these and 10 of these and six of these and 10 of these.
So what's going to happen is that they're each 8.
So this is a 8.
So this one gives us 80 and that's six times eight and that's 80 that's 48 there and that's eight times
12.
So that's six and then eight times three and eight times four.
And so if we add all of those up then we'll see how many bits overall that we're using.
Now the only thing is with that it might be a good idea if they're all use about the same amount that
it's eight times for A's is going to be how many bits we're using for eight times three B's is going
to be I mean it's reasoning for B etc..
The only problem is that we don't really need to use that many bits we don't really need to make them
all the same size and if we don't we actually have a lot of savings that occur in terms of sending information
which is the point.
OK so now how do we go about doing that.
One way to do it is a dictionary.
And another way to do it is a Hussman code so huffman code is a way to compress data.
There's two types of compression there's lossy compression and the lossless compression K lossy means
we can lose information.
Lossless means we don't lose any information when we do it in a lossless compression is Huffman codes.
Ziv Lem E.W. codes others Lossie codes or something where you know it's not such a big deal to lose
information like in a picture where we can basically probably figure it out otherwise.
So for instance let's say this side were this color and the other side were this color even if we didn't
know exactly what things are we could probably figure it out if we just inthe information and this this
they even if there was a change in she'd starting from here starting from here all the way till they
are a shade change we can you know figure it out or write some you know do it in some way that would
that would work.
But essentially we do have to come up with a system to do it so we have lost in the lossless compression.
OK how do you do a lossless compression.
The huffman code which is optimized you take the two lowest ones and you add them together so that we
get a color that's a little bit better for this.
We're going to have a J and an I.
OK so that's one and one so I'm going to put the J in the I that's one and 1.
I'm going to add that together I get to OK.
Now I take the next two smallest ones that I can and the other I use these are 1 and 1 2 4 and 2 and
6 the smallest ones are 4 and 2.
So going to get my H then I'm going to put that right over there that's a 4.
I add those together I get six.
Now I have 6 6 and 7 the smallest ones that I can add together would be a 6 and a 6.
And so you know what let me make this let me change this over here to a 7 just to show you what it is
I'm going to highlight that I just did that and they make two different colors so it's clear.
So now let's say that we had seven seven and six What should we have together.
We could either add this G or this F because they're equivalent.
Let's say instead of that's We actually had maybe let's go with a fives.
All right let's see what would happen if we had five in five and six What should we do.
Well the five in the six could be the other but the smallest would be and the two fives together.
So let's add that G and the f those are each 5 and I'm going to add them together and I get 10.
So now I'm up to the 8 5 8 6 10.
What are the smallest and together the 8 in the 6 7 and 8 which is
which is an e.
So 18:6 is 14 and then I have 25 14 and 10.
The smallest two together would be the 14 and 10 and get 24 now I'm 24 25 29.
So the smallest to add together would be this is a six months to get it to 25 24 which gives me 49 so
I'm going to have that d over there and I'm going to say 25.
I add these together that's 29.
Sorry that's 49.
And then I have 29 49 and 50.
Let me make this just a drop smaller so that way you can see again the point being that let's say that
this is a 30 right let's pretend that that's 130 now.
So what's going to happen is we don't have 49 29 and 30 the smallest that together would be to be in
the seat.
So I'm going to say be and see that's 29 and 30.
And then I add those together.
I get 59 now I have 59 120 and 49.
So the smallest and together would be those.
So that's 49 and 59 So 60 plus with these when tens are 1 0 8 is what I have.
And now I have the 8 which is 125 which is 120 added together and then I get 100 plus 1 0 8 is 2 2 2
2.
OK.
So this is really pretty.
I'm pretty unclear about exactly the details of this tree but here's what you do.
OK.
I'm going to redo this tree in the second to show you and I'm going to take a different color.
So it's clear you just add zero on one on each spot where there is where things move in either direction
0 1 0 1 0 0 0 1.
Now let's find out what a is a is just 0 because that's all we need to do.
Now if I go let's do B that's 1 1 0 and I'm just traveling down to find out what B is 1 1 0.
See that's 1 1 1 I traveled down the loop and I get there.
Now let's find the that's 1 0 0.
So D is 1 0 0.
Now let's go find the.
OK that's 1 0 1 0 0.
He is 1 0 1 0 1 0 0 except for let's do I just because it's down there that's 1 0 1 0 1 1 0 sorry one
on one says 1 0 1 0.
Right down here 1 0 1 0 1 1 1 1 1 1.
So now you can see that a occurs how many times 120 times that's what that's relevant to 125.
That's why I have the number there are 120 times how many bits that I use for that just one.
So that is 120 times one B is three.
How many times that occur 30 times.
So that's 30 times three and that's how many bits I'm using for B C 29 so that's 30 times twenty nine
times three.
Twenty nine times three the 25 the.
So it's 25 times three because there's three bits.
He is one two three four five.
It occurs eight times so that's eight times five.
Except for now you can see that a it occurs many many times but they only have to use one bit to encode
it.
So if I had a message a B D A C A.
What would that look like.
That would be a b the A C.
Hey now how do I know where things begin and end because there is only one thing that starts with the
zeros so that must be that.
And there's nothing else after it.
Now there is only one thing that has a 1 1 and 0 afterwards.
And that must be that because everything else will have a 1:1 either one or a 1 0 afterwards.
But there's nothing else that has a 1 1 0 so that must be beat.
Then afterwards let's see I have something with a 1 0 0 but there is nothing with a 1 0 0 0 afterwards
so that must be the end of that that's the and we can figure out that that's a that's C and that's a
and we can go down the old is doing.
Now how many bits does this cost us.
All we have to do is add up all these numbers 120 times 130 times 3:29 them to 25 times eight times
five etc. for all the different numbers and that will give us the total number of bits that are used
in that will be significant savings over if the are all the same number of bits.
If these were all 8 bits or whatever it is that we would want to use the minimum that we want to use
that will give a significant savings to do it this way over doing it this way.
OK.
So that's your huffman tree.
Let's do another example quickly.
OK.
So a b c d d f small example k 2 5 7
19 20 and 35.
OK.
That means acres 35 times B occurs 20 in the message C.A. is 19 the across seventy five and the across
two.
Now the minimum that I could use to do this would be how many bets that would give me one.
Let me let me do it with spots instead.
OK.
So if I wanted to encode one letter
want to.
So for instance I could have this being zero.
Let's actually just count that will be easier to remind ourselves that account than anything else.
That's one two three.
That's 1 2.
That's one that's two that's three that's now that's three right.
So that's four and that's five.
So the minimum amount that I could use for this message is that now I'll actually get to make my message
a drop bigger.
I'm going to actually add one or two letters in here just to make it more untenable so I'm going to
six seven eight so f g h.
So that's five that's six seven and F G H I.
OK so we'll just make this one one and one because it really doesn't make a difference.
But you can see now the minimum number of bits I can have if this is going to be 6 7.
This is going to be 8.
That means that each of these minimum has to actually be four bits
OK.
Now how many bits do.
How many of these are each four.
So let's get the total number of bits that this would be.
OK I'm just going to do this part in Excel.
Let's get the total number of bits of this would be
OK.
So that's going to be 35 20 19 7 5 2 1 1 1.
OK I'm going to multiply each of these times for.
And so I'm going to say some now I'm going to multiply each of these times for so some that and I'm
just going to multiply by four and because I have to do it the other way maybe I could do it this way.
Yeah.
So I'm going to multiply this whole thing those four then add it all together and they get three inches
sixty four.
That is how many bits.
Overall I would need to imagine 64.
OK so let's put them on the side.
I'm going to copy that and I'm going to paste just that number over there and I'm going to get rid of
these guys.
And now remember three engine sixty 64 is the number of bits that I would need if these were all four
to send the message that at 35 A's 20 B's X Centra there's going to be that many bits.
So let us now go and figure out how many it is with our Huffman trees let's go do the huffman tree OK
I G H I.
Doesn't matter which I pick.
So I'm just going to pick G and H are going to add them together.
That's going to be to kag I can put a 1 next to it it doesn't matter.
So it's going to be 1 in 2 or 1 and 2 I'm going to add my f and g together because why not F and G O
Sir F and I.
It doesn't really make a difference because they're all one but F and I.
That gives me three.
OK.
Now I have five seven two and three I have the smallest two together.
So that's five.
Then I have five and five and seven I the small these two together.
So he is five.
I get 10.
Then I have seven 19 and 10.
I add the D together.
So that's seven and 10 is 17.
And then I am 19:17 20 That's 19 and 17.
So it's going to be my see they could see it's very very one sided but it doesn't make a difference
really.
That's thirty seven to six.
And then I have 20 35 and 36 I should have the lab and be together because there's a police so we get
55 and then I add both of these together and I get a the one.
OK now let's put our symbols in.
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1.
Great.
Now we've got to figure out where each letter is A is 1 0.
B is 1 1 C D F G H.
Let's go figure this out.
C is 00 K D is 0 1 0 0 1 0.
B is 0 1 1 0 0 1 1 0 F is 0 1 1 1 1 0 0 1 1 1 2 3 4 0 and G is 0 1 2 3 0 1 2 3 0 h is 0 1 2 3 0 1 0
1 2 3 0 1 and I is 0 1 2 3 4 5 0 1 2 3 4 5 1s.
OK so now let's go figure out how many there are over here doing the same method that we did earlier.
So over here a is going to be k is going to be there's two of them.
So there's going to be 2 times 35 because that is how many ways that 70 that's how many days I had 35
of them and it only has two bits.
K. B is 20 and there's two bits so that's going to be 40 bits altogether C is 19 times 2 is thirty eight
and the is three long and there is seven times three is twenty one is one two three four four times
five is twenty.
F is one 2 three four five six times 2 was 12 and G is 1 2 3 4 5 6 times g is 1 so that's 6.
And then the others are 6 as well and they're all ones or VHI are 6 so that's 6 and 6 that's.
This is just to this is how many A's A B C D F G H.
Now each of that's how many bids it's all going to be together.
OK.
And that's how many there are.
And so therefore I'm just going to sum those things up here.
OK.
And we get to 19.
Now originally it cost 364 if they were all four bits however there's a lot of A's and B's unseasoned
D's and most of the numbers are there and it's going to give us significant savings over here.
OK so over here it was 35 thums for bits.
Now it's 35 times Two-Bits and so significantly less what are our savings at the end of the day.
What are the savings.
Let's go check it out on Macinnis and drop.
We can see it.
The savings are equal to 219 divided by three 64 and that gives us 60 percent.
So we are only at 60 percent and there's the same 40 percent.
We're saving significant space by doing our treat by doing our huffman code.
So that is a huffman code.
That's how it works.
We build the tree up k we build the tree we put the numbers in we count how many there are and then
we get.
And then we get the numbers and we in fact got 60 percent because to through 365 means that we're only
using We're compressing it 60 percent so that's a phenomenal rate of compression.
And there you go there's your huffman tree.