Video 7-7: Random access in BWT-compressed texts

0:03 Okay, with this we can build random access in the BWT. I've basically shown you how. Um, what I didn't tell you is how to get this sorted D to use up less space. The way we described it here for the inverse BWT is not quite how you want to do it. Um uh if if you care about the space because it would for one thing in the first column uh store the the text symbols explicitly again and then you need the second one is a lot of indices. However, there's a data structure that we're not going to get into how it works. We'll just use the result that does exactly the right queries and that's uh rank and select on sequences.

0:56 Look at a text like ours here. It has a bunch of characters that occur AB and N in this case. And I can define a rank query which is in some prefix say up to position four. What is the number of A's in that prefix? uh two or what is the number of B's in that prefix well just one and what's the number of N's in that prefix also one that's the queries I can ask I can also do the kind of inverse query if uh if you tell me I want A's but I want the second A in the text what's the position of the second A in the text then this entry tells me it's at position three which is here. Okay, these are clearly useful operations because uh formally defined here. Um uh I'll appeal to the example instead.

1:54 We can use we can use those to build the two operations to decode the BWT from just these rank and select operations. Uh the the first one the second one is particularly easy. If you want the arth occurrence of a character C, that's exactly a select select query. And if you want the um the first part, where does a certain occurrence the E character in the sorted order of uh occurrence of a certain character appear in the sorted version of the BWT? That's almost a rank query, but you have to offset it with all the characters that come before you in the alphabet. So formally you uh um you take um if you just need the character you just need to find in in this array that stores how many characters are alphabetically smaller than you the the right index. Um you can also get the actual occurrence of the character. We don't actually need that.

3:03 That's right. We just need to read out the character in the sorted position. So if you can do rank and select on sequences, you can simulate what we've done with these sorted pairs, the sorted D.

3:20 And without explaining how this works, there's a data structure called the waflet trees. In other contexts, some of you have discussed this um which supports exactly these operations and uses nlock sigma bits of space at most. You can you can actually do a bit better. But even to state the guarantee would lead us further away than I want to go at this point. um it happens to be possible with that data structure without extra cost to support precisely the queries we need. I don't need to do this uh offsetting trick here. Um you can also for a character define this this sigma rank which is the normal rank but plus all the occurrences of characters that precede this character in the alphabet. So for all C prime less than C in the alphabet, you add how many occurrences they have in the total text. That turns out to be exactly what we need. And wavelet trees can support that essentially natively if you like. Um so you don't even have to puzzle that together separately.

4:31 Uh sadly, we'll have to leave it with a promise that this somehow works. If you want to see how, then you need to come back next term. [snorts] Um, now I committed to doing that. I guess uh we'll leave it for for the rest of today with just this black box that there's a magic way the wavelet tree to store a string in our case the bersa transform uh that can answer these rank and select queries. Uh the running time by the way is big O of log sigma. So if you think about a bioinformatics context, the alphabet will be small. Sigma is four or maybe 20 for proteins. And so this is really fast.

5:19 Okay. If we store the verse wheel transform as a wavelet tree, then we can decode decon reconstruct any characters from the text uh just from that in LO sigma time if we know where to start. So remember we needed the rank array to do that. Now if you invested all this effort to compress the BWT, you don't want to spend another n login bits to write down this this bloody rank array. But you can have a a simple trade-off here that you only store every teeth entry of the rank array. So you can reduce the space by a factor t and keep decoding for a bit longer. So in particular you can if you know you want to start at position I then you can't get the suffix there but you can start a little earlier round down to the next nearest I divided T and start decoding from there. There's going to be at most t characters that you uh decode it uh as extra effort but then you can reduce the space. That's a simple trick to get um some reasonable space. And this is um a practical alternative that people use with that we have essentially a data structure that you could say it's a locally decodable bur wheeler transform.

6:42 We don't need the text anymore. We can reconstruct the text on demand whenever we need it. And you can use that wavelet trees can be further compressed which again I know in this context I haven't told you how. And so you can just say, "Wow, okay. I'm I'm going to believe this. Um, that's all I can offer. See you next term if you want. [snorts]