Video 7-7: §7.5 Lempel Ziv Welch

0:00 Introduction to LZW

0:03 so the lamppost if welsh algorithm is a variant of this family of compression methods the lambulsiv family that is arguably the cleanest and nicest is also very practical it used to be protected by a patent so it was a bit controversial uh how to use it it was uh legal trouble but this is all uh gone and passed now um the patent has expired because the method was old enough so it's uh this is no longer an issue

0:36 i mentioned last time that it's a variable to fixed encoding we take a variable length thing part of the source text and encode it with a fixed number of bits and we'll use this typical choice of of 12 bits but that is a parameter you can tweak and play with and that can be this variable to fix should be contrasted to huffman where it was fixed to variable but really now how do we do this and that's the interesting part so this is where you should wake up and pay close attention we maintain a dictionary that is a collection of strings of phrases these are all substrings of the text that we're compressing at most to the decay entries initially we will only have some entries for single characters from the source alphabet but this dictionary will get filled over time and the indices in the dictionary the order in which we add things to the dictionary that will be our code words so we reserve the first code words the first little sigma code words are assigned to the single characters of the alphabet and all the other code words so this is usually much smaller than 2 to the k

1:02 LZW compression logic

1:55 and all the other uh all the other slots in the dictionary are reserved for phrases that we will add and that depend on the text now how does this work uh to add new phrases to the dictionary in lemposif welsh it's done as follows whenever we encode a bit of the text we add a new phrase so each time we encode one thing we also add one thing to the dictionary and the rule is as follows if we encode a substring x of s currently so that's what's shown in the picture the gray part is what we've already dealt with that is encoded and done now i'm deciding i'll tell you in a second how that the next thing i encode is this substring x ban in this case this is the next thing that we encode as one chunk as one phrase and the reason is it occurred already in the text earlier what we do now if we store such a phrase x we add to the dictionary a phrase that is one character longer we take the phrase we've just stored ban uh and we add one more character which is this c so in this banner in this case okay that's it uh that's the rule whenever you store something you take the next character

3:16 that you could not at the moment already encode alongside with this and you add this one longer phrase one character longer phrase to the dictionary this new phrase is assigned the next three code words just by adding it at the end that naturally happens uh and that's that's the core of levels of welsh it's a fairly simple method now i haven't told you yet uh how to select x how to find x um and the deal with that is you just check your dictionary and you find the longest thing you could uh match in your dictionary and uh because we started with all the characters you can always find such a match we'll see an example where this becomes very clear

4:07 just a little as a little side remark if we would if we are implementing this we would not store the string in the dictionary explicitly but instead we we would compress this in the following sense that whenever we used x we know we have a code word for x and so we can just store that code word and the new character so we don't have to store very long strings in this dictionary that's a as an implementation detail that we might not uh care at the moment so much for let's go through an example to see how this works and also see how we find x on an example i said um it's the the longest string that you currently have in your dictionary that you find at this position and let's let's practice that on an example so here's our input yo your yoyo and we will build the coded text one by one we'll start in this case i'll i'll just assume the full ascii character set as the alphabet then we get a more realistic feel for how big the the dictionary gets we only use the ascii set not full unicode so the first the first part of our dictionary is already filled with all those individual characters and i'm only listing those that occur in

4:40 Encoding example

5:36 in our example text we include all of them here because we want a generic compression method that works for any text file and not just for those that are comprised of these few letters okay so what do we do first we try to find the longest phrase in our dictionary that starts at the beginning of our text of the uncoded part at the moment we haven't coded anything so we're at the beginning we only have single characters in our dictionary at the moment so the longest thing we can find possibly is just the y and so we look up in the dictionary that this is uh 89 so we would first store 89 as our first code word and then move on with the next phrase but before we do that we have to add a new phrase to the dictionary remember whenever we add we encode something we add a new phrase with the one bigger one more character added to it so the first thing we add here is is yo because the next character is an o okay that's how it goes um next thing we start again from here read the longest thing we find in our dictionary well we haven't seen so much so that's just a single o so we put that here but then before we

