Video 5-9: §5.9 Burrows-Wheeler transform

0:02 in the next section of our compression unit we'll look at the most powerful text transform that that I know of and that will'll present here that's the burough wheo transform it starts off as a really weird kind of idea and it's not even clear how to invert it um but it it turns out after studying this for many many uh years people found lots of uh helpful properties so this is really a a cool trick that is kind of a threshold innovation in that sense um it enabled a lot of progress um in this space so maybe I um I hope you appreciate it the same way or you find it as as interesting as I did uh when I first saw this um I called it here a sophisticated text transformation technique you'll be my judge the the key property is it takes the text and it just permutes the letters in a very specific way um and turns out that the outcome is more compressible in the sense that we discussed in the section on move to front specifically it has locally low empirical entropy if uh the input text has some as some structure for example English text or more General is uh come has has low higher order empirical entropy but we

1:25 didn't talk about that in detail uh one one other property that's not so great actually is that it needs the entire text up front so it it needs to work in blocks of the text or it needs the entire text up front that's why when it was first invented it was dismissed by its inventor as so impractical that he didn't even bother to write it up initially he thought this is totally beyond the capabilities of computers that was in the 80s and he said H that idea is is cute but it's so useless I'm not not even I'm not even discussing it with anyone I'm not I'm not publishing it formally and now it's a standard method that we run routinely that's also a little bit of a lesson on algorithms and theories things sometimes sound purely theoretical uh until they become very practical just by things speeding up okay but for here um you need to work in entire blocks so you need the entire Source text available that's unlike lample

2:36 sa and uh specifically the bwt the burough wheeler transform followed by the move to front transform so we take our text we put we make it low local empirical entropy move to front makes it low Global empirical entropy run length encoding because there's a specific property I'll come back to and then half man these these four things in a row crazy pipeline that's uh what's behind the be e zip program it's not so well known but it's a standard program on Unix and you can use that to compress and to convince you that it's powerful I took some vers some English version of the Bible so it's uh 4 million characters it's just as a text file just the the plain text if you do something like gzip then you get it down to a quarter of that roughly if you use seven siip maybe something uh people know as by and large often a good compressor it's it's a bit more slow it's bit slower but often gives good compression that brings it down further but bzip gets even even further and is is faster than seven sip so it's uh for English text at least it's usually the best method um by being fast and small now I wanted to add this is something um it's

3:52 a bit out of out of the competition here because nobody's seriously using this but you can go further remember the hutter price that that I mentioned at the beginning of this section of this unit uh where there's a price for compressing a chunk of Wikipedia text and you can even earn half a million um that was one of the competitors it's no longer the best uh tool but is one of those that are general purpose uh the Pak compressor it takes six minutes for this 4 megabyte text file and after thinking for a very long time it finds an indeed smaller representation so there you can do better than what I presented here the Z program but if you also want a reasonable compression time then uh there's usually nothing better but for uh for completeness I think this this belongs on the slide as well so what is the bwt I hyped it up enough I guess uh we need one definition before we can get started and that's the notion of a cyclic shift it's a very simple thing though imagine you have a a text and now you write this uh along a circle and you just close the loop so a standard string is a cyclic string plus a starting position right where you know

5:08 this is where I'm starting and then I read in that direction the cylic shift is the same same Circle but I start at a different position you can also explain it you can take a bunch of characters from the beginning and move them to the end that's the the other thing that happened and of course you can do that with any number of character it doesn't have to be at a word boundary that's just to make a more fun example that's a cyclic

5:39 shift um yeah that's that's a nice one so we'll come back to this in Unit 8 uh the uh you can make this you can make the cyclic shift unique uh uniquely you can make the text uniquely reconstructable from the cyclic from any c click shift by adding a special character end of string um we'll do that a lot in Unit 8 um for a similar reason uh slightly different reason but if you if you imagine you have a a special marker that tells you this is the end of the string then whatever cyclic shift you take you still know where the original end of the string was and you can just unshift it so we can recover uh the original text from that then and that's what the burus wheeler transform also does uh we do from now on implicitly we'll always have this end of string marker at the end of our string all of the strings in this subsection will have that and the examples will will duly show this dollar symbol by the way dollar is just some somehow that's the convention um it's supposed to be a character that comes before everything lexicographically so we we assume this is smaller in the alphabet than all the other

