Video 7-6: §7.5 Lempel Ziv Welch introduction

0:00 <Untitled Chapter 1>

0:03 in the next step section i want to discuss the first method that is used as as given um in in practical application and that's the the length of welsh compression algorithm i want to first motivate this uh with a little warm-up exercise it's a little um wordplay not necessarily to be taken too serious

0:14 Warmup

0:31 it definitely is about so peace porridge i had to look this up when i moved here this is some british local cuisine um not scouse though uh but it exists and it's it's some type of stew or soup it doesn't matter too much so the core idea of lampulsif welsh is to represent parts of the text using parts of the text that you've already encoded and this is very nicely illustrated in this example and i want to also shoot up the the question for this i'd like you to give me the content of this second to last row so this one

1:17 i won't really explain how this works i think it's uh the graphical explanation is self-explanatory and it shows that for some texts like this poem which is fairly repetitive as you will see if you decode it you only really store the uh the printed letters and the other boxes are just um a number or a pointer back to the coded text so these take a certain fixed small amount of space so it might already be obvious that this is a method that can again drastically reduce space and it works fairly well for a variety of data in particular

2:18 maybe i'll just leave it open for a sec but then you don't see this picture anymore i probably have to just be a little patient here maybe at least two more people can send in their answer the ones i got so far are fine

3:00 so maybe i should i should add a word of explanation how this should work if there's a box that's empty then there is an arrow attached to it and you should follow that and that will point to somewhere where you can copy what goes in this box so this fourth line says nine days old because you copy this substring from cold now sometimes you copy something that's actually not there itself but it's copied from somewhere else so here you have this this piece porridge well that itself again is not fully here because you have certain things that are copied from other places like uh here again so you have to follow all these pointers but if you do it then it'll read like piece part piece for it cold piece porridge in the pot nine days old some like it hot some like it cold some like it in the pot nine days old i'm not recommending eating nine nine piece porridge but that's what it says so yeah uh many of you um got this um good let's

4:08 uh let's see how this connects to a more serious um discussion of levels if but the the idea is is exactly that use um references to previously occurring things but let's uh let's start from scratch and properly

4:21 Lempel-Ziv Compression

4:32 huffman coding and run length encoding both both talk about uh single characters either by their frequency overall in the text or by being the very same thing repeated but we don't have that so often in many inputs instances what we more often find is that substrings certain phrases or words are more frequent than others for english texts these are the most frequent ones and i'm sure you would have found others in other languages stuff like in html you often see these things as combinations and there's many many others and i guess you can can imagine how this how this goes now you could think uh you could try to put some um application specific encoding together where you give a special character for these phrases that you think occur often or maybe you could try to find out which phrases are more frequent than others um yeah let's not stop the poem now you can check the recording and go through this again if you want in in detail uh so you don't want to hard code this or you don't want to uh you don't want to have to specify or divide phrases into this is frequent this is not frequent you want a method that organically finds these by itself and nipples if does exactly that

5:58 it's a family of compression algorithms not a simple thing the idea is what you've seen in this in this poem you have a certain part of the source text and instead of encoding it literally by giving all the characters you say i've seen this before it occurred at position five and the following characters so you you uh store things by a reference and i will be uh very precise and concrete when we discuss the actual uh levels of welsh um so a code word here is no longer encoding a fixed thing

6:44 it encodes a single character or a substring of something we've seen before and depending on the on the source text that can be a different string each time the important part will be that both the encoder and the decoder must have seen that substring before otherwise you could not decode it again but this will this will work out there are many variants of levels if [Music] they differ in the details of what is allowed the original version would allow copying something from itself uh not sure if that makes a lot of sense um uh it it's also um can you only copy things that were a phrase before or can you start at any point that's that's the difference is but um uh we we won't discuss that here we'll focus on on one representative variant of lempelsif which also is the cleanest and the most widely used in practice and that is uh the limbulsif welch algorithm so historically lempel and siff came up with the core idea in a sequence of papers and then welsh later rephrased it a little bit um and uh added uh more twists to that just make the the method a little rounder for implementation but the the historic content uh context the site uh we'll just look at the the final

7:47 Lempel-Ziv-Welch

8:15 results from from this history uh i won't go into the details but i just wanna um today i just want to give um the the core setup uh lamppost welch will be an instance of a variable two fixed coding so we will fix a length for the code word um a typical choice in practice is 12 bits and then all the code words will use exactly k bits but they will represent a variable portion of the source text and this is the opposite of what we used in huffman there we had a fixed to variable encoding fixed was one character is encoded at a time variable was the length of the code word here we flip this around we do it just the opposite way we represent something of various length and the method will have to tell you how this works and it's represented by a fixed length code