Video 7-10: §7.7 Inverse BWT

0:00 Intro

0:03 uh we left off yesterday um discussing the boros wheeler transform so uh here's a nice picture that concisely shows what it is so maybe i'll try to leave leave this up

0:23 so what is the borosweiler transform just to get us briefly back on on the same page you take a text you see this text is written down here or also here you take all the cyclic shifts well first of all you put a dollar sign at the end so that you know where it ends then you take all the cyclic shifts and you sort them alphabetically or lexicographically and then you get this this little matrix of of characters and you take the last column that is the boros wheeler transform of the original string and we noticed that this transformation has some some

1:02 cool properties in that if the original string has repeated substrings for example the orange ones here that occur exactly repeated or very similar then you will also find these grouped together in the burroughs wheel in the verse wheeler transform and they will give rise to local clusters of characters um which can be in the form of pure runs the same character repeated many times well they can be like in this orange case local clusters of this space character but there might be other characters sprinkled in occasionally and so how we use this in compression is to first apply the boris wheeler transform to a text t that gives us this string and then we went on to take the move to front transformation which we also discussed last time to transform that into a sequence of numbers integers and you notice that local clusters like this here tend to either go exact repeats go to runs of zeros and local clusters lead to small numbers the example is still a little bit too small to see this in full um but well how big is the alphabet in this example uh well it's this it might be it might be too small to see the effect um very pronounced but you see there's many zeros

2:43 uh there we get a couple of twos and ones and we do get some bigger numbers too but they're only relatively infrequent so that was the reason why the very wheeler transform is great for compression if you apply it to a text you take the same characters of the text you just permute them shuffle them around and magically well not quite magic but it's built into the transformation the resulting text the transfer range the transform of the text tends to be much easier to compress with methods we've already seen move to front can amplify that even further and then we can use tricks like run length encoding and huffman coding to exploit the fact that we see many zeros and many small numbers in this move to front of the bwt of the text

3:46 okay in the last part on compression and on text transformations we will talk about how to invert the bwt we've seen in the last section that the verse wheeler transform is great in making the redundancy in a text more explicit so that we can exploit it using the the chain of applying the bwt to the text then move to front transformation and then other methods that we've discussed huffman coding run length encoding but this is only useful if we can decode the bwt as well so given the bwt can we get the original text back and that's if you look at the definition not at all obvious because the bwt involves sorting and usually sorting is a destructive process if you start with a list in some order and then you sort it there's no way you can get back the information of how the list looked like before you can try to store that information separately by annotating each element with the index where it was before the sorting but that's not what the bwt does so how is it possible that we can invert it that's what we'll look at next and uh it turns out there's a very simple solution that lets you do it and we'll i'll just show you on an

5:10 Magic Solution

5:17 example how it works and then uh we'll spend the rest of the video to understand why it works it's a it's a very interesting algorithm because the fact that it works and the algorithm is is very very simple and you'll see in the example it just works but the tough part is understanding why so implementing the algorithm very simple understanding why it's actually correct a bit more tricky

5:51 okay here's the the magic solution on an example this is the transformation that's the bwt of some text but we don't know the text the only thing we know is well it ended with a dollar sign and it obviously had a couple of a's one r one c a couple of b's etc so we know uh what characters the text is comprised of how many copies of each character because that stays the same if you take the bwt but that seems to be pretty much all we can obviously see from looking at this so here's the algorithm uh here's what we do we create an array of pairs this is written down from top to bottom here and the uh pairs consist well its pairs consist of two uh entries the first one is the arth character in the bwt so the entry at position r is the arth character in the pwt and the second is just an index so we kind of remember where the element was in the bwt but that's not the same as was what i said before with the sorted list because this is already sorted this is remembering where it was in the sorted list but here's the definition so this is what d looks like the second component

7:09 just counts from zero up to uh length minus one and here you can read again the bwt so nothing intelligent happened so far the second step is we sort this list

