The Beauty of Lempel-Ziv Compression
Вставка
- Опубліковано 11 гру 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
The topic is so well-explained. Can't believe the vid doesn't have more views!
Great explanation and example.
It felt almost like ASMR to hear the algorithm play out in the example.
I really enjoyed this video. Thanks for making it.
Perfectly explained video. Congratulations!
this is concise and precise explanation, easy to understand, thanks a lot sir
Great video as always.
By the way, yesterday I had my exam. And I wrote answer on LZW compression.
You have a talent for stating things clearly.
Wow! I'm amazed for such quality of explanation, thank you!!
appreciate the feedback, stick around for more
Wow amazing. It was very smooth teaching. Thank a lot.
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!
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.. Great video. I am intrigued by how Lempel-Ziv came up with this. Simply beauty!!
thanks, stay tuned for more!
This channel has great content. Keep it up Brit!
Will do, stay tuned for more
this video created such a great intuition in my mind. thank you!
thrilled it could help you
Awesome Explanation!, Thank you!!!
Always love the videos. Great work.
Appreciate the feedback Divy
are sir ap XD
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 💪😎💯
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
Best explanation so far. Thank you
glad you found this
I love this channel.
thanks for watching, more to come
Great explanation !
Great description! Thanks.
New video is up on Evolution of Intelligence ua-cam.com/video/5EcQ1IcEMFQ/v-deo.html
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
Amazing! I always wondered how zip compression works. Thanks!!! :)
me too :) glad to hear it
Awesome as always
Appreciate it, stay tuned for videos on AI
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.
Amazing! I love your animation and background music. Keep going
thanks! more IEEE videos coming soon
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.
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!
Simply awesome!
appreciate the feedback!
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.
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 :)
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.
you deserve more subscribers
Unique explanation 😍
thanks prachi, stay tuned for more.
Excellent!
thanks for your feedback, stay tuned for more
best videos for learning information theory concepts
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
thank you
Funny how the numbers and letters are then compressed again using Huffman coding, which itself is also very interesting.
Thanks!
Thank you kindly! I really appreciate this
Just posted a new vid! ua-cam.com/video/5EcQ1IcEMFQ/v-deo.html
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
wow thanks
nice
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
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.
How do you delimit between symbols?
all anchors lost, not doing well since the amputation, my markets are too bad for quotation, everyone else inside giant fish, send help :-/
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."
Do bzip2 next
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
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?