Video 7-8: §7.6 Move to front text transformation

0:00 Introduction to transforms

0:03 in the third part of the compression unit i want to talk about text transforms these are things that don't by themselves compress text but they help other compression methods and uh one of them in particular is at the core of of the modern achievements in compression and compressed data structures and text indexing so it's definitely a very nice idea to hear about

0:30 so the idea of text transformations is to help compression methods overcome limitations what we've seen so far is that certain methods can exploit certain types of redundancies for run length encoding these are long repeated runs of the same character for huffman it's some characters that are very frequently used and others uh infrequently and for elements of welsh if we have many repeated substrings not too far spread apart because of the dictionary size then levels of welch does well unfortunately methods can be very stupid whenever it goes a little bit beyond that for example lamppost if welch doesn't pick up any repetition if they're too distant if the dictionary is already flushed then we will not profit from these and this is inherent you can make the dictionary big but then your code words are longer and you you waste space on that side of things unless you do extra steps after it or you make your dictionary small and then you miss out on this long distance repetitions huffman encoding totally ignores that the frequencies can be different in different parts of the text that's particularly relevant for biological sequences it just looks at the the global average how often does each character occur in the entire text and so if you have local clusters where

1:59 some characters are more likely than others huffman is totally blind to this and run length encoding is very very picky in that it only allows exact repetitions of the very same characters and any slides

2:18 well slight disturbance completely throws it off in particular if you have a long repetition but it's alternating of two characters run length encoding would completely fail and and not achieve any compression so text transformations are invent have been invented to at least shrink these blind spots of the known compression methods as i said they don't themselves reduce the space usage at all they might even make it bigger in some cases but they make the existing redundancy they transform existing redundancy the text into a slightly different form and that's often one that can be picked up by existing methods and we'll see two examples of these

3:09 Move to front algorithm

3:11 the first example is the move to front transformation you might have seen move to front in a data structures class for uh self-adapting linear lists if you haven't uh it doesn't matter it's it's uh that's very historically the idea came from um i think uh but it doesn't really rely what we what we will do doesn't rely on on that use so what is move to front suppose you have a linked list of items and you repeatedly access items in that list then the link list is not sorted but you would like to profit from something like the same element is always accessed or some elements are much more frequently accessed than other elements and you don't know this information up up front so a simple heuristic a simple idea for exploiting this is that whenever an element is accessed in this list whenever you needed it you move it to the front of the list so a linked list right is just like this

4:29 and let's suppose here is your element x and you access x now so what you would take is uh what you would do is you take the entire list and uh leave everything unchanged except that you now uh take x out

4:54 move that to the front of the list and because it's all pointered uh you can do this without moving the other elements and you shortcut the old pointer for x so with changing two pointers you can do this the actual cost for the access is bigger than because you have to start from the beginning and walk along the list until you've found x but the cost of changing the list is really just two pointers and there's some some some theory about this move to front heuristic that i won't get into here but it's a it's a cute topic in data structures that this heuristic is enough to learn the axis probabilities of objects uh in an in an effective way in a specific sense but let's leave it wake at this point

5:52 we will use here the same idea but we abuse it for something very different we will use a move to front list for the alphabet characters and when we encode a character we find it in the list and we use as the code for this character the index in the list how how many positions did i have to walk uh back in the list and we used its old position because after it was accessed it always becomes the front of the list but we can always store zero then we can't decode we cannot invert this transformation

6:31 but we can we can store the old position in the list and then do the update so that means our code words now are integers from the same range as the alphabet is big that's um different from many of the other methods we've had it's it's not a binary alphabet but a much bigger one

6:56 and maybe if you think about this maybe we'll do an example first okay this is this is what it leads to let's uh let's see an example first and uh to get started i want you to practice the move to front rule itself so you have a move to front list as i just described it where whenever you access something you put it to the front and so this is the current content and now you access a what is the list content after this single access so this is just uh [Music] i abused the the word cloud paul but you can just type in the uh content of the of the queue of this move to front list and i would say put spaces in between the characters

7:54 okay some answers are dropping in and that seems fine to me maybe i'll give you a little bit more time so we have a few more answers and then i'll show the results

8:24 so remember move to front works as follows you you access the element in the list and then you take it out and put it in well you take it out and put it in front of the list