7:17 characters uh that happens to be the case if you put if you use asky characters but of course yeah uh only with the letters the standard letters uh theoretically it's just any letter you can pick whatever you want um that's just the convention to show it as a

7:36 dollar then what do the B wheeler trans bur wheeler transform really do it takes all the cyclic shifts of it of a string so um I'll have an example on the next slide you sort them lexicographically as

7:48 strings uh treating the dollar smaller than anything and then you take the last column of what you get so here's an example um it's this very very uh helpful but real text Al it's Alp Alpha now you get all cyclic shifts by letting this dollar symbol slide forward and of course then anything that's pushed out of the left side is uh appended at the end that's all cyclic shifts if we sort them what we get is this and you see here the dollar is the smallest then come all the spaces then a a e f and so on and whenever we have a tie everything that starts with an A here we sort by the second letter and so on right there if there's ties with the second and third letter even you keep going that's lexicographic sorting of strings um okay and the last bit is take the last column so we just read that column top to bottom and that's the burough wheeler transform so spelled out here like this um first observation that has to be a permutation of the original characters uh because here any column I pick in this in this Matrix has each position of the text exactly once because we shifted everything through by one position here so any column has each position of the

9:21 text exactly once now when I take here what I do by sorting is just reordering rows I swap two rows or put one further up that doesn't change the property that every column has each position exactly once and so in particular for the last column here it has every character of the original text exactly once but scrambled up and in particular this is what you get in this

9:52 case if you think about how to compute this and how to comput it efficiently uh it is in the end possible to do it in linear time so you're uh you can essentially produce the bwt in the same time as you need to read the text this is totally non obvious though if you go from the definition uh you may recall unit three on sorting where we discussed even this lower Bound for sorting arbitrary things by comparisons and there we said ah you need you need at least n Logan comparisons if you need n if you need elements sorted and there's n in total and here we have n different things if the text is nend long you have n different cyclic shifts how can you get down to just linear actually things are even worse because um one comparison between two strings of length n could take time n if I have two strings that have the same character I keep comparing and they always have the same character I have to continue checking if I don't do thing don't don't do anything smart I might need linear time for each comparison uh and so it could even be n^2 log n with a a standard comparison based method um but in in in in a way there's

11:13 n squ characters in this Grid in this Matrix so it feels like even to just read the entire Matrix you need n squ time so how on Earth how on Earth are you going to get this down to linear a short answer is we'll see later uh as a little precursor of why that should be even possible is that as you can see here these characters are not really random right uh this this Matrix here has a lot of structure these diagonals are all the same characters so it is only possible to speed that up that much because these are all the suffixes of one big string they're not arbitrarily chosen

11:56 strings okay but for now let's ignore how to do this in detail we'll come back to the this and spend uh a good deal of our time somewhat soon on this but now let's just assume we can compute it um and see what we can do with

12:15 this now if you look at this a bit more closely the bwt this last column so this just the same example from before uh we can observe a few things so if if um if I have occurrences like in this string there's Alf Alf an Al that occurs three times so I also have Alf here then I have another Al here so that's the shifts where this Alf is moved to the beginning when I sort those three the three will go together because they start with the same thing and so indeed they're all together in on the right and so what is in the column at the end for these three occurrences of Al well it's a cyclic shift so what comes before this moves around to the other to the end so the character that precedes the occurrences of Alf are in the last in the last column so here's a different example this character sequence LF in this string is always preceded by an a because it's always Alf uh and that means we get a a group of A's when we look at all the occurrences of uh let me maybe use a different color here so if we look at the L LF then we get Three A's at the back because that's

13:52 always what precedes LF so we get a certain grouping now remember when I said said bwt gives you a locally low entropy that's exactly that if I have all A's that's minimal entropy locally it's it's the same character repeated all

14:15 over um a bit more generally we can we can say there's contexts so there's certain substrings that occur several times and if I if I mark them here I get whatever precedes them on the right group

14:30 together uh and as a special case what we've just seen if I have a whole substring that literally occurs several times in the overall string then I get a run in B of these preceding

14:44 characters so run here in the sense of of run length encoding again run of the same character is just that character repeated uh and so uh I was I was trying to give you some statement here but then found it too much of a detour to make it formal so let's just keep it with this with this vague statement if in the text that you're given that you start with the source text it's possible to predict what comes before a certain context so you have a certain context a certain substring if that makes it easy to predict what comes before that con that substring uh then the burs wheeler transform has locally low ENT ropy by this grouping condition and so what does this predicting like look like for example in English if I tell you I have the letters uh H and E what might come before H and e or it's not it's not obvious there's different options but it's likely it could be a space because then it's he or it could be a t then it's article or it could be an S and it's the pronoun she there's a few options but there's many options they're not plausible it's probably not common to have a zed or a q i mean q is almost

