Rabin Karp RollingHashによって生成されたハッシュがテキストに反映されていない
-
28-10-2019 - |
質問
注:重複の可能性はたくさんありますが、私の問題を解決しているものは何もないようです。
MOSS に基づく盗用検出に取り組んでいます。
必要なすべての詳細(コメント、句読点など)を取り除くフィルターの実装に成功した後、ローリングハッシュ実装(ラビンカープ)を使用してコンテンツをハッシュします
ただし、ソースコードの2つのテキストファイルで一致するハッシュは、基になるテキストが大きく異なります(盗用はなく、同じハッシュです)
私が実装したアルゴリズム(Ruby)-> (部分スニペット) ジェネラコディセタグプレ
実装に問題はありますか?または、指定したパラメータに問題がある可能性がありますか?
基数= 34を取ります (それが正しい値であるかどうかはわかりません。削除されたテキストにはアルファベットと「+」、「-」、「*」、「/」などの特殊文字のみが含まれると想定しているため、合計34の概算です。文字)
q(prime)を101としています
これは私が扱っている衝突の問題ですか?問題に取り組む方法について何かアドバイスはありますか?
解決
q= 101の場合、可能なハッシュ値は101のみ(0、1、2 ... 100)であることに注意してください。qを増やしてみましたか?別のアプローチは、ハッシュ値が0,1..q-1の可能な値内でランダムに選択された値であるように見えるかどうかを確認することです。
もちろん、プログラムを見つけるために文字列が繰り返される場合にもプログラムをテストする必要があります。失敗すると、衝突を引き起こしている問題の別の症状が発生する可能性があり、見つけてデバッグするのが簡単になります。
所属していません StackOverflow