Video 7-9: §7.7 Burrows Wheeler transform

0:00 Burrow Wheeler transform

0:03 in this last subsection from the compression chapter i want to talk about the burroughs wheeler transform that's the most sophisticated text transform that we will cover and again it will not by itself make the text compressible but it ex it makes redundancies in the text explicit and then allows other compression methods to work much more effectively and that makes the borrows wheeler transform the core ingredient for modern compression both for static compression where you compress and decompress and for data structures where you work on the compressed representations for both the burysweda transform has been instrumental and it's also a beautiful theoretical idea

0:58 maybe also as a historical uh site remark when the transform was first uh thought of it was deemed impractical because it needs a lot of extra memory it needs to have the the main tech the text all in main memory and so it was deemed impractical and not pursued and only much later it was published when people realized that it is practical with the improvements of hardware and and memory sizes so this also tells the story about algorithms in general sometimes a sophisticated idea looks impractical at the time you think of it but it's still worth exploring because it might become practical in the near future and this is what definitely happened to the burst wheeler transform

1:47 what is it the burst wheeler transformed the bwt it's a way to scramble around the text characters it uses the same letters as the source text but in a different order

2:04 and that order is specifically chosen to help compression to help other compression methods we'll come to that in a second a downside from that is that it needs the entire text to compute we need you need the entire text to compute the bwt

2:24 and uh maybe what convinces you most is if you take the bwt follow it by move to front then run length encoding and then huffman at the end that is in at the core what is behind the bzip program and that achieves the best compression we know for uh english text i've i've shown you here uh this is just the the english bible so that's um some four megabytes that's all there is to it if you store it in in plain text if you use uh gzip the the new sip you get it down by a factor of 4 which is not not bad 7zip which is often deemed the most effective channel compression method is is much better than gnusip gets it down to that but bzip actually beats 7-zip for text and

3:24 without without discussing this much further it shows that having the right conceptual ideas achieves good results also in practice and and that's even though these two are very highly engineered this comparatively simple method beats them by using the appropriate tools

3:53 to be fair i should mention here that bzip tends to be slower than the other methods so there's a trade-off to be made between the time it needs to compress and decompress and the compression ratio but if the actual compression ratio is what you're after then bzib is is very solid

4:12 okay i finally want to tell you what the bwt is for telling you that i need to introduce a cyclic shift of a string that's a simple concept if you have a text t a cyclic shift just means you start in a different position and wrap around so if you write the string like this on a circle time flies quickly

4:37 then originally this was the starting position i can move the starting position to some other point and then i start reading this the text from here that's a cyclic shift uh cyclic because it's on the circle i think it's intuitive um enough and so one one cyclic shift of this string is flies quickly time not sure if that's a sensible sentence but it's the best example i could come up with

5:09 uh if we add an end of word character and we've uh you're by now familiar with these then the cyclic shifts become invertible i can always take continue shifting until the dollar sign is at the last position so that's a convenient convention and we will use this for bwt as well so take a text append the dollar character and then the boros wheeler transform works as follows you take all cyclic shifts of your text with the dollar sign at the end you sort all those cyclic shifts lexicographically and then you take in that sorted list the last column top to down and read down these characters uh and that gives you the burst reader transform of the text this i'm sure sounds crazy and it kind of is but it's magic no it's a smart trick and uh a smart way to exploit redundancies but i'll i'll show you in a second let's first see an example on how this works

6:22 Sample text

6:26 so here's a sample text that we that we will see a couple of times over the next slides uh elf eats alfalfa that's some some sort of grain or so some plants so it's an actual valid english text if in case you care for the beat up for the bwt this is not the main point what we need is all the cyclic shifts so this is the text with the dollar at the end you get all cyclic shifts by starting at a certain position and then starting from the beginning modulo the length of the text again so these are all the cyclic shifts right starting at at all positions and you see visually how you just shift things by one character to the left when you move down one line now we lexicographically sort these and that gets us this list so these are the same strings but now sorted alphabetically so the dollar comes first that's our convention from unit 6 as well then space comes before all the all the alphabet characters so if you if you look at this list this is always uh sorted right

7:44 but uh the only thing we really take from this picture is the last column of uh of this sorted list so you read this column top down and that is the borough's reader transform of this text and if you look at this gibberish it's not at all recognizable where this came from it looks quite different and quite weird you might notice that there's these runs of characters and that is a typical thing it it's definitely something that happens when the text is repetitive and that will be what we're after but the way we got to this bwt might still sound fairly wild

8:35 now uh i want to get you a little bit thinking and in case this wasn't already on your mind i want you to think about the relation between bwt and suffix arrays

8:53 so the concrete question is we had the suffix array l the leaf array right um in uh well the the sorted suffixes of a text take all the suffixes of a text and sort them uh that's l and we have the text and we have the bwt and the text and so the question is if you have either combination of either l or b and the text is it easy for you to determine what the other is and [Music]

