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

0:00 Introduction

0:03 in this section we'll see the first compression method that already as it is shown here is is competitive in in applications and that's the lampposif welsh method but you would probably better know it as variants of zip and that's it's lampposif is an entire family of compression algorithms and this is one specific example that is arguably the cleanest to show they all have similar flavors and so it doesn't matter too much um but i definitely want to stress that whenever you use programs like zip gzip and their variations they build on ideas around that and add more bells and whistles to it but the core idea is is what's uh coming up in this lecture to motivate this uh let's do a little toy example without much saying further often without any further instructions um head over to slido and tell me what the second to last line of that poem is

1:14 i'll leave i'll leave the the slide up but this idea of presenting things in this activity is is taken from uh computer science unblocked which is a lovely resource for explaining computer science concepts in a really approachable way and without computers hence the name there's many other cool things there but this is from their compression unit

1:58 in case you're like me and you were you wondered what peace porridge would be that's shown in the picture i was told some some northern english dish but i haven't yet found a local to confirm this it's not it's not northwest it's

2:40 i don't know let's uh briefly show them for for the record so what you've probably figured out without me telling you much uh there's arrows that mean certain boxes you have to go somewhere else and look up what the box stands for and for at least for these kind of extreme cases like this very repetitive poem uh you only get to write a small number of letters explicitly and all the others can be referred to

3:17 the visual impression that you just store maybe a third of the characters is a little misleading because the arrows also need to be represented somehow if you encode it but the key idea is that's what's behind lampelsif try to reuse things you've seen before okay yeah of course uh the poem reeves peace point hot pea sports cold piece porridge in the pot nine days old some like it hot some they get cold some like it in the pot nine days old uh

3:47 let's try to put that into slightly more structured language uh what we said before is um what we looked at before is always looking at single characters and already this motivating example with from from the shining is uh showing that this is not exactly capturing all the sorts of repetitions that we find and here's some examples where we have this repetition i mentioned frequent words in english but there's also other applications if if you have html websites there's lots of of tags that appear all over the place again and these will be repetitions and there you find bigger structures that are repeated many times as well

3:50 Structure

4:36 so to capture this we need a different idea lempel siff is a whole family of such compression algorithms and as in the in the uh poem you store things by referring to things you've seen before um what you can uh store more specifically in in in lemposif for examples of welsh is either a single character or a substring of the text of the part that you've already encoded

5:10 there are many variants of roughly the same idea which essentially differ in how you find the thing you want to refer to and how you store the thing how you store these pointers back to a different box um i just listed these because i think they they cover many many key phrases you might recognize but this is not something you need to know which one exactly is it which in which program

5:36 Variant

5:38 the variant i want to discuss is lamppost welch so this uh is a third person who invented a part of it whereas lampelsif were the the founding fathers of the idea if you want uh all of these nample zif codes are variable to fixed encodings which is supposed to mean a variable length portion of the text is encoded using a fixed size code word so you will have a fixed size a fixed list of things you can refer to but the things they can refer to can be of arbitrary size in principle a practical choice is having 12 bits or something around that for these code words but that's not written in stone

6:30 what these methods do is they maintain a dictionary of of strings or phrases that you can use in encoding the next portion of the text that's why they are also sometimes called dictionary encoding i'll denote this by d because the code words have k bits you have two to the k entries in this dictionary and each entry in the dictionary they're just numbered and that's the code word okay so it's the indices in that dictionary we always fill initially the first positions in the dictionary with the single symbols from the alphabet we need that to get started and then whenever we encode one portion of the text we add something new to the dictionary

7:20 and maybe let me explain that in the picture so we store something new in this case ban is a string i found in my dictionary before so i use that and i add to my dictionary the new string where i take one more character so whenever i use a phrase i insert into my dictionary a new phrase that's one character longer and the well this is not um not not clear here yet but we'll make sure that whenever i take a phrase this is also the longest phrase i could have taken

8:01 uh the the trick here is to make this so that the decoder can also replicate the same process and so uh you have to be a bit careful in doing that but we'll we'll see how that goes

8:13 Example

8:16 let's do an example um explain the algorithm on an example [Music] and that might make it a little clearer how this works so here we use the ascii alphabet so there's a quite long table for all the letters etc as you've seen on last time and so i only show the ones that actually occur in the text but the indices are as they would be for full ascii and then there's more entries in the dictionary that are currently empty uh and they will be filled once in a while while we're going

8:51 initially so what we do is always try to find the longest next portion of the text that occurs as a phrase in our dictionary sometimes we find several strings in fact we will most of the time find a shortest string that's already in dictionary and then a longer is also in the dictionary we always take the longest match so we try to find the longest string starting from the current position that we find in the dictionary but initially we have only the single letters so we just take y its code is 89 and so that's the first code that we output but we're not done yet remember whenever we produce something we insert a new phrase into the dictionary and that is the phrase we stored plus one more character so we insert yo into the dictionary as a new string to use in the future okay next step is a single o because we haven't seen anything that starts with an o yet so we just encode the single character again o is here but we do add another string to the dictionary o plus one more character all right

10:10 uh next one we haven't seen exclamation mark so nothing happens just a single character same game we insert one more uh phrase into the string into the dictionary space is new again we can't find a longer string but we insert one for later and now the for the first time something interesting happens we we have y in the dictionary but also y o so we use this as the longest match we can find and use this new code to represent that two character string and we also add a new string to the dictionary which is one character longer taking the one more one new character from the text okay

10:53 uh you we haven't seen so nothing interesting happens the exclamation mark we've seen before and it was followed by a space before so we can reuse this two character string and we insert another three character string where we have this combination okay and now i guess you start getting the hang of it the longest next thing is u we find it here so we use that code and we make the one bigger string part of the dictionary there it goes your r we haven't seen so nothing interesting happens then space but we have seen space y before so we can use that again

11:42 one more okay oh we have seen but o y we have not seen yet so we can only use the o but an insert o y then we see another yo we haven't seen yo with an exclamation mark behind that's it and one more and then we're done

12:04 if you if you're worried about how to find this longest string that is in the dictionary a convenient way to store the dictionary or the encoding step is to store it as a try now we'll have to modify our notion of try because we essentially have not prefix free sets of strings here indeed all the longer strings by definition have a prefix that's already in the in the dictionary and so uh where we have to use an extended version of the tri where we allow um values in the internal nodes but other than that that's that's a convenient way to find the longest match because you start traversing the try in the root with the next character and you follow down as long as you can and the first character that doesn't match is the one that you have to add to the dictionary after that the note where you stop tells you what character to use so instead of this table which is convenient to show to you you want to use a try to make this efficient

13:19 Code

13:24 here's that idea spelled out in code the dictionary is stored as a try here we keep the next three code words so the next the next row the next index of the row in the dictionary

13:41 and we keep x as the previous phrase that we used because remember we have to insert that into the dictionary okay so then we iterate through the text that's this outer loop we take the next character of the text

14:01 and then we ask the dictionary have you seen whatever was the previous step plus this new character and if so then we go one step down in the try

14:16 and we continue with the for loop so we try to find the longest match as long as we can traverse an edge in the try we keep doing that when for the first time x was in the try but xc no longer is we jump into this else branch then we get the code for x without c which was a mismatch and append that to the coded text and we put xc into the dictionary because that's our new code word