Video 7-8: §7.8 Move-to-front transform

0:00 Intro

0:03 i have a third part in the compression uh chapter for you which is about text transforms and these are a bit a bit weird at first because they're not compression methods by themselves but they somehow make text more compressible without compressing themselves so they just bring things that compression methods cannot use right away to the surface so that they can be used and we'll see some some two examples of this that nicely highlight this it's just um yeah a curiosity that the compression methods cannot do this right away but there's effective ways around that

0:46 if we if we look again at the three big compression methods we looked at so far that was run length encoding huffman coding and lamppost if welsh uh then you see they they have some some things that they like and that what they're where they are really effective one length encoding as the name says if you have long runs repetitions of the same character uh huffman is good if there are some characters that are much more frequent than others or vice versa if there's some characters that are much less frequent than others and labels of welsh is good for picking up exact repetitions right so that's that's the the positive things uh there's many things where it is frustratingly ineffective to use the compression methods we've just seen uh as they are even though as a human if you look at it you see like you see there is something going on in terms of repetition that you would like to uh to capture a simple example for lambos if welsh is uh what i mentioned before if you have an exact copy from very far ago then you might not find it just because the dictionary is just not big enough and keeping the dictionary growing has downsides too because the solution is not just to keep the

2:02 dictionary growing uh we might want a fundamentally different way to approach these long distance repetitions huffman coding the way we did it suppose the first half of the text is all a's and the second half of the text is all b's huffman would still say use one bit per character and then the compressed text would essentially look the same as the source text whereas obviously something like run link encoding would work well in this case if you have something slightly less artificial in the first half of the text a's are much more frequent than b's but it's still not quite all a's and the second half the other way round b is a much more frequent it still feels like you want to compress this better than what huffman would do by averaging all the frequencies and not compressing at all but it's not completely obvious how to do this and well run length encoding of course in the way we presented it is so limited that there's many ways you can imagine to trick it into not finding some repetitions

3:05 Text transformations

3:10 so text transformations try to bring out these features so that they are compressible with the other methods to exploit such types of of repetitions so they're they're called transformations because they take the source text and produce some coded text and they have to be invertible but by themselves they don't achieve compression and so they're usually used as part of a bigger pipeline you first feed your source text through some transforms and then through some compression and for the decoding it's the opposite and you always have to go back the same way as you came in in encoding

4:06 the first example of a transformation is called the move to front transformation is um in principle a fairly simple transformation and it might not seem very useful at first sight but it's historically the one that combined with the second one gives you the the most the most effective compression for english language text and some other types of inputs

4:30 Movetofront transform

4:33 so let's have a look at this [Music] who has seen the move to front heuristic for self-adjusting linear lists it's a topic that sometimes appears in some data structure classes um often to introduce uh competitive analysis and online algorithms but it's maybe not so standard to cover it even even in cs undergrads so has anyone seen it okay it's only vaguely related to that so we don't really have to get into that the idea is you keep a linked list of some objects and it's not sorted this list um and so let's do a small example maybe okay i have space down here

5:33 i'll just do this with letters and and say this is null so it's just three elements in my list now when i want to access an element i traverse from the start so here's that's the start that's why i always begin my search i go through the list until i have found the element and after that i make that element the first element in the list so if we access zed we go through the list until we find set and then we take it out of the list remember in a linked list you can take elements out by just rewiring pointers so this is it's a cheap operation to put um well i can again if you want i can keep this in the same layout and then it's closer to what the algorithm would do

6:31 so you make the start point to zed then that points to the old beginning of the list and y now points to no so i've i've just taken said and put it at the front of the list not changing the relative order of anything else okay that's that's what's spelled out in in in the text here and you keep doing like this when i uh do the next axis maybe that's to set again then i find it at the first position and if i then access uh access say x then i would swap x in nz so the idea in this is over time if you keep accessing elements like this those that are have been accessed frequently or those that have been accessed lately they end up in the in the beginning of the list and so you get cheap access to them because the time to traverse the list of course is the same as the number of elements you you visit so uh if you've seen something just before then it's at the front and if not then it's a little further in the list but they're roughly ordered by the least accident the last access to them so it's a way to somehow learn access patterns without explicitly doing anything it's just