7:28 stably after the first entry so what do i mean by stable sorting i just mean if there's several a's i will group together all the a's by sorting and i'll i will leave the second component intact in the same order as it was here which is a fancy way of saying you just sort the pairs lexicographically first after the first component and if that one's the same you sort it after the second component i'm stressing this fact that we don't do this because we don't have to the second component is already sorted and it it is cheaper in terms of the running time to only sort the first component because that's from the alphabet we assume that's a small alphabet or in any case it's never bigger than the number of characters so we could do the sorting step in linear time with counting sort okay that's another instance where we make use of this fact that we can sort in linear time if the universe is small enough uh if if we have numbers from roughly the same

8:38 universe size as the length of the array okay again we haven't really done anything magic yet but what we do what we do now um is we interpret this new list which still has uh indices but now of course um because i changed the order the entry at position three no longer has enter has a second component three as it was before and now we simply reinterpret this list as a linked list representation for the original text namely the first component gives me the next character and the second component tells me where to jump to get the next to get to the next entry that's exactly like we use pointers in simply linked lists and that gives you the text in the original text order let's see it on an example

9:39 the first the first entry in this sorted list necessarily is the dollar sign because we always have that uh first in the lexicographic order we define it to be smaller than all the other characters so this is always the first entry but what we do in the algorithm is when we arrive at a pair we write down its character but in the initial step we we say we're already there so we don't write the dollar now instead we follow the three right away

10:14 and that brings us to that position and we write down a as the first character in the string okay so this first step is a bit the definition just has to be whenever you go to a new pair you write down its character okay so we did that now next thing is seven so we jump to seven write down the character b that's the second character in the string i promise and we continue so we jump to eleven that's down there so next is an r now we jump to 4 that gives us another a jump to 8 gives us a c and you see whenever i enter a new pair i write down the character here so i produce the the source text from left to right by just following pointers in this list so let's uh let's do that and one more time and then at some stage we enter the first element again um i want to be on that side at some point we enter the first uh the first pair again which means we output the dollar now and that also means we know we're finished as soon as we reach again the index 0 we're done and

11:36 the definition of the bwt guarantees us that we will always walk through this list and at the end return back to the first entry and uh here you see the the source text was abracadabra and um if you write this down take all the cyclic shifts of the suffixes and sort them take the last column you will find that this is indeed the bwt of of abracadabra

12:06 that's magic isn't it so let's have a look at why this works again the algorithm is very simple to implement you form these lists you sort them after the first component and then you walk through the list as if it was a linked list with pointers okay very simple uh why on earth does that correctly invert the bwt

12:10 Algorithm

12:39 Where to start

12:44 first first piece of information here is we can always find the the dollar character in the bwt and that means we know where to start now here we used sorting to implicitly get the dollar to the first position but what we needed from the dollar was this three which is its position in the bwt right the so the the first step was just a sneaky way of finding this position of the dollar in the bwt but we can always do this uh manually as well if we wanted because there's only one dollar sign in the bwt so we can always find the unique position where it's where it is so that tells you in in this sorted um in this uh sorted list of cyclic shifts where is the starting row because then if you find the dollar in the right hand side um you know where to get started maybe let me show this on the example so the uh the picture illustrates the second point but i want to first look at at this again

13:58 so we find the unique position of the dollar sign in the bwt and because that's uh where the dollar is the last symbol we know that this is the first symbol so if we jump to uh if we take the the position where the the dollar is um that's the the starting row in um in the sorted list of of suffixes

14:29 Finding the first column

14:34 the second piece is so we know where to start now that's great now we need two more things first of all we need to find in the current row in this list of sorted cyclic shifts we need to find the first column the character in the first column as you've just seen in the example that was the the b the first letter in in the string so we have to somehow make the jump from the last column to the first that's uh that's part one so maybe make that green because i'll i'll have more things to draw in a second and then the second thing we need is now we uh now that we have this character in the first row we want to find that character in on the right so that we can then jump back to the front of that row okay so let me illustrate that again

15:37 no i took green for this one so let's take orange for the second step green for this step we know where to start the green thing says i have to jump to this to the first column because i know i need to know what that character is so that i can i can output the b and then the next step is i have to find this b on the right so i have to find that this is the first letter in the string so i have to find this one which is also the first letter in the string so i somehow have to make this move to the right okay which is illustrated in the picture for uh for the a's but let's do it step by step here so this is what i have to do now how can i do this uh switch to green again

