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

0:00 Introduction to Boyer-Moore

0:01 in this next section we'll briefly discuss an algorithm that tries to somehow beat K moris prad in a specific sense that's the the boom more algorithm KMP is essentially optimal because uh it has the worst case complexity of Big O of n plus M character comparisons and we already discussed last time that this is uh um already required to just read the text and the pattern so how could you possibly improve on that now

0:31 the point is that this is only optimal for the worst case um I'm ignoring that we're living in in the Big O land so there's also constant factors that you can improve uh but that's not what I'm getting at in this section the point is it's about the worst case whereas for many instances of texts and patterns you can do much better and here's a a concrete extreme example where you need way fewer comparison or character comparisons than the can more sprad algorithm would use uh the text is just all A's the pattern is just all X's so without looking at it much you can immediately say there won't be any matches now of course the algorithm uh can't just uh look at the text as a whole it will has have to examine individual characters as would you if that was uh 10 million characters but it's still enough to check um for these four positions and notice that there's a mismatch to certify that there's no um no matches in the entire text and the point is that these uh these four mismatches these four guesses that are not matches they cover the entire text and that's enough if there's no match that can possibly overlap any of these positions then we're done and notice that we didn't actually

1:55 look at all the text characters and that's totally fine in many cases the boom more algorithm tries to exploit this this observation more systematically um and in particular you see what was useful here was using the last character as the check first and that's um that's the key essence of the boore algorithm instead of trying to do the comparisons from from left to right you do them right to left uh now that causes some

2:02 Right-to-left comparison

2:30 some problems further on that we'll we'll have to fix in the rest of the section but the good thing about this is if we're somewhat lucky then uh a single comparison eliminates an entire

2:53 and uh we can shift the pattern all the way behind uh that now that can go wrong in the very same way as The Brute Force algorithm sometimes goes wrong and here's a concrete worst case example where you see you have to do all the n * m comparisons if you do just that just compare right to left so to avoid that we have to use something like in the can moris prad algorithm the failure of links we have to somehow find a way to exploit the knowledge we already uh gained during the compar

3:34 and that turns out to be roughly as tricky as for KMP but we want to keep the right to left order so instead there's um there's two new rules that often work super well

3:58 okay uh if if anyone in the live stre live stream can confirm that if videos working fine YouTube complaints but the recording should be fine so maybe that's all we need so the two rules are are called the bad character jumps that's um if we have a mismatch at a certain position there'll be more detailed examples um on a in a second so there's a certain mismatch in the text now if our pattern does not at all contain this character C then any such overlapping placement of the pattern uh can't be a match so we can shift it entirely behind that character or if the pattern contains the character C we can put that so that it aligns with the text um and we can shift it to the last occurrence of C in the pattern that's the that's the simple simple version

4:11 Bad character heuristic

4:58 um so let's do well so last occurrence in the pattern and uh if there's no Occurrence at all then we just say it's it's at the front so that often helps uh especially if you have a large alphabet then maybe the pattern doesn't even contain all symbols uh but that that alone um wouldn't save us um in in all cases so um we have a second euristic which is a little more

5:36 Good suffix heuristic

5:43 subtle in the general setting we have a text and we have some position of the pattern where we have some characters in alignment right and then there's a mismatch at this position we compare right to left there's a mismatch at this position so we now have to shift somehow the pattern to avoid uh that mismatch what we'd like to keep is this matched part it would be uh it would be useless to shift the pattern in a way where you have a mismatch between that part that was already good before so if there's any position here where we don't have a match between that position and the position in the green part there's no use in trying that

6:36 that's what the good suffix euristic uh tries to do we we shift our pattern forward if there's a mismatch so that the part that we've already seen in the text so far is in alignment with the pattern at this

6:53 point uh if you um if you ignore how to compute these two euristic the overall code is relatively simple that's why that's that's um on the slide first we go through the text ones uh we start at the right of the pattern so with the last index in p as long as we haven't reached the start so we haven't found um the entire pattern yet we check the next character if there's a match then we go to the previous position in um in the pattern and if we reach by that point the beginning of the pattern so we've just jum over P0 then we found a match at this position and otherwise we have to shift the pattern forward by a certain amount and what we take is the better of the two euristic they both tell us okay there's no point in Shifting the pattern less than so and so many positions and so we can take the maximum of those two

7:57 Heuristic examples and logic

7:58 guesses now here's a few more concrete examples of of the two euristic and um I'll leave it then uh with that so if we have the pattern uh Alo and where's Waldo is the text then here in these first two characters we try to match first from the right we compare with r now R does not occur at all in the pattern so we can shift it all the way behind the current guess

