Video 5-6: §5.6 Lempel-Ziv-Welch encoding

0:01 in the next subsection we'll look at the LOL Welch compression algorithm it's part of a family of compression algorithms known named after lample and C uh many of them in in some form or another are in in all the compression methods that are used in practice in particular the the the zip formats uh they all build on some form of this and uh the lample Welch format is probably the cleanest to explain and Implement so we'll focus on that but you'll get the idea of the others um from the same from the same algorithm uh to explain the concepts um I picked something that needs no words really um but it illustrates perfectly well what What llef compression is like so stare at this for a moment and um I'll have a slideer question for you I'll show you in a second uh to to decode the second to last line I

1:09 think yeah the second to last line of the poem is what what I'll ask you on slido so um here's that thing again but I'll leave it in in the big picture so you can you can see it

1:36 and this question basically is my my experiment also whether this is self-explanatory enough or whether it does need a few words to make so just this part is what you're supposed to

2:26 produce not sure if adding more lines to this picture is a good idea uh maybe that okay I see see see many right answers so maybe we don't have to wait for for everyone uh what the goal here is is to illustrate if you have a text that is somewhat repetitive like this poem you can often specify what comes next if you're trying to to read what comes next here by saying ah I've I've actually seen this before I'll just tell you where it is and how many characters you have to copy so that's with these arrows symbolize of course if you encode this in bits you'd have to say for this arrow with where does it point to where does it start and then also how big is this box it's nicely drawn in this in this visual format but of course you would have to specify that for computer memory so if you if you follow all the pointers we can just do this here so um if you try to follow where this box comes from it points to that box all right that points to that box so it's some like okay and this is an i some like it and then the other box points to in the and then this points up here just

4:01 the circle part in the middle and this part is an O so it's OT that's missing here some like it in the pot that's that's how it goes right

4:19 um what I like about this is also just visually for this poem um how few characters you need in total to specify it if you wonder what PE forage is that's what that's the image on the right is some some English dish but I didn't get a chance to try the original some kind of um uh some kind of soup and and peas like this is a that's an old spelling for

4:49 peas apparently right okay back to computer science uh no recipes and poems anymore more for the moment what we've seen so far is um single characters and um what we find in many texts is that there's substrings that are more frequent than others not just single characters I just wanted to list a few more examples to make that concrete if you have English text there's some frequent words that just occur all the time uh if you have HTML web pages then there are certain fragments of HTML that you'll see many times and uh it makes sense to somehow represent those with less space um and lle is is trying to do that but not by analyzing the text up front and finding frequent subwords or anything fancy like that it's just a simple mechanism for adaptively finding these boxes and back pointers so the idea is as in this poem uh we we store repeated Parts by pointing back to where they occurred before and more concrete rely what what does that look like um we can either have a single character or we can have a substring that we've seen before and this will um we we'll have some very concrete examples in a second I just wanted to list first that there's uh there's different variants there's

6:20 two bigger families um named after the papers when they were introduced lle 77 and lle 78 um for for this module it's not so important to know the differences uh but I wanted to give you the the terms in case this appears somewhere if you read about compression methods people might refer to one of those two so you know these are two variants of lle and they're a slightly different variant of what I'll show you lle valch is the algorithm that was long protected by a patent so it wasn't used in some formats but I think it's the cleanest way to to formulate the idea or make the idea

7:09 concrete so what does that look like um all of these lample C algorithms are variable to fixed uh yeah okay I'll take that back not all uh lampos Val is is clean because it's a variable to fixed coding they all have the variable part uh but producing a fixed length code word is what makes if Welsh a bit nicer uh think of this as being a code word of of 12 bits something like that um but the 12 bits in the coded text might represent a much longer part of the source text if that's

7:50 compressible how will we do that um we maintain uh a set of phrases a dictionary that has up to two to the K entries well two to the K just because that's how many different things you can specify with K bits and code words um the things that uh that we store in the code text these are just indices in the dictionary uh specifying one of those entries we'll always start by filling the dictionaries with these single characters in the alphabet and leave the rest empty for now and then we'll we'll fill it as we go whenever we encode some bit of the text We'll add a new code word to the text that has something to do with what we just stored so when we encode a substring x that's this one when we store that one so okay I should maybe explain the picture a bit better we're currently at this point everything to the left is already encoded so uh we know we we assume the decoder knows that and now we try to find um a next bit that we want to encode if that is this part X X because we could find a copy of X earlier then we do we store X by a reference to this previous occurrence

9:07 and afterwards we add X and one more letter to the dictionary so when when you keep doing this you'll make longer and longer phrases um in the dictionary all represented by a code word of the same length that's where the compression comes

