Video 7-7: §7.7 Lempel Ziv Welch decoding

0:00 <Untitled Chapter 1>

0:03 in this section we'll look at how to decode a lambo's if welsh coded text because like you might miss does that mean that the encoding process yeah okay so the question was um is it possible that this encoding method misses the longest phrases or the best way to compress i mean taking your question in the most general sense it definitely will sometimes miss the best way to compress remember this fractal picture where we said the ultimate way of compressing is write a program that produces the image and this is a problem that's not just expensive to compute it's utterly impossible to compute with a computer at all so in that sense definitely we'll miss things

0:17 LZW encoding - Example

0:57 there are ways there are things that are good about this we'll we won't talk about this in in in the lecture but since you asked it's kind of an excuse for me to digress a bit uh the lamppost if welsh methods have some properties that are similar to huffman codes so they achieve something like huffman but in a stronger sense uh they can achieve something like k-th order empirical entropy so this uh is like the entropy we've seen but you take into account what was before the symbol as well and that kind of reflects this repetitions

1:34 in another way i think people are still this is still active research find something that is like entropy so you just take the text and you compute some number from the text and that expresses the compressibility of that of that text again the ultimate thing would be kolmogorov complexity which is out of the question but some somewhat sensible way of doing this that reflects the type of repetitions you can pick up with schemes like that uh there's still no definitive answer to that seems to be tough to capture this exactly

2:13 if you if you ask more humbly there are specific strings where you can show that lamppost if welch doesn't do great and a slight twist of the method does much better so in that sense also yes uh maybe that was the question you had in mind because if you look at if you look at some specific examples you sometimes it's it's it springs uh jumps at you that you can do slightly better but it's tougher to make this into a general method then uh yeah so that that's um it's a good part of the decoding chapter so i don't want to cut this out let's leave this in so it's an it's a good question um before we come to a little more of discussion how how well this works let's see that we can actually decode what we produced with lemprelsif welsh

3:04 as always decoding is the opposite of encoding so kind of we just replay what the encoder has done so the decoder will have to play the same game of growing the dictionary whenever you you decoded one phrase so for the decoder this looks as follows you decode a substring y of the of the text of the source text by means of finding it in the dictionary and after a few after you it why you have to add from the previous phrase a new code word to the dictionary right so that's um in the picture this y is the thing you encode now or sorry decode now and it points to some earlier occurrence of this of this substring so that's one one phrase in your dictionary and after you've after you've decoded y you still have to do what the encoder would have done which means uh add x and then this new symbol c to the dictionary that's the same steps that the encoder would have done it's just uh we have to delay this adding things to the dictionary a bit because we have to wait to see what y is before we can add this new character to the dictionary

4:32 okay um if we if we've decoded y then the first character is is the c i think that's that's so far clear from the picture let's uh let's see how this works on an example first and then um code will follow and uh pay close attention okay so here's um a sequence of uh of the code words for phrases in the dictionary we start the dictionary in the same way as before um so we initialize it with all the characters in the alphabet so here again the ascii characters this this will be a different example yeah

5:20 but the same initialization so we use the ascii characters so the first thing we know 67 decodes to a c and that's that's the first thing we we learned so the source text will appear following down this this column then we read the next code word which is 65 so that decodes to an a so far so good and then the second step is add a new phrase to the dictionary all right so uh our y now is a we take the first character of y it's just a and we take the previous phrase called x before which is now just the letter c and so the new thing we add to the dictionary is ca all right let's see one more sixty is 78 is is an n uh so that's our y the first character is still n is just a single one and we take the previous phrase that gives us a n and we add this to the dictionary

6:19 uh something to stress here maybe if you implement this you wouldn't really store these these strings literally instead you make note of the fact that this this uh apart from the last letter it's a phrase you had before so you can just store it as one code word and then one new letter so you don't need to store a long string in case you uh you care about the the space for the dictionary here okay one more and then things start slowly getting a bit interesting so space and we add after that previous phrase plus the new character to the dictionary and one more time and then for the first time we see a code word used that was not just a single character but was one of the ones that we we added to the dictionary after that so that's the input we look it up the new code starts here so we find a n is one of the new entries in the dictionary so we decode that and now the first character of a n is a that's our y zero so we have to add the previous phrase followed by a into the dictionary

7:32 okay can it ever happen that what we try to add to the dictionary here is already in the dictionary suppose it was it was possible so what would happen if ba is already in the dictionary before

