No video :(

How Huffman Trees Work - Computerphile

Подписаться 2,4 млн

Просмотров 252 тыс.

50% 1

How do we derive the most compact codes for a situation? Huffman Trees can help. Professor Brailsford explains how computer scientists like their trees to be upside down.
"Entropy in Compression - Computerphile" precedes this: • Entropy in Compression...
EXTRA BITS: More on Huffman Trees: • EXTRA BITS/TRITS - Huf...
Error Correction: • Error Correction - Com...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradycha...

Опубликовано:

26 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 209

@TonyManso 11 лет назад

I just love his enthusiasm and ability to simplify things that might otherwise be difficult to understand

@Cathalion 9 лет назад

"And now a bit on chemistry...." The mans level of knowledge is astounding lol.

@jonnypanteloni 9 лет назад

I don't know what I'm looking at after the tree diagram. I would love to learn and take notes on what this all means - I watch computerphile in my spare time when I am not editing videos, photos and other work for clients. It's good for the mind!

@bobbyd9115 6 лет назад

Just wrote a file compression program in smalltalk for my class. I love how he explains the algorithm.

@AvZNaV 8 лет назад

I used H for enthalpy in my chemistry classes, S for entropy and Q for heat

@timsiwula 9 лет назад

Does anyone have a link to the original 12 page paper David Huffman published in 1952? Thanks!!

@cyberb4ss 8 лет назад

Title confused me, because I'm so used to seeing upside down trees!

@Cyberkygen 11 лет назад

I would like to have this gentleman as my teacher! So inspiring!

@joealias2594 10 лет назад

Why did he start with an example where every probability is equal? That makes the encoding totally arbitrary and really defeats the whole point.

@U014B 8 лет назад

7:00 Need an example sea creature? Why not Zoidberg?

@TheMoolica 10 лет назад

So Huffman was Australian?

@Booskop. 11 лет назад

No problem man, I'm sorry that everyone is telling you that you're wrong, but the only thing you wanted to do was to make a point about the video, by giving an example, so everyone can understand better, thanks for sharing your intellect with us, and don't beat yourself up over a mistake. We're all human =)

@AlanKey86 11 лет назад

I was a little confused at the start of the video - I thought I'd skipped a bit by mistake. But then, almost immediately, I remembered about that good ol' weather station and it all came clear. Maybe there should've been a "Previously on Computerphile..." intro sequence

@Disthron 10 лет назад

Is that kind of reel paper still in use or is that all old stock? I can't remember the last time I saw those types of printer paper. I thought they were only used in dot matrix printers.

@Kelimion 11 лет назад

No problem :) The receiver might then have seen 11 at the end of a packet and know another 1 or 0 is needed to make sense of it. They'll wait for the next packet to arrive and add that to the buffer. Basically they'll always consume the buffer a bit at a time until they get a code they recognise. For the termination code, if you can't send a header because you don't know how much you'll send, you'd add a code with the lowest possible probability (it occurs once in the whole stream).

@PiratWeber 11 лет назад

I could listen to his voice for hours and hearing about computer science.

@dooge1992 11 лет назад

I think what's really missing here is the biggest application for huffman tree's, text compression. We use a similar system, replacing probabilities with counts of chars, but the big thing is prefix-free code. We can generate unique binary codes representing a traversal of the tree to a specified goal. It's a good topic for another video/sequel to this one.

@sanko111 11 лет назад

The advantage is that with this algorithm it's impossible to create ambiguous code, so you can put a lot of them next to each other and the original message remains perfectly clear. With your example, if someone sent you 10, you wouldn't know whether it's 1 tuna or 1 bass and 1 cod.

@Keduce22 10 лет назад

My last computer science project of the year was a huffman compression algorithm encode/decode. My solution was so hacked together. The provided code for c++ contained c code which works perfectly but is not exactly right in terms of good coding practices. Then my group member did his own solutions. My code was the most buggy thimg ever. It took weeks to get it right and for the automarker to accept it.

@pdieraue 11 лет назад

Everything that could potentially be a prefix of a code is contained within the tree as a node that splits. Only the nodes that don't split are assigned a code. In the example you can see that "1", "11", and "111" are all assigned to nodes that split, meaning they are prefixes for codes and therefore cannot themselves be codes.

@Kelimion 11 лет назад

Put differently: In your example you'd need extra symbols inbetween each code to tell 0+0 apart from 00. Huffman codes can always be told apart. Because the shorter codes are used for things sent more frequently, the average bits used tends toward the optimal amount you could possibly use to send things without any ambiguity.

@JimCullen 11 лет назад

I believe he explained it in the first video on this topic. When you are sending the message, if at any point the sent message is equal to one of the messages that they recognise, it stops. So in your example, if they wanted to send Shark, they would send 11. However, in order to send 11, you must first send the first 1, and then the second 1. After the first 1 has been sent, it recognises that as Bass, and stops.