16:04 always followed by U so there's a few things that you can rule out meaning that there is a certain predictability from the context okay let's make this um a bit more Concrete in a bigger example I hope it's still readable so that's the text is not a super useful text but I tried to find an example that's not tiny but also still has lots of repeated parts so that something interesting happens if you compute the bur wheer transform then that's this and if you apply the move to front rule of of the bwt that's the result okay uh and what you see is there's a lot there's a lot of zeros in the move to front transform of the bwt here essentially half of the thing is zeroed out and that obviously makes it compressible that's that's what much of the compressibility comes from um the other thing it's over well over all 24 characters in principle at least and it has spaces and soone sprinkled in so it could have large numbers like here we had a 10 and an eight but most numbers that occur are small are relatively small that again adds to the compressibility

17:30 and that's indeed a general thing it's not just in this hypothetical text if you make a larger text and compress that in one go you'll find half of the output is zeros okay uh time for you to wake up um here's the same same example I can go back to the other slide uh I wanted to be very precise and look very carefully at uh these different options

18:00 so this is one of the read me very carefully had a few more people vote earlier on the attendance code so I'll give you a bit more looks like most people are are done so let me show you um what the votes were uh there's various votes for various things right um now the the answer I had in mind was this one uh but let's go through all of those this is um is insightful I think uh to think about the others well let's stay here when we can read it better so specifically the question was about this long run of Ages in in this so what's meant is is this right so we have a lot of a lot of Ages that come in a row that means they have the context here I have to match this

21:29 up so they all have this this context uh that groups it together now H can be super frequent but still be spread out in the bwt so this first answer doesn't really uh explain that um if H is always at the beginning of a word that would mean it's preceded by a space and the space characters would be grouped together uh but there are usually other characters at the beginning of a word so it wouldn't necessarily be a a a complete run in the bwt almost all words start with an H that's getting closer but it's it's not actually uh the explanation here um because that would lead to a run of space characters so if you look here everything that starts with an age the we have 1 2 3 four five occurrences of age at the beginning of a of a uh these are the ones that are grouped together here so it would give you a run of these space characters in The bwt because the ages on the left group together so that's also not quite the the explanation H is always always followed by an a that's kind of it's getting in the right direction but it's kind of the wrong way around um because that means um when whenever you have an H there's an a

23:01 behind it uh but it doesn't mean that there's not um other things that can come before an A and those would split up uh those would split up the Run of Ages so really the main the main thing here okay the last one I'm not even it's not even a serious one um all A's are preceded by AG is what we get here because that means

23:34 uh all the A's are grouped together here and uh if they all preceded by an age the previous character which is wrapped around and at the end is always an age and so you get this long run of Ages uh that question is not necessarily what what I would want you to keep in mind about the bwt in general but I think it's insightful to be precise in a concrete example just to know know how how the properties of the transform play out um that's that's what the target of the question

24:16 was now interestingly you can also make a compression method just out of the bwt where you take the burst wheeler transform and then you compress like in this example just the the runs in the BW UT you don't even exploit the finer points of this low local low entropy you only express the extreme cases of low entropy which is a run so you can use something like the Run length uh encoding that we've discussed but with one twist you also have to say what character is the next one right the Run length encoding VI that we did was just for binary alphabets and then you know if there was a run of zeros before then it has to be a run of ones now next uh but here you have the freedom so you have to store the next character and even in this tiny example you see there's uh there's three runs longer than one and in longer texts if you take a big portion of the text and that already gets gets compressed a bit and it's it's something that was um bit of a mystery for a long time people knew this from observations in experiments uh it's a fairly recent celebrated result that put this in in proper connection so it showed that the

25:30 number of runs in the bwt uh can be upper bounded by this expression so it's it's essentially the number of number of phrases in some lample variant it's not the lample VCH that we discussed it's a it's a variant thereof it's a slightly different one but it's not so important for us uh time St something that depends on the length of the text but it's it's logarithmic in the length of the text so it's a fairly small contribution

26:02 so in a way that's [Music] um that's that's a cute property and I think it's it's always cool to see results that are very young uh but the the proof of this is beyond the scope for us