16:31 how can i get the characters in the first column well that is actually easy if you look at those guys these characters in the first column they are just all the characters in the bwt in sorted order right the dollar first then all the a's and all the b's all the ends that i can obtain by just sorting the bwt as if it was a list of characters now if you go back to the algorithm we didn't explicitly sort the bwt anywhere but well we sorted these pairs so here here is the same green row of characters in the first column

17:19 okay so that part's uh indeed not too hard we get that by simply sorting the bwt alphabetically the tricky part is the is the second thing um we have to make the jump to the right and um in general there can be many copies of the character of a character a and many copies of the of a character a on the right so how do we know which one matches uh which when i went from this b to that b i kind of used the entire matrix seeing that this b is the first so it follows the dollar sign so i i've seen that here it follows the dollar sign here it follows the dollar sign so it must be the correct one this is not something that the algorithm can do because it doesn't have access to the middle columns it only sees the first column in the last column we can still do it though because the relative order of the same characters stays the same if they're sorted this is a1 a2 a3 a4 then a1 a2 a3 a4 stay in the same order in the bwt and the reason for that is this list is sorted lexicographically so it's sorted by whatever follows the a and if you take the a to the end that

18:44 means you now start with one character later and if ban was the smallest of the strings that follow an a it still is smaller than all the other strings following an a like n and now ban and a ban not a band etc okay so because this was sorted and the a is the same the order of what follows these guys stays the same if we take the a away so the first a in the sorted order here has to map to the first a in the bwt

19:21 and that again is something we implicitly did in the algorithm here by keeping track of where these uh where these positions are so we kept for a's we kept their indices 0 6 7 and 8 and 9 and well that's it and now if we were at the second a we know it is actually in in row 6 and so we know where to go next

19:56 Finding the second column

20:05 how this algorithm actually uses the information of the middle columns that it doesn't explicitly know by using these two facts that we can jump to the left by sorting the characters and we can jump to the right to the next character find the corresponding copy in the in the right most column in the bwt by going from the either currents of a character to the ith occurrence of a character and that's uh what we do um by stably sorting the pairs it's still a little magic and i find it i find it very exciting each time i see this because the definition with the pairs is so simple and so easy to execute and yet it takes it takes a good deal of thought and and caffeine to digest why this uh actually works and correctly decodes the bwt

21:11 that brings me to the end of the bwt section we now know how to encode and we know how to decode the running time is linear in both cases building on how on the fact that we know that we can sort suffixes in linear time

21:29 but remember that this is a fairly complicated algorithm we can do it in linear time but the algorithm needed well this it was the dc3 algorithm with these three steps and there was this alphabet explosion we had to rank reduce the alphabet we had to do a fancy merging method etc etc for decoding the only thing we need is counting sword so that's a an exercise for a first year programming class so again we have a method with this observation that we've made for many of the other compression methods decoding is usually simpler and faster and that's also true for the bwt computing the inverse bwt is very simple and fast even though conceptually it looks it looks very challenging to do and encoding seems more complicated even though in theta notation there's no difference

22:30 Downsides

22:35 the downsides of bwt is is exactly the suffix sorting it is slower than other methods simpler methods and we also need the entire text available we cannot do this streaming unless we break the text into blocks which is of course an option but the big big positive thing and this should be like i should have drawn the icon a bit bigger it is the culmination of this long unit on compression to have uh explained all parts of this pipeline that give you the best possible compression that we know of for typical english language texts and and other similar types of data data sources

23:22 by combining things in this way and you can look up the the bz program to see more details so the bwt is on on the slower end of the spectrum but gives you the the best compression ratio that we have seen

23:37 Summary

23:41 and that concludes concludes the unit 7 on compression methods here's again in a nutshell the methods that we've seen the the non-trivial ones we have huffman coding which is

23:56 fixed to variable we have single characters are encoded using variable length code words it's best possible in this case if you insist on if you insist on encoding each character in isolation then we've seen run length encoding which can get really really great compression in very extreme cases but in isolation is not very strong but is a valuable part of the pipeline limpulsif welsh a fast but effective method if you have repeated substrings and i used um variable to fixed encoding and then the two text transforms the move to front um to to transfer transform simple repetition into uh well redundancy of the characters and then finally the bwt um that allows to group things by context and thereby greatly amplify the compression that we can achieve