Video 5-9: §5.8 Move-to-front transform

0:03 in the last part of the compression unit we'll look at text Transformations or text transforms which are methods that don't by themselves uh by themselves reduce the compressed size of the text but they help other methods pick up redundancies that were there from the beginning but they couldn't see them sounds a bit curious maybe um so uh to to motivate where this comes from um if we if we recap what we've seen so far we've seen run length encoding which can pick up runs long repeated uh occurrences of the same uh character we had Huffman to pick up uh unun non-uniform frequencies and L LEL

0:45 for somewhat locally repeated substrings uh but all of them can be frustratingly blinded to some obvious redundancies for example if the repetitions are too distant lampol belch doesn't pick pick them up because the dictionary is already flushed if overall the probabilities for each of the the frequencies of characters are evenly distributed but they're um more likely to be a certain character in one part and more likely to be another one in another part it averages out and Huffman doesn't profit from it whereas it might be profited from with a more clever regime and um this is not a hypothetical thing this is what DNA sequences often do uh there's regions where some fre some nucleotides are much more frequent or much more likely than in than others and then in other regions it's different and so overall you can't compress a DNA sequence with Huffman much but locally you sometimes can uh but hufman doesn't see that and similarly for run length encoding I mean it's it's very very greedy about the the runs uh if you have something that's slightly different but still very repetitive it doesn't see it at all so what can we do well the hero of the day for for this one are these text Transformations these are functions that

2:10 um take text and produce text and you can invert them they don't by themselves reduce space but they um somehow make the the redundancies more digestible and we'll see one concrete example now in the form of the move to front transformation

2:34 the idea of move to front comes from something entirely different um namely from the idea if you have if you want to use a singly linked list for storing a dictionary so you have objects and you store them these uh as a linked list like this right uh if you want to access one of them then you have to Traverse so you have a pointer for the first thing you have to Traverse through the list until you find the one that you were looking for now that's overall not a great dictionary implementation linear time for most elements to find them but if you happen to find one of the early ones if you're if you're trying to find one of the early ones it's very fast so in some cases when you're um when your accesses are very clustered you can maybe hope that the thing you accessed before is is close to the beginning uh and move to front is the idea of of making it so so if if you have some some entries here and you say okay I have an access to a I have to follow through this but then after I access a I'll make I'll move this to the front so I'll I'll take the pointer here point to here and move the overhaul

3:58 tail to a so if I several if I if I access a straight away again it's at the front if I access it without many other things in between it will still be close to the front so that's why it's called a self- adjusting link list because it it's automatically learns a bit which things are accessed more often so the the rule here again um was very simple whenever you access something you take that out of the list and make it the new front of the list you move it to the front MTF and you can do this in link lists by just bending pointers around don't think of this as an array that's where this comes from now this has nothing to do with compression right what we'll use here is such a self- adjusting link list for the alphabet okay so each um each character we can treat as an access to the this list of all the characters and then we encode the character with its index with its offset in this list how far did you have to travel down the list um and we keep keep the rule as before

5:41 all right everyone relieved that it still works could have been able to tell after 10 seconds but well um we still keep the move to front rule so when we access a character we move it to the front of the list so the the numbers that we associate with characters keep changing all the time uh the only thing that we have to make sure is that the decoder does the same then that's fine so in this case um unlike what we had before the source alphabet is arbitrary but the coded alphabet now is is integers and again think of this as an intermediate stage you have to do some some encoding after that anyways so it doesn't have to go to Binary straight

6:29 away H we we'll come back to to what properties that has um after the example but first I want to make sure that the move to front rule is clear so here's a a small innocent question if you you have that as the entry of the list let me let me draw it um then you do an access to a what what does the list like look like

6:59 afterwards and you should imagine AIS axis at the uh most people seem to be uh certain and so uh let's not delay it for what than necessary um how does it work we go through the list until we find our a and we rip it out so we take take a

8:11 copy we take out our a put it to the front and just close the list again here so we get a XYZ BC okay good that was easy enough I hope uh because it's so easy let's start with the code um just because it shows how encoding and decoding is very very similar in this case in both cases we start with our move to front list of all the alphabet symbols and by convention we start in alphabetic order we have to have some convention um in the encoding step we have the source text given and we produce the coded text so we go through all the letters in the source text we find um find the next character we find the position of that character in our move to front list and that position is added to the coded text and then uh we do the move to front transformation on L and for decoding we do the exact same except now we're given the coded text and we produce the source text we find the next position in the list by taking the code word then we get the character at that position and append that to the source text and apply a move to front so um quick example not so much because I think you're you needed to

9:33 understand this but because it illustrates the properties nicely okay um so here's our alphabet and here's the source text now how does encoding work we find the position where the letter is that's eight so that's our coded thing and now we apply move to front right so we take this one and put it to the front and if we do that um see I is now here these have all shifted over the next letter is at at that position so it it's encoded by 13 and then we take it move it all the way to the front so all of these will move one position right and N goes to the front n is here and these have all moved the next letter again uh we find where it is store it by that number and do move to front I I I'll Zoom through the rest um I think it it's hopefully clear

10:34 okay um so what what you what you get at the end is a sequence of numbers and on this example um I'd like to have a closer look at what what the properties of this sequence of numbers could be uh first of all if we have a run of characters in s what happens with that so we have a a very short run here two Fs in a row well after the first f f is at the beginning of the list so the second F will be a zero obvious right and if I had more FS FS then there would be more zeros so we get zeros after the

11:27 first um now sometimes you also get these these things like in the in the coded text all these threes what does that mean well if you look where it comes from it meant that c at this point was at position three in the move to front list and then this was at position three and then this was at position three so it means that there's another occurrence of this string somewhere earlier and there's um there's some letter letters in between that mean things are are uh shifted over but other than that um each of these letters just shifts the list and we keep a constant offset as how far we look back so there's there's somehow um a repetition in s that leads to something like a very uh monotone sequence in in the coded text so these are at least hints that something becomes more compressible in this in this uh via this process

12:34 okay so if you look at it U move to front itself doesn't really uh compress the text um depending on how we store things but if you use some some fixed code again we would have to specify how we uh encode the code words here um what happens intuitively and I hope the two examples in the the questions from the example hint to that is if you have something with low empirical entropy locally so

13:04 there's a a region in the text in the source text where you have only some characters occurring but these characters can change over the different portions of the text then move to front transforms that to a globally low empirical entropy remember empirical entropy was this we take the frequencies of letters and take the entropy of that we covered that yesterday B and that means low low entropy means half man works well and so move to front uh is somehow able to take changing but low entropy uh Parts in the text and transform them in globally low entropy on those numbers and so via that vehicle it makes makes Huffman more effective um if we want to store uh the the numbers we can also to use use gamma code but uh um halfman will usually be better the there's a tendency in the move to front output to have small numbers if if that is the

14:19 case now uh the property that Mt have MTF has is great but it turns out that at least English text doesn't actually have these locally low empirical entropies I mentioned DNA data sometimes has so that there it works directly to some degree um but many many types of texts don't have this um but it turns out we have another transform coming up that helps there but we'll have to delay that and um the way it works in the end will be another transformation the bir wheer transform creates such low local entropy MTF transforms that into low Global entropy and then we can apply half Mana the