Video 7-5: The Burrows-Wheeler transform

0:02 Before we can get to the self indexes, we have to take a little detour uh introduce this cool uh trick or transformation on text um the Burwa transform that that the the coolest of these self-indexes are built on. Um for a moment it will look like it has nothing to do with text indexing. Um but again like for RMQ bear with me for a little bit it'll come back. Um, for everything we've done so far, we need the text and essentially in fast memory to do random access on the characters and that can be a problem for a single genome these days is a bit questionable if I don't know 4 gigabytes of main memory is not a big deal. Um, if you think for the next thing uh the NHS the uh national health service in UK has recently collected um I think they've done a 100,000 genomes. So multiply your 4 GB with 100,000 and you do get into trouble for main memory unless you're maybe the beefiest of beefy machines, very expensive can still hold that in in one place, but it's getting very questionable. So you want to compress and then that means you can't explicitly store the text anymore.

1:18 That's my point. Um, take it for that. And so we can't use the enhanced suffix array as is. That seems inevitable as long as we uh want to reconstruct the text except we can compress, right? Okay. Um maybe this is useful to keep for terminology. Um uh people call this the encoding model. We want to answer queries about some some piece of data. Uh but we're allowed to we have to keep essentially um the data around to be able to answer these queries because the queries themselves allow you to reconstruct the data itself. But we don't need to keep the data in the original form. We're allowed to encode it in some new way. That's what this uh self-index is also going to do. Okay. General like a end of advertisement. But the the the research field um that talks about these things is computing over compressed data in a more general sense where data could be other things than text.

2:32 In the interest of time, let me move on to the definitions. Um the first thing we need is a cyclic shift of a text. So here's a text. Here's a cyclic shift where all that has happened is take a bunch of characters and move them at the end to the end of the string. And you can do this with any number of characters. In general, uh, as this example maybe shows, you can uh not necessarily reconstruct where you came from unless you know by how many characters you shifted. But standard trick that we've applied in all of the previous uh chapters was append an a unique character the end of word character and then of course you can recover from any cyclic string what the original string was because you keep shifting until this thing is at the end. That's the setup. Now the burrows wheeler transform this mysterious text transformation works as follows. in a text with this end of word marker, you built all the cyclic shifts. There's all going to be exactly n plus one of them.

3:33 If the character had if the text had n characters plus the new one, then we sort those lexographically. And then comes the weird and crazy stuff. Take the last column, the last character of all the cyclic shifts. And you read that top top to bottom in sorted order. That's the BWT.

3:56 example. Here's some uh obscure text. Uh here are all the cyclic shifts. You see that the dollar sign walks all the way to the left. And then you sort these alphabetically which gives you this. I'm here again assuming dollar comes before all the other characters and the rest is just the ASKI order. And the last column in this arrangement is the BWT. So you turn this text into this.

4:29 Uh why on earth that should be useful will come to soon. Um a quick observation because you've wrote down every cyclic shift exactly once. You've written down every shift exactly once. every character um in the text occurs in every column exactly once. For example, the first a occurs in the first column here at the top because that's where the first uh guy was. Uh in the second column, it appears exactly down here and so on and so forth. And that's true after sorting because you're just swapping color rows around.

5:09 In particular, also the last column consists of one copy from every index in the text. In other words, the BWT is a permutation of the characters of the input text. It's going to be the same number of the same characters, but in a weird jumbled order. That's just from the construction.

5:36 Um let's talk about how we can find this because uh it involves sorting and uh we've talked about sorting strings already a good deal. Indeed, it is nothing but suffix sorting if you look at it from the right perspective. And the reason is that these dollar symbols mean never ever are you going to look in a comparison at the characters after them because the dollar symbol is unique. It occurs exactly once in each column. So whenever the comparison supposedly reaches the dollar symbol, you're not going to look after because that one decides the comparisons for sure. So between any two strings, if you compare them at the very last with the first of the dollars, you know which is smaller, which is bigger. The dollar decides that was not a political statement of currencies. Uh so that means if you sort the suffixes then um that there's these cyclic shifts there is just a kind of management you're draw dragging some baggage around but they don't influence the sort order.

