This is the last of the three trial Basics videos! This pushed my quick-explanation skills to the limit, but I figure that "slow down the video and replay if necessary" is better than "let people get bored"...
These are really great - this one taught me something new, and I really do feel like I understand it now! If you do this again, and you go to the Computing Museum, will you let people know, or will it be a surprise? :)
+miles4711 I also watch there. But Tom's approach here was well done in a way I hadn't quite seen before. That said, I'll look up those specific videos you mentioned. Thanks
So basically, this method is the best given the frequency distribution of those single characters. But... if you have more information on how your data is distributed/patterned, you can get further compression by using those patterns.
It's amazing how every video that Tom puts out always has an incredible amount of attention to detail. Take for instance the increase in video compression when he talks about it (0:43), him saying "worms" instead of "words" when talking about (0:52) lossy text compression, and the fact that at (4:40) he does his gestures mirrored so it is our left and right and not his left and right. On top of that he does it all in one take. I'm always amazed when a new episode comes out.
I've been binge watching your videos for the last few days procrastinating on my homework. Now my CS class has a question on a Huffman tree, and I end right back up here. Thank you, Tom. You made it super easy.
During my encoding class I had to write a program that compresses files with huffman coding. As I was turning back my program the professor asked me: -Where is the source code? -Oh here, you just have to decompress it with my program.
"You know how I was supposed to be picking a version control system? Well, I decided I didn't like any of them, so I wrote my own and checked it into itself. I put the repository on my web site..."
Yeah once I was like "Wait does git has it's own repo where it keeps track of itself? (check) oh actually it does". Another thing is that gcc is written in c, so it can compile itself.... moreover it can compile a newer version of itself
Everyone's talking about Tom sending the wrong worms, but there's precious little talk about the video quality going drastically downwards as he talked about video/images being lossy compression right before that.
Thus proving his point that some things like images or audio can be compressed using a lossy technique without losing any of the actual meaning (we could still see and understand a lower quality video.) you only loss detailing.
I think that's because everybody noticed that and it was a pretty obvious and predictable joke, whereas "sending the wrong worms" makes people do a double take.
THANK YOU TOM SCOTT!! I have wondered how compression like this worked for the better part of a decade, and I've even put a decent amount of time into researching it, but it never clicked until this video. You have the best content on this entire platform, both in subject matter and quality.
Tom Scott, you, sir, are a genius. Nobody has ever been able to explain something like this to me in such a simple fashion, I actually understand this now, and I could decode a file by hand with a Huffman tree now just from what I learned in your video.
try Wow Wow by Neil Cicierega, I can assure you Wild Wild West (and All Star if you fall into the rabbithole that is Neil) will have a brand new type of impact on you !
This is amazing. I am a CS student, and needed to implement a huffman algorithm as an assignment. There's an explanation in the assignment about the huffman algorithm, but it's really poor. Having watched this video before, I came back to see if it could explain the algorithm, and Tom nails it. The algorithm is explained well in a way that both the layman and the experienced can understand. Tom is an excellent communicator!
This guy really seems like he LOVES to teach what he knows and is passionate about! I'm really enjoying the enthusiasm as well as the knowledge being shared. This is so good❤
Wow, everyday I see that Huffman reference in my daily job and I use it to pack files, and I never new it was a masterpiece of software engineering. thanks for explaining it so well
Video 4 years old at this point, but relevant and awesome as ever. I am a big fan of compression, because I hate wasting anything in life. Hate wasting food, wasting water, wasting gas, wasting time......... And wasting space, physically and digitally! I like to experiment, what kinds of files can be further compressed through means like Winrar. Videos and images (like JPEG and PNG) usually can't be compressed any further, but I found out at some point, that for example Photoshop files (.psd) can often be heavily compressed. Depending on their content, really. But I have had compression rates of up to 93% on particular files. What a load of wasted space.
Would love to see more of these. Even when I already know about what you're explaining, your videos are so superbly made that they're still fascinating to watch.
An extra joke for those who watch with subtitles at 0:53, if anyone's interested. I love how Tom puts in that extra touch every here and there, even though most people probably wouldn't notice.
This is magic. I've just finished my text compression algorithm in C++ the day before yesterday, and this video was uploaded. I feel I'm being observed.
I've been in IT about 26 years and learnt something from this video. Never knew how compression worked. Explained very clearly. Or vry clrly. Or 10010011000110001.
It's pretty simple really. Huffman Trees are very straightforward. Think about a short tree, like this one: o / \ o B / A o C D This means our alphabet has 4 letters. A, B, C and D. Now I want to compress a short text using this tree. The text is "DAB" (sorry, only thing I could think with these letters) So, we'll start by converting D into binary. To get to D, we gotta go to the left twice then to the right once, so here it goes: "Left Side: 0, Left Side: 0, Right Side: 1". So a D corresponds to 001 in binary. Now to get to A, it's 1 left and 1 right, so 01. Now to B, all I need is 1 right. so 1. This turns DAB into 001011. 6 bits of information. When you read this file, you'll convert 001011 back into DAB by doing the opposite process. You'll read bit by bit: 0 -> go to the left once. It's not a letter yet so read next bit. 0 -> Go to the left again, it's still not a letter so read next bit. 1 -> Go to the right. Oh it's a letter, letter D. OK so writing it down on the output: D. Now reset to the tree root and read next bit. 0 -> Left. Not a letter. Next Bit. 1 -> Right. It's the letter A! Write it down to the output. DA. Reset to root and next bit! 1 -> Right. It's the letter B! OK! Write it down to the output. DAB. There are no more bits to read so it's done! Your text is DAB!
I teach Huffman Coding to my intro to programming students at Stevens Institute of Technology, an engineering university in Hoboken, NJ. Starting this semester, I will absolutely be showing them this video prior to them working with Huffman Coding!
Karate Girl91 There are a lot of sophisticated compression algorithms. Zip, 7z, rar, gzip, deflate, bz2, botli, etc. Some of these are stream algorithms, and tend to work in a concert with tar to compress folders.
It's not Tom, but Prof. Brailsford did a video explaining LZ77, which is still a very popular compression algorithm, variants are used in in ZIP, Gzip, RAR etc. It's easy to understand and a good place to get started if you want to learn more: ua-cam.com/video/goOa3DGezUA/v-deo.html
This is really cool. Honestly really curious as to how the tree itself is stored. That would be really cool. Tbh I want Tom to teach a whole computer science basics class.
What I did was to store in the header of the compressed file the preorder traversal of the tree and then an array with information about which nodes are leaf nodes. You could also store combination of 2 different traversals, but "my" solution would only take up to [number of nodes] + ceil([number of nodes] / 8) bytes - not that significant difference, but still a difference :P
idt the tree itself is stored it is just used to create the translation list which is used to compress the data, then you can send the list and the compressed data
love that your getting back to the educational stuff. Breaking down complicated topics in computing or explaining how a hack was done was always a fave.
Awesome presentation....inspired by you...I am an IT engineer...:wanna start my tech channel too after viewing your video and fan base....wish me good luck ☺️☺️☺️
A note about image/video compression at 0:45 : there are a lot of lossless compression methods, especially for images. You don't typically deal with uncompressed lossless files (e.g. bmp, the netpbm formats, raw images), but rather png (more or less row by row zip compression), gif (lossless if you fit the 256 color palette) or other lossless images.
This video was SUPER helpful! Thank you Tom!! I can't go to IRL classes right now - pandemic and all that - and this introductory video is the next best thing. And dare I say, my teachers are not as skilled at succinct explanations. Thanks!!
Just want to thank you for this video, because if I had taken a computer science exam this summer (cough cough COVID cough cough), this video would've been extremely helpful!
Let's imagine we have some "compression" tree and a string consisting of 10111010... . Every letter has an individual number assigned(the number is assigned with the tree). some are 4 digits long some are longer. So the computer sees the 1 and compares it with every assigned number. So the Pc checks 1-(every assigned number). If the result is zero it arrived at a letter. So the pc checks 1. No zero as result. Take the next bit 10. No 0 as result. Next bit 101. Still no zero as result. 1011 we get a zero as result. And display that letter. then we start again. 1. no zero as result .... Every letter has an individual path. So there will never be a letter assigned to 10111. that's how the pc knows when to seperate the string.
It separates the letters by referencing the tree. As it gets 1s and 0s it goes down the tree until it hits a dead end. The letter at that dead end is what is outputted, and the program heads back to the top of the tree. The structure of the tree is how it knows where the breaks are.
No branching point has a letter so if the point it comes to has a character instead of a branching path it has found the character needed and the next bit starts at the top of the tree.
Look at the graph at 5:02 Every time the computer reads a 1 it goes right in the tree, every time it reads a 0 it goes left. In this infinite sequence of zeros and ones, you only get to a letter at the end of a branch. You can imagine letters at the end of the branch as "leaves" in a tree, where every branch must end in one and only one leaf. The computer stores the entire tree so it knows if the sequence has reached a leaf or if it is still on a branch. If, with the last bit read, you did not get to a letter (end of branch) you continue reading. If you got to a letter, write the letter and start a new one.
Your presenting skills get smoother and smoother. Pretty soon you'll be doing ten minute, one-take videos (without blinking), on how to film one-take videos!
At 2:16, the text "0100111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000110011101101001011101100110010100100000011110010110111101110101001000000111010101110000001011000010000001101110011001010111011001100101011100100010000001100111011011110110111001101110011000010010000001101100011001010111010000100000011110010110111101110101001000000110010001101111011101110110111000001010010011100110010101110110011001010111001000100000011001110110111101101110011011100110000100100000011100100111010101101110001000000110000101110010011011110111010101101110011001000010000001100001011011100110010000100000011001000110010101110011011001010111001001110100001000000111100101101111011101010000101001001110011001010111011001100101011100100010000001100111011011110110111001101110011000010010000001101101011000010110101101100101001000000111100101101111011101010010000001100011011100100111100100101100001000000110111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000111001101100001011110010010000001100111011011110110111101100100011000100111100101100101000010100100111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000111010001100101011011000110110000100000011000010010000001101100011010010110010100100000011000010110111001100100001000000110100001110101011100100111010000100000011110010110111101110101" should've flown across the screen really fast, just to really drive the point home.
I believe you look much more confident in compare to your previous videos, and also I wasn't expecting that your video will be so hypnotically extremely understandable; but you just nailed it. Thanks for sharing!
My teacher is trying to teach this, I hop on youtube and learned the concept in 7 minutes. go back to zoom, teacher haven't done with the example yet 🤣
Marvelous imagery! If it weren't for the intuitive visuals and your keen explanation, I would have never understood this. This is fascinating once you get it!
Great summary. This method is also combined with LZ ("repeat 6 characters starting 8 back from the one you just decoded") and RLE ("repeat this character 5 times"). As far as I know those plus Huffman are the fundamentals of every compression algorithm.
This video was well-written, and the execution was exceptional. Engaging, informative, and entertaining. Very nice! I would like to see more like this.
Funnily enough, I have proved mathematically that Tom Scott's videos are the most efficient way to insert knowledge into my head. (Do I win a Nobel prize?)
The issue is that people are getting higher resolution displays, needing higher resolution textures, and games are using less repeating textures to make each location feel unique.
![How are Images Compressed? [46MB ↘↘ 4.07MB] JPEG In Depth](http://i.ytimg.com/vi/Kv1Hiv3ox8I/mqdefault.jpg)
This is the last of the three trial Basics videos! This pushed my quick-explanation skills to the limit, but I figure that "slow down the video and replay if necessary" is better than "let people get bored"...
Are you bored of this realm?
Tom Scott 2 days ago??
These are really great - this one taught me something new, and I really do feel like I understand it now! If you do this again, and you go to the Computing Museum, will you let people know, or will it be a surprise? :)
I know some people can't cope with the high speed delivery, and thus just stop watching - if YT had an easy 'slow this video down' button....
We need more like this.
Dang, that last line got me. I want a series on more than just the basics now!
WΔY ΔWΔY The channel Computerphile (where Tom also featured a few times) has something on Huffman coding. And a lot more interesting stuff.
+miles4711 I also watch there. But Tom's approach here was well done in a way I hadn't quite seen before. That said, I'll look up those specific videos you mentioned. Thanks
So basically, this method is the best given the frequency distribution of those single characters. But... if you have more information on how your data is distributed/patterned, you can get further compression by using those patterns.
Right? I've got total blue brains now.
Then I suggest you check out Crash Course Computer Science. It's a bit more than just the basics.
Would love to learn more about compression! This was fascinating :-)
xisumavoid 😱 I love when someone I admire on yt also admires someone else I admire, I wish you both the best.
Did not expect a Minecraft youtuber here!
Second comment I have seen from you on this channel!
wow uh hi
ecks eye zooma void
It's amazing how every video that Tom puts out always has an incredible amount of attention to detail. Take for instance the increase in video compression when he talks about it (0:43), him saying "worms" instead of "words" when talking about (0:52) lossy text compression, and the fact that at (4:40) he does his gestures mirrored so it is our left and right and not his left and right. On top of that he does it all in one take. I'm always amazed when a new episode comes out.
Speaking of one take, have you seen the ending to "Will UA-cam Ever Run Out Of Video IDs?"? :)
frletmiflm with their old kit
Tom if you keep this up people will realize its not magic. If I have to stop wearing my wizards hat to work Ill spell you so hard.
Naa we just have to make doing the same thing more esoteric therefore appearing as advanced wizardry... just like we have for the last 20 years.
Ömåå
Å
Few people even watch UA-cam videos like Tom Scott's and other educational stuff. Don't worry, most people are on music and entertainment.
@@traewatkins931 40 years. I started working as a programmer in 1979 😱, and that's how it was then 😂
@@unlockwithjsr for some of us this is entertainment
3:00 God how I love the square sneaking of the screen
I've worked with various compression algorithms derived from Huffman and this is the best description of it I've seen.
"... or you'll send the wrong worms" damn Matt, that joke was awful!
I live how many of the comments are pointing that out and also changing one word in the comment as well
at which point translators just gave up subbing the video ಠ_ಠ
"Send Words" changing one letter becomes "Send Worms", becomes "Sand Worms", becomes THE SPICE MUST FLOW
'Matt'
Are you kidding? That was grape!
I've been binge watching your videos for the last few days procrastinating on my homework. Now my CS class has a question on a Huffman tree, and I end right back up here. Thank you, Tom. You made it super easy.
During my encoding class I had to write a program that compresses files with huffman coding. As I was turning back my program the professor asked me:
-Where is the source code?
-Oh here, you just have to decompress it with my program.
How many quines did you submit?
I'm not sure if it counts as a quine as it takes an external file
"You know how I was supposed to be picking a version control system? Well, I decided I didn't like any of them, so I wrote my own and checked it into itself. I put the repository on my web site..."
Yeah once I was like "Wait does git has it's own repo where it keeps track of itself? (check) oh actually it does". Another thing is that gcc is written in c, so it can compile itself.... moreover it can compile a newer version of itself
There are many program languages that are programmed in themself, and are compiled by itself. Nothing strange there. Look up Bootstraping.
Everyone's talking about Tom sending the wrong worms, but there's precious little talk about the video quality going drastically downwards as he talked about video/images being lossy compression right before that.
Thus proving his point that some things like images or audio can be compressed using a lossy technique without losing any of the actual meaning (we could still see and understand a lower quality video.) you only loss detailing.
I think that's because everybody noticed that and it was a pretty obvious and predictable joke, whereas "sending the wrong worms" makes people do a double take.
I don’t think it was obvious, I thought it was inspired.
Smittens Yes, I noticed that and wondered at the coincidence.
literally better than my entire CS class in 6 mins 30 secs. thanks Tom!
THANK YOU TOM SCOTT!! I have wondered how compression like this worked for the better part of a decade, and I've even put a decent amount of time into researching it, but it never clicked until this video. You have the best content on this entire platform, both in subject matter and quality.
Tom Scott, you, sir, are a genius. Nobody has ever been able to explain something like this to me in such a simple fashion, I actually understand this now, and I could decode a file by hand with a Huffman tree now just from what I learned in your video.
Yo, the YT algorithm is giving me a Tom Scott renaissance right now and it's all so good. Love this guy!
I never thought that Wild Wild West would ever be used to such a profound effect. Well done, Tom.
To me, "Wild Wild West" is the least memorable movie in the history of cinema. OK, maybe except maybe for "Ishtar".
You have obviously never heard the masterpiece Wow Wow by the legend Neil Cicierega
Thanks for the tip! Maybe I'll even watch it (or try to do so :) ).
Walter Lowe I KN E W I WASNT THE ONLY ONE WHO CAUGHT THE REFERENCE
try Wow Wow by Neil Cicierega, I can assure you Wild Wild West (and All Star if you fall into the rabbithole that is Neil) will have a brand new type of impact on you !
Wow! I can't believe you just explained something that you would learn at a university lecture, but in a way that was so thoroughly entertaining!
This is amazing. I am a CS student, and needed to implement a huffman algorithm as an assignment. There's an explanation in the assignment about the huffman algorithm, but it's really poor.
Having watched this video before, I came back to see if it could explain the algorithm, and Tom nails it. The algorithm is explained well in a way that both the layman and the experienced can understand. Tom is an excellent communicator!
Basics videos are great. You're a good communicator, and it's fantastic for children doing computer science at GCSE.
This guy really seems like he LOVES to teach what he knows and is passionate about! I'm really enjoying the enthusiasm as well as the knowledge being shared. This is so good❤
Wow, everyday I see that Huffman reference in my daily job and I use it to pack files, and I never new it was a masterpiece of software engineering. thanks for explaining it so well
Always needed a clear and concise way of explaining Huffman Coding. Thank you!
"The wrong worms" Godlike writing, nice job tom
Studying for a computer science exam about datastuctures and I am very glad that I can watch a Tom Scott video in my study session
This is an absolutely amazing series. I hope there will be more in the future!
Video 4 years old at this point, but relevant and awesome as ever. I am a big fan of compression, because I hate wasting anything in life. Hate wasting food, wasting water, wasting gas, wasting time......... And wasting space, physically and digitally! I like to experiment, what kinds of files can be further compressed through means like Winrar. Videos and images (like JPEG and PNG) usually can't be compressed any further, but I found out at some point, that for example Photoshop files (.psd) can often be heavily compressed. Depending on their content, really. But I have had compression rates of up to 93% on particular files. What a load of wasted space.
Would love to see more of these. Even when I already know about what you're explaining, your videos are so superbly made that they're still fascinating to watch.
6 minutes of proper clear information. my professor took a lecture of 30 minutes and still could not explain it half as good as you
"But text has to be losslessly compressed: you can't just lose a bit of detail, otherwise you end up sending the wrong worms." 🤣 Nice play there Tom!
Along with the fact that video compression artifacts were added just before that
@@KaosFireMaker such a nice little touch!
i dont get it
An extra joke for those who watch with subtitles at 0:53, if anyone's interested. I love how Tom puts in that extra touch every here and there, even though most people probably wouldn't notice.
This is magic. I've just finished my text compression algorithm in C++ the day before yesterday, and this video was uploaded. I feel I'm being observed.
The algorithm watches all
I've been in IT about 26 years and learnt something from this video. Never knew how compression worked. Explained very clearly. Or vry clrly. Or 10010011000110001.
I love your videos. You make complicated things look so easy (altough I don't understand the technique and logic behind it anyway :D)
brayzbeats. Doing this means the most commonly used characters end up at the top with the shortest binary codes.
It's pretty simple really. Huffman Trees are very straightforward.
Think about a short tree, like this one:
o
/ \
o B
/ A
o
C D
This means our alphabet has 4 letters. A, B, C and D. Now I want to compress a short text using this tree. The text is "DAB" (sorry, only thing I could think with these letters)
So, we'll start by converting D into binary.
To get to D, we gotta go to the left twice then to the right once, so here it goes: "Left Side: 0, Left Side: 0, Right Side: 1". So a D corresponds to 001 in binary.
Now to get to A, it's 1 left and 1 right, so 01.
Now to B, all I need is 1 right. so 1.
This turns DAB into 001011. 6 bits of information.
When you read this file, you'll convert 001011 back into DAB by doing the opposite process.
You'll read bit by bit:
0 -> go to the left once. It's not a letter yet so read next bit.
0 -> Go to the left again, it's still not a letter so read next bit.
1 -> Go to the right. Oh it's a letter, letter D. OK so writing it down on the output: D. Now reset to the tree root and read next bit.
0 -> Left. Not a letter. Next Bit.
1 -> Right. It's the letter A! Write it down to the output. DA. Reset to root and next bit!
1 -> Right. It's the letter B! OK! Write it down to the output. DAB. There are no more bits to read so it's done! Your text is DAB!
brayzbeats. I do understand these well, but math and engineering videos go past vocabulary and I have to watch them twice to understand sometimes.
That's it.
That helped a lot, thank you!
ayo you better give your editor a raise; this video is bang on
I love how you just seamlessly blend in jokes to your script.
Bless you, Tom Scott! You managed to make me understand in 6 and a half minutes what my teacher couldn't in an hour.
When he talked about images and the screen went low q I thought it was my connection! Well played!
I teach Huffman Coding to my intro to programming students at Stevens Institute of Technology, an engineering university in Hoboken, NJ. Starting this semester, I will absolutely be showing them this video prior to them working with Huffman Coding!
Can you do a video on zip files?
Do one on 7Zip and RAR, too.
Karate Girl91 There are a lot of sophisticated compression algorithms. Zip, 7z, rar, gzip, deflate, bz2, botli, etc. Some of these are stream algorithms, and tend to work in a concert with tar to compress folders.
It's not Tom, but Prof. Brailsford did a video explaining LZ77, which is still a very popular compression algorithm, variants are used in in ZIP, Gzip, RAR etc. It's easy to understand and a good place to get started if you want to learn more:
ua-cam.com/video/goOa3DGezUA/v-deo.html
Ethan Pender has
2 computer science lesson now make sense after 6:30 of of Tom Scott explaining Huffman Code! Thank you
Thank you very much Tom. I’ve had a hard time understanding Huffman trees in school so that really helps me!
I'm always amazed at how many clever people are in the world, with solutions to problems that I know I could never have come up with.
This is really cool. Honestly really curious as to how the tree itself is stored. That would be really cool. Tbh I want Tom to teach a whole computer science basics class.
What I did was to store in the header of the compressed file the preorder traversal of the tree and then an array with information about which nodes are leaf nodes. You could also store combination of 2 different traversals, but "my" solution would only take up to [number of nodes] + ceil([number of nodes] / 8) bytes - not that significant difference, but still a difference :P
idt the tree itself is stored it is just used to create the translation list which is used to compress the data, then you can send the list and the compressed data
Love the subtle pixelation effect between time 0:46-0:50, demonstrating video compression codecs in operation!
Toms red T-Shirt probably has it's own insurance.
Im proud
Which one of the hundreds?
And he's not even the guy known as "red shirt guy".
Though I bet Tom use a green or blue shirt in public to avoid people recognizing him.
*its
He implements "redundant red shirt error correction scheme" explained in one of his other video.
"This series is called the basics, so, uh, deal with it" this is why i love your computer science videos
3:02 I love how the pointer gets so angry it just leaves
This channel taught me more than what I’ve learned in my 4-year computer science degree
"You end up sending the wrong worms"
Wow, that jake was funking awful
im dying now
It reminded me of this! ua-cam.com/video/aJ0nFQgRApY/v-deo.html
Hierophant yarn response was as goo as the original jack?
Taikamuna It took me a couple of minutes, but I got it in the end. The wrong worms is "the wrong words" but worms is the wrong word.
Before opening I assumed you would link this ua-cam.com/video/pImWVCMgEYQ/v-deo.html
love that your getting back to the educational stuff. Breaking down complicated topics in computing or explaining how a hack was done was always a fave.
I like the dry humor, "Otherwise you say the wrong worms" is just objectively funny
I've got an exam tomorrow, and one of the topics happens to be Huffman code. Thanks Tom!
Surprised we didn't learn about Huffman coding in university. Could have been mentioned right after the sorting algorithms...
Trurl In my school we did it
@@wappa6914 my school too. Did an Information Theory course in my final year.
So... In about 6 minutes I have understood Huffman compression algorithm... WOW Tom you are a wizard
Awesome presentation....inspired by you...I am an IT engineer...:wanna start my tech channel too after viewing your video and fan base....wish me good luck ☺️☺️☺️
Amazing to find this comment from you at the beginning of your channel! Now you have nearly 200,000 subscribers and that is simply amazing. Congrats!
@@Phil8sheo Was thinking the same. Amazing!
This comment is amazing. Wow.
A note about image/video compression at 0:45 : there are a lot of lossless compression methods, especially for images. You don't typically deal with uncompressed lossless files (e.g. bmp, the netpbm formats, raw images), but rather png (more or less row by row zip compression), gif (lossless if you fit the 256 color palette) or other lossless images.
This video was SUPER helpful! Thank you Tom!! I can't go to IRL classes right now - pandemic and all that - and this introductory video is the next best thing. And dare I say, my teachers are not as skilled at succinct explanations. Thanks!!
you explained this better in six minutes than my professor in university did in the last three lectures.
thanks.
This one of only two things I remember from my programming module - the other is a habit of typing both the open and close brackets at the same time.
Thats where Limpel-Ziv strolled in and started using blocks.
Thank for this, it is the best (that I've seen) explanation of Huffman.
0:49 this was funny on so many levels, hope no one sends me any worms, my computer's laggy enough as it is
A basics video with two machines who you programmed in 'basic'. Brilliant.
0:46 I actually thought my wifi was acting up again
I never expected that I'd to watch Tom Scott videos for my exams, yet, here I am.
0:50 Hilarious, reminded me of SCP-586 (Anything talking apple it has one typo.)
Just want to thank you for this video, because if I had taken a computer science exam this summer (cough cough COVID cough cough), this video would've been extremely helpful!
But using the hauffman method, how does the computer separate the letters as long as they are in a constant stream?
Let's imagine we have some "compression" tree and a string consisting of 10111010... . Every letter has an individual number assigned(the number is assigned with the tree). some are 4 digits long some are longer. So the computer sees the 1 and compares it with every assigned number. So the Pc checks 1-(every assigned number). If the result is zero it arrived at a letter. So the pc checks 1. No zero as result. Take the next bit 10. No 0 as result. Next bit 101. Still no zero as result. 1011 we get a zero as result. And display that letter. then we start again. 1. no zero as result .... Every letter has an individual path. So there will never be a letter assigned to 10111. that's how the pc knows when to seperate the string.
It separates the letters by referencing the tree. As it gets 1s and 0s it goes down the tree until it hits a dead end. The letter at that dead end is what is outputted, and the program heads back to the top of the tree. The structure of the tree is how it knows where the breaks are.
No branching point has a letter so if the point it comes to has a character instead of a branching path it has found the character needed and the next bit starts at the top of the tree.
Look at the graph at 5:02
Every time the computer reads a 1 it goes right in the tree, every time it reads a 0 it goes left. In this infinite sequence of zeros and ones, you only get to a letter at the end of a branch.
You can imagine letters at the end of the branch as "leaves" in a tree, where every branch must end in one and only one leaf.
The computer stores the entire tree so it knows if the sequence has reached a leaf or if it is still on a branch.
If, with the last bit read, you did not get to a letter (end of branch) you continue reading. If you got to a letter, write the letter and start a new one.
Giacomo 3003 it knows because it reached the end of a branch.
Your presenting skills get smoother and smoother. Pretty soon you'll be doing ten minute, one-take videos (without blinking), on how to film one-take videos!
At 2:16, the text "0100111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000110011101101001011101100110010100100000011110010110111101110101001000000111010101110000001011000010000001101110011001010111011001100101011100100010000001100111011011110110111001101110011000010010000001101100011001010111010000100000011110010110111101110101001000000110010001101111011101110110111000001010010011100110010101110110011001010111001000100000011001110110111101101110011011100110000100100000011100100111010101101110001000000110000101110010011011110111010101101110011001000010000001100001011011100110010000100000011001000110010101110011011001010111001001110100001000000111100101101111011101010000101001001110011001010111011001100101011100100010000001100111011011110110111001101110011000010010000001101101011000010110101101100101001000000111100101101111011101010010000001100011011100100111100100101100001000000110111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000111001101100001011110010010000001100111011011110110111101100100011000100111100101100101000010100100111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000111010001100101011011000110110000100000011000010010000001101100011010010110010100100000011000010110111001100100001000000110100001110101011100100111010000100000011110010110111101110101" should've flown across the screen really fast, just to really drive the point home.
Its a rickroll...
Tom Scott, you are the definitive ´Elder of the Internet´.
3:05 someone give the animator a raise 😂
now I want a video how how the tree is actualy stored, how compresion for big chunks like words or phrases works and more. This is awesome
"... or you'll send the wrong worms" *5 seconds later* Nose Exaling
I like it when you talk about something that combines computing science with mathemetics. you seem so passionate!
"... or you'll send the wrong worms"
Colten Pilgreen 😂 0:50
Exposed! You need to make sure your computer virus is compressed properly? :D
Wong
Ip happesad mo we onze
I believe you look much more confident in compare to your previous videos, and also I wasn't expecting that your video will be so hypnotically extremely understandable; but you just nailed it. Thanks for sharing!
"You can't just lose a little but of detail, otherwise you'll end up sending wrong *worms* "
Damn, that's clever
Well, I have my algorithms final tomorrow and I wanted to have a quick recap, Tom Scott nailing it, again. Thanks!
I feel so smart now
My teacher is trying to teach this, I hop on youtube and learned the concept in 7 minutes. go back to zoom, teacher haven't done with the example yet 🤣
I'm so glad you're doing computer stuff again. The travel stuff is fine, but this is why I'm subscribed.
A minor point: Position of atoms on a disk? More like magnetic fields.
Edit: Nice visual stepping tree!
The magnetic fields are defined by the orientation of electrons around the atoms of the disk; so it's 6 of one, half a dozen of the other really.
Marvelous imagery! If it weren't for the intuitive visuals and your keen explanation, I would have never understood this. This is fascinating once you get it!
0:50 "...sending the wrong *worms* " I see what you did there =D
I was able to understand more in your short video than any other attempts I have made in the past. Thanks!
"The wrong worms" I see what you did there... nice.
I can't believe how far computer monitor design has come since this video was filmed back in 2017!
THAT DAMN WORM PUN!
Thanks to this channel I know the solutions to so many problems I didn't previously know existed. Thank you?
Did he actually say "you end up sending the wrong worms"?
Great summary.
This method is also combined with LZ ("repeat 6 characters starting 8 back from the one you just decoded") and RLE ("repeat this character 5 times"). As far as I know those plus Huffman are the fundamentals of every compression algorithm.
"Otherwise you end up sending the wrong worms"
Blah Cga it means "sending the wrong *words*" but he sent the wrong word so it says "worms"
This video was well-written, and the execution was exceptional. Engaging, informative, and entertaining. Very nice! I would like to see more like this.
1:08, no animated sunglasses? Disappointed.
This takes me back to uni, heh. I'd actually forgotten everything about Huffman Coding except how it looks and its purpose. Cheers!
Tom Scott: Text has to be losslessly compressed!
Xerox: Hold my copy machine!!!
*Hold my toner.
Funnily enough, I have proved mathematically that Tom Scott's videos are the most efficient way to insert knowledge into my head. (Do I win a Nobel prize?)
Matematicians don't get Nobel price :-)
Shame modern game devs have given up on saving space and increasing efficiency. Brute force is now the solution.
The issue is that people are getting higher resolution displays, needing higher resolution textures, and games are using less repeating textures to make each location feel unique.
Thank you for putting this in layman's terms. This is super interesting, and you make it so I can actually understand every bit you say. Cheers!
Those here for Cryptocracy :)
ayyy
got the answer?
@@ipsitayankakoty652 paala ni