php - PHP 中的 Rabin-Karp 算法

Question

我想知道是否有人可以分享 Rabin-Karp 算法的来源？

谢谢

Answer 1

http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node43.html

这里有几个来源。

Answer 2

这是Karp-Rabin 算法的 C 实现的一个端口：

function KR($haystack, $needle) {
    $n = strlen($haystack);
    $m = strlen($needle);
    if ($m > $n) {
        return -1;
    }
    /* Preprocessing */
    $d = 1 << ($m - 1);
    for ($hh = $hn = $i = 0; $i < $m; ++$i) {
        $hh = (($hh<<1) + ord($haystack[$i]));
        $hn = (($hn<<1) + ord($needle[$i]));
    }
    /* Searching */
    $j = 0;
    while ($j <= $n-$m) {
        if ($hh == $hn && substr($haystack, $j, $m) === $needle) {
            return $j;
        }
        if ($j === $n-$m) {
            return false;
        }
        /* Rehashing */
        $hh = (($hh - ord($haystack[$j]) * $d) << 1) + ord($haystack[$j + $m]);
        ++$j;
    }
    return false;
}

Answer 3

为了说明起见，这是 Gumbo 上面的答案稍有改动的版本，具有更简单的散列和更清晰的变量命名。

在下面的说明性散列中，我只是将每个字符的 ord() 值添加到表示散列的数字中，然后在推进搜索时减去该值/添加下一个字符的 ord()。这很容易发生冲突（因此不利于生产），但如果您只是从概念上学习 Rabin-Karp，则更容易理解。

function rk ($needle, $haystack)
{
    $nlen = strlen($needle);
    $hlen = strlen($haystack);
    $nhash = 0;
    $hhash = 0;

    // Special cases that don't require the rk algo:
    // if needle is longer than haystack, no possible match
    if ($nlen > $hlen) {
        return false;
    }
    // If they're the same size, they must just match
    if ($nlen == $hlen) {
        return ($needle === $haystack);
    }

    // Compute hash of $needle and $haystack[0..needle.length]
    // This is a very primitive hashing method for illustrative purposes
    // only. You'll want to modify each value based on its position in
    // the string as per Gumbo's example above (left shifting)
    for ($i = 0; $i < $nlen; ++$i) {
        $nhash += ord($needle[$i]);
        $hhash += ord($haystack[$i]);
    }

    // Go through each position of needle and see if
    // the hashes match, then do a comparison at that point
    for ($i = 0, $c = $hlen - $nlen; $i <= $c; ++$i) {
        // If the hashes match, there's a good chance the next $nlen characters of $haystack matches $needle
        if ($nhash == $hhash && $needle === substr($haystack, $i, $nlen)) {
            return $i;
        }
        // If we've reached the end, don't try to update the hash with
        // the code following this if()
        if ($i == $c) {
            return false;
        }

        // Update hhash to the next position by subtracting the
        // letter we're removing and adding the letter we're adding
        $hhash = ($hhash - ord($haystack[$i])) + ord($haystack[$i + $nlen]);
    }

    return false;
}

Answer 4

试试这个。在将其发送到 之前，您必须从$needleand中删除标点符号，但这基本上遵循维基百科页面上给出的算法。$haystackmatch_rabinKarp()

// this hash function is friendly, according to the wikipedia page
function hash($string) {
 $base = ord('a');
 if (strlen($string) == 1) {
  return ord($string);
 } else {
  $result = 0;
  // sum each of the character*(base^i)
  for ($i=strlen($string)-1; $i>=0; $i++) {
   $result += $string[$i]*pow($base,$i);
  }
  return $result;
 }
}
// perform the actual match
function match_rabinKarp($needle, $haystack) {
 $needle = substr($needle);      // remove capitals
 $haystack = substr($haystack);  // remove capitals
 $m = strlen($needle);           // length of $needle
 $n = strlen($haystack);         // length of $haystack
 $h_haystack = hash($haystack);  // hash of $haystack
 $h_needle = hash($needle);      // hash of $needle
 // whittle away at the $haystack until we find a match
 for ($i=0;$i<$n-$m+1;$i++) {
  if ($h_needle == $h_haystack) {
   if (substr($haystack,$i,$i+$m-1) == $needle) {
    return $i;
   }
  }
 }
 return false;
}