7:48 following this this heuristic uh that's that's the move to front heuristic because of the obvious property if you access something you put it at the front good we'll just use this and apply it on the alphabet characters of our text and basically see what happens

8:10 Alphabetic order

8:13 so here our list contains all the symbols in the alphabet you have to initially sort them somehow so we'll start with alphabetic order initially to access to encode a character of the source text now we access that element in the list and to encode it we write down its position in the list so the number of elements we had to follow and after that we apply the move to front heuristic so what this means is if you access a character more often it will get smaller numbers right

8:48 the code words here are just integers it's one of the examples where we don't go to binary right away but remember move the front by itself doesn't really compress well so this is the first step in the pipeline anyways um and so let's let's see an example where we can point out this property yeah before that i wanted to see if you understood the rule

9:18 so pretend you have x xyz abc in your list initially and then you access a what does the list look like after that okay looks good um give you a second to vote but seems that one was was doable

10:21 and well you can still cast your vote but uh let me let me continue because it seems uh easy enough so if we access a we have to move from the front till we find a and then we just take it out and put it at the beginning so

10:47 just with a removed from that list okay oh you don't see it you did see it all good then did i make any silly mistakes uh looks okay to me good so that's the rule um and this time because it's simple enough here's the code first we'll do a tiny example afterwards very well zip through quickly on that one um in coding you start with the list containing the letters in alphabetic order start with the empty the empty string for the coded text and then you go through each of the letters you find it

11:05 Code

11:33 oh sorry that's the you find the next character in the text then you find the position of that character in the move to front list that's um the position p that is your code word and then you move c to the front of the list i didn't spell out the code for that but i guess you could imagine how to do that i wanted to point out in this case how very parallel the encoding and decoding is so the decoding does the same it starts with the list in sorted order it starts with empty source text that's what it produces but then it iterates through all the positions in the coded text and now instead of finding a character it finds the position so it jumps to position p in the move to front list and gets the character from there and then outputs that and then does the same move to front step okay of course it's important that they do this nicely in lockstep otherwise we wouldn't decode to the same thing that we started with

12:32 and so i want to run through a quick example not to show the procedure again but to show you an example what happens if you do this transformation so relatively quickly we find i in the list that's so we start with the whole alphabet in sorted order we find i it's at position eight so that's what we put out and then we have to move i to the beginning and move the rest best over so you see i is at the beginning then there's a b c d here and between h and j where i was before this is gone okay next character n we find at position 13. so that's our output and n has to move to the beginning and then that's what you're left with so n is here i is here and then all the others uh between m and o n is missing next character is an e so we find this at position six that's our output and then e goes to the front and so on and so forth i think uh it's kind of clear how this works so let me jump through this more quickly now um okay here's here's the final result and let's spend a second to um to ponder over what happens during this

13:46 encoding what happens with this transformation uh instead of letters we have numbers now that's obvious what is a if we have a run of the same character in the source text for example here ff what does that translate to in the coded text now uh yeah it would have been nice to properly align these two things

14:25 as you can see um the second f becomes a zero and of course it has to because after f has been accessed it's at the beginning of the move to front list and so next time it's used it's at position 0. so runs of the same symbol the same symbol repeated several times in the source gives you a run of zeros in the coded text except for the first occurrence

15:00 and now the other way around uh what if we have something funny like these um repeated characters in the coded text the three threes uh what could that mean the well it's the characters here

15:20 and maybe you can visually spot that there's another occurrence of this string and if you check this is exactly three characters ago of four if you we start counting at zero okay so

15:37 so if you go back by index um there's there's three things in between and so that's that's another general thing you get these these runs in the output if you had a repeated string in the input that feels like something useful for compression and that was something a bit like lampposif where we tried to do things as well it's a little more limited if between the two occurrences there are other occurrences of the same letters the nice run gets a bit destroyed then you get numbers that are smaller than the three in between if there was between the c i e c i if there was another e then we wouldn't get a three here but it at least gives you some hint some intuition what what might be going on there

16:45 okay as i said as before it doesn't compress by itself but because of these two properties it sometimes can bring out compressibility that's otherwise hidden if you wanted to encode the code words you have to think about that but you usually put some other things after it the the key application of move to front at least historically comes from after another transform and that's the one i want to look at next um

17:18 and yeah different options how to encode the code words i don't want to get too much into the details of that