Entropy in Compression - Computerphile
ฝัง
- เผยแพร่เมื่อ 9 มิ.ย. 2024
- What's the absolute minimum you can compress data to? - Entropy conjures up visions of chemistry and physics, but how does it apply to binary codes and computer science? Professor David Brailsford continues his discussion of compression.
Addendum: the formula at 4:40 is the "weighted average bits for that state"
rather than the total number of bits - (log^2)
Original Professor Brailsford film on compression: • Compression - Computer...
Professor Brailsford on Error Detection: • Error Detection and Fl...
/ 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:periodicvideos.blogspot.co.uk/...
The last example is actually pretty good, too bad that you didn't do the matching calculation in the video itself to show why possibility can matter *a lot* in compression:
1/2 of the time you send 0 = 0.5 * 1 = 0.5 bits
1/4 of the time you send 10 = 0.25 * 2 = 0.5 bits
1/8 of the time you send 110 = 0.125 * 3 = 0.375 bits
1/8 of the time you send 111 = 0.125 * 3 = 0.375 bits
Which sums up to only 1.75 bits needed per state, saving 12.5% of bandwidth, and shows nicely how knowledge about the to-be-compressed data allows beating the standard approach of taking log(number of states) as the number of bits needed, which is pretty much always the worst case for compression.
This guy looks so incredibly passionate about what he is teaching. If he was at my Uni, I would not regret paying my tuition if I knew he was getting paid to teach me.
Damn. Makes me wanna be a professor.
His voice is so relaxing. I would love to hear an audiobook read by him haha.
You should have uploaded this video in 144p
That professor is such a badass :)
I love that on your channels you only find talented enthusiasts that not only explain stuff very clearly but also make it sound fun. Good job, Brady.
Once again Bradey asks the perfect questions. I think he has a great gift to help get the information across to viewers.
I have no idea how I passed my chemistry tests on entropy, the way those books explain those concepts is so terrible. I just remember memorizing something along the lines of "entropy is a measure of disorder, and it always increases" and I didn't have any freaking damn clue what that even meant or why that was significant. The state of education is so bad. it just a plug'n-chug system, no creativity. Absolutely no passion for teaching or in learning is instilled into people.
Great video!
Annotation added for absolute clarity (though the Prof says it almost in his next breath) >Sean
What a pleasure it is to hear somebody who knows what he is talking about answering sensible questions.
Probably the best one Computerphile has done so far. This covered so much ground clearly and in only 12 minutes.
"We edit nothing out of you" and everything befor and after that is pure gold.
Do steganography one of these times pls.
I found myself drawn into this video more than I usually do for these kind of videos. The topic was shown in a very interesting way and the professor's voice quite enjoyable to the ears.
A big part of the greatness comes from the questions asked by the student.
This is precisely the type of content this channel needs.
Couldn't the weather in San Francisco be transmitted more cheaply if leading zeroes were omitted?
0 = $1000
1 = $1000
10=$2000
11=$2000
Average number of bits needed: 1.5
Average cost for transmission: $1,500
In fact, no weather report could be interpreted as sunny.
= $0000
1 = $1000
10 = $2000
11 = $2000
Average number of bits needed: 1.25
Average cost for transmission: $1250
Now that we've freed up the zero, I suppose we can move all the values down by one.
= $0000
0 = $1000
1 = $2000
10 = $2000
Average number of bits needed: 1
Average cost for transmission: $1000
Just saying.
Of course, I'm probably breaking some cardinal rule of information theory with this.
*EDIT:* Yes people, I understand why I'm wrong. You can stop telling me.
Nathan T Hi Nathan, I think this is happening because TH-cam is showcasing your comment as a "Top Comment" but it does not show the countless replies that have been made so far -.- So now and then someone is going to see your comment, not realise it has already been replied to, and reply to it. It's not going to stop unfortunately I think.
Quanxiang Loo
Oh.
I think I'll edit the comment, actually. That should work.
I loved the style of this video. It's great seeing the professor talk to Brady. It brings another level of humanity to the conveyance of the topic.
This guy is awesome.
He should have his own TV show or movie documentary.
I'm a CS major and this channel is teaching me more than my class so far.
Okay, I'll admit I've already learned what this class is teaching from youtube as well, but that's beside the point.
This guy has an amazing way of holding my attention for long videos.
I love Brady's incisive, curious and critical style of interviewing.
Imagine having him as a lecturer, he's definitely one of the best!
This is my favorite phile site!
Great job delivering educational and fun material,
thanks guys
This professor is awesome... He seems like a GREAT teacher, if allowed to teach
I have spent the last 3 years of mathematics thinking logs were useless now. Thank you for proving me wrong.
This is a good one. Don't shy away from the details!
I'm really enjoying these computerphile videos.
I hope to see more from this gentelman. I is mindblowing how one's passion to anything can transfer to others through a youtube video. inspiring!
This is awesome!! I always wanted to know how this worked! What a great guest!!
Yeah, he quickly gets to the point, he doesn't mess around when explaining and explains extremely well. On top of that he just seems so passionate about what he does, if that were my field of study, you couldn't ask for a better teacher.
the limit of Brady's channels as it approaches infinity = an intellectual society.
I hope we get much more from Professor Brailsford, he's great.
Wow, I actually learned something new on this video. I had never thought about this in all of my time of programming and working with computers. Keep it coming computerphile. Also, I am glad I subed to this channel.
I would pay anything to get a class with this guy. So inspiring!
PNG: each scanline is fed through a filter, which predicts the pixel value from the nearby pixels, and the best choice is encoded on a per-scanline basis. then the output is fed through Deflate, which may recognize patterns but more often does RLE, and which also applies the use of Huffman coding.
for example, each pixel could be predicted by subtracting the value of the pixel to the left. if they are the same color, you get "0,0,0,0", and with a lot of this, the image compresses nicely.
right, I'm going to clear some stuff up about those who want to get around this problem.
sending data at x mins past the hour
christian wagener -
"
Send a "0" on the hour = weather A
Send a "0" one min past the hour = weather B
Send a "0" two min past the hour = weather C
Send nothing = weather C
Single bit at $750 on average:)
"
the problem is, what if the weather changes 30 from weather b to weather a 30 seconds after hour? you'd be left with a problem. even if you think "oh just give the data recorded on the hour", the problem is, I don't want to wait 2 mins to get the info, I don't want to wait any amount of time. time adds entropy, sure. but If I ask for the weather, I need it now.
another problem is what if the connection break? then we think they have weather C constantly.
MRAROCKERDUDE -
"
I don't know if this is just reading too much into the weather metaphor but could you not encode the different weather states as 1, 0, 00, 11?
"
the problem here is, it's not like speaking. you can't just stop half way through the sentence to add entropy like you can with speaking. think of it like a bunch of 1s and 0s going through a data line.
say I have 4 weathers and I encode them as 0,10,111,110 this is good because I can do this: 01001000110 and I know what it means. with weather 1 being a and weather 2 being b and so on I can say that is: a ,b ,a ,b ,a ,a ,d
however if it was 0,1,00,11 well... try decoding this: 01001010110010
Just start watching all of those, and I love it, thx.
that's the storage vs. time thing I'm sure we'll get to eventually.
The various notions of optimality in computer science sure will give some nice videos.
Maybe even how various compressions and codings relate to temperatures in physics. I've recently read a paper on a basically 1:1 mapping between code complexity and thermodynamics.
Great video. FYI the encoding method he is referring to for encoding varied probability symbols (7:38) is called Huffman encoding.
I love this man. Make him a regular, please :3
Getting closer to Huffman coding used by LZH / ZIP compression. I hope we'll see more about that. Also as long as we're looking at image compression it would be cool to see a demo in slow motion of a JPEG, GIF, and PNG decompressing into a visible buffer.
Its great to see videos about entropy, I hope to see more on information theory which is exiting and unfortunately underrated....
This was the best computerphile yet :) You really can't separate computers and maths (if you are talking about the internal workings at least). Computers are logical systems... math is logic.
Awesome video! It gives an interesting insight to the statistical meaning of entropy
The presenter always asks good questions
I love seeing these compression and data videos
Very nice explanation indeed. These concepts are so important these days for machine learning algorithms :)KD
Great job Brady! Another excellent video!
It would be nice to see an episode on gray code counters and their applications. I was intrigued by that when I learned about it in comp sci classes years ago. I imagine they're used in countdown timer circuits to avoid transient states associated with critical events.
The probabilities of a state have nothing to do with how many bits you need except when all states have equal probability. If there was one chance in a million of rain in the Sahara and one million minus one out of a million of sunny, then you still need only one bit to determine the state. The limiter is how many states you wish to report on.
After this video, an introduction to Huffman encoding is an absolute must have. Once you know that you should give shorter codes to more probable events, then huffman coding is the next step to deciding which codes should be used. It's also dead simple to teach.
I like this new channel a lot.
That was great...Truly interesting. Thanks Dr. Brailsford & Brady.
love this guy!!! get more videos of him Brady!
It was a bit confusing, but the formula -(p*log(p)) is normally not used alone, but rather one sums over all events that are possible and so the p term is just to obtain a weighted sum since what one is really interested in is what the average number of bits is for an event.
The -(log(2^-2)) formula comes from the summation formula and you get (-1/4*log(1/4)) + (-1/4*log(1/4)) + (-1/4*log(1/4)) + (-1/4*log(1/4)) = -log(1/4) but this only works since the events are equiprobable.
You should specify that entropy is reached only for statistical compression algorithms. With LZW for example you can go bellow that. You should do a video about it, because it's quite interesting. I was mesmerized the first time I learned about it.
You're actually correct. In this case your interpretation is very valid. As long as the receiver and the sender both sync up at a particular time to communicate, then you can use that scheme. However, what he described in the video is the precursor to large file compression. If you had to send weather data from many different cities, you can have a bit stream that starts like "000000...". The receiver would not be able to tell if that's 6 sunny or 3 rainy. The method here is Huffman Coding
Yes, we want to see more videos with him.
These videos are awesome.
Ahhh... My Information Theory course is all coming flooding back to me. My favourite course at Uni, too... Claude Shannon was a badass.
I wish I had such a professor in my college
He's not dumb, he represents the common man, that's why he always talks to experts on all of his channels and asks probing questions.
What a fantastic professor
Brilliant Episode.
I love this channel.
Given context, you can compress 4 states to fewer than 2 bits.
For example, you could say that if the weather is unchanged, only send one low bit. This requires the listener to be able to determine whether it is a 1 or 2 bit signal, which means either having metadata such as a length header, or a timeout to determine the end of the signal.
This guy is an excellent instructor!
in a real-life data-format, also typically the Huffman tables are sent prior to any globs of encoded data, so a single decoder can deal with multiple sets of data. in a format like Deflate, the tables are themselves entropy coded.
some formats (such as MPEG) use fixed tables, but still send a synchronization code and basic headers (for each frame).
(some others send tables only on I-Frames).
the Huffman table basically tells how to map the particular symbols to the particular bit patterns.
I could listen to him for hours and retain every word.
Great vid Brady!
Damn it Brady, where do you find these amazing people?
More of this guy :D Excellent vid Brady as usual thanx
this vid is awesome. and the professor is great.
This video goes quite nice with the most recent Crash Course Chemistry video
I just didn't get this back when I was in my teens. I was sure there must be a way around it. Its only when i got older that it seemed obvious. Lossy compression is another story. There may be ways to improve that.
Insane video for these guys, for their memory. I wonder how their life changed since then.
In addition to the length of the tone that others have mentioned, there are also other ways of differentiation high from low bits. For example, they could be at different amplitudes (volume) or different frequencies (pitch or even colour). This is known as modulation.
Great explanation!
This guy is great at explanations. Keep the videos going Brady!
11:37 Lakasomeboooooodeee.
It is amazing that you made such a simple and easily corrected mistake, but that you do not have enough intellectual humility to just understand where you've gone wrong, accept it, and move on.
There are some underlying issues that are specific to network theory and confidence in the received data that they cover *very* briefly in the beginning when they discuss sending a zero for sunny in the Sahara "just to be certain". You need high confidence that you actually received the correct message, and treating null as a state ignores many other possibilities in this scenario (cut wire, building on fire, etc.).
Hello! Considering that there is another video on compression (as there are multiple videos on sorting for example), a suggestion may be to put a link in each other's description to point to the next and/or previous video. This would keep everything toghether.
Thanks for the excellent reply bud.
I was being a bit more abstract though. I wasn't thinking of the 'data' being sent by computer, just coloured light. So, for example, if the weather was sunny, the colour is orange etc.
It was only after I posted it that it dawned on me he meant 'bits' literally as binary digits. I was being a bit more analogue :)
I want to say that practicaly you can send the LA wheater report in one byte if you use time differences. sunny - send 0 at 5 : 30, rainy - send 1 at 5 : 30, foggy send 0 at 6 : 00, cloudy send 1 at 6 : 00.
Time is information. You may physically send one bit, but the time is an implicit source of information no matter how precise you want to be. When we talk information theory, we're interested in all factors that may constitute "information".
And it still ignores the various possible problems that may occur in transit, which can include unpredictable delays in timing, throwing off the system. As mentioned.
You could sent one click at a certain time for each different message. Send at 8:00 if sunny send at 8:01 if rainy. Right?
You're almost correct. Most serial communication system use a clock called "BAUD rate" but they use -volts for logic high, +volts for logic low and 0v for idle. Old RS232 used +-12v
One of the hardest things about client-server relationship in an environment that is time dependent is getting them both to "think" in the same frame of time. Have a read particularly at video game client-server synchronization techniques and you might understand just how complicated this issue is.
in the video, yes, basically.
they didn't talk about the (relative funkiness) that is arithmetic coding though, which can also use fractional bits, but is still limited by entropy limits. it typically compresses slightly better at a significant speed cost vs Huffman (Huffman is generally preferable as it is much faster, and the size difference is usually fairly minor).
ergo, it;d be ambiguous if it were automatically decoded. you are exactly right. the code has to be the expected length. but wen you;ve only got four conditions the supposition I took was that the telegraph operator would manually decode it. He was speaking to the fundamental elements of complete and unambiguous code -- I didn`t realise you were informed, while relating to you the simplest situation as I could, as an answer to your question.
This reminded me of the golomb coding, which is one of the lossless compression methods heavily employed in MPEG standards.
I love this guy, he's very interesting.
I love his enthusiasm.
Oh, I get it now. Thanks for the explanation.
like they mentioned later on, it cannot be a prefix of another code. in your example if you get a series of codes, like 1010 is that sunny, rainy, sunny, rainy or is that foggy foggy? i dont think they did the best job of describing this, but its in there!
Wish I had a teacher like him.
A "baud" is a physical link-level symbol that can have any number of states, not just two. Many modulation schemes allow for encoding multiple bits in a single baud/symbol - don't worry, this is widely known and used.
Please go over to the wikipedia page on bauds and symbol rates and read up (and stop by the page on QAM as well). I can't repeat what's on there in 500 chars, and the articles address your questions quite exhaustively.
The reason why prefix codes are used instead of what you propose is because a continuous sequence of such codes would be ambiguous. For instance in your proposed code the decoder can't distinguish whether "0001" means "foggy(00) sunny(0) cloudy(1)" or "sunny(0) sunny(0) rainy(01)" or any other valid combination. You'd have to waste more bits for a 'word length' prefix or some framing structure to allow you to detect word boundaries, and at that point you might as well use a prefix code.
Amazing, you have my subscription.
Perhaps it should be mentioned that the calculation for number of bits per state, p*log(p), is based on minimizing the expected total cost of transmission.