Video 7-9: §7.9 Burrows Wheeler transform

0:00 Introduction

0:00 in [Music] in the next section of our compression chapter we look at the borough's wheeler transform and is one of these things that look really magic at first sight and unclear how they could help and then over the time people found that this is a really really key step to bringing compression to the next level and also putting it on some more principled legs all right let me show you what it is uh first of all the burst wheeler transform is just the permutation of the letters so you you're given a text and then you jump all the letters around and that becomes the transform but it's a specific way of doing that okay it's not not just randomly throwing the the letters around and it happens to be that the output text is much more compressible traditionally by putting the move to front heuristic after the bwt but there's many other ways to see why it has compressibility features

0:33 BurrowsWheeler transform

1:16 the slight downside and yeah maybe i can give this this historical anecdote as well it needs the whole text to apply this transformation you can't do it easily in a streaming fashion so in practice it's often applied to some block of data but in principle you can do it for the entire text you just need enough memory and this also meant that at the time when this was thought of when it was invented

1:45 by wheeler he thought that's a cute idea but it's completely useless because it's impractical to do he thought there's no way that we'll ever have enough main memory to make use of that compression technique so he ditched it and later when he had i think his student burroughs he explained that idea again to him that was then in the mid 90s and he said yeah let's let's implement this this this should work fine and it did at least shortly after that and it's still using the same memory in a so there were no theoretical improvements on the idea at that stage but it became practical because the machines got a little bigger and a bit faster so it used to be something that people believed is just of of curiosity of academic interest and a curios a curious algorithms a curious algorithm but then it turned into something practical and now it's at the heart of pretty much all genome-wide analysis to use something like this transform on really huge data so it's a nice illustration that sometimes things don't seem practical right now but often that's that's only a statement for a certain time and it can change as data becomes more big becomes bigger and bigger asymptopia comes closer to us in this

3:10 sense okay but back to the more concrete topic the bwt is is became famous for being part of this this bzip program if you have a unix system where you use the departmental ones it will usually be installed it's just bzip as a program b zip two i it's not as well known as i think it should be if you take the ascii text of the bible by the way it's uh four million characters is pretty much the text of the bible in english and you can compress this with um well gzip is some some implementation of the zip algorithm gets down to a quarter of that 7zip this may be more well known

3:58 well hack combining many many different heuristics gets it further down but bzip is even better than that and that's typical for for natural language text it is slower than gzip by many quarters of magnitude i think but still fast enough to do on on large inputs so what is the bwt now um

4:18 Burst Wheeler transform

4:26 that's two t's the bwt transform is the burst wheeler transform transform it is based on the notion of of cyclic shifts if you have a text then imagine you write it on a circle then there's a certain point where the text begins and ends and a cyclic shift is you just put this divider somewhere else and i tried really hard to find a string where you can do a cyclic shift and it still is a correct english sentence

4:58 even though maybe not a great one so that's that's a circlic shape right every position where you could potentially put this this separation between start and end gives you a difference so click shift now in general um you could have a string where there are not as many cyclic shifts that are different as there are positions just because two of them are the same to avoid that situation as we've done many times before we always throw this end of word marker at the end of the string pretending that dollar is some symbol that doesn't occur anywhere else that means we can always recover the original string from the cyclic shift we just have to look for the dollar and put the the cut right after that so far so easy the burst wheeler transform now does does three things and this is so this is the conceptual view i will present you how you should think about this this is this is not the way you want to implement it because that would be awfully slow but let's first understand what it is you write down all the cyclic shifts of your text one after the one below the other that gives you a matrix of characters i'll have an example on the next slide

6:12 uh then you sort these strings lexicographically so you sort all the cyclic shifts lexicographically and then the last column is the bwt so again on an example we have this text elf eats alfalfa again as a brilliant example because has lots of repetition and in case you haven't heard this before alfalfa is some sort of grain i mean it's a real thing to eat um whether elf would like it so you write down all the circlic shifts and you can see how the dollar sign makes its journey all to the way to the front that's that's how you can easily see that you got everything but this is this is just all the cyclic shifts what we want to do next is sort them lexicographically so that gives you that list okay and as before we'll treat the dollar symbol to be smaller than all the other characters then space this is like in ascii spaces before the letters then come the a's e's f's l's and so on and where there's a tie you go to the next character you know what lexicographic means i guess so this is this is a well-defined step and now the bwt is take the last column and read these letters top to bottom so from elf eats alfalfa what you get is

6:27 Example

7:38 is this permutation of the letters and you may note or you may count that there's one dollar here one dollar here there's a whole bunch of a's over there and they occur as well down there it's the same number they just get shuffled around already on this tiny example you can see there are things going on with runs there's three l's and three a's in a row and that's not not coincidental

8:10 it's one feature of the bwt that you tend to see repeated runs of one character the same character repeated several times before we dive deeper let's think about whether you've seen something similar before

8:21 Question