@Toksyuryel 11 лет назад

What's left unspoken in this video is that the codes are all padded to the same length afterwards. After that padding is applied, the Bass, Tuna, and Barracuda codes you suggested are no longer unique: they are all 100.

@stellarfirefly 11 лет назад

Prof. Brailsford should use a simple word with obvious repeating characters, such as "abracadabra", to create a Huffman tree. He could then later explain how Morse Code was a very early attempt to use a Huffman-type encoding. (For example, the letter "e" in Morse Code, which is the most used letter in the English language, is simply a single "dot".)

@parkamark 11 лет назад

Peter's reply is right, but to explain it another way, Huffman Codes are "instantaneously decodable". Your codes are not this. Take the bitstream: 011001. Under your coding scheme, does this mean Cod (0), Bass (1), Tuna (10), Cod (0), Bass (1) OR Cod (0), Bass (1), Barracuda (100), Bass (1) ? An instantaneously decodable code is one which, as you read the bit stream, once you have a match, that's your answer, and you know where the start of the next code word is.

@mkaatr 11 лет назад

It is used for compression. For example if you want to send a message stating the order of fishes such as : Code,Bass,Tuna,Code,Tuna,Bass,Code,Code,Tuna ... then instead you could send: 01011001101000110 which is much shorter (notice that these are bits, so there are 3 numbers to be send instead of 36 numbers for the whole list). The other side would decode the message and generate the original list.

@thecassman 11 лет назад

The fish example is a bit contrived as a proof but... Think of it this way; if i wanted to send "Tuna Cod" as a message in your coding above then i would send "100"... But that's also the code for Barracuda, so the receiver wouldn't know which you meant. In the coding of the video "Tuna Cod" would be sent as "1100" which is a sequence not shared by any other possibility, so it wouldn't be confused with anything else.

@Kelimion 11 лет назад

They occur in different probabilities, so if you're sending a rather large text describing each of the fish, coding the fish that occur more often in fewer bits will result in a total shorter than the naïve coding which doesn't take the probabilities into account.

@MrCOPYPASTE 11 лет назад

If you see in your example you will find that the only entry that is not ambiguous is the first one, all the others don't represent valid data. Using 011 could represent: Cod(0) + ((Bass(1), Bass(1)) or Shark(11)), the Huffman algorithm prevents that from happening, another way to put it is that you only have valid codes on the tree leafs and in your example you're using the branches to contain them. Another thing if you don't keep your tree small you may end with a bigger output than the input

@StSin666 11 лет назад

Not a comment for this video, but a request for Computerphile. I would like to see more videos about hardware, i.e. different architectures of a CPU, von Neumann and Harvard. Difference between a CPU and an GPU. Logic gates, FPGAs, parallell computing, sensors, I/Os, AI hardware and so on.

@Vulcapyro 11 лет назад

Differences between how a CPU and GPU are used would be fantastic, it's a key part of a research area I'm currently in. You'd definitely have to thoroughly explain how the CPU works though, which would take quite some time in and of itself. Logic gates would be nice too.

@HenkJanBakker 11 лет назад

LOL. Eye rolling sure brings the 'I don't get it' to a whole new level.

@MeepMeep 5 лет назад

THIS MAKES SO MUCH SENSE THANK YOU

@samposyreeni 9 лет назад

Why don't you do Shannon-Fano as well? That's of course what the Zip/DEFLATE format uses, so huge practical appeal. Thought not quite optimal. :)

@Kelimion 11 лет назад

No problem. That's why you wouldn't use 100 for barracuda, because you can't distinguish it from bass+cod+cod. The useful property of Huffman codes is that you can always tell codes apart, and that the running average of bits used converges to the optimum amount. (For powers of 2 probabilities, otherwise use arithmatic coding for example, where you can use any probability you like).

@qwertyfinger 9 лет назад

so it actually approximates numbers of bits between integers? that's really cool. the first example kind of misses that point, much easier to see with the non-powers of two.

@Nathan-ji2nd 11 лет назад

I...I understood this one! I was giving up on computerphile and relying on numberphile for all my smarts!

@MrAnonymousCitizen 11 лет назад

This man's voice is wonderful.

@millionsteve 11 лет назад

I agree....the camera work in most of these computerphile videos do that. it's like it's filmed for dramatic effect than education.

@NoNeaNaNoNly 11 лет назад

That would make it easier for end users to subscribe to different channels but what if something covers two? And who decides where one begins and the other one ends? I think that would make managing the channels more difficult :D I'm fine with as it is at the moment. What they could do though is using tags or something, so you know what the video is about, like [Programming File] at the beginning so you can already tell from your subscription box.

@razorborne 11 лет назад

