Video 5-10: §5.10 Inverse BWT

0:02 in the last section on the compression unit we'll see how to invert the burs wheer transform again as we've seen it's based on sorting the cyclic shifts and sorting is usually a destructive operation in that you cannot unsort something if you haven't remembered what the original order was and so it's it's a bit weird how would that be possible with the bur wheeler transform which is based on sorting and that's Cru crucial we need to be able to invert this otherwise we can't decode our encoded text it would be utterly useless uh indeed it turns out to be a total non-issue you can invert the bwt but I want to point out that this is somewhat

0:49 surprising so uh it's it's not obvious that it is invertible from the definition and in this case unlike in most of the other examples where we covered things like that I want to show you the solution first and then explain afterwards why this works the point the my reason is the solution is so beautiful and simple that you're all able to follow the algorithm and it doesn't really explain why it works at least I I think it's uh it's quite opaque but the solution is so cute so uh here here goes um you take your uh the bwt is given as this array of of characters uh we have have the Assumption as before that the original string had this dollar appended before it was transformed that's crucial so we need that um otherwise it's an arbitrary text and we only get the bwt first step is form pairs so uh here's here's an example that's our bwt as an input and the dollar here can be anywhere right for the UN for the source text it was at the end but in the bwt it can now be shifted around so that's one concrete example um and you create this array of pairs first the character from the BT and then it's index that's what's written down here

2:12 then we sort this uh list of pairs and if you were to do this in Python it would automatically do exactly what's what's needed here we sort first by the first component and among those that have the same character there we sort by the index in the second component uh and then the last maybe a bit less clear so we use d as a kind of a a pointer representation for a linked list and just follow pointers um Let me show this in the example then maybe is is a bit more clear the Sorting step I I guess is is clear also note the Sorting step necessarily puts the dollar sign in the first position because I said this is supposed to be smaller than all the other characters so we definitely get this for free we don't have to look for the dollar and then we just take um in each step we take this number as a pointer to uh where we should continue so the first step is follow this one uh at index three we have the next pair a and seven and so we produce as the first letter of the output the A and that's all now we follow through from the seven you know we go down here so follow that one um we

3:31 find a b that's what we output and we find a new pointer so it goes through dancing here by following these pointers um and it takes a while uh but eventually we'll find a pointer to zero and when we've produced the dollar sign we know it has to be over and in this case I mean we started here so we would run back into a c Circle so we have to stop ourselves here but it's obvious when we know when we find the dollar we know that we have to stop simple method right why does that have anything to do with the bwt why should that be the original word it's maybe uh not not

4:29 clear it's true there's there's a sorting up here too um of course I mean there's no magic really behind this but it's um it just looks looks not well from here to here that's sorting these these pairs there's nothing nothing special going on I mean the it doesn't do exactly what the bwt did it's not that you take a text apply the bwt and apply the bwt to the bwt again and then you get the text back that's not how it works okay it's not uh it's not self in self inverse or something like this uh you would get some garbage if you keep applying it uh both both have a sorting step involved but it's also very asymmetric the bwt forward the from the last section needs to sort this Matrix of strings which is it turns out to be cheap but it needs a sophisticated algorithm whereas this sorting step here is Trivial uh you sort by one character you can use something like counting sort for that uh and the second component is integers and these are also from a small range so again you can use counting sword so you already know how to sort this how to produce that column in linear time without any fancy tricks whereas for the other part

5:58 we'll come to the fan tricks um so let me try to explain a little bit the connection um I mean first of all it's easy to follow the algorithm and compute it so even though in Big O notation both are linear time the the inverse is much cheaper to compute it has a smaller constant uh but why why does this invert the bwt uh well first observation we decode character by character and we we can always find the dollar sign because that's supposed to be unique it's the Single Character single currence of that thing and we know that that comes last in the original text so that's at least an anchor and we can use that as a starting row so in the bwt we can find Row in the sense of uh this but also in the sense of these columns I had earlier okay that's a a lot of clicks back but let me briefly show it what I mean rows in this sense right we can find the starting row by finding wherever the dollar is so here in this

7:24 clicky so we have a starting row great what do we do next well uh to get the next character we need somehow in that row we currently have the last character the last column that's where we are in the bwt if we can find the character that corresponds to that row but is in the First Column that's what first step second step is find where that character in The Last column is in the bwt so let me draw it a bit schematically we're currently in this in this row uh where we currently have this entry that's the bwt