6:59 go before we move on also add the one longer next the longer phrase is o with the exclamation mark so that goes here and takes up the next slot in the dictionary okay you see how this goes as long as we haven't seen much the method is fairly boring we find the longest is the exclamation mark single character we add exclamation mark space to the dictionary as the next phrase and we continue one more time so here again space we haven't seen anything with space before so the longest match is this the single character but we add um space y to the dictionary because that's the next character now things slightly start to slightly become more interesting because now we've actually seen yo before so here we have to pick the longest uh the one we want the longest match in the dictionary that we can find at this position and that indeed is is this yo so here we use this new character this this new code word that stands for a phrase we haven't initially had in the dictionary but it's a a substring of our text but we do the same thing um we store this phrase it represents those two characters yo and we add u to the dictionary because that's the

8:29 next character yo plus one one more character all right see how this goes and see how this eventually starts to save space as you see more and more of the text if these things show up again you will represent larger and larger parts with the same fixed length code words

8:55 all right um we go on the u we haven't seen so uh there's just uh the single character match but we add uh u exclamation mark to the dictionary um for later use uh now now comes another interesting one uh the exclamation mark space we have seen that before so we can use that and there's no longer match so that's the one we take so we use this this code and add a new entry to our dictionary where we have exclamation mark space and then the next character is a y again okay now

9:36 things get again interesting we have y in the dictionary we have y o in the dictionary but we also have u in the dictionary so here we can encode three letters with just one shot um and add the next character as a phrase to the dictionary so here's your all right

9:58 uh r we haven't seen so that would be just the single character but we add to the dictionary r space um next thing we've seen space y and that's the longest match so we can encode that together and store space y o in the dictionary now i'll move myself to the other side uh and then we're almost done oh we have only seen o exclamation marks so far so we are back to a single character where we would add uh the o y for future use and then here uh the y o we've seen but not followed by an exclamation mark so um we've only got this one here and we would add the other thing to the dictionary and finally encode the exclamation mark so this is

11:07 the final result that's the encoded text for you your yoyo and the decoding essentially works in the same way where you have to replay this game but first of all if you have questions about the encoding parts this is a good point to discuss them

11:13 Data structures and tries

11:33 and if they only come up later then we'll talk about them as they arise uh here's a more structured pseudo code how this would be implemented what i didn't talk about here is i did this manually finding the longest match that's currently in our dictionary but we know a good data structure for doing that and that is a try so for encoding um we definitely want to represent the dictionary as a try because then um you can you can start at the root and traverse down from the current position in the text onwards and see how far you can get and as soon as there's no more outgoing arc with the right character you know uh you're at the longest match now unlike in the suffix tree applications and all examples of tries we've seen so far here we actually want strings that are prefixes of each other in fact we will always have strings of single characters so we must have we must allow these so here we would have space goes to one note and that for example is labeled with 32 but we could also continue reading space y and i think that's the only character so with space y we get to another node 1 3 1 and there's also space y o which gets us here

13:14 1 3 7. so if we read in our text suppose we're again at this position we would now start traversing from the root downwards reading characters as long as we can so we can read the space we can read the y and we can read the o so we would stop at this position but if we were for example um well

13:53 uh suppose the text would continue with y i uh then you would start reading the space and the y and then you were you would get stuck in this case so you still need to have the shorter strings in your dictionary because you sometimes need them and then extend the dictionary with the i with the new uh with a new code word after you've after you've added this okay so that's that's the motivation here um and that's that's reflected in this code so uh the code starts with initially an empty phrase we have nothing seen the coded text is also empty and the dictionary is initialized as a try containing just the single character strings um the next free code word is always stored in k and then we walk through um the positions in the text what's the next symbol of the text we have to encode we get that symbol now we try to find x c in the dictionary that essentially is walking down the try along the next character if we can find this then we keep that but we're not necessarily done yet we have to continue with the next character so we start we continue traversing the try as long as we find matches and the first time we fail to extend the

15:25 current match we don't find a longer string in the dictionary that's when we get into this else branch so here we append the code word for what we currently have read x that's the the prefix the phrase we found and we add to the dictionary this one longer phrase and we assign it the next free code word that's that's exactly what we did in the example a bit more structured and if you use a try for the dictionary this is also efficient this traversal can always be done in constant time for the next character

