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

0:00 Intro

0:03 the first of the two other string matching algorithms is the boy or more algorithm and I titled the section Beyond optimal because in a way we left KMP saying it's an opt it's worst case optimal so how could you possibly want to go beyond that

0:20 Motivation

0:25 what else could we hope for well in a way this worst case is rather pessimistic in several uh often occurring scenarios and to motivate that in an extreme case look at this example if the text is just a bunch of A's and the pattern is a bunch of axes now I don't have to tell you to look much so you immediately know that this pattern cannot occur in there now poor computer cannot look at this globally but you can do four checks of guesses and after that conclude that the pattern doesn't occur why well if you do this one comparison here and you pre-process the pattern you know that there's no a in p so there's no way how you can ever align this position a in the text with any position in the pattern and the same here same here and then okay at the at the end because this doesn't didn't divide nicely now we have to spend one more but it's clear that you basically get by with n divided by m checks in this case maybe plus one

1:38 now this is for the for the extreme case that I depicted here right question so we have to just every time we have just just need to move one state so we need more conversations like that right yeah so the the objection is yeah yeah p is a very special case I totally agree uh it's it's a it's a bogus case but it is one where it's easy to do much better than KMP so how about others right is there uh does this occur more of is this the typical case or is the p is ABC whatever the typical case I think the truth is somewhere a bit somewhere in between but closer to this at least for natural language text uh so the the remarkable thing is here I previously just just uh five minutes ago said you can't possibly find all occurrences if you don't read the entire text well if there are no occurrences you can find this fact without looking at the entire text at least in this example it's obvious okay so sometimes simple insights work um what makes boyo more tick is to compare the pattern from right to left and then the rest is a lot of fixing up so that um all the good properties that KMP hats

3:04 are not entirely lost but that's really the essence is it's as beautiful as it is simple because um had you started comparing from the left here you hadn't learned as much uh it's it's much easier if you have a mismatch here to shift it entirely along the line in this extreme case it doesn't make a difference but um well now yeah in this extreme case it doesn't make a difference in many other cases where the pattern is not quite as degenerate um this is a key ingredient if we're lucky one check can eliminate several guesses and we can just move move forward much more quickly now if you just do that uh you're back to almost the naive magic string matching algorithm for example if the text is all A's and the pattern is a b followed by Ace if you compare of them the right then you you check these M minus one A's each time just to find that then the last character is in mismatch so you don't want to do that

4:18 so we need something like the the rules in the string matching automaton that we eventually used in KMP but for this right to left procedure and what boy or more came up with is is two rules that allow you to jump forward with your pattern several positions potentially uh which are which are never wrong you never miss something they're not necessarily the best you can do but it must be something that you can compute cheaply and so these are the bad character in good suffix heuristics so the first kind the bad character jumps they're fairly easy if you have a mismatch in the text because the text had a character C then uh you can first of all if this character C does not at all occur in the pattern you can shift the pattern entirely behind C so maybe quick picture instead of just waving my hands there's a c here and we have the pattern here and there was a mismatch at this position if I now notice that there's no C at all in the pattern so that's case one no no character C in the pattern at all I can shift the pattern just behind this occurrence of C because I wouldn't be able to match it anywhere even if we're not don't have this

5:43 degenerate case we can still learn something if There Is An Occurrence okay maybe um let me make them some room I didn't catch everything let's put that up here and two below if we have a c here and there's the pattern and we know the last position in the Carrick in the pattern that has a c is this one then we can at least shift it forward so that these this last occurrence is in alignment with the c in the text

6:25 that's a a slightly more general rule than just saying if there's no C in the pattern we shift it beyond that if there is one then we can take the last one the the rightmost one and shift the pattern so that this aligns all right

6:43 now the the other rule the good suffix jumps they're a bit more more convoluted um again I think a picture for this is helpful so we have the the text and we have something of the pattern aligned with the text and because we start from the right we have some suffix of the pattern that uh we could bring into alignment with the text now we want to keep that knowledge that we learned in a way uh the first rule gives you Knowledge from a mismatch and now we want to have Knowledge from the past matches that we've already made so we want to align that with the pattern again so there's no need to shift the pattern to a position where what we align here doesn't match so instead we want to shift the pattern so that the things we already learned about the text occur in the pattern at some point otherwise we can again shift it beyond that

