11

JavaでRabin-Karpアルゴリズムを実装しようとしています。ローリングハッシュ値を一定時間で計算するのに苦労しています。http://algs4.cs.princeton.edu/53substring/RabinKarp.java.htmlで 1 つの実装を見つけました。それでも、これらの 2 つの行がどのように機能するかを理解できませんでした。

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;
txtHash = (txtHash*R + txt.charAt(i)) % Q;

剰余算術に関する記事をいくつか見ましたが、私の分厚い頭蓋骨に突き刺さる記事はありませんでした。これを理解するための指針を教えてください。

4

2 に答える 2

6

これは、ハッシュの「ローリング」の側面です。最も古いキャラクターの貢献 ( ) を削除しtxt.charAt(i-M)、最新のキャラクター ( ) の貢献を取り入れていtxt.charAt(i)ます。

ハッシュ関数は次のように定義されます。

            M-1
hash[i] = ( SUM { input[i-j] * R^j } ) % Q
            j=0

(ここでは^、「のちから」を表すために使用しています。)

しかし、これは効率的な再帰的実装として次のように書くことができます。

hash[i] = (txtHash*R - input[i-M]*(R^M) + input[i]) % Q

参照コードはこれを行っていますが、さまざまな手法を使用して、結果が常に正しく (そして効率的に) 計算されるようにしています。

したがって、たとえば、+ Q最初の式の には数学的な効果はありませんが、合計の結果が常に正になることが保証されます (負になると% Q、望ましい効果が得られません)。また、おそらく数値のオーバーフローを防ぐために、計算を段階に分割しています。

于 2011-05-24T13:07:07.557 に答える