16:04 all right we can now we can now encode with lamposif welsh and achieve great compression but of course a compression algorithm is only useful if we can also decode it so in the next part we will look at how to decode with lamppositive welsh how to decode the output of the encoder as always the two steps encoding decoding they have to stay in sync they have to replay the same game and in this case it's growing the dictionary so whenever we decode something we have to add the next bigger thing into the dictionary and for decoding this looks as follows

16:14 LZW decoding process

16:51 if we currently decoded x this ban that's the last thing we decoded we know in the encoding step when we encoded ban we added band plus the next character to the dictionary so we also have to do this now and uh so we

17:13 we take um the next character from the next phrase so we have to decode one more phrase before we can do this edition in the dictionary so we decode the next phrase and take the first character then we know what the x c used to be in the encoding phase and we can add that to the dictionary so in a sense we're lagging one step behind but other than that um we're replaying the same game we always have to deal with uh two phrases we encode one then we encode the next one and that's when we can deal with the addition to the dictionary of the first phrase so we only start adding to the dictionary after the second phrase is decoded let's see an example for how this works and to make it a bit more fun this is just showing the coded text and you will only learn what the uh decoded text is as we go along to make this a little more interesting so how would how should we start uh remember we cannot add to the dictionary at the beginning what we start with is a dictionary that's filled with the single character strings so the first step must be a code word that's already in our dictionary and in this case we find it's a c so

18:28 the first character decodes to a c so far so good now we cannot handle the addition when we encoded c we added a new phrase the dictionary we cannot do that yet we need the next character so we decode the next phrase that is the 65 goes to an a and now we know z was c was followed by an a at the time of encoding so c a was added as the first non-trivial phrase to the dictionary and well in the computer it would be stored like this because we only have to represent the code word for this potentially long repeated thing in this case it's a single character so it doesn't matter much but just for completeness but it's it's enough for us now uh to focus on this on this column so we've added a new phrase to the dictionary and assigned it the next free code codeword 128. now we decode the next thing uh it's again a single character string found in the original dictionary we add this now we know a n after a when we encoded this it was followed by n so we would have added a into the dictionary so we also have to do that now and assign it the next free code word let's continue the same thing happens we

19:48 decode a single character and add this n space to the dictionary and another time um and then the things start to get interesting so uh 66 is a b the last uh character was a space so space b was added at the time when the space was encoded okay so far it was fairly boring we only used the original dictionary but now things become interesting because the next is a code word above 128 so here we use what we previously added to the dictionary so the the text so far uh reads like can ban

20:32 um and uh we know the last phrase was a b the first character from the new phrase is an a so we would have added ba at the time of encoding to the dictionary so we have to do that now as well and so we move along and until oops until we run into the situation that we're trying to use a code that is the next free one and we don't know what it decodes to yet so it seems like we are stuck in a dead end because we we would need the information that the encoder put in after encoding this phrase but we only get to that information after decoding this next phrase so how how can we uh get out of this this problem so that's a tricky situation that arises in limbos of welsh encoding but fortunately by looking very closely at this specific situation we can actually resolve it

21:24 Handling special cases

21:43 let's uh zoom out a bit and see what happened the reason why we ran into this problem is that the decoder is one step behind the encoder encodes a phrase and then adds that phrase plus the next character the diction character to the dictionary when we decode we cannot do this because we don't know the next character yet we have to wait for the next phrase to be decoded and then we can add it to the dictionary but it might occasionally happen that the phrase that we just inserted into the dictionary is the one that we use next in the encoding and in that case we're in this in this dead end so we're trying to use a code that we're just about to build to insert into the dictionary uh the good thing is by looking carefully this is something we can actually handle because we have all the information that we need so we decode using k in the step that will define k so we definitely add something to the dictionary it after this step and that would be the one the thing that we need we know the last phrase x but we don't know uh the next phrase y yet we would need it to insert it into the dictionary and then use it

23:01 immediately but we have seen x so that's where we decode it already and the fact that the encoder used uses the same phrase that we just create means that the last phrase plus the first character that's the xc that we added must also be what comes now right in the in the encoder we used this anna right after we inserted it so anna was the thing that we inserted x plus the next character and this is what we used so we know that this is the same thing and in particular the first character here the c must actually match the first character of x so we know this um that the next the next entry in the dictionary xc must actually be x followed by the first character in x so it always has this little self-similarity in it because of this overlap so this situation can arise it can happen as we've seen in the example but if it arises we actually know what to do so it's not a problem after all