8:35 and that's this question maybe superficially you recognize we put end of word markers and there's some sorting going on so that should ring a big bell about suffix arrays but the precise statement is a little tricky so have a quick think about this

9:38 okay we had 30 people voting before so i'll probably have to leave this open a bit okay 25 let me show it for now and so here's here's your answers and

10:20 the uh the right one is is really b um there's some truth in saying both a and b but that needs some extra tricks at least so that's why i put this

10:37 easily here i think if you say very easily for the first part then it's justifiable to say that's wrong let me show you though what is doable namely the other the other direction how could we compute the bwt so what we don't want to do is write down all these as literal strings and then sort them that would be at least quadratic just to write down all these characters contradicting in the length of the text and that's where we already walk away and say no come on that's not good enough for us but we can do better we note we may note that these cyclic shifts are essentially the suffixes of the string i grade out the characters after the dollar sign here which is just visible maybe and if you think about it if you compare two of these of these cyclic shifts in a lexicographic way you will never compare beyond the dollar symbol because they're cyclic shifts so the dollar symbol is at a different position in each of the lines and as soon as you compare the dollar you will have resolved all ties even if the rest of the text is the same character repeated you never compare beyond the dollar symbol so you will never need these grey characters to decide any

10:45 Solution

11:59 ordering questions so in a sense i could have just removed the grey characters and i would get the same sorted order on the on the right that's the first observation so we could get with the suffix array we could get where do i have to start with my cyclic shift so the 16 here means i start at position 16 the last character in the text and then read from there and so on and so forth and now how do i get this last column that's why it's convenient in the bwt to add the the entire matrix of characters so we can just say take the last column but it's a cyclic shift right so if i go forward to the right i go left and wrap around if i go to the previous character previous character compared to the first one so if i know that the cyclic shift starts at 16 what's in the last column is 16 and whatever comes before that so 15. and the 15th character in the text is an a so you can always do this and that's what's what's written here the ith character in the bwt is if you take the suffix array and for position i subtract one because we want to go one character before

13:24 and then take the position at the text you have to take care of the wrap around yeah if you have the zero then you have this extra special case but the rest is regular okay so this is this is in a sense you can very easily compute the bwt if you if you are given the suffix array now you've already learned how to compute the suffix array though that direction is fine so we can compute the bwt in linear time okay so it's a good transform it's it's relatively quick to compute it even though more tricky than move to front to be fair now why is this transformation any good

14:11 because we sort what happens is that in the sorted order same things are grouped for example you have here a lot of a's in this text in the first column they have to be all together because it's sorted by these strings so all the characters all the uh first column is is just the characters in sorted order

14:41 and then uh what is going on in the last column means that this a is what comes before this uh sorry what comes after this f so you have a context a that is fixed and then you look at in the bwt what are the characters that come before this a well more generally you can have several characters like lf appears three times

15:13 if you look in the text lf and the character before this lf is always a and that's why you get three a's in the bwt right here all these a's are followed by lf and the lfs mean they're grouped together

15:38 so in a in a sense what the bwt achieves is it groups characters by their context what follows them in the text and if there's a character followed by the same things then it will appear as a cluster

15:54 and these local clusters of some characters being much more likely than others this is what then uh is picked up by the move to front heuristic that will mean that the move to front output has mostly small numbers in a big sense and the other way around if you have um a repeated substring in s some exact repetition of of a string that inevitably means there's repeated runs in the bwt that's the example of lf for example the repeated string is alf and if you take the the first one off lf is grouped together by the sorting and so all these a's are lumped together okay

16:41 somewhat magic but that's that's the the essential property this part is is what what really makes the output of the bwt more compressible to show this in action here's a bigger example so this is this bigger text and here's its bwt you should see the the matrices up here um and then i also applied the the move to front um

16:57 In action

17:16 to this one and uh i think we'll discuss this at the end all right let's do it um there's another slightly tricky question i do want to show you how to decode this so maybe let's just do this a quick let's do this quickly

17:52 the runs of h is so this is long run of h here which of course in the move to front then gets to a run of zeros what can we say where does this run come from

18:18 Results

19:00 okay in the interest of time let me show you the results that you gave um there's several statements on in the list of options that make some sense the very concrete thing that we can say for this run here is if you look in the first column there's all these a's

19:24 now these happen to be all a's in the text okay in the first column they are all together and these are all the a's which correspond to all ages in the last column so what does that mean it means all a's are preceded by an age in this text so whenever i see an a in the text the character before it was an h that's why we get this long run of edges in this concrete text that's the more the most precise statement we can make it's also a little bit of an anomalous text because it has this the strong property that uh every a is preceded by an h if you have something slightly slightly weaker then you might not get one uninterrupted run of age but you might get a long run of the same character maybe with a few other characters sprinkled in

20:29 the first one doesn't really explain the run in the last column this one is the opposite it's the context in the other direction so what the bwt gives us is the things that come before h it's a little unintuitive maybe so these two things go look in the in the wrong direction

20:53 and h is always followed by a is is similar but again the the real statement here is is this this other one