テキストに現れる、長さ m (mは照合パターンの長さ)の文字列すべてに対してハッシュ関数の値を計算し、その値が照合パターンのそれと一致するかどうかを調べることで文字列照合を行う方法。ラビンとカープ氏による。ハッシュ関数に h(k) = k mod q を使う。ここに、 q(ハッシュ表の大きさ)は大きな素数。ハッシュ表は実際に用意する必要がないことから q として非常に大きな素数を選ぶことができる。

この方法ではまず照合パターンのハッシュ関数値 h1 を、つぎにテキスト最初の m 文字分のハッシュ関数値 h2 を計算する。そのあとテキスト上の照合開始位置を右にずらしながら、ハッシュ関数値を漸化式によって計算し、その値と h1 との比較を繰り返す。

<関数名>
  rkMatch ラビン-カープによる文字列照合アルゴリズム
  rkHash 照合パターンのハッシュ関数値

<形式>
  文字列照合
    char *rkMatch(char *text, int len, int patlen,
        unsigned long patHash, unsigned long dm);

  照合パターンのハッシュ関数値
    unsigned long rkHash(unsigned long *dm, char *pattern, int patlen);

<引数>
  文字列照合関数において
    text   (入力) テキスト
    len    (入力) テキストの長さ
    patlen  (入力) 照合パターンの長さ
    patHash (入力) 照合パターンのハッシュ関数値
    dm    (入力) 256m-1 % の値

  照合パターンのハッシュ関数値の関数において
    dm    (入出力) 256m-1 % の値
    pattern (入力) 照合パターン
    patlen  (入力) 照合パターンの長さ

<関数値>
  文字列照合関数について
    照合パターンがテキストから見つかった場合はそのポインタ、
    見つからなかった場合は 0 (NULL)。

  照合パターンのハッシュ関数値の関数において
    照合パターンのハッシュ関数値

<注意事項>
  rkPattern() を呼び出して照合パターンのハッシュ関数値を算出した後、
  文字列照合関数 rkMatch() を利用すること。

用例

<関数本体>
  rkMatch.c

<説明>
  この方法の計算量 O(m+n) 。違う文字列が同じハッシュ関数値をもつことは理論的には否定できないが、大きな素数 q を選べば実用上その問題を無視してよい。

Comments are closed.

Post Navigation