問題タブ [rabin-karp]

これは、C＃でのRabin-Karp文字列照合アルゴリズムの実装です...

}

しかし、結果がコピーされていないことを示すよりも2番目の文字列の位置を変更すると、1つの問題が発生します。

ここではコピーされていないことを示しています

最初の文字列からのコピーかどうかを確認したいのですが、何かを追加したり、位置を変更したりしますが、違いはないので、文字列内の各単語のハッシュを比較するように変更する方法は、実装する............

Cormenなどによるアルゴリズムの概要で文字列アルゴリズムについて読んでいます

以下は、いくつかの基本的な数論的表記法に関するテキストです。

注：以下のテキストでは、==をモジュロ等価として参照します。

ある整数を別の整数で割ったときの余りの概念が明確に定義されている場合、余りが等しいことを示すために特別な表記法を提供すると便利です。（a mod n）=（b mod n）の場合、a == b（mod n）と記述し、aはnを法とするbと同等であると言います。言い換えると、aとbの余りがnで割ったときに同じ余りがある場合、a == b（mod n）になります。同様に、n |の場合に限り、a == b（mod n）（b-a）。たとえば、61 == 6（mod 11）です。また、-13 == 22 == 2 ==（mod 5）。

整数は、nを法とする剰余に従ってn個の同値類に分割できます。整数aを含むnを法とする同値類は

[a] n = {a + kn：kZ}。

たとえば、[3] 7={。。。、-11、-4、3、10、17 、。。。}; このセットの他の表示は[-4]7と[10]7です。

[b] nに属するaを書くことは、a == b（mod n）を書くことと同じです。そのようなすべての同値類のセットは

Zn = {[a] n：0 <= a <= n-1} .----------> Eq 1

上記のテキストでの私の質問は、式1で、「a」は0からn-1の間にあるべきであると述べられていますが、たとえば、0から6の間にない-4として与えられているのはなぜですか？

上記に加えて、ラビン-カープアルゴリズムでは、3番目の数を法として2つの数の等価性を使用することが述べられていますか？これは何を意味するのでしょうか？

Introduction to Algorithms by Cormen などで Rabin-Karp アルゴリズムを読んでいます。

www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt

== が mod 演算子として使用されていることに注意してください

上記のスライド 13 の注記、つまり式 34.2 は、ここに図として添付されています。方程式では、h == (d)powerof((m-1) (mod q) は、m 桁のテキスト ウィンドウの上位位置にある桁 "1" の値です。

ここでの私の質問は、「m桁のテキストウィンドウの上位位置にある数字「1」の値」とはどういう意味ですか?

スライド 14 で、著者はどのようにして (7-3.3).10 + 2 (mod 13) を 8 (mod 13) として得たのでしょうか?

Average case analysis では、q を法として値を減らすことは sigma* から Z へのランダムなマッピングのように機能するという仮定に基づいてヒューリスティック分析を行うことができると述べられています。

私は、 MOSSの Idea を使用する小さな剽窃検出エンジンに取り組んでいます。ローリング ハッシュ関数が必要です。Rabin-Karp アルゴリズムから着想を得ています。

私が書いたコード -->

私は値でそれを実行しています --> calc_hash(text,5,101) ここで、テキストは文字列入力です。

コードは非常に遅いです。どこが間違っていますか？

注：重複の可能性がたくさんありますが、私の問題を解決しているようには見えません。

私はMOSSに基づく剽窃検出に取り組んでいます。

必要なすべての詳細 (コメント、句読点など) を取り除くフィルターの実装に成功した後、ローリング ハッシュ実装 (Rabin Karp) を使用してコンテンツをハッシュします。

ただし、ソース コードの 2 つのテキスト ファイルで一致するハッシュは、基になるテキストが大きく異なります (盗作はなく、ハッシュは同じです)。

実装したアルゴリズム(Ruby) --> (部分抜粋)

実装に問題はありますか? または、指定したパラメーターに問題がある可能性がありますか?

私は基数= 34を取ります（それが正しい値であるかどうかはわかりません。取り除かれたテキストには、アルファベットと「+」、「-」、「*」、「/」などの特殊文字のみが含まれると想定しています。合計34文字の概算）

q(prime) を 101 としています

これは私が扱っている衝突の問題ですか? 問題に取り組む方法についての指針はありますか？

数週間前、大量のテキスト内のパターンを検索するための効率的なアルゴリズムの作成について、Stackoverflowに質問を投げかけました。現在、文字列関数indexOfを使用して検索を行っています。1つの提案は、代わりにRabin-Karpを使用することでした。次のようにRabin-Karpの実装をテストするために、次のように小さなテストプログラムを作成しました。

そして、これが私が使用しているRabin-Karpの実装です。

Rabin-Karpの実装は、探している文字列の正しいオフセットを返すという点で機能します。しかし、私が驚いたのは、テストプログラムを実行したときに発生したタイミング統計です。はい、どうぞ：

これは本当に驚きでした。Rabin-Karp（少なくともここで実装されている）は、標準のjava indexOf String関数よりも高速ではないだけでなく、桁違いに低速です。何が悪いのかわかりません（もしあれば）。誰かがこれについて考えていますか？

ありがとう、

エリオット

こんにちは、Rabin-Karp アルゴリズムを実装するための PHP クラスを作成しています。一部の再ハッシュに問題があります。このコードには、文字の一致する部分は含まれていません。再ハッシュの問題により、ハッシュコードが一致しないため、停止する必要がありました。誰かがそれを理解するのを手伝ってください。

ありがとうございました。

ウィキに記載されているように、サブ文字列を検索するためのラビン-カープアルゴリズムの実装に興味があります：http：//en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm。宿題のためではなく、利己心のためです。Rabin-Karpアルゴリズム（以下に表示）を実装しましたが、機能します。しかし、パフォーマンスは本当に、本当に悪いです!!! 私のハッシュ関数は基本的なものだと理解しています。ただし、strstr（）を呼び出すだけで、関数rabin_karp（）よりも常にパフォーマンスが向上するようです。理由は理解できます。ハッシュ関数は、各ループを単純な文字ごとに比較するよりも多くの作業を行っています。ここで何が欠けていますか？Rabin-Karpアルゴリズムは、strstr（）の呼び出しよりも高速である必要がありますか？ラビン-カープアルゴリズムが最適に使用されるのはいつですか？したがって、私の利己心。アルゴリズムを正しく実装しましたか？

ウェブサイトのフォーラムでこの Rabin Karp 文字列マッチング アルゴリズムを見たことがあり、それを実装することに興味がありますが、変数 ulong Q と ulong D がそれぞれ 100007 と 256 である理由を誰かが教えてくれるかどうか疑問に思っていました :S ? これらの価値観にはどのような意味がありますか?

Rabin Karp アルゴリズムを使用して、ファイルをチャンクにスライスすることになっている ac プログラムを作成しました。これは、ここにある ac# プログラムを改造したものです。

動作しているように見えますが、問題が残ります。平均チャンク サイズが期待どおりではありません。

使用方法は次のとおりです。

Rabin Prime WindowSize BoundaryMarker ファイル

どこ ：

Rabin は実行可能ファイルの名前です。

プライムは高い素数です。たとえば、100007

WindowSize は、ローリング ウィンドウのサイズです。たとえば 48

BoundaryMarker は、フィンガープリントで 0 に設定されたビット数です。

File は処理するファイルです

BoundaryMarker を 13 に設定すると、平均チャンク サイズは 8K になると予想されます。実際、それらのどれもが約 8K ではありません。

プログラムの何が問題なのかを理解するのに苦労していますか? 手伝って頂けますか ？

ありがとう