8:08 it can it can it cannot happen can someone tell me why should have prepared a slider question for this one yeah yeah you're getting at the right point i mean first of all yes the the decoder can't really know you have to look at the encoder and the encoder made sure that you always take the longest match and then add one new character and now uh we're replete replaying the same thing so uh if this had been in the dictionary already then uh there should have been a longer match before when when b was chosen as the code word by the encoder it should have chosen ba instead and the fact that it didn't means it wasn't there okay so this this looks like it's all going fine until we arrive at this funny situation uh the new code word is one three three and you see this is not in the dictionary yet so we're kind of stuck because we would like to need we'd like to know what 133 is but it's the same time this is this is the time step where we would fill this cell and this can happen because the encoder is always one step ahead of us remember encoder does encode a new phrase and add a new thing to the

9:47 dictionary the decoder has to wait with the adding of the new thing to the dictionary until it has seen the next phrase and so it can happen that because you wait you need the same phrase right again

10:05 so it looks like this is um a dead end and the reason is um there's one step behind in creating of the dictionary uh so putting in this in a different way we want to use a code that we're just building and there's a very very specific situation where this can happen and luckily we can analyze this situation and solve it because there's only one specific case where this can occur so here's the situation um indeed the example um from before if you followed it through but uh try to not um like not read ahead so these these three characters y are not known to us yet okay the the decoder is at the stage it knows x that was the previous step maybe show this one more time so we know x-a-n that's the last thing we decoded we are at can ban

11:08 LZW decoding-Bootstrapping

11:12 this new part kanban that's where we are and then we ask for a phrase that we're just about to fill now when we create this phrase in the encoder we of course know what this text is and after we encode it anna we add the previous phrase and c so this anna here and you notice it's the same string here and that's that's not quite coincidental because if uh if this thing that you use now then if you create a code word and then use it right away that must mean that this x here is the same as this here so the new phrase is the one you just inserted so the new phrase y is the same as x c that's why i put it here below with this green bars indicating these are these same characters because the the encoder creates a new phrase and then uses it right away that means it must be the same thing he just inserted and that also means we know what x and c is because they're they're copied over and so in particular we know that c is the first character of x in this case and x we do know that was the previous phrase is a little is a little tricky but the

12:31 thing is if you if you write down all you know the only potential situation is is that the new phrase that you're trying to decode is the one that was just inserted and so because you know x you know that the first character of x must be the unknown character c okay so you can actually solve this by um by getting uh in this case just setting c manually as a as an exceptional case and then using that as y and inserting the phrase in the dictionary after that like before um okay i thought i had the example completed i guess after that maybe do that first so in [Music] in this case we we decode this by using that x the previous phrase

13:15 LZW decoding - Example continued

13:31 as as first character a and that must be our c so if we take x and then c we get a n a that's anna so we can put this both here for the source text the decoded text as well as here for the the new phrase we want to add to the dictionary

13:53 LZW decoding-Code

13:53 okay it might look a bit magic spelled out in code it looks like this [Music] there's not much there's not much beyond what i showed you in the example uh one thing that we didn't care about in the example is the data structures to represent the dictionary uh in this case the easiest because you want to access the dictionary by index you have a code word and you want to look up what that stands for so we don't use a try but instead we just use an array and the array stores for each for each code word it stores what it stands for which can either be a single character or another phrase followed by one single character

14:40 we we keep ax around for the last phrase we keep y around for the next thing to decode um k is is whatever we would insert to the next free code word the next position in the dictionary that is not used yet um initially we set this like a we initialize the dictionary with all the alphabet symbols so the next free one is is after that and q is is the code word so that's the next thing from the coded text and then we go through um all the letters in the coded text these are the letters are numbers here it's a it's an array of of code words it's already split up the bits into code words

15:25 we remember what we had in y before remember that in x then we take the next code word and here this is the special case if the code word that we're trying to decode is the same as k the next free one then we're in this in this anna special case and in that case we just set y to x followed by the first character of x in any other case we said why we look up what what the codeword stands for

15:56 because then we have it in the dictionary then we append this to the output y is the decoded text and then we have to store the new phrase xc as a as a new code word and x we we have remembered and c is the first character of y and because we caught this special case here above the adding things the dictionary is is regular is the same in both cases

16:35 okay there's one more line to finish this example off but that is uh is a regular case so nothing special to say there and so that completes that example

16:57 a bit how well this works um time to wake you up with a slightly unrelated question to this decoding part this is just about the encoding if you want

17:28 oh is it thanks i was wondering why you're so slow this morning this is a fairly tough question it means fully understanding the encoding part and then analyzing it on the spot so i'm i'm asking for a bit here maybe this question is is more for me as an excuse to talk about this best case then to really check your understanding

18:53 a few more people on the live stream today which is great that it's used i wonder if that has any correlation with the nice weather outside or there are other things going on um i think i count it to something like 25 the people in live stream plus what we have here so uh unless anyone's still busy thinking

19:19 let me let me show the answers first and there's variety and an interesting peak for this one um the uh the right one is ruden as i said this is a this is a fairly tricky one but uh it's a great excuse to briefly uh look at this example

19:37 Clicker Question