you could represent them all with 3 bits, but then you'd have to send more data on average. while it represents a couple of the results with 4 bits, the two that you're most likely to send are represented by 1 and 2 bits each, so 66% of the time you're beating the 3-bit line. another 11% of the time you're matching it, and 22% of the time you're one over. so while you're increasing the maximum amount you might have to send, you're reducing the average.

@GilliamHimself 11 лет назад

A numberphile about logarithms would be very helpful

11 лет назад

That... Actually made an amazing amount of sense. Kudos

@uriituw 11 лет назад

I loved studying Huffman encoding in uni.

@TylerLarson 11 лет назад

Compression. Given the relative frequency of a a given set of "words", determine the smallest way to store some sequence of words.

@TheLatterPartOfToday 11 лет назад

I absolutely love this channel (and numberphile of course). Thanks for another great video!

@Kelimion 11 лет назад

The codes are constructed so you always know if you've already received it, or if you're waiting for more bits. So with the 1 on the end you know it's not a valid code, yet, and wait for the buffer to fill up to tell you what follows.

@Tat2ice 10 лет назад

Huffman codes, which are part of Information Theory, are used to compress data, with is a "computer-related" idea. Also, I find Numberphile to be related to purer mathematics, rather than its applications. But that's my opinion :)

@mage1over137 11 лет назад

Q is for heat H is for enthalpy which is the amount of energy needed to push out the gas so you can put your system in that place.

@yukhui 11 лет назад

I don't know anything about this subject but I'm wondering is there any particular reason for using 2 sig figs in showing the sum of the probabilities equal to 1.0?

@Kelimion 11 лет назад

Bit more complicated in reality, but that's the gist of it. You could also always reserve space at the end of a packet for a header, telling the receiver how much you've sent and if more is coming or not. Loads of possibilities.

@LudicrousTachyon 11 лет назад

With the 1/3 example. It seems the efficiency is lower mostly because the shorter codes aren't exhausted before moving on to longer codes. There are no 2, 3, or 4 digit codes beginning with 0.

@MeepMeep 5 лет назад

Studying for my midterm by watching Computerphile feels wrong. I'm not supposed to enjoy studying

@MrCOPYPASTE 11 лет назад

Imagine that you have a sequence of 16 zeros, if you use your coding you will have 16 * 3 bits as a result but if you use only one bit for each zero it will produce 16 bits, the key part of this algorithm is that it replaces the most frequent data with shorter codes not fixed sized ones.

@jimbean5657 11 лет назад

Right you could divide into two spaces... I was thinking more along the lines of a Mediasite Video presentation style since RU-vid presenters are advancing in their production values. Anyhow... sorry for interrupting the thread

@taesheren 11 лет назад

It was not directed at you specifically. I just thought I'd put it out there, because I know it is a common misconception.

@Beesman88 11 лет назад

you can't differ 0 and 00 so you can use clasic info sending for 5 states (000,001,010,011,100) and you got 101,110and111 leftover - also you will always send 3 bits. But with this method he showed - you send 2.2~something bits on average. so you are eficient.. this is ofcourse not really mindblow you but if it would be sending 10MB per second or sending 6MB per second per average - you see where it is going..

@MichielVanuytsel 11 лет назад

That depends on the possiblities of the different answers :) Huffman code gives you the smallest average length (or power length, not sure)

@StSin666 11 лет назад

I'm currently writing a master thesis on FPGAs. I love hardware stuff =)

@TheMohawkNinja 11 лет назад

So how does this work in a computer, since the codes are of different length? You can't just send no signal, and have it be perceived, right?

@Kelimion 11 лет назад

It's the average length of bits needed for things you're sending using those probabilities. In his calculation for that average he takes the individual probabilities into account, whereas you didn't.

@kolnder 11 лет назад

Can someone pls help me understand that? first, did they made a video about the whole entropie and bit length things? second, if you are sending those codes, what happens if you send a message ending ith a 1, and then one of the coded fish names, how do you know wich fish it is? e.g. ...1110... this could be a 1 from the last message and then tuna or just shark?

@JanCRefsgaard 11 лет назад

Isn't negative powers of 2 the lowest probability?, and the best sets are the ones where the distribution is the most extreme, because they gain most from 'short branches' if one of the states is 0.99, then you have 1x0.99 and numbers lager than 1 times numbers lower than 0.01, meaning you are pretty close to entropy=1

@daedra40 10 лет назад

Nice one professor, I was actually confused with the entropy symbol, and you saved me :P

@shaihuld 11 лет назад

Best teacher ever, can't wait for it to get deeper ^^ !

@TheWeepingCorpse 11 лет назад

so is 10 = tuna or is10 = to bass followed by cod? how would the receiver distinguish between them?

@he1986 11 лет назад

Damn. What part of youtube am I on now? A polite conversation between a comment and a reply.

@geordonworley5618 10 лет назад

