問題タブ [rabin-karp]

私は CLRS を読んでいます。この行に出くわしたという点で、「任意の ts が q を法として p に等しくなる可能性が推定できるため、スプリアス ヒットの数は O(n/q) であると予想できます。 1/q として」

34.2トピックの下に完全な説明を含むWebサイトを掲載しています

スプリアス ヒット = O (n/q) を期待する方法を説明してください。

参考までにhttp://staff.ustc.edu.cn/~csli/ Graduate/algorithms/book6/chap34.htm

ここで Rabin-Karp アルゴリズムを理解しようとしていました: http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html。

さまざまな記事を調べたところ、多項式ハッシュの一般的な形式は C1*A^k-1+C2*A^k-2+C3*A^k-3 であることがわかりました。コードを見ると、文字列の数字をどのように加算および減算するかがわかりました。

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

ここで、プログラムは先頭の数字を減算し、ハッシュ全体を乗算してから、新しい数字を追加しています。しかし、ハッシュを計算する関数を調べたところ、多項式ハッシュの一般的な形式に従っていませんでした。次のように見えました。

この関数では、ハッシュと基数を乗算してから、key.charAt() を追加しています。関数が key.charAt() に R^k-1 から始まるベースを掛けていると思います。次に、for ループが続くと、基数が R で除算され、多項式の累乗が減少します。この関数がどのように機能し、上記の形式でハッシュをどのように生成するかを誰か説明してもらえますか? ありがとう！

複数のパターン検索に Rabin Karp アルゴリズムを使用することはわかりません。インターネットで探してみました。私は欲しいと思いましたが、残念ながらgolangで。このコードを PHP で使用する方法、または PHP で使用できますか?

出力

完全なコード

Rabin-Karp アルゴリズムの最悪の場合の実行時間が O(nm) であり、平均的な場合が O(n+m) である理由を理解しようとしています。

誰かがそれを手伝ってくれますか？

f# で巡回多項式ハッシュ関数を実装しようとしています。ビット単位の演算子 ^^^ と <<< を使用します。配列をハッシュする関数の例を次に示します。

私の問題は、 の型'aが に制約されることですがint、この関数は、ビット単位の演算子で機能する任意の型 (たとえば、char. を使用してみinlineましたが、ライブラリのさらに下の方で問題が発生します。を使用せずにこれを修正する方法はありinlineますか?

わかりやすくするために編集: 関数はライブラリの一部になり、ビット単位の演算子をサポートしない型には別のハッシュ関数が提供されます。この関数を数値型および/または文字の配列で動作させたいです。

編集2（問題解決）：インラインの問題は、ライブラリから関数をロードする方法でした。それ以外の

私はこのバインディングを使用しました：

関数はライブラリ内の関数ですが、入力型myFunctionを int に制約します。関数の呼び出し方法を変更すると、型制約の問題が修正され、以下の回答が示すように完全に正常に動作します。createBuzhashinlineinline

サブストリングを検索する Rabin-Karp アルゴリズムの実装に興味があります。これが私が使用したアルゴリズムです: algorithm .

私が同じために作ったコードは以下の通りです。しかし、出力は空白です。ビルドが成功したと表示されますが、出力はありません...

多くの重複排除ライブラリまたはアプリケーションは、Rabin Karp ローリング ハッシュ アルゴリズムを適用して高速ハッシュを行い、ファイル バイナリからチャンクを切り出します。
私の質問は、なぜ Rabin Karp アルゴリズムがチャンクの切断によく使用されるのでしょうか?
私はそれが高速ローリング ハッシュ アルゴリズムであることを知っていますが、私の質問はより基本的なものです。
チャンクをカットする方法はたくさんあります。
たとえば、1 バイト (mod 操作なし) を値と比較してチャンクをカットすると、平均で 256 バイトのチャンクになります。
9 ビットを比較すると、平均で 512 バイトのチャンクに
なります。ハッシュ化せずに最後の数ビットを比較するだけでは、Rabin Karp などのローリング ハッシュ アルゴリズムに似ていますが、高速になるのでしょうか?

Rabin Karp 部分文字列検索アルゴリズムでは、次のようになります。

1) 部分文字列のハッシュを計算する 2) スライディング ウィンドウ [部分文字列のサイズに等しい] を取得し、ウィンドウ内に存在する文字列のハッシュを部分文字列のハッシュと比較します。3) ハッシュが一致する場合、ウィンドウの内容を部分文字列と比較します。

質問: 1) ハッシュを最初に照合してから比較することにより、パフォーマンスの点でどのようなメリットがありますか? なぜ単純に比較できないのですか？ハッシュの比較はより高速になる可能性がありますが、どのように（取得できませんでした）？