Это видео недоступно.
Сожалеем об этом.
How Huffman Trees Work - Computerphile
HTML-код
- Опубликовано: 17 окт 2013
- 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/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
I just love his enthusiasm and ability to simplify things that might otherwise be difficult to understand
"And now a bit on chemistry...." The mans level of knowledge is astounding lol.
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!
Just wrote a file compression program in smalltalk for my class. I love how he explains the algorithm.
I used H for enthalpy in my chemistry classes, S for entropy and Q for heat
Does anyone have a link to the original 12 page paper David Huffman published in 1952? Thanks!!
Title confused me, because I'm so used to seeing upside down trees!
I would like to have this gentleman as my teacher! So inspiring!
I absolutely love this channel (and numberphile of course). Thanks for another great video!
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.
THIS MAKES SO MUCH SENSE THANK YOU
Best teacher ever, can't wait for it to get deeper ^^ !
This is very interesting stuff, thanks for doing the video!
That... Actually made an amazing amount of sense. Kudos
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.
7:00 Need an example sea creature? Why not Zoidberg?
Nice one professor, I was actually confused with the entropy symbol, and you saved me :P
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 =)
Awesome video Brady!
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.
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).
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.
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.
I could listen to his voice for hours and hearing about computer science.
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.
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
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.
so is 10 = tuna or is10 = to bass followed by cod? how would the receiver distinguish between them?
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.
I...I understood this one! I was giving up on computerphile and relying on numberphile for all my smarts!
So Huffman was Australian?
LOL. Eye rolling sure brings the 'I don't get it' to a whole new level.
This man's voice is wonderful.
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?
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.
Couldn't agree more! Great stuff :)
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).
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?
Best one so far
Sorry, I am confused, what does the entropy represent if not the maximum amount that you can compress a file?
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?
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. :)
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
Are you going to do a video on recursion?
Using this on my exam tomorrow! thanks.
Will you do a video on arithmetic coding?
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.
A numberphile about logarithms would be very helpful
That depends on the possiblities of the different answers :) Huffman code gives you the smallest average length (or power length, not sure)
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.
love this guy great vid
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 :)
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.
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.
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".)
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.
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.
I'm currently writing a master thesis on FPGAs. I love hardware stuff =)
Studying for my midterm by watching Computerphile feels wrong. I'm not supposed to enjoy studying
So, is unicode a similar approach to these?
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.
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.
Damn. What part of youtube am I on now? A polite conversation between a comment and a reply.
Compression. Given the relative frequency of a a given set of "words", determine the smallest way to store some sequence of words.
Very interesting video.
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
Very nice!!!
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.
How would you tell 00 apart from 0+0? Or 11 from 1+1? Or 01 from 0+1. That's why.
I loved studying Huffman encoding in uni.
If negative powers of two get maximum efficiency, then what set (or sets) of probabilities has the lowest possible efficiency?
Learned something new today :) +1
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
Why did he start with an example where every probability is equal? That makes the encoding totally arbitrary and really defeats the whole point.
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.
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.
It was not directed at you specifically. I just thought I'd put it out there, because I know it is a common misconception.
10:00 I'm down for that Brady!
And here's Brailsford with the weather.
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.
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.
Ok. It make sense now... Thank you for answering! ;-)
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.
I agree....the camera work in most of these computerphile videos do that. it's like it's filmed for dramatic effect than education.
audio and video compression are also pretty big users.
(granted, many newer video codecs use arithmetic coding instead...).
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.
Right you could divide into two spaces... I was thinking more along the lines of a Mediasite Video presentation style since RUclips presenters are advancing in their production values. Anyhow... sorry for interrupting the thread
*eyes rolling in infinite tiredness*
"Here's an unsolved problem, I've done it, please give me a PhD"... New signature :)
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... ?
Thanks, that also answered my other question. :)
I have a question if anyone can answer... why doesn't he make the first two probabilities have a "code" of 0 and 1 and the next four be 00, 01, 10, 11 and so on for how ever many there are to save on bit space? Why do they all have to be the same amount of bits long?
Huffman coding guarantees lossless compression. If he had just set the probabilities without building a tree from the probabilities then the receiver of the data has no way of reversing the code back to its original state. Example, for A = 1 B = 0 C = 10, then how would you know if 110 meant AAB or AC?
Oh i see... thanks!
This Washington my last project for programming 101 in Java
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..
That would be a good thing. They do 'outtro's' so it would make perfect sense.
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.
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..
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.
I don't get it. What do you use this for?
In the end of the video, shouldn't it say ternary rather than trinary? Not that I'd know, I just always assumed.