8:41 let's see at least 10 okay so we have a wild collection of ideas um and also of different spellings that makes it a little challenging but the fat one that was sent a couple of times is is the correct one it used to be x y z abc now we access a so that means the a is moved to the front but the rest stays the same so we have a x y z and then bc is left as it was

9:15 okay so that's that's how move to front works you uh this used to be x y z and now i used x here again i used x u instead of a but it was a bc and then after that

9:44 you would have a x y z b c another box for the c doesn't fit on the slide that's how it works now first question is uh why why should that be any good second question is can we invert it can we get the original text back uh the answer is yes in both cases let's first look at the second question um okay that doesn't work so well i want to show the the two codes just next to each other because they they do the very same thing and it's it's nice to see how they work in in sync because that makes it explicit how you can invert

10:09 Inversion and execution

10:34 the move to front transform so for encoding we start with a list of all the characters in the [Music] well not sure if this should be cs instead because uh it's the source text um well we only have one alphabet and the other the output alphabet is the numbers anyways so we take a list containing the alphabet elements in sorted order so this is important because we have to know how to start then for encoding well initially there's nothing encoded so we start with the empty string for the coded text then we walk through the characters in the source text that's the next character we find the position of c in this list so we we walk through the list and check if that is the character we find and then we store that position as the next code word and finally we move c to the front of the list and we repeat we do the same thing in the in the decoding i have to fix this here

11:51 so decoding starts building the same list the alphabet in sorted order initially the decoded text is empty we walk through all the coded symbols which are the numbers and then we find the p position in the list and return that okay and then again we do the same move to front so you see how these are these are synced up they start with the same list and they always change the same list they change the list in the same way and they extract the characters in the same way so by putting the code next to each other like this it becomes obvious that they do the very same thing so encoding goes from characters to numbers decoding goes from numbers to characters but they always make sure that these two things remain in sync by keeping the move to front list in sync

12:44 uh i have a small example for you on this um but i want to go through this fairly quickly because i think it's fairly easy here's the alphabet sorted initially in the list now you start with i you find it in the list it has position eight so the first output character is eight and now you have to move i to the front of the list so you see how

13:14 these all jump one position to the right and i jumps to the beginning right i jumps to the beginning then comes a b c d e and so on up to h

13:26 next character we want to encode is n it's found at position 13 so we output 13 as the next codeword and again move n to the front and everything between the front and n one position to the right so one more time there it moves over the next character is e so we find it at position six store the six then move e to the front gives you this list uh and so on and so forth i think the uh the concept is probably clear um so you you can go through this in detail if you feel like it's and well double check if you arrive at the same the same result now an interesting observation is what happens in this transformation with certain features in the input text for example when a the input source text has a run of same characters like here what does that correspond to in the coded text and uh what does the run in the coded text mean for the source text that's um two interesting questions to think about um

14:08 Analyzing redundancy

14:48 i think i should put these on top of each other so that this becomes more visible but the first question is really a run of characters in the source text means after the first character from the run we have that character at position zero so all remaining characters from the run will have a zero will be represented by zeros

15:19 so we find zeros in the coded text whenever there were repeated characters uh and what does a run of a certain digit in the coded text mean for example here the the threes those are these three characters they're not the same so what does that mean well it means that maybe let me do this in a different color

15:52 a different color run in c it maps to these three characters and you find three positions back the same substring occurs so uh runs in the coded text mean there was a repetition in the source text and that's a pretty neat result because we know how to exploit runs in the coded text with run length encoding and we didn't know uh well at least not with run link encoding how to handle repetitions of this kind levels if welch would have been able to pick this up if it's a short distance but that gives you a first idea why move to front might be useful

16:40 as i mentioned before move to front doesn't really compress that's why it's called a text transformation it doesn't really make the um the tech the text itself shorter but um it allows for other methods to work better and it's basically used as part of a longer pipeline in isolation it doesn't really do a lot of good um the code words that come out of the move to front transform itself have to be represented in binary somehow you could use the elias gamma code that we used in run length encoding and that makes sense because smaller numbers get shorter code words in that code and if we have local clusters of characters that will lead to small numbers after the move to front transformation so that can that can work well and the other option is of course a huffman code then you would have to do the two passes but it achieves better compression but the most striking reason why we want the move to front transformation is actually only clear after we talked about the next transformation because those two in combination are the really effective compression methods