In celebration... here's Boyer Moore

Submitted by Arancaytar on Thu, 2006-07-13 09:09

The exams are over. I got 2.7 on Data Communication, 2.7 on Statistics and 2.0 on Computer Architecture (which would be C+ and B, respectively). Now I have some time to myself. To celebrate that, I fiddled a bit with PHP and implemented a text search algorithm I'd learned. It's called the Boyer Moore Sunday algorithm, and works as follows:

  1. Begin with the offset 0.
  2. Test the substring of haystack that begins on offset:
  3. Begin with needle-offset 0.
  4. Compare the corresponding characters of needle and the substring of haystack.
  5. Continue with 4. until the string is found or there is a mismatch.
  6. If there is a mismatch, examine the character in haystack immediately after the substring.
  7. Take the last position of this character in needle, or -1 if it does not occur.
  8. Shift the offset in haystack to the right by the length of needle, and to the left by the position you just calculated.
  9. Continue with 2.

The implementation is here. Note that PHP differs from compiled languages in some syntax points - for example, a String is simply an array of characters and can be treated as such. The return value is typeless, it can be a boolean or an integer.

<?php

function boyer_moore($haystack,$needle,$start_at) {
    /* build the last-occurences table */
    $last = array();
    for($i=strlen($needle)-1;$i>=0;$i--) if (!$last[$i]) $last[$i]=$i;
    /* loop */
    for ($i=$start_at;$i<=strlen($haystack)-strlen($needle);) {
        /* i determines the offset attempted */
        for ($j=0;$haystack[$i+$j]==$needle[$j];$j++)
            if ($match==strlen($needle) return $i;
        /* mismatch. examine next character. */
        if (!($offset=$last[$haystack[$i+strlen($needle)]])) $offset = -1;
        /* use the offset to shift i */
        $i = $i+strlen($needle)-$offset;
    }
    return false;
}

?>
Keywords: 
Boyer-Moore
text search
News Category: 
Algorithms
  • 6249 reads
© 2006-2012: All content, unless otherwise noted, is the property of Arancaytar. It may be copied and modified with attribution for non-commercial purposes. By publishing comments on this site, you grant Arancaytar a non-exclusive, perpetual license to reproduce and publish these comments along with any identifying information provided. (You may request your comments to be deleted or edited voluntarily.)