Video 7-6: The Inverse BWT

0:03 There's one important thing we haven't talked about which is how to get back to the original text. I told you it's used for compression and we want to build a self-index based on it. It would be quite useful if we could get the text back and uh normally if you take a list and sort it there's no way to get back to the unsorted list, right? This is a destructive operation in some sense. At least it it uh it loses entropy in that sense. Well, for the BWT that's not the case. We can get the text back. Let me first show you how and not tell you yet why because I think the uh aha moment is bigger that way. So, here's the magic solution. You take your BWT. Now, you build this curious uh these objects of pairs of of uh uh a character and a number. The first is the character at the BWT at at position R and the second is that position.

1:02 Then you stably sort those pairs meaning first by the character and then breaking ties by the number. And then you use this as essentially a linked list to jump through the text. Let me show you on an example how this works. Here's the BWT of some text. Um, unless you're you're a genius on these things, maybe it's hard to see what the original text was. Maybe you can guess or maybe you've seen the example before or you're a genius. Uh, one of the three options. >> Yeah. Yeah. Here's the D. Uh, every magician needs a trick. So, um, the show starts with doing these pairs. That's that construction. Then we sort them And this third part I think needs an explanation that is really clearest in the example. Um we know where to start because the dollar sign has to be at the end. So we start where we find the dollar and then the main iteration starts follow the pointer that's given in this current pair. So the three tells you to go to position three output what you find there in the first position and then keep going. So we output the A as the first letter in the clear text in the original string and follow the pointer seven to go to the next position. That tells us to write a B. Then 11 goes down here and so on. And you jump wildly through the text and at at some point you have to stop, right?

2:37 How do you know how to stop? Uh I guess there's two options. You know the total number of characters so you could count. Uh but you also know when to stop when you reach the dollar symbol. Abracadabra. Why does this work?

2:53 Uh first of all, the running time of this is pretty good. You can do the sorting in linear time because it's uh small integers.

3:06 What we um what we have to do to decode the BWT uh consists of always two steps. And let me show you the example again with um kind of the the black cloak uh drawn and you can see what's underneath. This is the BWT. Here's our D and the sorted D's. [snorts] We know where to start with a dollar. That was here the three which means we're currently we're currently looking at this this row in the BWT in this matrix. Now the first character the beta the dollar is the last character. What we'd really like is the first character in the text which is in that same row the entry in the first column. Now the first column is special as you also see in the example. It has to be the characters in the text which is the characters in the BWT in sorted order. which means we can easily reconstruct this from the BWT without extra knowledge. Just sort the characters which is exactly what we've done as part of the decoding by sorting the pairs. Right?

4:16 So uh when this in the BWT was at position three or still is at position three after the sorting it remembers that position three. But now going to this character here at position three means in the sorted list of the characters go to index three. So this a here is the same a as this here because we took it from there essentially. Uh it's also another a. This a also occurs somewhere on the right.

4:52 So u I'm jumping a bit ahead of my um slides. We need two steps. The first is what I've just illustrated. We're in some column in some row and we want to jump to the same character in the first column. That was the part that just needed the letter sorted. Then we also need to find where this A occurs in the BWT to do the next step. For the dollar, this was a bit easier because there's a unique dollar. So, you know where it is. For A, that's not the case. There's four five A's. What else? Uh yeah, five A's in the whole string. So how do should we know which of the A's on the right is this A? And we need to pick the right one otherwise it will break. Now the trick is that okay this first one we worked out by sorting the characters for the second part we have to use that these guys are sorted.

5:50 So there's these five A's here. There's these five A's here. Surely nothing is lost, but we need the mapping for that. Look at what follows the A in these in these five suffixes. And I've tried to color this in five different colors that show a sorted order. They're just what follows the A in alphabetic order. Now, if you take the A away and you go to the cyclic rotation, one character shifted, these A's were all tied. So, the comparisons were all decided by what followed the A. If I take away the A, if I take the A away, all these five suffixes or cyclic rotations, they will be sorted in the same way because the dollar following the A here is still smaller than everything that followed A here. So this dollar is smaller than all these guys. And the same for the others. So these colors after the A and the colors without the A remain in the same sorted order has to be. And that means this A is mapped to the first A here, the second A is mapped to the second here, third to third and so on. That's why we can decode because it means um that this A here the third in the sorted order I know that it's the third because I know the position and number of characters. So we also know it has to be the third A here that we have to go to.

7:29 the decoding algorithm does this kind of automatically by keeping track of the indices. But the reason why it works needs the argument. I've explained this in detail here again because this trick is precisely what we'll use for the data structures in two different ways. Number one is we can actually decode substrings of the text starting at any position and for as many characters as we feel like. So if we want to find where um I don't know in our example say we want to find uh I'm I'm making this up. No, that's a bit too short. Let's say let's say 5 to 8 but exclusive. So these three characters T567, how would we find them? Once we know where to start, if we if we know a position in the BWT, we can do the same steps. Jump to the character here, find where that is, and so on. But how do we know where to start? That's indeed not possible with just the BWT.

8:36 We need something else. Um but we have a structure that tells us where in the BWT index 5 lands because that's the same as where um a corresponding suffix in the sorted order is. That's the rank array. So T5 is the character here. Now we don't know this guy, right? You have to imagine we can't see this. Um but what we do know is the entry in the rank array which tells us this uh suffix that starts at position five is at position one at index one in the sorted order here which means also at index one in the BWT is the first character here that we is the row where we start. It's not that N is the character we're looking for. We start same as before with the dollar. We start one character before where we want to read and from here on we do the same decoding step as for BWT inverse.

9:42 We could use the same um sorted D. So it tells us we should go to position five here. So we output a B. Then we should go to position two. That's here. So we output an A. Then we go to position seven. So we output an N. And that's almost right except that I missed the A from here. Right? Did I make a mistake in the decoding?

10:16 I didn't output the A here when I when I arrived. Uh I said we land here. We're not using the N, but I have to use the A. I was looking at the wrong column.

10:25 Okay. So off by ones are tricky, but the decoding step once you know where to start follows the same steps as the inverse BWT, but we now have a data structure where we can store the text in some potentially uh smaller space form, but we can still read out any uh substring of the text. What we need for that um was a way to do this. find um the E character in the sorted order in the first column of the matrix for BWT and then jump to the corresponding occurrence in the BWT. That's what that was the two operations that we needed and the sorted pairs was one way to do it.