Video 7-8: §7.7 Lempel Ziv Welch decoding

0:00 <Untitled Chapter 1>

0:04 after we've seen how to encode with limposite files we now want to decode the decompress step and in principle it's easy we have to reverse what the encoder has done otherwise we don't get back to the same Source text the details are a little more tricky because um as we'll see the uh decoding is always a bit lagging behind and in the intuition behind that is is easy remember we always encode one code word and then store a new one and so we have to do the same in the decoder so the the normal mode of operation is we decode a substring from The Source text which we find as a fixed length code word so the splitting of the coded text into code words is easy is always in the example the slides at 12 bits is a typical size in fact it's a parameter you can often play with if you use sip programs so there's a fixed length code word so it's always clear what the next code word is in the coded text and hopefully that maps to Something in Your Dictionary so you can decode that codeword to Something in the clear text in the source text and after we've done that we have to add a new string to the dictionary because

1:23 that's what the encoder did and we have to keep adding these because they might be used in the future and just for notation I'll always use Y for the thing that we decoded and then x with C added as the thing that we add to the dictionary

1:46 [Music] um and now that the trick is that in the encoder X and Y was Y and X was basically the same but now because we're lagging one step behind access the previous leak decoded thing right remember we can only store the new thing to the dictionary once we know what it is the encoder encoded one step and then added that thing to the dictionary in the decoder I can't really do that I first have to decode the thing before I can add it and so the easiest way to deal with that is to say we decode one thing and then add something but what we add is actually the the previous previous string

2:33 so we'll have X as the phrase that we decoded in the last step why the phrase that we decode now and XC this one more letter that we should add is actually the first character of of Y because that's uh the new phrase so here's a concrete example that may show may make it more clear why we have to do it this this complicated way in the previous case in the previous step we decoded X and that was ban now the encoder would have added Banner band plus the next letter to the dictionary but at the point of decoding band we don't know what a is we don't know what the next letter is we haven't seen that a yet so we have to wait for the next step when we decode Y which is a n in this case then we know the first letter of Y was an A and only then can we add x c to the dictionary okay that's the complication we're always lacking one step behind because we need this first letter of the new phrase so we can also um only start adding after we've seen two phrases decoded we can't start earlier clear so far

3:48 LZW decoding-Example

3:50 let's have an example for that as well a similar setup but a different string so that doesn't get too boring so what we get is a sequence of code words now these are written in Gray they will they will come up uh highlighted later on we start again with filling the dictionary with all the single characters in our alphabet that's the same as before and it's important we use the same initial state of course and then you see the code words are just these these numbers they're really fixed length bit strings I just wrote them in in decimal to make it more human friendly but you think you should think of these of all having say 12 bits and there is leading zeros where the numbers are shorter that clear that was a question that came up on campus wires I thought I'd point this out again all right so how does the decoding work we see a number 67 and so we find the entry in the dictionary that's the first phrase that we decode that's great and so um here is uh it's written as a table but it's it's producing the source code and what you add to the dictionary in one go just have it nicely written up so we decode this to c that's the first part

5:12 of the source text and you will be able to read The Source text down from here at the end we can't do anything else we should add C in the next character to the dictionary but we can't do that yet so we we move on to the second code word decode what that is so again A Single Character so we read that from the dictionary we find the a and now we add a new phrase the dictionary namely the previous phrase plus the first character of the current phrase so that's why

5:49 uh sorry no that's that's a that's a new phrase X is the previous phrase that's C and so we add X and this first character of Y to the dictionary

6:03 and that's what we do okay and again of course we don't really store this as string we can store it as one code word plus one letter uses less space okay keep going like this for a while so 78 is another single character letter so we we decode that and now we have another round of a previous phrase a a new phrase n so we add a n to the dictionary s as shown here now in these simple examples at the beginning X and Y are single characters but in the general case X is any string and what we add to access this the first character of Y

6:53 one more we decode the space and we add previous phrase plus first character to the dictionary one more and then things first get more interesting so we have the 129 that's one of the phrases we added so it decodes to a n it's the first time we use one of these so let me write one last time our previous phrase was the B the new phrase is a n so the first letter of a n is a which means we add ba to the dictionary and that's what you see here all right so just to the point where we see okay we have understood things now suddenly we run into this weird situation the next coded word is the 133 which would be the next code to fill but we haven't filled it yet so we don't know what to do we don't know what to decode it to and it looks like this is um a terrible dead end which comes from the fact that in the encoding is always one step ahead and now in decoding we never quite catch up and so we can run into this situation uh fortunately by just looking at this a bit more closely we can resolve it

