The Beauty of Lempel-Ziv Compression
Vložit
- čas přidán 11. 12. 2018
- Information Theory Society presents how the Lempel-Ziv lossless compression algorithm works. It was published in 1978 (LZ78) and improved by Welch in 1984 leading to the popular LZW compression. This video covers the key insight in their paper: how to construct a codebook that doesn't need to be shared with the sender. It's a subtle, yet beautiful idea which is still in use today.
Ngl, I struggled to understand the core concept behind this algorithm. Even after watching so many "technical" videos here on youtube, I still couldn't wrap my head around it. But after watching the first 30 seconds of THIS video, it was crystal clear all of a sudden. I just love how you visually presented the inner workings of this algorithm!
woo! I'm thrilled to hear this. it's how I felt when I was researching this video.
Always believed in your channel, first priority while searching for any topic
thank you for the kind words, I will continue!
That was so easy to understand. Why can't my proffesor be this clear? Thanks a bunch!
wowwwwww. I love watching this vid. Easy to undestand, clear, and fun! Thank you so much
yes I loved making this! i was so confused when I first had to learn it
Wow! what a simple and intuitive explanation, excellent!
thank you glad you found this, was it suggested or did you just discover it? I'm trying to learn
@@ArtOfTheProblem I'm ur huge fan bro 🥺 ... Please remember me, I'm gonna meet u 1 day! Keep up the good work 💪😎💯
Great explanation and example.
It felt almost like ASMR to hear the algorithm play out in the example.
The topic is so well-explained. Can't believe the vid doesn't have more views!
Great video as always.
By the way, yesterday I had my exam. And I wrote answer on LZW compression.
Great description! Thanks.
New video is up on Evolution of Intelligence czcams.com/video/5EcQ1IcEMFQ/video.html
Great content, keep going! I like the style and how you bring up the philosophical side of information theory in your old videos. Nevertheless, this being more practical, it's equally interesting to watch.
Thanks. yes these IEEE videos are very focused on concepts in specific academic papers. However I'm currently planing to do a new video series on AI which will follow the model in my "old" videos. Stay tuned!
Wow. Such an amazing explanation. I have an Information Theory exam in a few weeks and this really helped. (Along with your other videos!) Thanks a lot!
excellent to hear, I was once in your position wanting this kind of help. please share with others.
I remember trying to learn LempZiv and nothing...nothing...worked for me.
You have a talent for stating things clearly.
Wow.. Great video. I am intrigued by how Lempel-Ziv came up with this. Simply beauty!!
thanks, stay tuned for more!
Perfectly explained video. Congratulations!
This channel has great content. Keep it up Brit!
Will do, stay tuned for more
Wow! I'm amazed for such quality of explanation, thank you!!
appreciate the feedback, stick around for more
this is concise and precise explanation, easy to understand, thanks a lot sir
Excellently made. Would be thrilled if you uploaded regularly (daily/weekly)
Thank you. Monthly would be top speed for my style of production. You can make this a reality by supporting future work here: www.patreon.com/artoftheproblem
you are a very good teacher.. thanks for educating.. and god bless you to continue the good work
will do thanks for the support
Wow amazing. It was very smooth teaching. Thank a lot.
I really enjoyed this video. Thanks for making it.
Always love the videos. Great work.
Appreciate the feedback Divy
are sir ap XD
this video created such a great intuition in my mind. thank you!
thrilled it could help you
Best explanation so far. Thank you
glad you found this
Amazing! I love your animation and background music. Keep going
thanks! more IEEE videos coming soon
wow, you made it so simple ! very easy to understand, thank you!
thrilled to hear it, made this video because I hadn't seen any others do it simply
I love this channel.
thanks for watching, more to come
Awesome Explanation!, Thank you!!!
Amazing! I always wondered how zip compression works. Thanks!!! :)
me too :) glad to hear it
Great explanation !
After 5 years since I requested it... Thank you!
(it was in the comment section of the Makrov Chain videos I asked you to talk about this... Due to LZMA).
Amazing...slow but steady :)
Has it really been that long 😮 It’s so great that this channel hasn’t died, or sacrificed quality in the name of quantity!
You can tell as you were narrating it felt repetitive to use the same words for each step, during the compression explanation, repeatedly. But, it really did help for following the sequence. Another good video. :)
thanks so much :)
This is very interesting. Or should I say, "This 3s very 3n1e8e4t10g" - oh, that hasn't compressed at all, I guess it gets better the more combinations there are.
0b0e0t3e0r0u0s2z0i0v0c0o0m0p5e7s9o0n
Huh, this is even longer than if it was uncompressed...
I'm sure you could very easily construct a message that would be much longer compressed like this. However, the ,longer a message is, the better chance it has that it will have repeating content meaning easier to compress. Also a number has less data than a letter because there's only 9 numbers and 25 letters, so even if the message is the same length it has less information.
@@umnikos don't forget that every message you type is actually binary and not what you initially see.
@@inarisound yes, but then how do you transmit the numbers separately from the actual bits? They're both just 0s and 1s...
I can't decrypt that, so I think you might have done something wrong.
Awesome as always
Appreciate it, stay tuned for videos on AI
Perfect. So next time I'll send a message containing only two letters, I'll contact you for a smart algorithm for compression!
Fantastic, now I want to purchase my WinRAR activation
Thank you for the feedback on the pacing I appreciate it.
Simply awesome!
appreciate the feedback!
Unique explanation 😍
thanks prachi, stay tuned for more.
Excellent!
thanks for your feedback, stay tuned for more
you deserve more subscribers
Amazing, amazing, amazing. I have always wondered how compression works. Question though, why not send 3 1 (with a space to distinguish from 31) instead of 3A?
Tommy Dies letters, numbers, and spaces are characters, quest like the buttons on your keyboard. They are all represented as bits (0 or 1) in the end. A common and simple translation is ASCII.
thank you
Technically the code-book is not empty at the start: it contains the letters. Or at least, the sender and receiver must agree on an alphabet
best videos for learning information theory concepts
Thanks!
Thank you kindly! I really appreciate this
Just posted a new vid! czcams.com/video/5EcQ1IcEMFQ/video.html
wow thanks
nice
all anchors lost, not doing well since the amputation, my markets are too bad for quotation, everyone else inside giant fish, send help :-/
But how do you differ between regular symbols and special code numbers, for example in binary? I tried this method as you descibed but message only got longer: 42 bits from 33 bits. In your example: what if 1 is also a symbol in angiven alphabet?
The video used A and B for clarity, but everything would actually just be 1 and 0. Characters like a-z, A-Z, 0-9, etc could be encoded, using a simple scheme like ASCII which is still used today.
This implementation of the algorithm always results in the transmitted message alternating between an index and a character.
for very small data sizes compression may yield worse results than not compressing at all. Also data with little to no repetition will compress very poorly
Funny how the numbers and letters are then compressed again using Huffman coding, which itself is also very interesting.
If you have the last sequence ABA, why do you replace AB with the value in the lookup table, but not the last A?
E.g. if we had ABAB, wouldn't we replace it with 22?
The simple answer is "because that's how the algorithm is defined". You always find the longest sequence that is in your table already and add exactly one letter. If you would always compress multiple messages, then you would quickly run into trouble. For example, if your message is ABAABABBBABABA, then after the first two steps, your table would be "A-1, B-2". After that, you could "compress" the entire message as 112122212121. This wouldn't actually save you any space though, because you mapped one letter to one number.
Basically because you don't have spaces, so you wouldn't be able to know if you have "two one" or "twenty-one". Remember that in a real system you just have 0 and 1.
Very good explanation, thank you! However if you try the method on "TESTTESTTEST" it will make the dictionary ['T', 'ES', 'TT', 'EST', 'TE', 'ST'] and it'll never find out that compressing it as 3 * 'TEST' would be much more efficient? Or am I missing something?
Modern LZ approaches are able to have overlapping components-the codes are just described in terms of the previous values, so you could encode that as like
4,0,8TEST, which says "take 4 literals, and starting from 0 symbols back, copy 8 symbols"
so it would first write out:
TEST
^
and then copy 8 symbols,
after 4: TESTTEST
^
after 8: TESTTESTTEST
^
T,1E,2S,3T,4,4,4 itls works efriencet and amXing
How do you delimit between symbols?
Awesome. You had actual A. Lempel as a consultant?
That's correct, we were lucky to have the original authors participate in all the "information age" videos we've done together.
At 8:47, can't we write ABBA as 31, since ABB = 3, A = 1?
Remember computers would be using only 1 and 0 s, not letters. In the video, the letters A and B are used to emphasize the difference between coded and uncoded parts of the message. You could replace all of the As with 0s and the Bs with 1s and it would still work. It just would be less clear in the video.
@@MusicBent ok but then the question would be why didn't they code both the ABB and the A, and send it 31 and not 3A (meaning part coded and part not coded), I amnot sure if the guy making this video did that by mistake or the code has to be that way.
andres martinez hey, I looked more closely at that part of the video and I guess I’m not sure either. I would assume the video is correct, but not explained clearly...
The first four messages all are the same as the previous one except the last letter is new. The fifth message breaks this trend. Maybe that has something to do with it...
@@MusicBent Hey, if you think about it, it can`t send the code 31 as it would be confused with the 31st sequence... and the same goes for 21 42 etc... so I guess each sequence has to be coded as part code (number) and part not code (letter: or original message).
No you can`t because then you wouldn`t be able to use the code 31 for the 31st sequence, and so goes for the 42 41 32 etc... at 10:04 he says:
"notice the sender is always adding what it hasn`t seen to a growing code book, and then sending that sequence in coded form, MINUS the last letter (!), that`s the trick."
so this is LZ78 and not LZ77? as I understand it, LZ77 is the popular/most efficient one.
Could you use names other than Alice or Bob?
cubs0110 Adam and Betty
Idk, apparently it’s just a tradition in computer / communication science
Do bzip2 next
thank you you saved my ass
happy to help, I remember this crushed me in school
1 person is nostalgic for the seamen
Lempel-Ziv is a very old and obsolete technique now that we have middle-out.
ABBA is 4, Mamma Mia
So basically they are finding prefix codes on the fly and sending them.
If this series of videos was a psyop by IEEE Information Theory Society to steal away electrical engineers from other, non-information theory subdomains, well..........it might be working on me! :O
love it - our cover is blown
Great, but jif? Really?
That's how the inventor pronounced it, that's how I pronounce it
@@ArtOfTheProblem Then, let's agree to disagree :D
yiff OwO
I am very skeptical of the details of your example.
How so?