19:47 as often um well i don't know in this case the the single character repeated all over is the best case for compression that's uh it's a feature shared by many compression methods but maybe not also i won't promise more than than i can but in this case uh it's it's about as good as it can go so let's look at our text and i'll just put a few a's here and then we'll try to generalize from that how would encoding work for now let's just look at the phrases that the text is split into uh remember the encoding does this using a dictionary but really what matters for this question is how many phrases do we get and so this is just splitting the text up into certain sub segments the first phrase is just the character a we look up in the dictionary initially it contains all the alphabet letters there's nothing else in there after that we insert the previous phrase plus one more character that's a a and we find a a so this is the next phrase after we found that we add this phrase plus a new a which again we will use right away so this is if you want the text to practice this weird dead end situation

21:07 this will be always in that case it's always the phrase we just created that we now use again and i guess you see the pattern now right we take three a's for the next one then we add the fourth then we use that right away and so on and so forth uh so what you get is something like uh i mean it's 1 plus 2 plus 3

21:37 plus 4. that is the number of characters we used so far and what we want is that's obviously the sum of the first integers uh and we want to know let's say k phrases we want to know that and we want to have that this is at least n because we need this to cover the entire text and then you may know that this is very roughly i can write this in precise notation this is k squared over 2 as an asymptotic approximation it's not exactly that but pretty much and so if you solve for k that gives you square root n well it's an interesting little factoid to keep in mind if you compare it with run length encoding remember best case for run length encoding same same text compresses it down to log n bits because you just tell the decoder how long the text is in this case uh you you don't get square you don't get log n you get square root n that's um worse but still pretty good for many texts you won't get that much of a compression

22:49 okay that as an order of magnitude maybe is useful to keep in mind uh what else can we say about lambelsif welsh first of all about the implementation i presented it so that the output is a sequence of code words you might want to further compress this because the code words probably don't occur equally so they don't occur with equal frequencies so you might want to add another huffman code after that or some other code that can take advantage of this or you just write them in binary eyes um depends depends a bit uh then what i told you so far is a little it was a bit of a lie i said we fixed the size of the dictionary as two to the d so that we have d bits for each code word where if we keep encoding along a longer text then we run out of space in the dictionary so we need a rule to do what we do in this case and there are different sensible options we can add more bits to the code words to make room we can also just say forget the dictionary and start from scratch again or well scratch means we start from single alphabet symbols and then filling up again another option is

22:51 LZW-Discussion

24:08 to to trigger this case even before the dictionary is full and have some heuristic that detects when maybe it's a good idea why would you maybe want to flush the dictionary earlier the idea is there are some portions in the text that are similar and then there's a different portion of the text that has different character characteristics and all of this compression method is using that things you've seen before occur again and if that's if that's no longer the case then it's maybe a better idea to forget what you've seen and start again uh but this is this is a a gray wishy-washy area a bit there's no very clear rule when and how you should do this so practical implementations like zip they have some some rules for this uh sometimes the dictionary size is a parameter you can specify if you if you don't just click the default option but you use some tool that shows those so often these are things you can you can play with and you can fine tune it but for many applications doesn't matter too much in terms of running time they both can be implemented so that they run in in linear time which is uh the best you can hope for if you have to read the text so that's

25:24 that's pretty decent so we like that they're fast um you can apply them in a streaming like fashion if if you have some some rule for how the dictionaries are are handled if they get full you can do this in one go right it's not like huffman that you have to scan the text first count all the other frequencies and then start coding you can do this in in one go both encoding and decoding and that's why this is also used as transport level compression in you can specify this as part of of http that it compresses the payload and so it has to work in this in this way all right also it achieves good compression for many types of data you all have used zip and unless you zip a zip file again or zip something like um an already compressed jpeg image or video it usually works quite well and gives you some decent compression of i don't know fifty percent uh some some downsides is uh if you have very very long ranges of repetitions so you have a huge text file which is copied twice say as a hypothetical scenario if that is too big for the dictionary to contain everything it might get flushed and you don't get the

26:45 you don't recognize this repetition that's inherent in this in this method in a sense because you you will run out of space for the dictionary eventually or you will get some hit if you increment d you don't run out of space but your code words get longer that's also some somehow wasteful um yes let me point out that the no free lunch theorem that i promised you for last week is on this week's tutorial it's always confusing because i'm thinking about the next tutorial that i'm putting up not the one that you're already working on so this is up on the website now and you'll discuss this with ben this week there's a nice a nice little theorem that proves compression cannot always work i mentioned this a couple of times

27:32 yeah but by and large this is still a method of high practicality and is used in many places and here's a quick overview of where the different compression methods that we've seen are used or where they're good for and this summarizes just the summary slides of the previous section so i don't want to go over this eye in more detail it's kind of a service to you to not look it up on the other slides

27:39 Compression summary