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

0:00 <Untitled Chapter 1>

0:03 I have a third party of the compression units where the methods technically are not compression methods but they are useful in compression by in a way transforming the data into a more convenient form uh we'll see basically two of these and both turn out to be effective in their own quirky way I'll comment more on that later so to sum up the table from before we've seen ways to exploit redundancy in various in various methods if you have a character repeated many times run length encoding captures that if you have frequencies of the characters that are vastly different some characters much more frequent than others than half man's your your guy to capture that redundancy and if you have particularly long local repetitions something like a well okay don't want to go too deep too deep into any specific cases but uh some some text that keeps repeating like the The Shining uh text would be one is always the same sentence so it's it's never far to reach back to the last repetition then lempel Siff methods work very well if you apply these to all sorts of data that you that arises in application is sometimes super frustrating to see how blind they are to obvious redundancy but obvious to you as a human

0:19 Text transformations

1:34 some examples if the repetitions are too far away limposif has flushed the dictionary and forgotten everything so then it wouldn't work if you have say a text with lots of A's in the beginning lots of C's at the end then overall A's and C's may be equally likely you have the same frequency and Huffman wouldn't be able to exploit that but in the first half you should have really used the short code for a in the second half a short code for C Half Men can't really do that so it would be nice uh to have that more locally but it seems to get complicated to figure out a good way to do that and of course run length encoding is is so restricted that there's many ways how to make it not work by just breaking breaking runs and still if you have some pairs alternating it feels like it should be a run but uh it doesn't work with run length encoding as we defined it and that's where text Transformations can sometimes help they at least broaden the uh the range of texts or the range of uh data sets that compression methods can find redundancies in the they're similar to our compression methods and that they have a source code and a coded Source text and a coded text

3:01 and you can go back and forth you don't lose anything but the goal for them is to not directly reduce space usage that's why they're not called a compression method they're just there to make to set the stage for one of the previous methods to pick up the redundancy that's there and so they're used as part of a pipeline I think this becomes much clearer with a concrete example so let's see our first one

3:32 the first text transformation is called the move to front transformation and it comes from something that some of you may have seen it's often so this is like a little digression forget compression for a minute um this is a lovely little data structure problem sometimes used to introduce competitive analysis and online algorithms and things like things like that if you've never heard any of these don't worry uh you don't need that here it's just for context and make the connection if you have seen it um the the goal there is is to have a self-adjusting linked list it's just a linked list as you have seen it in our our implementations for stacks and it's unordered so if you search for something you have to start reading from the beginning and walk your way through the list now the question is what order should you keep the elements in in principle because it's unordered and the order is fine but here the the goal is to make use of the fact that maybe some elements are needed needed more often than others or maybe uh if an element was used now maybe it's needed soon again things like that and so as a very simplistic model you can say let's pretend we have to keep it

3:37 Move to Front

5:00 in a linked list but when you access an element you've walked through that list anyways so you may may as well restructure it while you're going and in general you can you can pay more and go further and restructure more that's their game in and the self-adjusting linked list world now if that sounds interesting I'm happy to give you pointers where to read more all we need for here is the following strategy that turns out to be a relatively good strategy for this for this problem it's very simple that's what it's written here whenever you access an element you walk through the list until you find it and then you rip it out there and put it at the beginning of the list

5:49 and uh intuitively it's something like a recently released recently used ordering right there the item you've just touched becomes the first the next item is the one that you used before that and so on so over over the over time you ordered the list in this order of least recently used

6:13 most recently used I think least recently used is the cash eviction strategy you sort the items by when you use them last very at the front Okay I think you get the problem um and so over time the list some somewhat automatically learns which elements are used more often uh what does all of that have to do with um with compression so let's come back to text the idea that people had was let's apply that to our source alphabet so we throw our source alphabet in a linked list and we apply this move to front rule whenever we encode when we find a single letter we find it in the list we represented by the index in the list that it had but then we move it to the front that's pretty much what it does um so that's that's just saying uh what I described you you find a new letter in your in your string in your Source text you search it in the list starting from the beginning and use the position as the code word then you move that element to the front and keep going so the code words now are integers you transform it from some arbitrary alphabet to the integer 0 up to Sigma minus one

