How Huffman Trees Work - Computerphile

[@TonyManso]

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

[@jonnypanteloni]

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]

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

[@Cathalion]

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

[@AvZNaV]

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

[@pdieraue]

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.

[@Cyberkygen]

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

[@PiratWeber]

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

[@Booskop.]

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 =)

[@joealias2594]

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

[@Kelimion]

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).

[@AlanKey86]

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

[@Kelimion]

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.

[@Keduce22]

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.

[@timsiwula]

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

[@JimCullen]

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.

[@sanko111]

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.

[@MrCOPYPASTE]

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

[@dooge1992]

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.

[@Disthron]

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.

[@cyberb4ss]

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

[@mkaatr]

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.

[@Kelimion]

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).

[@samposyreeni]

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. :)

[@qwertyfinger]

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.

[@Toksyuryel]

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.

[@parkamark]

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.

[@Kelimion]

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.

[@MeepMeep]

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

[@MrAnonymousCitizen]

This man's voice is wonderful.

[@Vulcapyro]

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.

[@stellarfirefly]

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".)

[@TheMoolica]

So Huffman was Australian?

[@Kelimion]

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.

[@MeepMeep]

THIS MAKES SO MUCH SENSE THANK YOU

[@thecassman]

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.

[@U014B]

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

[@MrCOPYPASTE]

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.

[@taesheren]

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

[@GilliamHimself]

A numberphile about logarithms would be very helpful

[@mage1over137]

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.

[@StSin666]

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.

[@LudicrousTachyon]

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.

[@TylerLarson]

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

[@Kelimion]

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.

[@razorborne]

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.

[@Retr0id]

Shout out to everyone revisiting in 2023 ;)

[@millionsteve]

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

[@Tat2ice]

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 :)

[@Nathan-ji2nd]

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

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

[@MichielVanuytsel]

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

[@vicpc55]

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.

[@jimbean5657]

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

[@NoNeaNaNoNly]

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.

[@JanCRefsgaard]

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

[@Kelimion]

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.

[@Beesman88]

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..

[@gpaluk]

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.

[@jimbean5657]

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

[@geordonworley5618]

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.

[@uriituw]

I loved studying Huffman encoding in uni.

[@TheLatterPartOfToday]

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

[@JBinero]

Maybe it's because the 1/3rd happens 3 times as much as the 1/9th, so it kinda makes sense to give it also a way shorter code.

[@Kelimion]

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).

[@TheMohawkNinja]

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?

[@eideticex]

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..

[@yukhui]

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?

[@StSin666]

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

[@DiaStarvy]

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.

[@HenkJanBakker]

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

[@edwaars]

Using this on my exam tomorrow! thanks.

[@TheWeepingCorpse]

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

[@shaihuld]

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

[@HenkJanBakker]

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

[@exiletomars]

Are you going to do a video on recursion?

[@symbolxchannel]

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?

[@BGBTech]

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

[@pielover267]

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

[@Mobin92]

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... ?

[@Mobin92]

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?

[@mac.8099]

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

[@HenkJanBakker]

Reminds me of mushrooms. What we call mushrooms isn't actually the plant. It's only the fruit. The actual plant is underground and (normally) invisible. It is the biological equivalent of a black box. Result seem always the same: A mushroom..... but underground there are also results we don't see. Actually we miss everything except these 'blips'. Does this make sense in this context to anybody?

[@kolnder]

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?

[@he1986]

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

[@scotianbank]

This Washington my last project for programming 101 in Java

[@L33tH4ks]

Awesome video Brady!

[@mostermand]

Will you do a video on arithmetic coding?

[@Kelimion]

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

[@recklessroges]

If you mean that the codes are the fruiting body of the mushroom and the "roots" in both cases exist but are hidden - then yes.

[@lloydgush]

Yes! S for entropy, and H for enthalpy!

[@daedra40]

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

[@taesheren]

Just thought I'd point out that mushrooms (and other fungi) is not plants. They are considered a separate form of organism from plant life.

[@christiandinkel8481]

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

[@ten.seconds]

So, is unicode a similar approach to these?

[@aphilra]

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

[@Vulcapyro]

Look at how the tree was constructed and take for example the bit string 01011111100. You read the first token, it's 0, Cod. You read a 1, ok, then you read next token. 0? Bass. 1 1 1 1, Barracuda. 1 1 0, Tuna. 0, Cod. There is no ambiguity in how it's read.

[@SoeaOu]

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

[@Keduce22]

Programming is a form of mathematics, they go hand in hand. Programming is a way to solve a problem logically. You could even go further to a proof which states that any algorithm is in fact a Turing Machine and every turing machine can be written as a single statement which would resemble more what people expet mathematics to look like. No really a practical thing to do though.

[@c.danielpremkumar8495]

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