From: engber@ils.nwu.edu (Mike Engber)
Subject: Boyer-Moore delta2 table construction
Summary: a new O(n) algorithm ?
Organization: The Institute for the Learning Sciences
Date: Tue, 13 Oct 1992 19:34:00 GMT


I recently had the need to implement Boyer-Moore string searching and ran up
against the infamous delta2 table. All of the algorithms texts I looked in
stopped short of giving the details of how to compute it and I found myself
unable to grok the original algorthm by Knuth (later corrected by Rytter). So
I came up with my own which I think is simpler and easier to understand.

The C code is short, but not obvious so I took the time to write it up in
case I ever have to look at it again. I figured I'd share my effort with
whoever is interested.

I know Boyer-Moore is old news, but if anyone still finds it amusing, I'd be
interested in:

 - A set of test cases to thoroughly test my delta2 table construction.
   
 - Any comments on my explanation or implementation of the algorithm
   (like if you think it's correct, after all Knuth got it wrong on
   his first try.)
 
 - Any pointers to Boyer-Moore discusions with especially clear explanations
   of how to build the delta2 table - particulary if it's a different approach
   than the Knuth-Rytter method. I've looked at Sedgwick and Wirth.

please cc via email if possible.

-ME (engber@ils.nwu.edu)

---
 
/*

Another Linear Time Algorithm for Computing the Boyer-Moore Delta2 Table
 by Michael Engber

This file describes an algorithm for computing the delta2 table (positional
mismatch) for the Boyer-Moore string algorithm. The algoritms text I looked
at all stopped short of presenting the algorithm for building delta2. The
original Boyer-Moore paper presented an algorithm which was O(n^2) in the
length of the pattern. Knuth later showed it could be done in O(n).

The only sources with details that I could find were an article in "Computer
Languge" and the original paper by Knuth and the correction to it by
Rytter. Unfortunately, none of these sources gave me much a feel for how
the algorithm worked. So, after thinking about it a while and getting some
ideas for Dan Halabe, I came up with one of my own. A brief description and
C code are presented below.

 - It's O(n)
 
 - I believe it's correct. It passes the test case that Knuth's original
   algorithm failed + all the other cases I've tried it on.
   
 - It seems (to me at least) shorter and simpler than the Knuth-Rytter
   algorithm.

It is assumed the reader is already familiar with Boyer-Moore and the
Delta2 table. If you're not, I highly recommend the article by Wiggins
(see References)


Description

The basic idea is to make several passes through the pattern trying to find
progressively longer substrings that match the right end of the pattern. We
do this matching from right to left.

Consider the pattern: "bcyzbcyabcyabc". The first pass we'll find all the c's.
The next pass we want all the bc's - we only have to check the positions to
the left of all the c's found in the first pass. The next pass we want all
the abc's - we only have to check the positions to the left of all the bc's.
And so on ...

To minimize storage we use the d2 array to keep track of all the substring
positions in addition to holding the jump values. We use the left portion of
d2 to hold all the substring start postions. We use the right portion to hold
the jump values we compute (filling in from the right). It shouldn't be too
hard to convince yourself these two storage requirements are compatible. (The
number of possible substrings decreases rapaidly with their length)

Initially, we consider every position (except the last) the start of a match
of length zero. So we initialize each d2[i] to hold i. The last position is
the trivial case of the pattern matching itself - so it isn't interesting,
plus we'll need that spot to store the jump value we compute during our first
pass.

During each pass we first initialize the jump entry we're computing to be the
largest possible value. Then we'll look at all the matches we've found so far
and see if they can be extended. If a match can be extended, then we store it
back into the left part of d2 for consideration in the next pass. Otherwise,
we use it to calculate a jump value.  Since we process the matches in left to
right order, the rightmost jump postion will be the one we finally end up
with.

An example might help:

elt#: 0  1  2  3  4  5  6  7  8  9 10 11 12 13  |
 pat: b  c  y  z  b  c  y  a  b  c  y  a  b  c  | '-' = unused
  d2: 1  5  9  -  -  -  -  -  -  -  -  ^ 15  1  | '^' = being filled in

Here we're at a point where we've found 3 matches of length 2 (starting at
positions 1, 5, and 9) and were trying to extend them to length three as well
as fill in the jump value at position 11. The match at position 1 doesn't
extend because it falls off the front of the pattern. The match at position 5
doesn't extend because the next character is a 'z', so we use it to calculate
a jump value, 10. The match at position 9 does extend. Notice, we don't also
use it to calculate a jump value because a mismatch at position 11 means we
encountered an '?bc' in the text where ? is NOT an 'a'. This clearly can't
match the 'abc' at position 9.

Another important point is that we must keep track of matches at the very
start of the pattern. In our example, the 'bc' at the front of the pattern
limits how far we can jump after matching a 'bc'. It's only necessary to keep
track of the longest match at the start of the pattern. The code uses the
variable, matchLenFront, to do this. When ever a match is extended a check is
made to see if it extends all the way to the front of the pattern. If so,
matchLenFront is updated.


Analysis

The algorithm is O(patLen). The algorithm consists of a pair of nested loops.
The outer loop executes patLen times. How often the inner loop executes for a
given pass through the outer loop depends on the pattern. But, we can see
that the total number of times the inner loop executes is the sum of all the
match lengths plus once for each match to detect its end. The maximum number
of macthes is patLen-1 and the longest possible match is also patLen-1. So
then total number of times the inner loop executes (across all the iterations
of the outer loop) is O(patLen).


References

 Boyer, Robert S., and J Stother Moore. "A Fast String Searching Algoritm."
  Communications of the ACM, vol. 20, no. 10 (Oct. 1977): 762-772.
  
 Knuth, Donald, James H. Morris, and Vaughan R. Pratt. "Fast Pattern Matching
  in Strings." SIAM Journal of Computing, vol. 6, no. 2 (June 1977)
  
 Rytter, Wojciech. "A Correct Preprocessing Algorithm for Boyer-Moore String
  Searching." SIAM Journal of Computing, vol. 9, no. 3 (August 1980)
  
 Wiggins, Richard and Paul Wolberg, "Searching for Strings." Computer
  Language, (November 1986): 28-42

*/

/**********************************************************************/

void MakeD2(char* pat,long patLen,long d2[]){
    long    i;
    long    endIndex        = patLen - 1L;
    long    matchLen;
    long    matchCount      = patLen - 1L;
    long    matchLenFront   = 0L;

    for(i=0L; i<endIndex; ++i) d2[i] = i;

    for(matchLen=0L; matchLen<patLen; ++matchLen){
        long    newMatchCount   = 0L;
        long    d2FillIndex     = endIndex - matchLen;
        
        d2[d2FillIndex] = patLen - matchLenFront + matchLen;
        
        for(i=0; i<matchCount; ++i){
            if(d2[i] >= matchLen){
                if(pat[d2[i]-matchLen] == pat[d2FillIndex]){
                    if(d2[i] == matchLen){
                        matchLenFront = matchLen + 1L;
                    }
                    d2[newMatchCount] = d2[i];
                    ++newMatchCount;
                }else{
                    d2[d2FillIndex] = endIndex - d2[i] + matchLen;
                }
            }
        }
        matchCount = newMatchCount;
    }
}
Newsgroups: comp.theory