Video 7-7: §7.6 Lempel-Ziv-Welch encoding

0:00 <Untitled Chapter 1>

0:03 in the next section we want to look at the lemposif compression family and specifically lampus if Welch algorithm as one example of that family which will be the first algorithm that gives you real uh sensible compression of this type of repetitive texts in lots of lots of practical examples run length encoding was all fine and we'll use we'll use part of that as a building block but by itself it doesn't compress most data super well

0:36 Warmup

0:38 now to warm up um without explaining much how lampless if works I want to just show you this and there's um a slider question for that which um asks you to produce the second to last line so this I'm interested in this line that's what you're supposed to answer on slido

1:17 at this point I took this example out of the computer science unplugged collection is a fun fun exercises that teach Computing Concepts without really using computers much um and this is a I think a really nice example it doesn't need words to really explain what's happening but it conveys the idea of impulsif so beautifully

1:45 and in case you didn't know what peace porridge is I was told that's that's the right thing is some kind of soup I don't know I didn't get a chance to try the the original one

1:59 but um I don't want to try the version advertised in this poem for sure um so that's still big enough all right I mean you can type it in and uh approach problem plus minus commas and stuff I think people get this uh the the idea here of course is um some of these boxes are empty but instead they are a reference to something that occurs earlier so you just copy whatever is there and and so you get peace Pro chart piece Point cold peace porch in the pot nine days old yummy some like it has some like it cold some like it in the pot nine days old and you see not a lot of explicit letters are needed because this is a super repetitive poem

2:36 Clicker Question

3:31 um this is pretty much what lemposif also tries it's a Morse uh structured and more systematic way of doing that encoding a text by repeating something that you've already encoded earlier

3:49 of course if you're doing this with a computer you have to somehow say what these boxes look like and what do the arrows correspond to and you want to be Frugal with the number of bits you use in both cases and that's where all the the complications start all right

4:12 Lempel-Ziv Compression

4:19 so so far we've mostly focused on single characters and now we'll definitely go away from that um again to motivate this a bit in many many cases you have certain substrings not just individual characters that are more frequent than others their word English words that are much more frequent than other combinations of letters I mean th e is probably much more common than x x y right and you have the same in other applications I mean uh most of the web is basically a big text file and a lot of that is some form of XML which is really not not the shortest way to write things but compression of the lamplusive type means you don't have to worry about that redundancy too much

5:12 it's a whole family of compression methods they're all adaptive in our classic classification from earlier so they don't use a fixed code but they keep changing the code as they go which is what makes them quite interesting

5:25 um in this case we'll have code words that's again the things that make up the coded text but in the source text they can either be a single character or a whole substring and we'll have to make sure that the encoder and decoder stay in sync about what that means there's lots of variations of that idea in in different ways what exactly are the boxes and what are the pointers stored like I don't think I want to go into this in any any more detail um it's it just shows you maybe that this method is is included in all sorts of compression methods in particular I should definitely point that out uh the zip compression format is pretty much impulsive with a few extra twists or um levels of Welsh or variations of that

6:26 what all these families have in common is they're more or less um the same in what type of redundancy they can pick up and so that's also why these formats often behave relatively similar

6:43 so let's come to the the star of our show in this section the limposite Welch algorithm it's usually seen as the cleanest version of those so that's why I'm presenting this one as opposed to another one but the others they are similar in spirit it's a variable to fixed length encoding we code a variable length substring but the code words will all have the same size think of something like 12 bits as a typical one if you've played with zip compression sometimes you can tweak a parameter called the dictionary size that will pretty much be the number k

7:23 now how does this work we maintain a dictionary again this is where this name comes from it's a list of portions of the text we have seen let's call this D and it has two to the K entries that's simply one entry for each possible code word if we have k-bit code words then two to Decay entries are in the dictionary we fill the dictionary initially with the single characters so we assume um these are already in the dictionary at the beginning and then we'll keep adding more things to the dictionary in each step

