問題タブ [rabin-karp]

Rabin-Karp 文字列マッチング アルゴリズムに関するウィキペディアのエントリによると、線形の複雑さを維持しながら、文字列内の複数の異なるパターンを同時に検索するために使用できます。すべてのパターンが同じ長さの場合、これが簡単に実行できることは明らかですが、長さが異なるパターンを同時に検索するときに O(n) の複雑さを維持する方法はまだわかりません。誰かがこれに光を当てることができますか？

編集（2011年12月）：

ウィキペディアの記事はその後更新され、O(n) で異なる長さの複数のパターンに一致すると主張しなくなりました。

誰かが Rabin-Karp アルゴリズムのソースを共有できるかどうか疑問に思っていましたか?

ありがとう

非常に大きな文字列の n-gram のハッシュを取得できるように、ローリング ハッシュ関数を使用しようとしています。

例えば：

「stackoverflow」を 5 グラムに分割すると、次のようになります。

「stack」、「tacko」、「ackov」、「ckove」、「kover」、「overf」、「verfl」、「erflo」、「rflow」

これはローリング ハッシュ関数に最適です。最初の n グラム ハッシュを計算した後、最初のハッシュの最初の文字を削除し、2 番目のハッシュの新しい最後の文字を追加するだけで済むため、次のハッシュは比較的安価に計算できます。 .

一般に、このハッシュ関数は次のように生成されることを知っています。

H = c ₁ a ^{k − 1} + c ₂ a ^{k − 2} + c ₃ a ^{k − 3} + ... + c _k a ⁰ a は定数、c1,...,ck は入力文字です。

Rabin-Karp string search algorithmでこのリンクをたどると、「a」は通常、大きな素数であることが示されます。

ハッシュを 32 ビット整数で格納したいのですが、整数がオーバーフローしないように、「a」はどのくらいの大きさにすればよいですか?

既に使用できるこのハッシュ関数の既存の実装がどこかに存在しますか?

これが私が作成した実装です：

私は素数として 101 を使用しています。ハッシュがオーバーフローしても問題ありませんか? これは望ましいと思いますが、よくわかりません。

これはこれを行う正しい方法のように思えますか?

私はC++でRabin-Karp文字列照合関数に取り組んでいますが、結果が得られません。一部の値を正しく計算していないように感じますが、どれが正しいかわかりません。

プロトタイプ

関数の実装

私の関数呼び出しでは、シーケンスとして2359023141526739921、パターンとして31415、基数として10、素数として13を渡します。実際の一致が1つ、スプリアスヒットが1つあると予想しますが、関数の一致部分から出力ステートメントを取得することはありません。私は何が間違っているのですか？

よろしくお願いします、マディソン

Rabin–Karp文字列検索アルゴリズムに関連するいくつかの問題を解決しています。このアルゴリズムでは、ローリングハッシュを単純な検索よりも高速にする必要があります。この記事では、ローリングハッシュを実装する方法について説明します。「ラビン-カープローリングハッシュ」を問題なく実装しましたが、実装の実装はほとんどありませんでしたが、計算の複雑さについても言及されており、循環多項式によるn-gramのハッシュが推奨されています。これは、そのような手法のBuzHash実装にリンクしていますが、その上にn-gramハッシュを構築するためにどのように使用できるのでしょうか。このようなものが欲しい、または

Javaの場合。

文字列検索に関連する問題に遭遇する人（私のように）のために、私が有用だと思った記事がいくつかあります：1、2、3

Knuth-Morris-Pratt、Rabin-Karp などのほかに、利用可能な文字列マッチング アルゴリズムは何ですか?

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

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

このおそらく繰り返される質問についてお詫び申し上げます。

Karp Rabin でローリング ハッシュを使用しようとしています。ローリング ハッシュの別の実装を調べましたが、どこが間違っているのか疑問に思っています。テキストにはパターンがありますが、ハッシュを使用した一致はまったく発生していないようです。ハッシュと検索を計算するためのコード (の一部) を添付します。

私は対処したバッファオーバーフローの問題を抱えていましたが、パターンとテキストハッシュはタンパク質配列テキスト文字列(1000文字)と17文字のパターンに一致していないようです私が間違っている可能性のあるアイデアはありますか?

ありがとう、バーヴィア

私の以前の質問は、一般的な文字列検索アルゴリズムに関するものでした。私はラビン-カープアルゴリズムを研究していて、次のような関数テンプレートを持っています。

search_phraseとtextに応じて、基数と素数の値がどのように変化するか知りたいですか？それとも、すべての場合に任意の値を指定する必要がありますか？

私はRabin–Karpアルゴリズムを使用して、任意の2つのソースコードファイルの盗用をチェックしているので、最初にそのアルゴリズムをc＃ここでそのコードに実装しますが、その平均および最良の実行時間は空間O（p）でO（n + m）です。 、ただし、最悪の場合の時間はO（nm）です。

それで、これよりも優れているので、ローリングハッシュ関数を使用してそれをより効率的にするにはどうすればよいでしょうか。