Video 4-6: §4.6 The Boyer-Moore algorithm

0:00 Intro

0:02 in the next half section i want to look at another string matching algorithm that seems to strike this this weird balance that it is better than the optimal knew with more spread algorithm and

0:14 Motivation

0:16 so i've just told you that knuthmore spread is the best possible so what else could we hope for and again you have to read optimal always with a grain of salt uh kmp is optimal in the worst case but that doesn't mean that it's always the best possible choice and so here's a concrete example that drives this point to the extreme if we have a very boring text and a very boring pattern and we ask if their pattern occurs anywhere in the text you would immediately say no of course not because i it has the wrong letters in a sense but that's kind of unfair we would have to find an algorithm that proves this by character comparisons but we can still ask what is the shortest way to tell uh to someone to prove to someone using character comparisons that this pattern doesn't occur in the text i in one way is shown in this table wherever there's that the x marked this is where you do a comparison so you compare this x to a find they're not equal and you do this four times and with these four negative outcomes so that the pattern character and the text character there are different you have excluded all possible matches because any match in the text would have

1:37 to overlap one of these positions okay now sometimes this is possible and then you can definitely do better than than kmp in other cases it's not possible and then kmp is the best possible in other algorithms sometimes struggle to achieve the same efficiency but what what this is all about is trying to tune the algorithms not only for the the worst case that might never appear but rather get them more efficient where possible something like the adaptive sorting that we've seen in unit 3. a striking example here a striking feature of this example is that we didn't even read all the characters in the text right we only read a fraction of them but it was enough to conclude that there are no matches

2:34 now how can we turn this into an algorithm that always works not just on this degenerate example and one very simple but also somehow uh incredible insight is let's check guesses from right to left instead of left to right in the hope that when we find this mismatch here we can immediately say nothing can no match can start here here here here or at the beginning and we can immediately shift the pattern to the right of this of this position now we can't always do this but we'll we'll look at what we can do but if we're lucky we can we can shift the pattern by a whole lot doing just one comparison

3:22 that's the key idea if you only did that you run into other nasty cases if the pattern if the text is very boring and the pattern is just one other character followed by many a's if you would check from the right you would always pass with the entire pattern and just fail on the last character so that alone is not so great what this algorithm of of boy and more does is it combines two rules on how far you can jump upon a mismatch how much you can shift your guess to the right and those two in combination often work really well uh the first one is very simple if we have a mismatch so the text at a certain position has a character c and this was not the right one for the current guess then if the pattern does not contain this character c at all we can commit immediately shift the pattern completely to the right of this position right that was the example before the pattern was all axis and the text was all a's as soon as i found this a i knew the pattern can't be on any of these positions and we can generalize this a slight bit we can always shift the pattern so that the last occurrence of this character

4:41 alliance with the current position that we checked the second heuristic is a little more more involved but it basically means if you've started comparing from the right a certain part you found a partial match of the pattern already in the text you would like to not completely throw away that knowledge and we'll see in examples um the details

5:12 Boyer-Moore Algorithm - Code

5:16 this time i'll start with code even though it has gaps so how to compute these two mysterious functions will come on the following slides and then the overall structure of the code again is we iterate through guesses in the text but because we do this with jumps it's a little little more tricky we start with the rightmost position in the pattern so we compare right to left and then as long as we have matches so we compare the character in the pattern with the current position in the text and if they match then we go one position to the to the left in the pattern and the text right and compare the next so that's the matching from right to left um if we ever reach the beginning of the pattern we have found all characters so that's a match and we can return this here otherwise if we find a mismatch we have to adjust our guess so move the guess to the right and we do this by using the bigger of these two jumps and again without defining what with these uh with the delta n gamma table is that makes little sense but we'll come to them okay and we'll make sure that we always shift at least by one position so that we make

6:32 progress other than that excluding the heuristics it's the very natural way to implement this right to left guessing instead of left to right so the first heuristic was this um with this bad character heuristic and let's do a concrete example here where we have some text and we have a pattern and so we made our first comparison the first guesses it starts at the beginning we start comparing from the right there's a mismatch the character in the text r is not the character in the pattern o and moreover r doesn't appear in the pattern at all so where do i shift the pattern or my guess next all the way to the right of the current one so i can shift the guess up to here and now compare these two characters again the last of the of the pattern and w again doesn't occur in the pattern so same thing happens and then well

6:45 Bad character examples

7:41 find the rest find the pattern at this position slightly more tricky example is down here okay we didn't look at a couple of characters the more interesting example down here again r is not the right character in the pattern but there is an occurrence of r in the pattern so we can't immediately shift the pattern to here that would potentially overlook a match instead we take the rightmost occurrence of r which is this and make sure that this r aligns with the r of the text so we just shift it by one position in this case and in general whatever the position of the last occurrence is we bring that into alignment with the text character

8:24 and then so this is put in parenthesis because we don't have to check this again we already know they match but we have to start comparing here again and then m is not e so we have a mismatch so we shift the gas again and using m last occurrence is here so we bring the m in the pattern in alignment with the m in the text so that's our next guess and then comparing from the right we find that this is indeed a match here okay so clear how the bad character your stick works i this is indeed the the more impactful in in many applications just because if you look for a small pattern it's quite likely that your text has characters that don't occur at all in the pattern

9:15 Last-Occurrence Function Preprocess pattern Pand alphabet

9:20 more formally we say we compute this delta array as the index where this character occurs last and then putting this into the pseudocode from before gives you the right the right results so here's a small example how you can build that table basically you go left to right through the pattern and overwrite the last position then you immediately get the the last occurrence of every character

9:49 and and here's how you work out how much you have to shift so just just on the example to um justify that formula if you initially start i is zero so that's the guess that's the starting position of this match right so position zero one two and so on uh j was four because we're still at the last position so uh zero plus four is the position here that's