24:19 here's the the full code where you see how this is handled uh and the interesting case is this um where we have to pull ourselves on our own bootstrap out of the swamp um by by using this special case

24:36 as you can see here we use the first character of x um maybe let me first finish the example and then i'll show you the rest of the code in slightly more detail so here again is our situation

24:51 and that's that's how it is resolved at the point where we decode 133 we had not filled it yet so that means we don't we didn't know what this is this was unclear but we knew the last phrase was x and that's indeed exactly the example that i drew here um also in this in this diagram we knew x was a n so the first character of a n is a so the next phrase must have been anna so we can resolve this here and we can also at the same time insert it into the dictionary and everything's fine and from then on we can decode as usual

25:38 Decoding implementation

25:40 so let's briefly look again at the code um how this can be spelled out in a little more systematic way again um we need a proper data structure for the dictionary for this to be efficient unlike before where we use the try here we actually need to find the meaning of a code word given the code word and that is actually much easier so we can just use an array in that where we use the index the code word as an index and then the entry in the array is just the well the phrase encoded as we've seen before

26:21 so we have similar variables as before the next free code word uh the first uh the first code word in the coded text that we're the next thing that we're decoding um and then the the next phrase and initially well we start with the whatever the first phrase is

26:50 and then we walk through all the the codes the code words we remember in x the last decoded phrase so we always need x and y remember let me decode one more

27:06 um that's the that's the next code word from the coded text and then there's two possibilities if we're in this weird special situation that what we want to look up now is what we would fill after this step we have the special bootstrap case and we know what y has to be otherwise y is just looked up in the dictionary we know the next phrase then and so in both cases we know x and y now and so we can add white to the decoded text we know why now that's the next uh the next phrase we looked up now we add the new thing to the dictionary which is x plus the first character of y uh and this this handles both cases now because we assigned y in the right way so that's that's all there is to lambdas with welsh decoding if you use an array here it's very efficient decoding is a tiny bit more efficient than encoding as we've seen before for huffman and indeed this is this is very fast um and can be implemented uh even even in hardware devices that's how the this patent came first into existence and uh in one way or in one variant or another lymphocytic values is below all all zip variants that are

28:24 out there and is very effective on many types of data so before we discuss a little bit more what levels of welsh is like here's a fairly tricky question just to see if you're digesting this well so this this is tough but it's an extreme case of a repetitive text we have just n copies of a and i'd like to know what would lampulsif welch do on such an input in a sense it's the ultimate repetitive input there's nothing more repetitive than just writing the same character over and over again remember something like run-length encoding would really compress this very well

28:42 Algorithm performance

29:23 and it's an interesting question to ask yourself what would lemposif welch behave like what would happen i didn't have an opening question today so uh i don't know for how many people we're waiting today but i would definitely hope for at least 20 or maybe 25 as usual

29:45 so i'll give you a little bit of time is also a question you actually have to think about a bit more it might be more suited for a tutorial problem but the tutorial was already full and so

30:00 i left it in the lecture 18 20 19 i'll rate a little more um give you a second here we're not in a big rush and i'll explain what the correct answer is after the after we we've seen the votes can we get two more people

30:58 doesn't look like it oh there they go of course uh great um so let's see let me lock in the results and uh indeed the correct answer the single correct answer is is this last one is this uh well the last one on the first page uh square root of n uh it's an interesting thing to look at so let me

31:34 and you might wonder why on earth square root of n and to see this you basically have to simulate the algorithm a little bit so let's try to do this just on a small example

31:53 where i use some ends and some small n and we'll look what happens when we start the dictionary only contains the single characters so we would encode this as a phrase and we would add a a to the dictionary we would always be in this weird bootstrap case for this example so we would always in the decoding phase we would always need this special case but that's beside the point the next thing we would read is a a because that's in the dictionary and we would insert aaa so the next thing would be these three characters and then well maybe i can add this so after the three we would insert four and then we find this as the last phrase so what you see is that with every the length of the phrase goes up by one so uh the total length of the string if i have k phrases say