8:06 entry all right now the first step means jump to the front of this there's some new character a here and then we want to find where in the bwt this a

8:23 occurs because there's some other cylic shift that's just one one a is shifted over so that this is occurring some and we need a way to find that if we can do these two steps then we can jump character by character through the bwt and decode and indeed that is what this uh pointer following did in dis

8:50 guys how do we do the step one if we know the index of the column in the bwt so if we know the how many character in the B WT we currently have we know the index of the row so we can know the index I where we currently look at this this thing here now the First Column is all the letters in the source text which is the same as all the letters in the bwt in sorted

9:22 order so we can just look in the sorted list what is the I character no magic needed we can just sort the characters and the list of pairs had the characters sorted and that's exactly what we did uh and for the second step we need a little observation um namely that the relative order of the same characters stays the same from left to right so if I have uh several occurrences of a in the First Column like in this case Four A's then the same a must occur in the last column it's just the permutation of the letters and the relative order Remains the Same this a is the same as this a how do I know well I know the context in the string so this a is actually the start of a ban and then comes dollar this a is also the start of a ban and then comes dollar so the letters themselves don't have an identity but their position in the text identifies them uniquely so why do the why do they preserve this order why is the first and second and third a the first and second and third a on the right in the the rightmost column that's because they're sorted by the same Criterion so uh the overall

10:41 list of rows is sorted so that means these occurrences of A's all gave a tie when I sorted those rows but then I had the next columns and maybe even further columns to break the ties the occurrences of the same characters a in the right means this a is stripped from the context but then the rest is the same so this ban was smaller than n so ban is still smaller than n if I take the a Away by the very same argument that's that's all there is behind it if there was a tie before for a then what comes afterwards doesn't change order if I remove that tight character and so that's why uh our our pointer following method only really had to sort the First Column and keep track which row things came from so that it can do this uh this pointer jumping step which effectively gives this this uh r two

11:52 step I so more more concretely like uh if I if I had this a here these four A's and I keep track of which row they came from uh then I can find those rows here when I when I need them again so when I when I have this character at the moment I jump to the a by looking I have the 0 1 two 3 index three of the rows and index three among the sorted characters is not just an a I know also it's the third a among those A's so I know where to jump to all right uh that was probably the most intricate part of the Sorting thing is a a little um you know bit a bit of a mind twister maybe um but that's that's the the climax for now um the decoding was much simpler but both encoding and decoding take linear time in Big O notation uh we'll come back to what that means suffix sorting um I mentioned it earlier uh as before or as we've seen with other compression methods the decoding is indeed much much simpler and faster also in terms of the constant factors at

13:13 least now what can we say about using bwt for compression uh it's it's typically slower than the other methods we've seen in this in this unit apart from this pack 8l fancy method that is way way slower and trying to find more more patterns still uh but among the practically used methods pwt is among the slower ones but that's less of less and less of a problem it also needs access to the entire text which means it needs a lot of main memory to keep all the text in memory as I mentioned earlier initially was dismissed as not even practical for that reason and now it becomes uh staple method um because memory is just not as pressing a problem and uh you get specifically from this pipeline very good trade-off between running time and compression it's also uh the bwt also is the basis of more modern versions of of this compression part so in a way that's um that's the end of the pure compression uh evaluation here but a second component is that the

14:25 bwt is is the basis of things such as the FM index uh which is a is a way to represent a text in compressed form but at the same time you can you can decompress it by asking random access questions you can jump to any character that you want which is for example not possible in a zip file if you compress thousands and th thousands of small text files and you try to get a specific one you can you can open the file and your computer will show you all the files that are contained in it but if you open one of the files in one want to see the contents it actually has to read through the entire file and if it's gigabytes of of zip files you'll notice U there's better ways to do this they haven't found their way into standard compression tools because they're usually still good enough is uh but the bwt is behind all these more modern approaches um and so that becomes more and more relevant with the the topics that we'll discuss in Unit

15:28 8 and here's a quick overview of all the methods we've seen um again nothing new on this slide it's just for your convenience to summary uh a summary of what we've seen

15:41 um and in particular the the two new ones we had a previous summary already here's another summary adding in these text transforms uh it's just an excuse to have a few more confusing acronyms on the slides