All language subtitles for 25 - Huffman Codes English

High in this video we're going to talk about Huffman coding.

Including is a great way to compress data and to be able to take a large amount of data and to shrink

it down to bite size chunks and so to give me a good example of how this works right here on the right

hand side.

We have the letters A B C D and D.

If we had a document that only had a range of these five letters and we want it to compress the data

Huffman coding would be a great way of doing that.

And the reason why is because if we want to store this data in the regular text format that usually

would store data you would have to do something like this.

You'd need to set up your system and each one would have to be represented by a byte and a byte is a

total of 8 bits.

And so you're looking at one two three four five six seven and eight.

And so you're looking at having to take up 8 bits for every letter but there's actually a lot better

way of doing this.

And that's what huffman encoding does and this only works with specific types of data.

So if you needed the full set and the full range of data this isn't something that would work for you.

But what we can do is actually take it.

So we have a range set of rules similar to something like this.

We can actually take it and instead of requiring a total of eight to how we can do this just by using

three bets and we're going to walk through how to do it in a tree form first and then I'm going to show

you how the actual code itself works.

So the very first thing we're going to do is on the right hand side the letter A.

Shows that we have 24 counts of the letter and B has 12 C 10 etc. etc..

And so if you're wondering when this could actually be important.

There are certain studies in computer science dealing with things like bioinformatics that this is absolutely

critical and because you're dealing with gigantic amounts of data and you need to be able to compress

and Huffman coding is one of the best ways of doing that.

So the type of tree that we're going to generate is going to be a little bit different than some of

the others we've seen specifically.

It's going to be different and like binary trees because it's going to have values associated with them.

And so we're going to actually start off with the two lowest values.

So we're going to give a B and then we're going to say that there is a count of it and we'll draw a

box around this and we know that D is the same thing.

So we will say there's eight of those and then we're going to push that up to the top and say that we

know that 8 plus 8 equals 16 to have a total of 16.

Now we know by looking up at our little chart up here that B and C both have 12 and 10 respectively.

And so we're going to use those values as well starting with the lower value first.

So we're going to start off with C

we're going to start off with C being equal to its value 10

and then B 12.

And you notice that we are leaving out a.

And that's an important part and I'll show you what that means here in a second.

So we have a B and C and that you total those up those equal 22

K and now all we have to do is connect these.

So we have 16 plus 22 which gives the total of 38.

And now all we have to do is connect.

So we have a.

Which equals 24

and then we're going to total that up.

So the way Huffman codes the root node doesn't actually containing data just contains a sum of the total

data we're looking for.

And so we know our total.

If you add up all of these right here the total is 62.

So that's how you know your root node is always going to represent the total amount.

So if you're wondering how this is better than just having a just regular text file or something like

that which usually to use like ASCII kind of format ASCII like we talked about takes bits or one byte

for each one of these items and so that can actually take up quite a bit of space where as what we can

do here is we can actually assign values.

And so we're going to give this a value of zero and we're going to give this a value of 1 and then we're

going to use this just like the regular binary tree.

Right is 1 and 0 is on the left hand side.

We'll do that with each one type.

Now the way this will work is a is just going to be connected from the root so the root A is going to

have the value of 0.

B If you look at the way this works and you just follow binary tree you'll have the room going here.

Here here.

So you're going to be looking at B being represented by the binary value of 1 0 0 and an see if you

follow it down in the tree where it going down 1 0 1

D is going to be 1 1 0 and e is going to be 1 1 1 and all we're doing is we're assigning the edges on

the path we're saying it a 1 or a 0 depending on if it's on the right hand or the left hand side and

then that is what we're going to store in our in our compressed files.

So instead of having to give a total of eight values here we are given a 1 instead of 8 values here

it's three.

And the reason it's 3 it's just one two three here instead of eight.

It's three three instead of a three instead of eight.

So all we're really doing is we're shrinking down the number of bits that are required.

And as you can see right here tab.

ABC D and E it with a normal system.

This would be eight times eight times five.

So we would need a total of 40 as compared to the new system that uses the Huffman coding which has

a total of one plus four sets of three.

So we're looking at 13.

So by being able to Huffman coding we're saving well over half of the amount of space and that's one

of the big reasons why Huffman coding is so powerful because by simply doing something by shrinking

down and number of bits that are necessary on a per energy or on a per letter basis we're able to have

a much smaller file.

And whether you're dealing with DNA sequences or something where you can work with the data set like

this.

This can be a great way of doing it.

So please let me know if you have any questions whatsoever and I'll see you in the next video.