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

0:00 Intro

0:02 in the next sub section i want to talk about the boya moore algorithm and how it in a sense beats the optimal knuthmore spread algorithm if that sounds weird you have all all the right to find that weird as i just said in the previous subsection kmp is an optimal algorithm so how could you possibly go better than have something better than that and the the sense in which you can beat it is uh is to look at what optimal means um i like to stress this because optimal is a term that's very often used and overused in computer science to mean different things and whenever someone says something is optimal be a bit skeptical and ask what exactly does that mean look into the black box and here optimal means the worst case over a text of length n and a pattern of length m needs at least n plus m time to read the text and the pattern that's what i just motivated an adversary could otherwise change the outcome by flipping a single symbol and no correct algorithm can avoid looking at all symbols in that worst case but there are many specific cases like this text that contains only a's and the pattern that is just a row of axes where uh there are no matches obviously

0:30 Motivation

1:33 this is um with one look at it you can you can tell as a human but also an algorithm can prove to you can certify that there is no match with only four comparisons uh namely these four i compare this position in the text with the last position in the pattern and similarly here and here and with only these four comparisons i can i can prove that there is no occurrence of the pattern in the text because if uh if there was one then the pattern would have to overlap this position or this position or this position or this position any possibility how you can shift the pattern along below the text would overlap at least one of these positions and all of them contain an a which is not the right letter for the pattern where we have an x obviously so none of these possibilities uh really um is is still there so you proved that there's no no possible position for a match and uh notice that we we read well eight characters four in the pattern four in the text and the text is i don't know how much longer and the pattern is longer than this so we haven't read all the characters yet we could prove in this case

2:52 that uh the output of the algorithm is correct no matches and something similar is is not so this is i mean this example is is far-fetched this is an extreme case you might not usually have this but something not too dissimilar from that is is quite frequent and this is what the boya moore algorithm can exploit whereas knuthmore spread essentially uses the same running time n plus m for all inputs even even for this one where it seems it leaves a lot of potential on the table

3:30 one observation from this example is look that i chose this position in this position that is the last position in the pattern here and that seems to be a much smarter way had i chosen the first position i would at least need one more check and here because um well the the length of the text and the length of the pattern doesn't nicely divide uh you have this this extra comparison here to just exclude one more um position of the pattern if this was a bit longer then you see that um you waste much less so starting with the last character in the pattern seems just much smarter and that's the core observation of the boyamore algorithm it's incredibly simple if you think about it just do the same thing as we did before but instead of starting from the left you start comparing from the right um incredibly simple idea but it turns out this is this is really a very influential one if we're very lucky um then the last character as in this example already is a is a mismatch and is of a kind that i can i can uh directly exclude all the other potential positions so the pattern cannot lie uh here it cannot lie here and it cannot lie here and it cannot

4:47 start here either uh that one okay i somehow mess up with the line lengths now um yeah i cannot start here and then starting here would have to end here well counting to five seems seems a bit challenging uh but one one mismatch here excluded um a whole bunch of of potential shifts

5:25 okay uh so how can we make this work we could start with just doing the brute force method but instead of comparing from left to right we compare right to left um you can think about this offline if you want it turns out this is this is um not going to work well um if your text looks like this in the pattern like this then you will essentially have the same worst case as the brute force method the original one so you have to do slightly more uh to to get this idea to work and you have to make bigger shifts that's for sure one very intuitive idea is the bad character heuristic and that means that's essentially what we've done in the in the example if you have the text and the pattern and there was a mismatch at a certain position you start comparing from the right but then here these were not the same so there's a i don't know how to draw this maybe a little lightning so there's a mismatch here now there will be a certain character in the text say it's a c um and if that c does not occur anywhere in the pattern we can already shift the pattern right behind that position c that's this first case

6:54 in the second case if c does occur but say only here then we have to shift the pattern forward so that this occurrence of c the last occurrence of c nicely aligns uh with this c that we found in the text okay so you make this a line in that way