8:04 and what do we add to the dictionary that's described with um something like this picture so suppose we have encoded our text up to this point that's the the gray part that's done and now there's more characters to follow and we we can look ahead at what are the characters that come now we find um a longest match in our dictionary that starts at this position so we look through our dictionary and try to find what is the longest thing that I can read from here that I've seen before and in this example say that's this this substring ban which occurs before here I mean you see the similarity of the picture before then that is what you encode and you encode it by using the entry in the dictionary so you've seen that before which means it has a code word assigned in the dictionary so that code word is your output but you're not done yet if you only would do that you would never ever get to bigger and bigger entries in the dictionary so the second thing you do is you add a new code word in the dictionary which consists of the old code word you found plus one more character so you add this next character a in this

9:23 case and then this this combined red and blue part together that's one new code word that you add to your dictionary to be used in the future all right and nitpick in terms of space you don't really have to copy these strings instead you can say I'm storing a code word X that's the one I repeated and then just the single new character so these entries in the dictionary they're all just two numbers let's see how this works on an example and I think that will make it clear I'm assuming here that we're using the standard ASCII alphabet so we can pre-fill our dictionary with the first the first few entries are taken just by the the ASCII characters I only show the ones that occur in our text but of course the others would be there as well and then we start start encoding at the beginning it's easy because there's only the single characters in the dictionary so we find the longest thing we can find here in this yo you your yo-yo is the letter Y which has code 89 so that's our output but we're not done we have to add a new thing to the dictionary at this point so we take the next character after after the Y and add that as a new

9:52 LZW encoding-Example

10:47 code word okay let me keep on going the next character we find is an O there's nothing longer than the single o in the dictionary so we encode this but we add one more thing to the dictionary which is O and the exclamation mark okay this keeps going for a while like that you encode A Single Character because you haven't seen anything bigger than that and you add to the dictionary what you've encoded plus one more character it takes a bit before things get interesting but at this point the next thing we want to encode Starts Here and Now we could just take the Y as before but we actually have y o in the dictionary as well so we take that because it's the longer match so we encode the 128 but as before we add this plus one more character has a new string in the dictionary and so you see how this builds up longer things in the dictionary to use later and so if things if some string occurs many times you can just reuse the longest version of that

12:08 here we have another one just a single character and insert that character plus the next here we have another match so the exclamation mark space that combination occurred before so we can add that and we make a new entry with exclamation mark space y

12:32 and so on next one we find our U again that we used before so we can make use of the three letter code word and we insert an even longer one

12:45 all right um R we haven't seen before so that's an individual character and we insert our space space Y is something we've seen before but we haven't seen anything longer so we take that one and insert a new one space y o

13:07 o we have seen before but with exclamation mark after it so the only only one is this one but not o y so we leave the single o but at o y now

13:22 um and one more so yo we've seen up here very first one so encode that and add a new one and then we're done foreign exclamation mark is encoded then we're done okay

13:35 so it's fairly straightforward how the encoding works um and you see how it picks up the repeated Parts by having longer and longer things in the dictionary if you put that into pseudocode you can write it like that you want to spend a little thought on how to represent the dictionary if you just have that as a table as in the example it wouldn't be very efficient you would have to search through it but we know a much better way to do it once again the try is what helps if you keep the code words in the dictionary in a try you you have to keep you have to change a little bit because there are prefixes of each other but the longest match will just consist in you start walking down the try as you read in the text and as soon as you can't continue you found the longest match so that's that's relatively straightforward and gives you um constant time per letter

13:47 LZW encoding-Code

14:41 then you keep a number that's um the next free code word that you want to assign and the rest is as you've seen in the example following through so we get the next character from the text we check if we can move one Edge down in the try if we can we we do that and we remember in X what the uh the phrase was that we could read if we fall out of the try we found our longest code word in the dictionary then we append to the coded text the code word for x and we add the new and entry in the dictionary which is C is always the next character in the text so XC is added and we insert K as the value that's the code word then we have to make K1 bigger and reset X to just this Single Character and so uh the code for this is is relatively straightforward we're just plugging in data structures to make it a bit faster