6:41 In particular you can reconstruct the bur wheeler transform just from the suffix array. If you have the suffix array L, then the I character in the Burita transform is obtained by taking whatever the E suffix is, but then the previous character because uh again this is wrap around right a cyclic shift. Uh you obtain where this character this this character here is the one that comes before the character here.

7:12 Uh that's exactly the example where the wraparound is needed is modulo n. So minus one uh needs to be modulo n plus one. If you have the suffix array, you can construct the bur wheeler transform from it easily.

7:32 And we know how to compute the suffix array in linear time. So at least in principle um if we're okay with in having this intermediate suffix array then we can compute the bur wheel transform efficiently. So that's that part that part's done. Uh again if you were to use this in practice there's good libraries that do this uh directly also avoiding the extra me uh working memory. Uh these are interesting methods but let's not get into this here. a tiny detour just motivating why the BWT is at least historically coming from text compression and not data structures. It turns out that for for typical kinds of texts, this uh BWT is more compressible than the original text in a specific technical sense. And the reason for that is that sorting groups by context. Specifically, the character here in the last column is whatever precedes these characters. And so um I have a yeah the example with LF um if you look at the suffixes that start with LF. These three all of the occurrences of LF in our original text started or were preceded with an A because it was ALF eats alalfa.

9:02 Uh it's prop proper English sentence, right? Um so these these three A's here are lumped together because they are uh much more likely in this case 100% likely if after them comes LF. In other words uh sometimes it's not as extreme. Um but you could say if you look at these all the suffixes that start with an A then the corresponding characters here are the things that come before an A. And usually that is giving you some information. Uh there's in in English text there's some letter combinations that are much more frequent than others. If you know what comes after a character, you know some information about the character itself. It gives you this skewed distribution. And then these characters at the in the BWT will locally follow this distribution.

10:05 Okay. Um so BWT groups the the characters by their context and that specifically means um if a character can be predicted with less entropy than uh otherwise from what follows after it then uh the BWT will have locally a low entropy among the characters. There'll be regions where you see mostly A's or regions where you see mostly L's. These kind of things. In the compression context, you can then use another transformation that turns this locally low entropy into globally low entropy by something like a difference transform. Conceptually, the the method is different. For those of you who have seen it, um you will know what I mean. Um but you could maybe imagine that you locally rename the the letters so that uh this this locally low entropy becomes a global thing that you can then exploit with standard tricks like Huffman codes for example. We're not going to do that here. This is just the historical context is entirely from text compression.

11:18 Um, and it turns out the PWT has a few other very useful properties that are certainly related to this, but uh are in a way stronger or more useful. Uh, just to illustrate um this kind of grouping becomes more powerful if you have a bigger text because then you have more things that share context and these are always grouped by the sorting. So, here's some text that's a bit repetitive, but to make it small enough for the slide, maybe that's fair. And what you see is that there's many many runs of the same character in the BWT. And that is something uh you typically see with with natural language text. Indeed, you can even proof uh we're not going to do it. I'm just citing the results. If you take the BWT and you run length compress it, which is I'm just going to write down here. This is seven times an H. Then comes two times an A, two * a V, four times a space. That's all I'm I'm doing.

12:24 And I call the number of such runs that I have to do when I write down the BWT R. Then uh here's some example from previously. Here r would be 12 whereas the length of the text was 17. So we saved a little bit by having these runs here. In this bigger example we uh even get to half of the length of the text. And this is quite typical to continue. And what you can prove is that this this number of runs is related to what you get from a lamp compression method. Again if uh if you don't know what lamp 77 is, it's not important. It's a way to use uh essentially local redundancy in that you have break phrases that occur again substrings that are repeated and this is about the best method to exploit that in some sense. If that is then the size of the text in this compression then this R from the BWT is only slightly bigger.

13:28 That's one reason why it works so well in comp in compression. That's all I'm going to say about compression. That's kind of the historical context where BWT first arose, but is not the main application these days.