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.
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.
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 !
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
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.
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
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.
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❤
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
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!
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!
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.
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.
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!
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.
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: ruclips.net/video/goOa3DGezUA/видео.html
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.
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 ☺️☺️☺️
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!!
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.
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!
I always thought of Huffman Coding as “That learning tool from college I’ll never use practically,” but tonight I just discovered that the Jeopardy NES game used exactly this to compress all its questions and answers to a small enough size to fit on an NES cartridge. So learn this stuff! Sometimes it pops up when you least expect 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.
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.
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!
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!
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.
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.
The wrong "worms", that certainly makes up for the Quadrillion / Trillion mistake! Edit: As I typed that, my grammar checker tried to suggest it should be "words"!
It's a play on words; or rather, characters. Tom was supposed to say "The wrong words" but instead replaced a single character to represent the incorrect character being sent.
On that tangent, perhaps a video explaining how spell-checkers work? I think it had something to do with binary search trees, which I only briefly covered in college.
![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.
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
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.
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 RUclips Ever Run Out Of Video IDs?"? :)
frletmiflm with their old kit
3:00 God how I love the square sneaking of the screen
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 RUclips 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
I've worked with various compression algorithms derived from Huffman and this is the best description of it I've seen.
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.
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.
"... 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 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 !
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.
Yo, the YT algorithm is giving me a Tom Scott renaissance right now and it's all so good. Love this guy!
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!
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.
Basics videos are great. You're a good communicator, and it's fantastic for children doing computer science at GCSE.
Always needed a clear and concise way of explaining Huffman Coding. Thank you!
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.
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
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
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.
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❤
This is an absolutely amazing series. I hope there will be more in the future!
literally better than my entire CS class in 6 mins 30 secs. thanks Tom!
3:02 I love how the pointer gets so angry it just leaves
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.
"The wrong worms" Godlike writing, nice job tom
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
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
I've got an exam tomorrow, and one of the topics happens to be Huffman code. Thanks Tom!
When he talked about images and the screen went low q I thought it was my connection! Well played!
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!
"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
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!
Thank you very much Tom. I’ve had a hard time understanding Huffman trees in school so that really helps me!
ayo you better give your editor a raise; this video is bang on
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
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 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!
A basics video with two machines who you programmed in 'basic'. Brilliant.
"You end up sending the wrong worms"
Wow, that jake was funking awful
im dying now
It reminded me of this! ruclips.net/video/aJ0nFQgRApY/видео.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 ruclips.net/video/pImWVCMgEYQ/видео.html
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
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.
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.
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:
ruclips.net/video/goOa3DGezUA/видео.html
Ethan Pender has
Bless you, Tom Scott! You managed to make me understand in 6 and a half minutes what my teacher couldn't in an hour.
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.
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.
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.
I like it when you talk about something that combines computing science with mathemetics. you seem so passionate!
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.
Working on a paper about Huffman Encoding. Without any prior knowledge, this helped a ton.
I love how you just seamlessly blend in jokes to your script.
So... In about 6 minutes I have understood Huffman compression algorithm... WOW Tom you are a wizard
I like the dry humor, "Otherwise you say the wrong worms" is just objectively funny
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:46 I actually thought my wifi was acting up again
This channel taught me more than what I’ve learned in my 4-year computer science degree
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!!
Well, I have my algorithms final tomorrow and I wanted to have a quick recap, Tom Scott nailing it, again. Thanks!
0:50 Hilarious, reminded me of SCP-586 (Anything talking apple it has one typo.)
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!
0:49 this was funny on so many levels, hope no one sends me any worms, my computer's laggy enough as it is
I was able to understand more in your short video than any other attempts I have made in the past. Thanks!
3:05 someone give the animator a raise 😂
"... or you'll send the wrong worms" *5 seconds later* Nose Exaling
The lossy compression bit was brilliant. Making it look compressed at the right time.
"... 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
you explained this better in six minutes than my professor in university did in the last three lectures.
thanks.
At 2:16, the text "0100111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000110011101101001011101100110010100100000011110010110111101110101001000000111010101110000001011000010000001101110011001010111011001100101011100100010000001100111011011110110111001101110011000010010000001101100011001010111010000100000011110010110111101110101001000000110010001101111011101110110111000001010010011100110010101110110011001010111001000100000011001110110111101101110011011100110000100100000011100100111010101101110001000000110000101110010011011110111010101101110011001000010000001100001011011100110010000100000011001000110010101110011011001010111001001110100001000000111100101101111011101010000101001001110011001010111011001100101011100100010000001100111011011110110111001101110011000010010000001101101011000010110101101100101001000000111100101101111011101010010000001100011011100100111100100101100001000000110111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000111001101100001011110010010000001100111011011110110111101100100011000100111100101100101000010100100111001100101011101100110010101110010001000000110011101101111011011100110111001100001001000000111010001100101011011000110110000100000011000010010000001101100011010010110010100100000011000010110111001100100001000000110100001110101011100100111010000100000011110010110111101110101" should've flown across the screen really fast, just to really drive the point home.
Its a rickroll...
"This series is called the basics, so, uh, deal with it" this is why i love your computer science videos
I feel so smart now
Love the subtle pixelation effect between time 0:46-0:50, demonstrating video compression codecs in operation!
"You can't just lose a little but of detail, otherwise you'll end up sending wrong *worms* "
Damn, that's clever
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!
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.
I always thought of Huffman Coding as “That learning tool from college I’ll never use practically,” but tonight I just discovered that the Jeopardy NES game used exactly this to compress all its questions and answers to a small enough size to fit on an NES cartridge. So learn this stuff! Sometimes it pops up when you least expect it!
0:50 "...sending the wrong *worms* " I see what you did there =D
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.
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.
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!
THAT DAMN WORM PUN!
I know about this stuff already but still watch it because Tom Scott is a good lad
"The wrong worms" I see what you did there... nice.
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!
Tom Scott: Text has to be losslessly compressed!
Xerox: Hold my copy machine!!!
*Hold my toner.
I never expected that I'd to watch Tom Scott videos for my exams, yet, here I am.
Those here for Cryptocracy :)
ayyy
got the answer?
@@ipsitayankakoty652 paala ni
2 computer science lesson now make sense after 6:30 of of Tom Scott explaining Huffman Code! Thank you
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.
This takes me back to uni, heh. I'd actually forgotten everything about Huffman Coding except how it looks and its purpose. Cheers!
Did he actually say "you end up sending the wrong worms"?
Tom Scott, you are the definitive ´Elder of the Internet´.
1:08, no animated sunglasses? Disappointed.
I can't believe how far computer monitor design has come since this video was filmed back in 2017!
"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"
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.
3:32 well that aged like milk.
Thanks to this channel I know the solutions to so many problems I didn't previously know existed. Thank you?
The wrong "worms", that certainly makes up for the Quadrillion / Trillion mistake!
Edit: As I typed that, my grammar checker tried to suggest it should be "words"!
It's a play on words; or rather, characters. Tom was supposed to say "The wrong words" but instead replaced a single character to represent the incorrect character being sent.
On that tangent, perhaps a video explaining how spell-checkers work? I think it had something to do with binary search trees, which I only briefly covered in college.
A quadrillion bits is actually 125 gigabytes, so I wouldn't consider it a mistake