7:44 um let's see maybe let's do that first so just to see if the if the idea is clear enough again this is not a question that's supposed to be tricky

7:51 Clicker Question

8:05 just making sure that my hand wavy explanation without a concrete example was enough for you so the way to read this um here's the front you have these letters in the list so there's I don't know shall we draw these lovely diagrams there's X and then pointer to the next element y pointer to the next element C and so on

8:39 all right now we access a what does The List look like when we're done the spelling how exactly you format things that screws up the display a bit but uh another thing most people got it

10:58 wait till 25 is anyone's still working in here looks like not not many all right 25. oh let's see there's a Big Blob for a x y c b c and the usual um and that's also that's the correct answer so what what you can do nicely here let's Okay copy let's see if that works this time he does

11:54 so we have that list before and then after what we do is we Traverse we walk through the list until we find the letter we want that's a then we rip it out of this here put it in the front rewire this so that c still points to somewhere and then if we read the list it's a x y z b C and that's what um what the majority has voted for

12:27 okay so that's how move to front works um this time I'll start with the code here because I wanted to show how very very similar encoding and decoding in this case is we always start with the move to front list initialized with some order and well without any other options just put the alphabet in sorted order then we start in the encoding the code word starts empty that's this Epsilon here then we walk through each character in The Source text that's our character C then we find the position in our Linked In Our linked list in the move to front list so we walk from the front until we find it that gives us a position P that's the index zero based that's what we store and then we do the move to front step or decoding almost the same we produce the source text of course not the coded text we read one character from the coded text and that's our position p and we get the character by moving to position p and l so in one one you walk through the list and check what character you have and the other you count down the index until you find position p but in both cases we do the same move to front step

13:54 all right okay I wanted to align this that didn't work okay let's let's see the example so the first letter we encode is I we find that in the list it's at position eight at this point so that's our output now before we move to the next letter we rip it out here put it in front that looks like this I is now here everything else shifted one position to the right next letter N we walk through the list find it at position 13 so that's the output and then we put n in front of everything there we are that's our n and everything else is shifted one position to the right we do that again e we find it at position six that's our output and we move e to the front all right you see how this goes um I think I can speed up the example it's the same thing happening over and over

13:58 MTF - Example

15:07 now uh I want to point out two things that might give you an intuition why this transformation is any any good if we have if you look at these two F's here so now I wish I would have properly put this one off below the other

15:30 but you may just make out what happens if I have twice the same character in The Source text or in general a run that translates into zeros in the coded text because I'm I'm putting it at the front and then using it right away again

15:48 uh and then there's other things like this weird pattern three C's what would that correspond to in the source text well it's the the letters before this that's this if you look at these cie not so clear anything special about those if you look closer aha it occurs earlier again so a run like this occurs when there's um a close repetition without reusing letters in between but you can see there's there's some tendency if the if the text has elements of boringness then that can translate to zeros if it's a strict repetition and a repetition of this kite might lead to runs of the same number that's all I want to want you to take from this for now

16:39 MTF - Discussion

16:43 so by itself doesn't help much you have an alphabet of size Sigma before an alphabet of size Sigma afterwards um but it turns out to turn things that we'll see after the next transformation into things that are easier to compress uh

17:09 two comments about the output of this transformation are integers so you still want to convert those to Binary if you use it in compression and of course again you have different options how to do that the Elias code that we've seen in run length encoding has the nice feature that small numbers are represented with fewer bits but of course a half man code would always always get you the best answer globally if you average out

17:46 uh one other thing I would like you to think about is some this this deficiency of Huffman I don't have this on the slide unfortunately but if you think about this text where I said oh it's very frustrating that Huffman codes don't seem to recognize that there's something to compress here a bunch of A's and a bunch of C's if you feed that through the move to front rule you'll get some arbitrary letter but then zeros and then you get some arbitrary number and then zeros again now this is this is degenerate of course with all the zeros so you you don't usually have that but I want to point out that you have zeros and zeros it didn't matter what the repetition is so in a way move to front manages to get uh different frequencies of characters down to the same numbers here we had lots of A's here we had lots of C's yet after we moved to front they both correspond to lots of zeros that's at least one step in the direction that might make a Huffman code after this more effective