問題タブ [rabin-karp]

Rabin-Karp アルゴリズムの効率的なハッシュ関数を探しています。これが私の実際のコードです（Cプログラミング言語）。

Rabin-Karp C の実装をいくつか検討しましたが、すべてのコードに違いがあります。私の質問は、Rabin-Karp ハッシュ関数が持つべき特性は何ですか?

Rabin-Karp 文字列検索アルゴリズムの実装に使用できる優れたハッシュ関数は何ですか? 私は多項式ハッシュしか知りませんが、いくつかの欠陥があります。最も顕著なのは、ハッシングが modulo 2 ⁶⁴で行われる場合、非常に頻繁に衝突が発生することが保証されているテストがあります (mod操作が非常に高価であるため、別の法を使用することは実用的ではありません) 。 . では、高速で書きやすい優れたハッシュ関数はありますか?

PS buzhash については知っていますが、他に代替手段があるかどうか疑問に思っています…</p>

私は Haskell の初心者であり、Rabin Karps アルゴリズムをプログラムする必要があります。私の答えはうまくいくはずですが、コンパイルすると「let」の解析エラーが発生し続けます。誰でも私を助けてくれませんか。

これが私のコードです：

文字列を検索するためのRabin-Karp アルゴリズムのqとd の選択について質問があります。このアルゴリズムは、値qをモジュラスとして使用し、 dをハッシュ関数として使用します。

2 乗の数としてqを選択し、d=q-1 または d=q+1を選択した場合

• これらの選択はスプリアス ヒットにどのように影響しますか?

• d=q+1 の場合と d=q-1 の場合にスプリアスが確実にヒットするパターンは？

Rabin-Karp アルゴリズムに基づいて、昇順で 2 つのテキスト ファイルの最長共通部分文字列を見つける関数を作成しました。メイン関数は「find_longest」で、内部関数は「make_hashtable」、「extend_fingerprints」、および「has_match」です。has_matchの平均的なケースの複雑さを分析するのに問題があります。

n1,n2 を text1,text2 として、l を現在の「ウィンドウ」のサイズとして示します。finger は部分文字列のハッシュ テーブルです。

これは「make_hashtable」です。ここでは、complexity が O(n2-l+1) であることを確信しています。

これは「find_longest」です。複雑さの分析には必要ないという事実にもかかわらず、この関数を追加しています。

これは「extend_fingerprints」です。

この2つのオプションの間に疑問があります:

1. O(n_2-l+1)+O(n_1-l+1)*O(l) r を定数として参照しますが、n1、n2 は非常に大きいため、ハッシュ テーブルで多くの衝突が発生します (すべての「セル」で O(1) アイテムとしますが、常にいくつかの「偽陽性」とします)。 "）

2.O(n_2-l+1)+O(n_1-l+1)+O(l)
適切なハッシュ関数に最適な r を参照してください。したがって、衝突はほとんどありません。つまり、ハッシュ テーブルで 2 つのテキストが同じセルである場合、それらは実際には同じテキストであると想定できますか?

個人的には大胆な声明に傾いています。tnx。

Coursera のビデオの 1 つでは、Rabin-Karp のローリング ハッシュ ( http://en.wikipedia.org/wiki/Rolling_hash ) が次のように示されています。

それは間違っていると思います。私はそれがあるべきだと思います：

どれが正しいですか、なぜですか?

次の疑似コードに従って、C#.NET で Rabin-Karp アルゴリズムを実装しました。

問題は、パターンが元のテキストと一致しないことです。コードを徹底的に調べましたが、コードの問題を特定できません。誰かが私のコードのバグを見せてもらえますか?

次のアルファベットを使用して文字列を生成しました。 {A,C,G,T}. 私の文字列には 10000 文字以上が含まれています。その中で以下のパターンを探しています。

• ATGGA
• TGGAC
• CCGT

O(m+n)実行時間のある文字列一致アルゴリズムを使用するように依頼しました。

どちらKMP and Rabin-Karp algorithmsもこの実行時間があります。この状況で (Rabin-Carp と KMP の間で) 最も適切なアルゴリズムは何ですか?