7:19 that's a very intuitive thing to do and that's um directly generalizing what we did here um there was a mismatch here a doesn't occur in the pattern so we shifted completely behind this this current guess um you can do just a bad character heuristic that is sometimes called the boy or more horsepool algorithm

8:07 i'm just mentioning this because this algorithm works surprisingly well it's very simple just using the bad character heuristic gives you most of the benefit from boy or more in in many cases but not in all cases if you just do this there's still worst case inputs where you're doing essentially as bad as the brute force method so what boy or more came up with is the second heuristic and that's the good suffix jumps

8:40 and these are somewhat similar to what the knuthmore spread algorithm did you try to use the self-similarity in the pattern to shift things forward so in the knuthmores spratz algorithm we tried to find a suffix of the prefix that we're currently looking at and uh here it's it's a bit different because we're matching from right to left but in a sense this is we'll look at this in more detail

9:19 it's the generalization of what knuthmore spread does if you start comparing right to left okay that gives us two rules they both suggest an amount that by which we can shift the pattern and we just use the bigger of the two in code this looks like this um we'll go into a little more detail how to compute these um magic rules here the last occurrence and good suffix rules the code then itself is is very simple we have the current guess i we iterate through that or we keep going as long as we haven't reached the end of the text and we start comparing from the right so we initialize the the position in p to the last one m minus one and as long as we haven't seen all of the pattern we start comparing the next character going uh right to left

9:34 Boyer-Moore Algorithm - Code

10:18 right to left um if we ever find um that we could complete this this while loop entirely we return the match and otherwise so this is the interesting case now that's the only um the only big difference from the right to left brute force way otherwise we update i to uh i plus this shift and so we either have this last occurrence shift or this good suffix shift and we'll now see what's behind these in a little more detail

11:02 Bad character examples

11:05 the first thing we'll look at is the the bad character heuristic and here i just want to show some examples so we have a text where is or uh where's wally i guess it should be in the uk these are these children books where you have to find this character to not violate copyright i'm not showing pictures but let's suppose you're actually looking for aldo and not waldo because you're a weirdo i guess you start comparing from the right the pattern has an o but here we find an r r does not occur anywhere in the pattern so we can shift it entirely behind this current character okay the second thing happens here um w doesn't occur anywhere in the pattern so you shift the pattern entirely behind this and now finally you find oh oh that's a match so you compute you compare uh right to left uh until you find indeed here um an entire match and uh well if you want to count then there's six characters of the text that you actually actually had didn't have to look at another example where we have the second case of the bad character heuristic we're looking for more in boyer more and so again we start as before we find an r here so that's a mismatch but we have

12:28 an r in the pattern so uh we only align we only shift as much forward to align this last occurrence of r it's actually the only one here as well with the r we found in the text and so the parenthesis here mean we don't have to compare again we already know that there's a match here but it's uh it's to no avail because the last character is a mismatch so this there's not an e but an m in the text so we check uh m is it occurs in the pattern namely at position one so that's the last occurrence of m so we shift the pattern forwards to align that occurrence with the m in the text there we go and now we start comparing right to left and of course in this case we find an occurrence of the pattern and again there's a couple of characters we never needed to look at

13:26 i think this part of boy or more is is fairly intuitive it's also fairly easy to code it up what you can do is you you pre-process the pattern and the alphabet and you compute this last occurrence function that is simply the index in p where the last occurrence of this character is and well if there's no occurrence then we put a -1 to indicate that so one more time to show an example here but i guess the the concept is simple you have this table lambda of c and all other characters in the in this alphabet so we need to know what the alphabet is up front and remember if this is unicode this could be 140 000 characters so you better have a smart way of encoding this but maybe you can restrict to just the latin alphabet for now and then you put -1 for all of these and for the others you just find where is the last occurrence so a smart way to do this is go through the pattern left to right and write the current index at the position of the character so we're at zero we write zero at m we have one so we write one in o but then we have o again so we write two in

13:31 Last-Occurrence Function

