3

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

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

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

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

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

 #Preprocessing from RobinKarp Algorithm
  for c in 0...k do
    text_hash=(radix*text_hash+text_to_process[c].ord)%q
  end

  #Main loop
  for c in 0...loop do   
        text_hash=((radix*text_hash-(text_to_process[c].ord)*highorder)+(text_hash[c+k].ord))%q

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

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

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

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

4

1 に答える 1

2

q = 101 の場合、考えられるハッシュ値は 0、1、2...100 の 101 のみであることに注意してください。qを増やしてみましたか？別のアプローチは、ハッシュ値が 0,1..q-1 の可能な値内でランダムに選択された値であるように見えるかどうかを確認することです。

もちろん、文字列が繰り返されている場合にプログラムをテストして、検出する必要があります。失敗すると、衝突を引き起こしている問題の別の症状が発生する可能性があり、検出とデバッグが容易になります。

于 2012-01-15T08:07:38.700 に答える