Rabin Karp 滚动哈希生成的哈希未反映在文本上

Question

注意：有很多可能的重复项，但似乎没有什么可以解决我的问题。

我正在研究基于 MOSS 的抄袭检测。

成功实现删除所有必要细节（注释、标点符号等）的过滤器后，我使用滚动哈希实现（Rabin Karp）对内容进行哈希处理，

但是在源代码的两个文本文件中匹配的哈希值具有非常不同的底层文本（没有抄袭，但哈希值相同）

我实现的算法（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

这是我正在处理的碰撞问题吗？有关如何解决该问题的任何指示吗？

Answer 1

我注意到，当 q = 101 时，只有 101 个可能的哈希值 - 0、1、2...100。你试过增加q吗？另一种方法是查看哈希值是否看起来像是在 0,1..q-1 可能值内随机选择的值。

当然，您还应该在存在重复字符串的情况下测试您的程序以供查找 - 失败可能是任何问题的另一种症状，也会导致冲突，并且会更容易查找和调试。