14:45 o we overwrite the old value one and by that you already you automatically get the last occurrence r we put a three e we put a four and that's that's it and so uh to see that you get exactly this shift um that uh i think i've shown green before so that's that's this um to see that that matches out in the example well you find the mismatch here you check the last occurrence of r lambda of r is 3 as indicated here so what you compute is j that's 4 because we're in the position 0 1 2 3 4 of the text sorry of the pattern and we're in the guess starts at position 0 in the text so what we shift i forward is by j minus this and that was three alright so we we take the character at this position r in the text look up what lambda is here and then shift forward by 4 minus 3. all right so the last occurrence function can easily be computed and can be stored in this array it needs space proportional to the size of the alphabet but if you think back to dictionaries and symbol tables there are alternatives if space is a concern

16:22 now the second thing i want to look at is the good suffix heuristic and this one is a little more complicated um i will not give you the full detail of how to compute it um as a pseudocode because that's a little finicky and also um beyond what i want to give you i want to give you an intuition how this works we've gone through the details for kmp and um the only thing i really want to get across to you guys is that it's a similar idea but you have to adjust the details and um we'll leave it with that then but let's look at examples to see what the good suffix heuristic is

16:55 Good suffix examples

17:05 suppose you have this pattern cells shells which has self similarities obviously in particular this substring else occurs twice here and here now um suppose the text is sheila sells shells so we do have an occurrence of this pattern but we won't get that far yet we put the pattern here we start comparing from the right and then we find a mismatch at this position we find an h we find an s instead of the h in the pattern so what we would like to do is keep this this good part maybe i should use blue to be consistent uh this is a good suffix we want to keep that we found that in the text it occurs here in the text these are the same right so we want to shift the pattern only to positions where these matches are preserved and in that example it means we should align the first occurrence of else with this occurrence of else in the text so this is what we do we shift the pattern forward to align this else so this else now is the first else

18:21 and then we start comparing um as before so that would have been start comparing at the right and actually find that there's a match here but that part will skip there is a second case for good suffixes which is why this is a little more finicky in the details a different pattern owed to food and the text i like food from mexico um yep i inherited these examples

18:50 from from a colleague from mexico who sadly passed away a couple of years ago so this is um kind of a kept in as a tribute but that's beside the point um we have found food here but then there's an e in the text and the pattern had o so we do have a good suffix here and we try to find another occurrence of this suffix in the pattern but obviously there is no other occurrence of food in order to food the only thing we find is that a suffix of the good suffix occurs as a prefix of the text so we can still preserve some of these matches but only really these two so we shift the pattern forward like this so we could still rescue some of these occurrences and what's more important any shorter if i had shifted the pattern by not so much say only up to here then there would have been a mismatch implied by the good suffix i already know so there's no there's no use in in testing this okay and uh well then again i would start comparing from the right to find whether there is an occurrence in the text which in this case there isn't but that's beside the point of this example

20:25 the crucial ingredient here is that we find the longest suffix of the matched suffix that's the good suffix that occurs earlier in p and this longest suffix in the easy case it can be the entire good suffix and then it might occur in the middle of the in the pattern like in this case else was not at the beginning the other case is only a suffix of the good suffix occurs but then it has to be at the beginning of the pattern so much for the good suffix heuristic

21:01 um to summarize this part um we we can compute the good suffix heuristic um i'm not sure if i want to give the the full details here um i didn't tell you what the the the number in this uh gamma array is um and uh so what we look at is the situation we've we've had a match occurred so gamma of j means that we have a suffix starting at j plus one of the pattern in the text but if i try to do the chafe character in the pattern we get a mismatch so that's why gamma j stores a shift where the search first failed all right now uh gamma j is um so j is is is the the first mismatch that we had gamma j is a shift by m minus l where l is um the

21:13 Good suffix jumps

22:24 we try to find the largest overlap part here um so that we can um we can find either the matched part as a substring here as a as a suffix of this prefix so um the pattern that's the good suffix this one