8:14 LZW decoding-Bootstrapping

8:17 so again problem comes from this lagging behind and that might lead to the situation that we want to fill we want to decode the codeword that we're just about to fill after this round so what can we do

8:35 um we can have a close look at when exactly this situation can happen and then you'll see that it's actually not a problem so we're decoding the same phrase that we're now filling and that means uh in the encoder the encoder also generated that phrase right from the previous step it has to be like that because otherwise the encoder would also not have had that phrase so the encoder started with a n and encoded that and then added to the dictionary a n a

9:13 and then a and a comes again that's exactly the situation it can only happen like this the encoder has a phrase adds a new character and then that new phrase directly appears one more time

9:28 but if that happens we know that this a n is the same as this a n and this a here is the same as this a here so we actually know a lot more about this specific string and in particular um we uh we know that this C must be the first character of the previous phrase in this case all right so again follow along the picture we have a n in the encoder previously we encode that but then we add the A and put that into the dictionary as a new phrase and now it says the situation means we've now used that phrase as the next step so the next phrase must be a and a and that's the next thing that the encoder uh in codes so it uses this new phrase and that means that this A and A is the same as this A and A so the the blue a always is the first character of of x so with this with this special case of of just using um the case analysis and substituting that here it's not the first character of Y but simply the first character of X again we can resolve that case

10:47 LZW decoding - Code

10:51 so here's the code for that it looks like a lot of text but um apart from this case special case there's there's nothing really uh um complicated going on we we start with a dictionary in this case we don't need a fancy try or any any special data structure it's just an array with strings or pairs of uh previous previous phrase and one character and we initialize the first section with all the in single characters in the alphabet then we have as before a variable for the next free code word as a shorthand we we cache the the next code word to decode and why is this phrase that we're now decoding same uh use same same name as before and we have the source text initially that's just the first phrase and we'll keep adding to it now we we iterate through the length of the coded text we remember the previous phrase in X what was y last time is X now we look at the next code word and then if that code word is the special case we're trying to use the code word that we're just about to write to the dictionary then we know Y is of this special special form we know what to do and otherwise we it's one that we added

12:19 earlier so we can look it up from the dictionary then we add that to our source text um store the new phrase so this is this is the the real y that we decoded so this is um

12:39 that's the the phrase that we add to the to the next point and it captures both cases now because we set y here to this and Advance this I think the code is is not too complicated after you've seen this special case the rest is is exactly as in the example um code it down

13:09 LZW decoding - Example continued

13:13 so to finish off our example from before if we're in this special case where we use exactly the previous phase we know previous phrase was a n we're in the special case that we need the same phrase again so we append the first character of that same phrase that's our new code word

13:37 or new phrase for the text so we add that to the dictionary and also use it right away all right the with the key things out of the way so if you have questions about the decoding maybe we should do that first um if not I'd like you to think about a bit about the extreme cases for this

14:27 okay slider keeps reloading I'll get there eventually okay in the interest of everyone at home I hope it's just slighter that's slow and not our connection here um I think we've been well over 30 before so let's wait a little bit

16:19 ah I didn't reset the answer so I don't know how many we've had today but given that you had a lot of time to think well I was fighting with slido Let's Pretend 30 is enough and um that means one more oh okay there we go

16:44 Clicker Question

16:46 uh let me dissect a bit why that's the case so this is a question in a way first of all a text that consists of just A's repeated hopefully is something like the best case for compression it's as boring as it can possibly get so we should in a way see this as the best possible case what's in the extreme case the compressed the compressibility or what What compression ratio can levels of Welch achieve if the text is as boring as as can be and so let's write a bunch of A's

17:29 now let's start simulating what the lampus of Welsh algorithm would do to see if we can spot a pattern initially it'll fill its table with all the the symbols in the alphabet let's suppose uh whatever a is one of these right so the first step the first phrase we find is just the single a we encode the code word for that whatever it is and then we add a plus the next character to the dictionary that's how it always worked so we add a a to the dictionary and then we move on next phrase is precisely that a a that we just created right that's the longest match we can find we encode that and store that plus the next character to the dictionary which is Three A's and then one together guess why what happens um we find the Three A's right again so the next phrase will be these and then we add a fourth a put that in the dictionary which is again what we find so you can probably spot the pattern by now uh if you decode this by the way we will always always run into the weird case where we use the phrase that we just are about to add so if you want to practice that and see