8:29 okay uh similarly in the Second Step so w doesn't occur in the pattern so we can shift it all the way behind it and then well at this point we find the the pattern here that's the standard standard checks uh here's another example that shows the more subtle case we try to find more in boore um we first align it okay we first align it here and we try to find so there's a mismatch with the the r now we try to find the last occurrence of R in the pattern that's here so we can only shift the pattern so that this last occurrence is in alignment with the r that's what the uh bad character your stick at least tells us and then we keep checking so here again um M the last occurrence is right at the beginning so we bring the last occurrence in alignment with that position and then again we can check

9:39 so the last occurrence function in in detail is just the position where a character occurs last or minus one if it doesn't occur at all uh here's an example for for that pattern and um I won't go into details it's very easy to compute this in code you basically scan through the pattern once and just uh update for all occurrences where you find something you you update the numbers um so I'll skip the detailed code there let's have a brief look at the second juristic which is a little a little more subtle there's two different cases that's a good suffix juristic um if we have this kind of pattern cells shells and uh we have this text here Sheila cell shells uh the first first guess would be this and we start comparing from the right until we find this mismatch now there's this good suffix of the pattern this part that we found and we want to keep that if we realign the pattern we don't want to destroy matches there so we try to check L's if I just shift by one or two characters there's a mismatch the only other occurrence of L's is here so I can shift all the way through so that these the other occurrence of else of this good suffix in the pattern

11:02 is in alignment with the text positions we've had before okay if you shift by any amount that's that's less far to the right then you will have a mismatch at one of these positions that's what the good suffix u means now this was the case where we could find the entire suffix within the pattern uh there's a second case which happens um with this pattern okay again um a text example and we start scanning from the right with matches so the good suffix is food and then there's a mismatch now I can shift the pattern uh but there's no other occurrence of food in uh in the pattern itself the only thing I can find is a suffix of the good suffix that occurs as a prefix of the pattern so the last two letters of food are at the beginning so if the first case doesn't apply we don't find the good suffix at all in the pattern then maybe we can find part of it at the beginning and so we can bring the first two letters in alignment with the last two of the good suffix and these letters are essentially skipped over or um yeah we don't we don't use those okay that's the two cases you can either find the good

12:28 suffix entirely within the pattern at at another position or you find the part of the pattern of the good suffix in the pattern and if if so it has to be at the

12:47 beginning so in both cases um there's the longest suffix of the Matched suffix of the good suffix that occurs earlier in p and these are the two cases now um

13:00 there's there's two cases of how to compute the shift from those again depending on which of those two applies I don't I don't want to go into these details especially because we are not doing any exam questions on this uh the key the key idea is just what you see in the example you try to find the part that you matched in the pattern again and the last occurrence of that uh is where you shift too now for this one you may um you may wonder how you can efficiently compute this and that's one of the cases where what I said at the very last slide of the previous section becomes true something like the the failure function of the KMP algorithm allows you to compute uh these these shifts in detail in in linear time um the algorithm is a little is a little tricky it's not long code but it's it's a bit finicky to understand you have to do lots of of index

14:08 arithmetic uh so again um this doesn't apply the whole chap the whole section is not part of the exam um that was from when when it was covered okay that's the boore algorithm uh apart from the pre-processing part I've shown you detailed code um it's surprisingly tricky to analyze this algorithm them the worst case running time indeed is uh essentially best possible but only if the pattern does not occur in the text uh this is not obvious but uh people have have done this um the way I described it the worst case overall is still n * m if uh we need to report all occurrences

14:18 Complexity and performance

14:59 um the reason for that is is that the your sticks don't always allow you to shift um further and uh they don't keep track of of matched Parts in all cases um that's that's part of the part of the comp complications that we uh got ourselves into by doing this um right to left checking if you remember in KMP all we needed to remember was how many characters of the pattern have we seen in the text up to this point that was a single number and then essentially that was the state of our string matching automaton now with boore it could happen that you had a few mismatches you had a few matches here then there was a mismatch now you shift the pattern over with a good suffix juristic so you have a few matches here and then you start matching from the end again and so it would be kind of wasteful to check those for matches again but the way I presented the algorithm it doesn't remember that it has checked these it is smart enough to not shift uh by fewer positions than are needed to imply that we have matches here but it doesn't remember the matches um and it's a bit more tricky because they're in the middle of the

16:18 pattern now so it's more intricate bookkeeping and uh the code gets a bit annoying so you can Implement for your more um to uh achieve the same worst case time but it's is much more tricky uh so most of the time when people use this algorithm they don't they H kind of just accept this worst case but also accept that typically on on something like English text uh boore only has to look at a quarter of the characters and so it's far away from this worst case and it's usually a good deal faster than KMP just because most of the time you can skip over entire parts of the text because uh the pattern doesn't even contain a character or so