22:51 we have the good suffix and we have a prefix of the pattern of length l and now either this good suffix is a suffix of this prefix or the prefix is the suffix of the good suffix that's a lot of mind twisting suffix and prefix essentially the two cases are the same as we've seen in the example and um so this is the precise definition what gamma is and with that definition it matches the pseudo code i initially showed but i actually don't want to want to give more details on this where i don't want to show the detailed code how to compute it i only want to mention that you can compute it in linear time and time linear in the length of the pattern with similar tricks to the kmp failure function indeed you can compute the actual failure function for the pattern and the reverse pattern where you just read it right to left because we read right to left here maybe this is intuitive from those two things you can compute gamma somewhat easily but understanding all the details is moving beyond the scope of today so also for the exam you don't need to know the exact values the only thing i would ask you is given an example like this what is the

24:14 shift that the good suffix heuristic would imply okay that's that's what you have to know basically what we did in these examples that's what i expect you to understand um the nitty-gritty details of this definition i don't think is important for this class and that brings me to the discussion we've seen the boya more algorithm with the two heuristics last occurrence and good suffix

24:31 Boyer-Moore algorithm - Discussion

24:45 there's a very subtle point to be made about its worst case running time as it is given the code actually has a bad worst case it's as bad as the brute force method in terms of the theta class and that essentially comes from when we want to repeat all occurrences the code as given doesn't remember implied matches in the middle uh if you if you look at this um for for kmp it was easy to get all matches without much modification remember we just had this failure automaton and you can basically add the failure link of the last state and then you can keep scanning the text no big difference for boy or more it's it's a bit of a a hassle because you have to if you have a an occurrence of the pattern here and then you try to shift it over then um you would have to deal with these with these matches but you start comparing from the right so you can get disconnected parts in the pattern that are already matched and unless you keep track of these you will not get below the n times m worst case but that said um unlike for the brute force method where this can easily happen for the boy or more algorithm you have

26:11 to find you have to search really hard to find an example and they're really more isolated also if the pattern does not really occur in the text you always get a linear time n plus m plus the length of the the size of the alphabet because that's time you need in the preprocessing so this is not not at all obvious it's a um a very complicated analysis behind this statement but it's still very useful to know that if the pattern does not occur boy or more is essentially optimal as well

26:48 the other statement to be made if you look at typical english texts and typical phrases that you might search so the text is english text and you search for a pattern that is um english words then uh you really only look at a quarter of the letters as a rough uh as a rough figure and that's quite interesting that means it is probably four times faster than kmp if uh number of comparisons is is the main thing and that is indeed what people find in practice so many implementations where you're looking for patterns are built on the boyamore algorithm or modifications thereof like the boyamore horse bull i mentioned and even though some of these do not care to get the best possible worst case they're usually much faster than kmp in many applications and that's that's good enough for for some of these cases another positive thing is the space usage is moderate but um it still has this dependency on sigma which can be um can be problematic

28:02 to finish off the the voya more parts i want you to get active again so here's some a question about this algorithm uh where i'm i'm basically asking you just to compare these two algorithms um and uh so you have to precisely read the statements um and only take those where it's it's clearly correct or it's clearly true and yeah some of some of the answers are pretty clear from what i've just said for others you have to think a little more deeply

28:44 me move over to this and um we've had some 30 voices so i would like to see at least 25 as as often before i want to reveal the answer

29:09 come on guys think of the important participation marks the little little percentages they're all for free you just have to vote i didn't put an option i have no clue but then you might just guess

29:37 okay see people changing their minds there we go 25 27 brilliant um so almost all of you got this this second part um let me switch back to this um yes uh

29:54 boy or more is uh faster than kmp for some inputs and um that's precisely the motivation of this subsection uh it happens to also be the other way around and that essentially follows from the worst case at least as as we've discussed the boy move version we've discussed has this bad worst case whereas kmp is always n plus m so there must be inputs where it's the other way around and a more subtle statement is the last one but it's also true if there are no matches then boy or more is never worse than kmp and the reason for that again is we're only counting simple comparisons and ignore the pre-processing and their boy or more is just never doing more than knew more spread they might be actually uh the same for many examples here but that's that's a different story uh it's only claiming less or equal okay thanks for that and uh that concludes boy or more the usual choice for string matching in practice