Video 7-10: §7.10 Inverse BWT

0:00 <Untitled Chapter 1>

0:02 to finish up the the compression chapter after a long ago i know let's have a look at how you can invert the bwt i've shown you how to compute it we've seen how to efficiently compute it and i gave you some intuition this grouping by context why it makes compression effective but from the definition it's not at all clear that you can decode it at all because after all you sort it normally if you sort a list of things then the original order is lost and in particular had i chosen this the first column of this matrix then i wouldn't be able to invert it the first column is just all the characters in sorted order once i've done that i have no way to go back to the original text but the bwt can be inverted and that's that's a remarkable property before we discuss how this works i'll just show you the algorithm

1:03 i'll show you on an example how it works and here's spelled out a bit more cleanly how to do it so we have an example that's the bwt now i write down the bwt here in the first component of a pair and the second component is just the index in the bwt okay so index 0 is an a index 1 is r index 2 is a d and so on that's what i what i work with and now um [Music] i sort these pairs lexicographically if you want again i sort them first by the character and i break ties by the second position and that's the list we'll we'll use for decoding so there's another sorting step but it has to be a very specific one as i explained you have to sort by the characters first and then by the index in the bwt that will mean always the first of these pairs has a dollar and now we'll do the following steps we'll use the second position like a next pointer in a linked list we start with the dollar and we follow its next pointer and whenever we enter a pair with the next pointer we write out the character that we see in the first column first position so this one has a index three so we jump

2:20 to three and a is the first output then we take the index from there and use it as an x pointer so 7 leads us to this down here puts a b out and we go from there to 11 so we find an r then 4 brings us to a and so on and so forth so you run through the text always just taking this one as the next index to visit and uh magically abracadabra you end up with the original text and you know when to stop because you've reached the first thing again or you've reached the the dollar symbol again either works okay i think the algorithm is very easy to follow if i gave you this example and told you another time how to do this or you have a look at this you would be able to reproduce this by hand quite quite easily but it seems completely unclear why this is the right thing to do

3:23 Inverse BWT - The magic revealed

3:25 so what we need to do this if you analyze the running time we need to sort and we sort pairs so that's two rounds of counting sort because uh the first one is is from an alphabet so that's small integers the second one is integers that's all fine so you can do use this black box from unit 3. but why why is this uh the right thing to do these are the steps we have to follow but i want the example on the slide

3:55 the decoding works character by character there's only one thing really to get started and that's the dollar sign that's only occurring once so that's somehow easy to find so in the bwt we can find the dollar symbol that's easy now what is the first character in the text it's whatever follows the dollar sign in the wraparound so we would like to know if i'm in this position how can i jump to the first character the the character in the first column of the same row that's this that's this first step and for that all we need is all the characters in sorted order if we had a list of all the characters in the bwt in sorted order then we can jump there because we're in position i and so we just take the i character in sorted order okay these are sorted if i know an index i can jump there and in a way what we did in the algorithm is we produce the sorted list of the characters so that's step one if i know a position i can jump to the character in the first column the second step is to continue that gives me the first character b now how do i find where to continue i have to use these i

5:14 have to somehow jump to the next character and so what you can do here um is illustrate it one step later if you have all these a's remember all a's appear here together because they're sorted and if you follow where they come from just from looking at which a in the word it is they appear in the same order they're the first first second third fourth first second third fourth the relative order doesn't change and that's a property of the bwt again because you sorted these texts if what comes here after this was earlier in the alphabet after the a then after you cut away the a ban is also before nnn so ban is before nnn so this a must come before all the other a's okay so how do you exploit this you find your b and now you count the how many if b is this it's not the first it's the second b and so you walk down your bwt and you also find not the first but the second b so that's the next step and then you do the same thing again you jump into the first column using the index in the sorted list and you find this is the fourth a so you go to the fourth a and the bwt and

6:41 that's how you jump from left to right repeatedly and get one character out each time that's the bwt so we've seen decoding is much easier actually it doesn't need fancy suffix sorting it just needs counting sword and following these these imaginary pointers

6:51 BWT - Discussion

7:07 but both are overall linear time if you just look at the theta class it's typically a bit slower than other methods but computers have become fast enough that it's very competitive and if you if you wait a millisecond for your zip file to email it to your friend or you wait half a second it doesn't matter much it doesn't need access to the entire text so it can't be used in a streaming fashion but you could apply it to blocks that's a hack to go the bzip 2 algorithm because i haven't pointed this out it uses first the bwt then move to front then run length encoding and then a huffman code for what comes out of that that's pretty much the compression method you've seen and that's still um among the best that we have there are more principle choices by now that actually get the same performance and are a bit cleaner to understand i wish we had some more time to go through that but i think the module is full enough and this session has been full enough so here's just um the update of the comparison these are the three compression methods we've had and we added the two transforms and yeah we'll leave it with that there's still interesting things

8:02 Summary of Compression Methods

8:16 happening in compression so a lot of what we touched on is is still active research so i like this topic a lot