That would be really cool to watch, but I imagine they won't go into depth on anything like that. They might do something like talk overall about FPGAs (probably using a lot of broad analogies), but never actually talking in depth about the topic. The fact that you are aware of all of these things likely means you already know at least the overall purpose of these things, so I would suggest to Computerphile to cover these topics in brief, as they do normally, for the majority of their viewers.

@gpaluk 10 лет назад

Guess what... Math is relevant to computer science too :p IBM and such did a lot of the work so that you didn't have to think about this, but it's systems like this that make computer optimizations a field of study and make your program code run faster.

@growlerjack 11 лет назад

so i think my brain just melted, and to think i want to do this sort of stuff in uni next year, damn i think i need to get on and learn haha

@vicpc55 11 лет назад

Yes, there are, but they tend to be less important than having a smaller average length. With a shorter maximum code, for example, you may need a smaller buffer on the receiving end to decode.

@eideticex 11 лет назад

Imagine catalog cards for library books. Each one specifies exactly where in the library you can find the book it represents. We do the same in programming for memory space. There's also usually a NOP in everything that matters for coherent behavior: no operation, just sits there acting like nothing happened preserving it's state..

@mac.8099 11 лет назад

If negative powers of two get maximum efficiency, then what set (or sets) of probabilities has the lowest possible efficiency?

@L33tH4ks 9 лет назад

Awesome video Brady!

@Kelimion 11 лет назад

How would you tell 00 apart from 0+0? Or 11 from 1+1? Or 01 from 0+1. That's why.

@ten.seconds 11 лет назад

So, is unicode a similar approach to these?

@Jamesey162 11 лет назад

10:00 I'm down for that Brady!

@pielover267 10 лет назад

Sorry, I am confused, what does the entropy represent if not the maximum amount that you can compress a file?

@BGBTech 11 лет назад

audio and video compression are also pretty big users. (granted, many newer video codecs use arithmetic coding instead...).

@edwaars 8 лет назад

Using this on my exam tomorrow! thanks.

@Mobin92 11 лет назад

I didn't get it... Whats the use of those codes? Especially in the fishing example it doesn't make any sense to me. It needs 4 bits to indicate 5 different fishes, but 3 bits would have been enough... ?

@Retr0id Год назад

Shout out to everyone revisiting in 2023 ;)

@exiletomars 11 лет назад

Are you going to do a video on recursion?

@mostermand 11 лет назад

Will you do a video on arithmetic coding?

@Hiimstring3 11 лет назад

This is very interesting stuff, thanks for doing the video!

@TehGordonFreeman 11 лет назад

"Here's an unsolved problem, I've done it, please give me a PhD"... New signature :)

@symbolxchannel 11 лет назад

Isn't it important that the codes are not the same length? I mean a "computer" would usually request (wait for) packets of specific sizes?

@SoeaOu 11 лет назад

I don't get it. What do you use this for?

@Kelimion 11 лет назад

You'd first send a header, letting the other party know how many entities to expect when the bits are expanded. And/or you'd add a termination code, which tells you when the list is done. Then you just send the codes sequentially until you fill up a packet, cut there, and send the rest in the next packet(s).

@musikSkool 11 лет назад

Genius, labeling each branch on the way down, so you don't need to go all the way back up to the top for every individual node. I have been doing my trees all wrong! (And I've been annoying Brady about logs for some time now :wink:)

@aphilra 11 лет назад

In the past they did it with annotations who link to related videos. Maybe they just have to add them for this one.

@christiandinkel8481 11 лет назад

In the end of the video, shouldn't it say ternary rather than trinary? Not that I'd know, I just always assumed.

@HenkJanBakker 11 лет назад

That would be a good thing. They do 'outtro's' so it would make perfect sense.

@PapP148 10 лет назад

And here's Brailsford with the weather.

@Mobin92 11 лет назад

Yes, but why is it useful to have a 4 bit code (1110) for the shark? Couldn't the codes also be like this for example? Cod: 0 Bass: 1 Tuna: 10 Shark: 11 Barracuda: 100 Why not? What's better with the huffman codes?

@jsnadrian 11 лет назад

This video should have really contained some sort of motivation for why Huffman trees matter. I understand what Pro Brailsford is talking about ... but if it weren't for his smooth voice and smarty-pants accent, I'd hardly care.

@adrienperie6119 11 лет назад

*eyes rolling in infinite tiredness*

@c.danielpremkumar8495 2 года назад

10.28 why is there a MINUS sign in the formula for "H" ?

@DiaStarvy 11 лет назад

If you want to send a list (say for fish caught in the week), something like "cod, bass, tuna" (0101) would be indistinguishable from "cod, shark, bass" (0101) in your system. Using a Huffman tree solves this problem.

@jimbean5657 11 лет назад

Man I wish RU-vid had a multi-screen display so you could see what someone is writing while watching them talk.