9:30 from I think that's all for for this part let's see a concrete example that makes this um makes this maybe more more explicit uh up here is a text with lots of repetition so that we see something interesting happening for this small example um I'm taking just the entire asky character set as as the alphabet so we would have a a dictionary that's pre-filled with all the asky characters um I've left out all those that we don't use but uh just to keep the example more realistic all the text characters are possible um and we'll start building the coded text step by step okay how does this work first because we have um right in each step we try to find the longest the longest code word in the dictionary that matches a prefix of what we have to encode so we try to find among all those because these are all empty it will be just a single character we try to find the longest thing that we've seen before and in this case it's just a single character so we store the code word for y over here in the output and that's that's encoding why done but remember uh after each such step we also add something new to the dictionary namely the thing we just

10:59 encoded plus the next character that's what the uh picture below here reminds you of we've just stored x x was only Y and then we take the next character which is O and we add that to the next free entry in the dictionary all right so far so good then we keep going we're have now encoded everything to the left of this now we find the longest thing that we've seen so far that occurs here we only have a longer thing that's yo and this is not yo because it starts with o so the best the best thing we can find is just a single o that's why we get the the code word 79 but we have to add something new to the dictionary again same game as before we take o and the next character and stick that as a new phrase into the dictionary all right

12:03 one more time we have the same situation it's a single character we haven't seen anything bigger or longer so we take the code word that represents the exclamation mark put that as part of our coded text but we also have to add a new phrase to the dictionary namely what we've had plus one more character all right the same thing happens another time I'll skip that part we find that code we add the new thing to the dictionary which is the character which just stored plus one more so far so boring now for the first time we have something more interesting happening because we've already stored this substring yo and that's uh reoccurring here okay and you can obviously see this here in the example but uh we'll talk about how the algorithm finds it so we take the code word for this which we assigned earlier that's part of the coded text and the rest is as before we keep adding a new thing to the dictionary which is the two letters we encoded plus one more so we now have a a phrase of length three in the

13:17 dictionary all right uh for youu we have nothing that starts with U so far so we'll get a single character but we'll add a new phrase with uh the next character to the dictionary well the next example again we've seen seen exclamation mark space uh before so we'll we'll get a code word for that and again we add to the dictionary exclamation mark space And Then followed by y as the next code word all right and here becomes interesting now we found an even longer phrase we've seen U before so we can uh take the code from there to encode the entire three letters and and we add one more thing as a new phrase to the dictionary I think by now it gets a bit boring so You' you've probably uh understood the this the process well let's let's finish it quickly so R we have not seen before so we just get a single character and we add our space to the dictionary with the next character uh space y we've seen before um but we haven't seen space y o we've seen that before in there's earlier occurrence of that um phrase in the text but it's not in our dictionary that's one of the differences between lolive Welch and some of the

14:40 other variants uh we don't necessarily scan through the text and find the longest thing that we've seen before we restrict ourself to to those that are in the dictionary and here space Y is the longest we don't have anything space yo in the dictionary even though that did occur earlier okay all right so we encode that and add one more thing to the dictionary for future use and keep going like this okay o we haven't seen uh we have seen o but not with a Y after it okay but now we put it in and one last one yo we've seen before long ago and then we reach the end all good so far

15:33 uh if you want to implement this efficiently here's here's some pseudo code um that describes what I've just done so uh we keep the the previous phrase that we just en encoded and that's the output the coded text we have the dictionary now we use a data structure here that we haven't uh discussed in detail yet um so you might only uh only understand the running time when you come back from Unit 8 to this um the next free code word we have to store so we we already have the dictionary filled with all the characters in in Sig Sigma s so the next free character the next free code word excuse me is is that one let me go through the entire um the entire text um we take the next character to encode if the dictionary contain me what we've seen so far and the next character then uh we grow our phrase so we keep we keep making the part that we store bigger um once we once we have a mismatch here so we haven't found anything longer in the dictionary before then we take what we currently have we take the code word for that and add that to the output so that's just saying aend in string notation and we add the new thing to the

17:00 dictionary that's this part we take X and new character C and we add that to uh to the dictionary uh then we have to increment the next three code word is one bigger and U we have to remember that we stored this before so basically this is all all easy if you um assume that we have this function contains key if the dictionary can somehow quickly tell us do you have a code word um of that string do you have that string stored as a code word as a phrase sorry and we'll see that Tri um allowed to do this in essentially constant time if you keep adding one character at a time and we'll we'll come back to that uh when we discuss it in unit8 so you can you can revisit this uh but basically this it can be implemented using a try so that when you add one more character you can do this in constant time to check um whether you can add one more character and you still have a dictionary