10:20 the position where we check that was the mismatch we found the character r in this in this position in the text and the last occurrence of r in this word is index three and so to make that occurrence align with the position four in the text we have to shift by one and in general it works out to j minus the value in delta a lambda okay

10:51 that's kind of um easy to do the only downside is we now have an array again for the entire alphabet so it's um there's some tradeoff to be to be made with the space let's also look at the good suffix example so again this is the second heuristic and it tries to keep if you have partial matches make make use of those partial matches to

11:01 Good suffix examples

11:18 not look at guesses that cannot possibly work and this one i will only explain an example and so the disclaimer is you don't need to know all the details for this one but you should be able to do it on a small example like this one this is the text and here's the pattern and suppose we have started from the right comparing the last four characters match but then we have a mismatch at h so we would like to shift this guess forward but we only want to shift it in a way that these matches that we already have don't immediately create a mismatch with the new guess that would be wasteful we already know that can't be and so in this case we can shift it forward so that

12:10 this else is in alignment with this else okay that's what happens if you put these on top of each other and that's that's pretty much the only the only way to do it here and then you can start uh

12:26 jumped all the way to the back there's another case for this heuristic though so a different pattern different text same situation you started comparing from the back and then there's a mismatch now you want again shift the pattern forward by as much

12:52 by by uh so much as to not immediately get mismatches again now you see uh food doesn't occur in the pattern so you might be misled thinking that you can shift the pattern entirely to the right of this but there's um a smaller part that does occur at the beginning and so the best we can do is shift it to this position and bring a suffix of the matched of the grid suffix in alignment with the prefix of the string so that's the that's the other case if both cases apply you have to use the one that gives you the smaller shift because you can't afford overlooking an occurrence

13:39 all right so the crucial thing was to have the the longest suffix of the the match part the good suffix of the pattern is what you found in the text and you want to find an occurrence of that earlier in the pattern if you don't find the full thing then you find at least the suffix of that

14:11 to compute those good suffix jumps the gamma table we store uh in in gamma j the shift that we would have had if we have matched the positions from the right up to position j and then at position j in the pattern we have a mismatch and so we know the the good suffix is everything after j

14:46 and we try to find the occurrence of that in the pattern so at this point well there's a matching the text up to this point that's the good suffix but a mismatch for the next position and then one of the two options that we've just seen in the example is chosen and we have to choose the larger of them

15:21 uh i'll skip the details but you can compute this in a way similar to the kmp function or to be more precise you can compute for the pattern the fail function that we've seen the failure links for kmp but you also need the failure function for the mirrored string where you just reverse the thing from those two things together you can puzzle out the gamma in in this optimal time uh but i think this this leads us too far and i'd like to focus just on on the conceptual idea here so specifically for the exam you should be able to do the examples we've done but the rest on this slide not

16:03 Boyer-Moore algorithm - Discussion

16:06 all right that's that's pretty much i want to say all i want to say about the boyamore algorithm you've seen the top level code you've seen how to compute the last occurrence function or the bad character heuristic and i've sketched how you can do the good suffix one

16:26 there's some some interesting remarks the the algorithm is a little more tricky to analyze than kmp where we've we've essentially done it it's completely not obvious but one can prove with a lengthy analysis that the worst case if the pattern does not occur in the text is essentially best possible it's n plus m there's the plus sigma because we have to fill the last occurrence array so that's inevitable here but usually the text is longer than the alphabet right it's a it's a very peculiar situation if you have a text that doesn't contain all the characters even though thinkable with unicode

17:10 so if if the pattern does not occur in the text boy or more is still worst case optimal but this is not true in general in particular if you want to report all occurrences and not just the first uh it seems it seems well the the solution i've shown you the code i've shown you wouldn't work well in that case it would in the worst case go down to this n times m one can work on this there's variations that try to be smarter uh it's trickier here than in kmp because uh you have to remember partial matches and these can be anywhere in the middle of the of the pattern they're no longer necessarily just a prefix but they can be anywhere in the middle and that makes it a little tricky to keep track of them uh for kmp this is not true

18:03 for kmp you can always report all matches in the best possible time by just keeping it running in the code we returned when we found a match we returned the starting position you can instead just store that to a list or print it out or something like this and keep the algorithm running it would work essentially the same way then you get all occurrences in that time and it seems not so easy to do this with boyamore on the positive side uh if you look at non-degenerate inputs or something that's maybe more realistic like english text then boyamore looks only at every fourth character on average and kmp doesn't compete with that

18:49 it requires moderate extra space but there is this dependency on sigma so it's not perfect i looked up in case you're interested uh the i said this earlier i think the the java library if it's still there's the same code the index off method is pretty much the brute force algorithm so you should be able to make this quite slow if you feed in worst case inputs python is a little smarter they they created a custom version that is a mixture of boy or more with some extra ideas and so they they took the key ideas from this one but modified it a bit further especially to avoid this this uh plus sigma space it's quite interesting if you want to read about it i can i think i put a link i can send you a link if you want

20:04 and again this is one where you want to read carefully it looks roughly where we were before three two one and locked okay um i'll switch back all right maybe should we should briefly go through all of these uh so boy or more is not better than kmp on all inputs we've seen some examples where boy or more at least our version is worst case n times m k and p never so that's clear for some inputs it's faster we add this english language text

21:14 Clicker Question

21:43 that's the opposite of the first which is also not true because uh well essentially it follows from this one um and there are examples where kmp is better than boy or more otherwise the first would be true uh the last one is also interestingly true uh

22:06 i'm not sure if this is obvious from what i told you really or if if i just threw this in for your information it might have to do with the the pre-processing

22:34 but let's let's take it as a fact for now