18:49 if you've got the got the cases right this is a simple example to force the special case okay so we we always make the phrases one longer what does that mean for the number of phrases if we sum up the total length that we covered with phrases then let's let's open um this runs to something that we don't know but we want that this covers at least the length of the string right so if you put some some specific number okay that we don't know yet if that inequality is fulfilled then we have enough phrases to cover the entire text and so this sum is in asymptotic notation uh let's write them down on this side is K squared over 2 . now I know you can probably work this out you all know uh gauss's little formula and so on you can solve it entirely but the the point is if you solve for k then roughly the order of growth is root n so that's why we get that it's not super intuitive you need to really think about some concrete example to see why that happens if you just think about the procedure and I would have told you root n is the best possible it feels like eh why there's nothing nothing squarish happening

20:16 uh it's only through this indirect route all right so that's all for levels if Welsh let's um let's briefly wrap up what we've seen so um there's a few bits and Buffs before before I come to the pro and cons there's a few things from the presentation where you should say hold on a minute uh I promise that we use this fixed size alphabet say 12 bits which means the dictionary is a finite size if I keep encoding things I will eventually fill up the entire dictionary I always add one more phrase so at some point um I have to deal with the with the situation that the dictionary is full and there's different options what you can do each can make sense uh depends on on what you want to achieve um and what the input looks like if you have reason to believe that the text is overall repeating then it might make sense to just increment the codeword size over time the other option often used in in practice because it avoids running out of memory eventually is to just flush the dictionary start from scratch so you fill it up and then you you pretend you start from the initial State again uh and indeed um most applications of sipped and so on

20:23 LZW-Discussion

21:51 they have a special code word where the encoder can say I think now is a smart time to just abandon the dictionary flush it and start from scratch now why would you ever want to do that on purpose before it fills up you would want to do that if the text changes its nature so if there's say if it's two documents one in English and one in French concatenate it then maybe there's not too much repetition in the French part branching back to the English part and if you can somehow with some heuristic detect say you've always just used single letters for a while then maybe it's better to just flush and start from scratch things like that um people try to try to do in practice

22:43 from our side it's just um we'll mostly in our examples we'll just treat the case where you still have time still have space in your dictionary for a general implementation you have to just decide what you want to do all of these halves their their pros and cons so this this gets better compression but might um yeah I might might fill up your main memory because you keep adding to a dictionary uh this avoids that but if if you flush the dictionary too early then you may miss some repetition from far back all right

23:27 uh the good part is that encoding decoding all runs in linear time and if if you have space for the dictionary you can even do it in streaming mode you don't ever look back into the text really all you need is your dictionary and that's why people use lampus if methods also for transport layer compression uh now good question of which layer is this I think it's it's at HTTP layer so web traffic you can automatically tell your your uh operating system to compress the stream before it leaves the network before it leaves on the network um and that this can be done while just reading the text once and outputting the compressed result that's important for such an application

24:23 so we like the fast encoding and decoding obviously and that it works in this streaming way um it also works really well for many types of data that we seem to have in our world and I've mentioned why before it's just a a lot is text based in one form or another and there's many human friendly text tends to have small repeated parts that mean something to us

24:54 with a bounded dictionary at least if we do this flushing technique uh we're somewhat local in the repetitions that we can catch and even if you keep increasing your dictionary you will be able to reach all the way back to find repetitions uh but you make all code words one bit longer which may um may not be a good deal in all cases so then you can play more tricks like um the first bullet take these code words that come out of that and try to compress that further with some other technique like a Huffman code but if you keep stacking things up too high it becomes tough to understand what's happening so there's some some slight negative part that capturing really long range repetitions doesn't usually work so well with lampus if I'm just mentioning this here because we'll we'll come back to that that question later

25:51 Compression summary

25:54 I want to summarize what we've seen so far because these are the traditional compression methods um and the three most important ones we've seen um I don't necessarily want to read that out all again it's basically repeating what I said in the discussion slides of the appropriate chapters but as a little service to you as I'm arrested um and there's a few comments on where where it's used in what form as I said before none of these methods is used in isolation as the solution for everything they're usually used in combination and we'll come back to that as well