php - PHP の Rabin-Karp アルゴリズム

Question

誰かが Rabin-Karp アルゴリズムのソースを共有できるかどうか疑問に思っていましたか?

ありがとう

Answer 1

これは、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 2

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

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

ここにいくつかの情報源があります。

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;
}