33:09 with k phrases i would go from length 1 up to length k and i would sum up this so n would be something like this except for the last phrase maybe but let's uh suppose it's k full phrases um so you would you would have this sum and as you know this is uh quadratic it's well we can say it precisely in this case not that it helps too much okay k plus one half so this is the famous uh little gauss formula and if you solve for k i mean this is this is essentially quadratic so if you solve for k this is square root n you need square root n phrases to cover n copies of a

34:05 it might be interesting to remark that run length encoding got this login which is the number of bits you need to specify the length of the string so that's uh it's hard to imagine that you can never beat this login here for that very special case uh but lambeau's welch at least gets down to square root n which is way way better than linear whereas uh the best you could achieve with huffman coding is is n bits right so there's no way you get sublinear if you just use huffman for individual symbols okay cool that was uh that was that question so keep that in mind this is essentially also the um the best case for lempelsif welsh you can you cannot really get better than square root n but that is pretty good so uh it's a decent um it's a decent uh best case run length encoding is really extreme good square root n can sometimes be achieved usually you don't quite get that but you often get either a very good constant factor or sometimes even slightly sublinear

35:19 Advanced considerations

35:29 we've seen that we use as coded alphabet this um this range zero up to two to the d um and uh well that's that's fine that is binary so you you can use it as i presented it but often you will not use all of the code words with equal frequency or equally likely and then it might help to as a second step after lambeau sif welch when you encode the phrases just using the dictionary index it might be a smart idea to use a huffman code on top of that so that you don't just get the reduction from long phrases being represented by a fixed length thing but also if phrases are used with different frequencies you also exploit that so that's a typical thing you will see again and again in compression uh you chain these methods one after the other to improve compression and get the last little bit of redundancy squeezed out what i didn't talk about so far is what do we do if the dictionary is full i said we use a fixed length um for the for the code words but we also add another phrase when we use uh when we encode it with one phrase so we have to do something eventually the dictionary will be full

36:56 and then we have different options we can actually decide that we then double the size of the dictionary make d1 bigger that is a solution but it means over the long term that your your code words always get one bit longer and maybe that is detrimental another idea is to just start from scratch throw the dictionary away start again with single characters and go from there

37:30 that's nice because it limits the working memory that you need remember for encoding and decoding you have to keep the dictionary in main memory and if you do this on a small on a small device when streaming internet traffic say you might want to limit this so that's something that's often done a little bit a hack in between is to reserve a special code word that doesn't really encode anything in the text but signals to the decoder please now flush your dictionary and start from scratch i did the same so these are these are things you can play with uh and the dictionary size is something if you uh if you call a compression method a zip variant they often allow you to say how big the dictionary should be and that's a cons a parameter you can play with okay with the data structures that we've seen we can do encoding and decoding in linear time at least when the alphabet is constant an assumption we often make for for compression here and so that is very fast and it can also be done without um seeing the entire text in advance remember half man had this issue that you have to count the frequencies first uh if we use huffman for the dictionary codes of course we

38:48 inherit this restriction what is often done is you use levels of welsh for a certain period of the text and for a certain block length and then you start from scratch that goes hand in hand with flushing the dictionary for example it does achieve very good compression for many typical kinds of data so typical i will always have these two examples english language text or natural language text in a western language or biological sequences and lumpus welch turns out to work well for these often achieving reductions of more than one half

39:30 of more than a factor two um what is somewhat of a downside at least from the typical implementations if you fix the size of the dictionary if there's a repetition but that's very very far spread out in the in the input text you might not catch it because you flushed your dictionary before you could see it

39:57 also the the square root n is is uh i said is it is a decent lower bound but it's not the best possible in some scenarios as we've seen um so these are slight um slight downsides but it's a very solid method that is uh in white use

40:16 i have a last slide on on this part where we have a little comparison of these uh three methods that we've seen huffman codes run length encoding and lambo siftwelch most of the things that are in here we already discussed when we were [Music] discussing these methods in more detail and this also gives some some typical applications and some numbers for english text where you see huffman is actually not too bad if you start with ascii but then lemposifelsch gets it down a good bit more

40:54 and yeah here are some some things where it's applied uh i think huffman codes are very ubiquitous in in all kinds of formats but just as a piece of it so that's a little uh with that little summary of the three main methods we've seen so far i want to conclude this this subsection