Video 5-8: §5.7 Lempel Ziv Welch decoding

0:04 an encoding method is only as good as uh long as we can also decode it so we should have a look at that as well in the next section we'll see how to decode lampol Welsh coded text again and uh we'll see that there's a slightly tricky situation to

0:30 overcome from a high abstract point of view all the decoder has to do is undo what the encoder has done so we have to uh do the same steps to grow the dictionary because um we need to know what the dictionary was at the time of encoding to decode the code words that were given so we'll have to roll through this process um and if you think about what that means um it's it's what's what's spelled out here you decode a substring of the source text y That's this part here and um in the encoding step we always encoded a bit and then added a new phrase to the dictionary so we have to do that as well namely um when we encoded y when we decoded y we have to go back in time and add from the previous phrase X and C to the dictionary the reason why we can't do this straight away is that the uh the new phrase that the encoder added after encoding X includes this first character C of the next phrase and we just don't know what that character is until we've decoded the next phrase as well so we have to delay the adding of of this new phrase until we've seen the next phrase but that's that's so F that's

1:55 that's fine so far right so um we just have to do this after after the next uh phrase is decoded uh and the rest works works the same so let's uh do an example again um same alphabet it's pre-filled with all the ask you symbols and here is a sequence of the coded text code words if we start decoding we find 67 in the dictionary so that's a c so um we put that to the source text that we've constructed so far now remember the encoder at this point would have added a new phrase to the dictionary C plus one more character but we have no idea what that next character is yet so we can't do it um we'll have to wait but we decode the next letter the next code word it's an A so that's that's going here and now we know okay the encoder added CA as a new code word to the dictionary back in the day all right so we keep going like this decode the next one that happens to be an N now we know the encoder must have added a an at the time to the dictionary so we also do that another one this decodes to a space so the previous decoded thing plus the

3:17 space is what's added to the dictionary uh just a remark here all the dictionaries the previous for encoding as well they wouldn't actually store these strings they can just store one code word and one additional letter because all code words are like this there're a previous code word and one Ed extra letter added at the end so you can store them like this the pro the benefit here is that this is constant length it's the the length of the code words 12 bits in the example and one more character whereas this could grow longer and longer all right uh let's decode the next next thing 66 decod to a b so we know space b went to the dictionary in the encoding so we do that as well and then uh 129 decodes to a an

4:20 um that's from this one something we added before and now we know B with the first character of that new phrase went into the dictionary so we have to do that as well fine until this point because now we're trying to decode um a code word that we haven't actually filled yet and that's a situation that can arise here because we're always lagging one step behind the encoder so it seems like in this case you're stuck and it's not clear how to escape that that dead end but luckily you can nail down the the exact situation when this happens to the degree that you can resolve it so the problem was we wanted to decode a code word that's not yet in the dictionary well that can only happen if that's the code word that the encoder would have put into the dictionary just before that step we can't ever get too far behind it's just one step but we're one step behind in creating the dictionary compared to the encoder so it can only happen when we're using a code that we're just about to build and we can analyze what that situation um is like so uh let's revisit what the encoder had done at the time it stored X um and then added X and the next

5:51 character to the dictionary and then it in The Next Step It reused exactly the phrase that it was just just adding to the dictionary that's the situation that tripped us over it can only happen if the phrase that we're using right after is the one we just put in the dictionary but that means um that these two phrases have a certain relationship it means that the next phrase is essentially x c copied down and so in particular the first letter of this phrase is the first letter of your previous phrase right so you can resolve this uh this conflict in the decoder by uh by introspection or I don't know how to call it um if you're in this situation like here where you you used the phrase that you're just about to fill you know that c is the first character of the previous phrase there's no other

6:55 option um okay here's this dis spelled out let's first finish the example uh I think that's that's better so we were in this in this situation to decode 133 and uh we know we just we were just about to fill it it's not yet here but the previous phrase was this a an and because we're we're in this special case we have to have this the first letter of the previous phrase appended at the end again to obtain this new phrase It's exactly this example that's shown here by the way so you can follow that through in in detail uh what's missing again is is detailed code how to do that um it looks like a lot of text but there's not much um not much complicated going on uh we start with a dictionary initialized just with codes for the for the alphabet in this case we don't need a special data structure like a try or so it's just an array and we use indices in this dictionary the code words are just indices in this array we also we have we have to simulate the building up of the dictionary so we use the same same variables the next free code word um and we have to remember uh the previous phrase um then Q is the next the next

8:21 code word from uh the the coded text and that will be uh the next phrase that we decode y let me go through all the code words in the coded text now because we have to uh lag one step behind we have to remember what the previous phrase was that will be X and Y is the one that we're decoding next we get the next code word and if we're in this special case that K uh that Q is K which means Q is the next free code word the one we're just about to fill that's that special case that we looked at and in that case we know that we can set y to X followed by the first symbol of itself and in any other case we just use the dictionary to look up what the meaning of that of that code word was uh then we we append the decoded phrase to the source text and we have to update the the dictionary so if we're not in this special case then uh we take the first character of Y and add that after X that's the new the new phrase we add to the diction AR okay that's exactly the process I showed you in the example but um spelled out carefully with this special case