7:52 so I have some concrete examples for for both so um that's just for the for the rough idea uh but I wanted to list them on one slide so that we can can get the global picture if you have a mismatch you have to shift the occurrence of the pattern by some amount to the right and try a new guess so how much can you shift you can always shift by one that's clear if either of the rules gives you a shift then you know a shorter jump shifting by less will not help you will you will get a mismatch at some point guaranteed so you can always use the larger of those two jumps so either one or this the bad character jump or the good suffix jump right

8:42 Boyer-Moore Algorithm - Code

8:46 the overall procedure in code then looks like this um there's these two functions that I will not give you the full detail on because I just want to give you the the key idea here and Computing the good suffix heuristic is a bit messy um but that one is it's not too hard but let's suppose we just have those computed for now then we iterate through all the possible positions in the text we start at the end of the pattern so J is the position in the pattern as long as we haven't seen the entire pattern and we have matches we just move with J to the left so we find a match suffix in the pattern if we ever reach the the end of the string then that's great then we found a match and otherwise we jump forward by well uh the larger of the gamma heuristic which is the good suffix and the the car the expression for this is is flipped around because um this gives you the last occurrence of a certain character again I think the example in the next slide shows that

10:03 Bad character examples

10:06 so let's do some concrete examples first for the bad character one again uh here's some text you were finding this trying to find this pattern there's a mismatch at the last position so you try to check how fast can you move the pattern and because are the pattern the text character doesn't occur at all in the pattern you shift it all the way behind this you have another mismatch with the last character now this times W again doesn't occur so you can shift it all the way through

10:43 another example where it's not not the degenerate case the second case we have a mismatch uh okay now okay I finish off with uh the last match uh forgot about that part so we found the match in this case

11:00 for the second example we find a mismatch at the last position but R occurs in the pattern so we can only shift by one position because that brings the last R in the pattern in alignment with the r in the text and we start again comparing from the right and we find a mismatch at the last position so here we find M instead of E M occurs at the first position of the pattern so we can shift the pattern all the way through so that the first character is in alignment with this m and then we start comparing from the right again and find our pattern

11:37 okay I think Bat character is is relatively intuitive you just shift so that you bring the last occurrence in alignment uh to formalize that and the last occurrence function the one that occurred in the in the pseudocode before is defined as the largest index where this character occurs in the pattern or minus one otherwise and um you can just compute this in one Loop so for each you keep a table for all the characters and um I can look like this so you have an entry for each character and you have one other dummy entry for the characters that don't occur and you can go through the pattern from left to right and whenever you find you go to the character's entry and right I there so you meet you automatically overwrite the previous occurrences and only the last occurrence remains if you do this on this pattern you would say the index is zero so I go to m and write a zero there then the index is one the character is an O So I go in O's column and write a 1 there but then the next position index two is again an O so I write a 2 there overwriting the 1. and the other two just end up there okay easy peasy

11:46 Last-Occurrence Function

13:07 and if you uh if you have that definition what's the last position of a character you can work out that you have to shift by J minus that position forward that's just uh do an example and work it out so here's our example

13:23 um we had a mismatch at the last position then we tried to find the last occurrence of R that's what gamma gives us that's at position three zero one two three right as it says here and so we have to shift so that this R is in alignment with that and you do that by shifting by J minus this at J was the the position in the pattern that the mismatch occurred at which was position four the last character here so J minus three A J minus Lambda so four minus three is one

14:01 okay how much does it cost to compute that It's relatively cheap there's this little caveat that you need a table of size Sigma potentially you can try to get a little smarter at least you need the different number of different characters in in the pattern and some way to deal with characters that don't occur so if you implement this table with a dictionary you can avoid this this cost of Sigma but then you probably have M log m there's a bit of a trade-off depending on how you do it if you want the fast access then you need Sigma space and time okay that's last occurrence and let's have a look at a few examples for good suffix because there's two different cases to distinguish so the first one here's our text and our pattern is so the pattern is cell shells we start matching from the right that all matches until we find a mismatch at this position

14:44 Good suffix examples

15:11 now what does good suffix say we should shift the pattern forward so that the good suffix namely the suffix of the pattern that we could match is aligned with another occurrence of that substring in the pattern otherwise we'll get a mismatch for sure so no no reason trying in this case in the pattern you have an occurrence of else here at the front again so you can shift the pattern there and it's also the only occurrence of that good suffix so you can shift it all the way there and you kind of inherit the matches at these positions

15:50 and then you start comparing from the right as before so this is this is one case the good suffix occurred somewhere in the middle of the pattern this is another case that happens um if the pattern looks differently so this case uh owed to food well whoever made up these examples right but um so you start comparing from the rights the good suffix is food

