34

I am facing issues in understanding Boyer Moore String Search algorithm.

I am following the following document. Link

I am not able to work out my way as to exactly what is the real meaning of delta1 and delta2 here, and how are they applying this to find string search algorithm. Language looked little vague..

Kindly if anybody out there can help me out in understanding this, it would be really helpful.

Or, if you know of any other link or document available that is easy to understand, then please share.

Thanks in advance.

11
  • Is the Wikipedia article any help? Commented Jun 1, 2011 at 21:19
  • No, wikipidea is also not helpful. I tried reading it.. but it is of no help... Please if anyone can help, its urgent...
    – AGeek
    Commented Jun 1, 2011 at 21:38
  • @AGeek: Well, which stage of the example on the Wikipedia page do you not follow? Commented Jun 1, 2011 at 21:43
  • @Oli - thanks. I understood the first para... I am not able to understand First table and second table creation, and how are they helping to search the existence of pattern.. :)
    – AGeek
    Commented Jun 1, 2011 at 21:52
  • Cannn anybodyyy helpp.. Please......
    – AGeek
    Commented Jun 1, 2011 at 22:07

2 Answers 2

119

The insight behind Boyer-Moore is that if you start searching for a pattern in a string starting with the last character in the pattern, you can jump your search forward multiple characters when you hit a mismatch.

Let's say our pattern p is the sequence of characters p1, p2, ..., pn and we are searching a string s, currently with p aligned so that pn is at index i in s.

E.g.:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i =       ^

The B-M paper makes the following observations:

(1) if we try matching a character that is not in p then we can jump forward n characters:

'F' is not in p, hence we advance n characters:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =        AT THAT
i =              ^

(2) if we try matching a character whose last position is k from the end of p then we can jump forward k characters:

' 's last position in p is 4 from the end, hence we advance 4 characters:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =            AT THAT
i =                  ^

Now we scan backwards from i until we either succeed or we hit a mismatch. (3a) if the mismatch occurs k characters from the start of p and the mismatched character is not in p, then we can advance (at least) k characters.

'L' is not in p and the mismatch occurred against p6, hence we can advance (at least) 6 characters:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                  AT THAT
i =                        ^

However, we can actually do better than this. (3b) since we know that at the old i we'd already matched some characters (1 in this case). If the matched characters don't match the start of p, then we can actually jump forward a little more (this extra distance is called 'delta2' in the paper):

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                   AT THAT
i =                         ^

At this point, observation (2) applies again, giving

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                       AT THAT
i =                             ^

and bingo! We're done.

6
  • 19
    As clearly demonstrated in this answer, an elaborate example is by far the best and simplest way to convey the gist of any reasonably sophisticated algorithm. Commented Apr 5, 2012 at 8:46
  • 1
    legend. good walkthrough. incase anybody else is wondering, horspool preprocessed table calculates jump = mismatch index, whereas BM preprocessed table calculates jump = the left-most index of mismatch (e.g. mismatch in S is 'A', so jump = left-nearest 'A', from the mistmatch in pattern). This sometimes means a greater jump than horspool
    – mn.
    Commented Oct 16, 2013 at 22:45
  • 1
    It's amazing how many "tutorials" fail to explain such a simple thing with hundreds of images. Well done @Rafe, that's how you explain something right.
    – user187676
    Commented Jun 2, 2014 at 14:37
  • @ErikAigner - very kind of you!
    – Rafe
    Commented Jun 3, 2014 at 1:36
  • 1
    All good with explanation, BUT: I'm still confused about the first shift. All sites mention if we have a mismatch on first comparison, we skip n chars of text. But what about example: "aaaaabaakakakak" and pattern "aaaab"? If we align to left, b is not a, but if we shift it for 5 chars to right, we loose match..
    – SubjectX
    Commented Aug 5, 2014 at 12:49
48

The algorithm is based on a simple principle. Suppose that I'm trying to match a substring of length m. I'm going to first look at character at index m. If that character is not in my string, I know that the substring I want can't start in characters at indices 1, 2, ... , m.

If that character is in my string, I'll assume that it is at the last place in my string that it can be. I'll then jump back and start trying to match my string from that possible starting place. This piece of information is my first table.

Once I start matching from the beginning of the substring, when I find a mismatch, I can't just start from scratch. I could be partially through a match starting at a different point. For instance if I'm trying to match anand in ananand successfully match, anan, realize that the following a is not a d, but I've just matched an, and so I should jump back to trying to match my third character in my substring. This, "If I fail after matching x characters, I could be on the y'th character of a match" information is stored in the second table.

Note that when I fail to match the second table knows how far along in a match I might be based on what I just matched. The first table knows how far back I might be based on the character that I just saw which I failed to match. You want to use the more pessimistic of those two pieces of information.

With this in mind the algorithm works like this:

start at beginning of string
start at beginning of match
while not at the end of the string:
    if match_position is 0:
        Jump ahead m characters
        Look at character, jump back based on table 1
        If match the first character:
            advance match position
        advance string position
    else if I match:
        if I reached the end of the match:
           FOUND MATCH - return
        else:
           advance string position and match position.
    else:
        pos1 = table1[ character I failed to match ]
        pos2 = table2[ how far into the match I am ]
        if pos1 < pos2:
            jump back pos1 in string
            set match position at beginning
        else:
            set match position to pos2
FAILED TO MATCH
4
  • This looked an awesome text and explanation.. but due to more text m lil' confused... I am trying to understand it now... Anyway Thanks. I will let you knw when i am done...
    – AGeek
    Commented Jun 5, 2011 at 11:54
  • can you help me on wiki program... creation of first table... what is he actually trying to do.....
    – AGeek
    Commented Jun 11, 2011 at 7:13
  • en.wikipedia.org/wiki/Boyer_moore >>> the first table creation,,,, i read the code also, but cudn't get the idea as to how to create the first table
    – AGeek
    Commented Jun 11, 2011 at 7:13
  • Thumbs up to your advice (Y).
    – MarwaAhmad
    Commented May 27, 2019 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.