9:39 added in so uh for for a quick test of the high level understanding this question is not about the specific special case or anything like that it's more um thinking from first principles what this method can

10:08 do and it's often insightful for a new compression method to look at extreme cases like this a boring text of just all A's what would I think this is a very insightful question so um I wonder if it makes sense to um leave you more time to think about it or would you rather uh discuss discuss the answer straight away

12:05 I think we'll do the following I'll show you the distribution of answers and um maybe leave you a bit more time to think about it but then we also switch to new topics I don't know if that makes makes a ton of sense um I feel this is this is a really insightful question for you to think about so I don't want to spoil it straight away on the other hand um if there's if there's confusion about the method it might be useful to discuss it uh so here's here's the answers it's pretty much every every option got some

13:05 okay um let me show you why that's the right answer um and you can practice this on on other strings I think that's that's still insightful to do so so the right answer is um this ominous square root n it sounds like I I've just added this as an option because it a square root sign always looks cool and it looks confusing uh why why is that um what comes out if you have this long string of A's let's briefly run through what else at w would

13:41 do initially you have nothing in your dictionary you have a single single letter so you would encode the a by itself then what what do you add to the dictionary well the previous phrase plus the next character so you add AA to the dictionary then the next thing you find oh that's AA is always this weird special case but fine that's what it is so you store the two A's as one code word and what do you add to the dictionary what you had plus the next thing Three A's after that oh I found three A's okay so the phrases each time get one letter bigger and okay let's make it work out nicely and evenly they get bigger each time okay how does that bring us to this answer well uh if we have K phrases they in total cover how many A's well you start with I from one up to K let move it down it'sit too

14:53 small and that's by and large okay we can we can of course do it precisely but um by and large it's k^2 over two so to cover Nas I can I can say I'm I'm using that as an equation k^2 over 2 should be N I need as many phrases to cover n letters so if you solve this then you get that K is of the order square root n so you need square root and phrases to cover Nas um and that's what uh lmol would do in this case so that's that's why you get this this slightly ominous answer it comes from from Little Gus's formula for the sum of

15:48 integers that's just as a cute side note and maybe it just helps practicing what happens or see clear of what happens if if you uh rise from the we weeds of the details of the code um the way we presented this here lsaw uses um some fixed code word size

16:10 uh where you can you can maybe tweak how big the dictionary is and uh as an as a side note most Z implementations actually allow you to do that you can say how big you want the dictionary to grow uh it's often hidden but they have parameters where you can set this uh we need another encode from those code words to Binary I've always just left it with decimal numbers and say oh there's a sequence of of these numbers so what you'll what you do in practice is have another coding after that and you could use a half man code for the code words that's one option um what we've totally glossed over is that I keep adding things to the dictionary as I encode more text So eventually it'll be full because it's a finite size it has two to the D entries and and we have different options what we can do and and they all can make sense uh one option would be to just double the size of the dictionary whenever we run out of space and then make the code where it's longer the other option would be okay whenever the dictionary is full we empty it and start from scratch and when we decide to do that anyways we might even have a special

17:20 code word reserved for this operation if the encoder feels like okay feels um is very vague and often that's a euristic if there's some euristic that tells the encoder I think the text is changing and um I might profit in my encoding from flushing the dictionary here then you emit this special code word that tells the decoder at this point start with an empty dictionary again so these are all the options and often often this one is is chosen in these these two in

17:56 combination but that's a these are tuning parameters one can play with encoding and decoding both are essentially linear time using the right data structures tries uh where we haven't discussed the details at least if the alphabet is

18:13 constant so overall the method is still very fast and and relatively simple um another nice benefit is it can work in the streaming model where you get the text piece by piece and you have to Output the coded version so um lample C compression is for example part of the HTTP protocols you can specify that a transport stream is is compressed while you're sending it so even though your web pages look like they have all this repetitive HTML XML tags what goes over the wire might actually be compressed to much smaller it's much smaller space uh and they yield they yield significant compression for many types of data that's why they're used so much I I bet you have made the experience if you zip some files they usually become I don't know maybe a third of the size or so depends on the data of course uh the slide down side with the bounded dictionary is that it it only captures um somewhat local repetition so this is a bit of an um a special case point but if you have um if you have data sets with very long things but they are repetitive an example would be a collection of human genomes each of them is very big they all also very similar

19:29 to each other but you need a very big dictionary to capture those repetitions because they're long range repetitions so the the simple versions of zip just don't do that and you would need a lot of uh main memory to capture those um but that might just be not not uh not possible to improve now let's use this point for a quick summary of what we've seen so far we've seen three methods Huffman run length en coding and lle if Welsh um and they have they exhibit slightly different different trade-offs and they follow different strategies uh that's summarized here um I want to go through all in in full detail um they have different regimes for the code words uh which part is fixed and which is variable either this part the phrases in the source text or the produced code words um hu man needs these two passes the others don't um and uh some some exemplary data on on English text uh ground length in coding basically doesn't work or doesn't compress at all whereas Huffman codes at least Works to a good degree and lle Welsh a bit more but also the difference between the two isn't isn't very striking at this level