9:26 yeah i'd like to see a few more answers and uh maybe up to 20 and i i'd like to show the results and move on and i think it's looking good yeah so there we are and let me lock that in uh the majority got it right um as you probably noticed uh from this picture i'll show you a better picture here

10:25 Sorting cyclic shifts

10:30 if you take cyclic shifts and sort them you never really compare beyond the dollar character because the cyclic shifts are these are all the different cyclic shifts dollar occurs only in one position you never have a cyclic shift where the dollar occurs at the same position you never have an equal there so any comparison between cyclic shifts will have the same outcome as if you ignored the gray part and just looked at the suffix starting at the same position okay so sorting cyclic shifts is the very same task as sorting suffixes and that of course means if you have the suffix array and the text then you know the sorted order the only thing you need then is to jump to this last column but that's always the character that precedes

11:30 that precedes this index so if you have for example here uh if we know that this is the starting position this a is the what is it it's actually the first character in the text that's uh let's not use this example that's degenerate but this one this is the suffix that starts at the second to last character so what's the last character in this column here that's whatever is preceding this so if you just take i minus 1 and access the text character at that position you get the bwt

12:05 so it's easy to compute the bwt from the suffix array and the text a is it's possible well it's always possible because you have to text um but a is more challenging because the bwt loses the information about where the text started it only keeps this last character the last column character and that alone doesn't make it very obvious how to compute it there are sophisticated most sophisticated methods with a little bit of insight that make this possible but it's not easily possible good so that connection gives us an efficient way to compute the burs wheeler transform because sorting sorting cyclic shifts is the same as sorting suffixes and we know how the sort suffixes all right and here's the formula more explicitly that shows you how to get the character how to compute b from l on the text here the text is called s but other than that it's the same thing okay that's how we can find the bwt that's the first good thing we can efficiently compute it uh the next question is um why is this any interesting why does the bwt help us in compression and for that i think i need here the example um what the bwt does is it groups characters by context namely by what

13:39 follows them so for example we have a context here lf is repeated here in in these positions and you see it's uh it's grouping these a's together into a run

13:58 uh and the reason is that we have this alf three times and it's uh it's contiguous here so all the occurrences of lf in the text are actually preceded by an a if there were other things that precede lf they would also be in this in this law in this little contiguous range so we group characters by what follows and that means if there's redundancy in terms of um i don't know th is often followed by e the bwt is able to pick that up

14:38 um and uh well if there's other characters that can come after th like a then the bwc is still able to make that more effective by leading to local clusters of characters so it groups characters together by what can come after them and if

15:13 let's do another example here if that is if that is my example then in english you can have a t in front of it or an s in front of it but you probably don't find an x in front of it very often so in the region where you have h a in in this sorted range in the front rows the last row would contain s's and t's a lot but no x's and that's what i mean by local clusters here and finally if you have repeated substrings in s you usually also get runs of characters in the burs wheeler transform as in this example so that's that's what i already said here alf is repeated three times in alf eats alf alpha and that repetition in the bwt leads to runs of characters

16:13 Example

16:17 so this was uh only a vague intuition why the bwt will be helpful for compression but it should give you at least some indication i want to show this um on a bigger example as well so here we have this this text have had and hasn't happened has what

16:41 if you look at the bwt you find there's a lot of characters that are repeated and if you then apply the move to front transform on the bwt let's remember what bzip does then you find a lot of zeros in the move to front transform of the bwt um

17:12 and uh yeah let me uh let me ask this question and then that's the last thing for today so a little uh just thinking from first principles on this example uh we have this

17:26 we have this example text half hat hadn't hasn't happened as what and it's bwt and it contains this long run of ages like like this one not quite as long but this uh

17:44 what does that really tell us how can we argue that um this is uh this is occurring as um as a runner how can we explain this run of ages and be be very careful about how to argue about this

18:06 because several of these answers make sense but they're not necessarily all um and again so i left this here because it's insightful to look at this run of edges here same here

18:40 and because we're already at 12 30 and i have a follow-up meeting right after this so that i can at least briefly discuss the result as well so i marked essentially only this single answer is correct

19:13 and um let's move back to this uh so i said uh the correct answer is that all aids all a's are preceded by an h and that's the statement that we have all the a's in the text here they are necessarily together because we sort the suffixes or sort the cyclic shifts and uh if you check what comes before those all ages here are before this a so there's no other character in this example text that precedes the letter a and that is guaranteed to give us a run of h's of the number of this of the length as many a's as we have we will have a run off of edges of course it's also true that this text has long repeated parts in particular

20:14 it has these these repeated parts space hat h a space h a space h a space h a quite a couple of of these and you can uh trace where they end up in the bwt they also give rise to runs in the bwt

20:41 or at least local clusters but not always contiguous runs for example here if you look at this this is all all these are these are all the suffixes starting with h a

21:07 but not all of them are preceded by a space there's also these two other cases so even though you have this repetition you don't get a clean run you just get a local cluster of the space in the bwt