16:21 but food doesn't occur anywhere in the pattern right so you can't find that again but it would be a mistake to say oh then we can shift it all the way behind the current gas because there's a part of the pattern a suffix of the good suffix occurs as a prefix of the pattern suffix of the suffix occurs as prefix so we can only shift to bring that in alignment that's the second case so case one good suffix occurs in the middle of the pattern case two a part of the suffix occurs at the beginning of the pattern and it might be an incomplete suffix

17:12 luckily that's the only two things that really happen that's as bad as it gets so you can summarize both as what's the longest suffix of the good suffix of the Matched part that occurs earlier in p either the beginning or somewhere else and there's these two cases now uh

17:32 Good suffix jumps

17:38 how do we store this in terms of this table so that gamma table was what occurred in the pseudocode earlier and what we store there is the shift that we should use if the mismatch happened at P of J which also means from P from J plus 1 up to M that's the good suffix so it's clear that there's one such uh shift for each of these positions there's only one one answer so we had match the part behind position J of of T but then we have a mismatch and so uh it's one of these two cases either um it's M minus L for the largest l so that we can find a part in the pattern so we um we find that suffix the good suffix occurs as a suffix of some prefix of P it's a complicated way I think of saying that the good suffix occurs in full somewhere within the pattern and what we want is the end point of that occurrence that's l and then gamma stores M minus l is a bit I know uh you have to draw it down in an example and then work out the formula and the second case is the good suffix uh is only occurring partially so you can flip it around and say

19:18 there's a prefix of the pattern p 0 up to L that occurs as a suffix of the good suffix that way you can formulate it with one parameter l so you find the largest else or the one of these two things is true and then that's the that's the value that goes into gamma

19:42 that doesn't tell you how to compute this efficiently I'll leave it with claiming that you can work it out by something similar like the knuth more spread algorithm so in particular you can compute the failure function for the fail array for both the pattern and the reverse pattern with those two things you can uh you can compute all of these efficiently but I'll spare you the details in this case so for us what you need to know is the the intuition the the intuition the idea behind this good suffix to the extent that you can do it on an example like the ones I've shown on the previous slide so I would I would expect you to be able to do that and um all that's on on this slide is essentially for your enjoyment or if you want to read it up it helps you I think to have that in in the back of your head but I think there's no point in having you learn the exact details they're just messing around with indices

20:51 and don't add much to uh to the con to the module of con to the module content if we sum up uh what this implies for boy or more in total we have a worst case running time when the pattern does never not not occur in the text at all what I've shown you gives essentially best possible worst case running time same as as canuth more spread the only nuisance is this plus Sigma and the fact that this has the optimal complexity there is is really hard to prove so this is not obvious if you try if you try to think about why that's the case there's a whole research paper on this is not obvious but it's true but that's if P does not occur in t the actual worst case running time is n times M which is a bit disappointing that's like the Brute Force algorithm and the reason is uh as the algorithm is formulated on the slides at least if we use the good suffix heuristic we know I said we inherit the matched characters but the algorithm as it's formulated doesn't take advantage of that it would compare them again in its move from right to left it uses the information for the shift it doesn't make use of the fact to save the

20:52 Boyer-Moore algorithm - Discussion

22:13 comparisons and that eventually gives you this worst case um people try to fix this I think there are fixes variations of boy or more that get it better but this is fairly complicated so this I think is the downside of boy or more the worst case is not not that great whereas knuth more Sprat can easily do this

22:40 but that said if you look at typical inputs at least if it's English language text you can can run experiments on on Benchmark inputs you find that boy or more only looks at every fourth character and of course KMP looks at every character maybe even twice and so that's way faster so if uh if you pull up a standard text editor and it has a search function it's quite likely that it's some boy or more variation that's the method to go for for most practical purposes the downside is is this um this extra Sigma but at least it's not M times Sigma but M plus Sigma so in a way uh that's that's less of a problem you can work your way around it

23:28 Clicker Question

23:30 so let's see if you um if you digest this part that's if if I remember correctly this is a bit tricky I guess that counts I want to show okay there we are

25:36 so here's my verdict done uh what I think is correct uh let's let's do this very briefly because most of you get this um well all inputs boy or more is not necessarily faster uh because we've discussed this worst case um for some inputs it is we've seen examples uh the other way around is also not true for for both algorithms you can find a case where one is better than the other which is essentially the statement behind the first four answers

26:13 um and uh if there are no matches the last one is the only thing that's a little tricky uh if if there are no matches then it turns out that boy or more is never doing worse than KMP uh even though um they might be essentially doing the same