注意:很多可能的重复项,但似乎没有解决我的问题。
我正在研究基于 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
这是我正在处理的碰撞问题吗?关于如何解决该问题的任何指示?
最佳答案
我注意到当 q = 101 时,只有 101 个可能的哈希值 - 0、1、2...100。你试过增加q吗?另一种方法是查看散列值是否看起来像是在 0,1..q-1 的可能值内随机选择的值。
当然,您还应该在有重复字符串的情况下测试您的程序 - 失败可能是任何问题的另一种症状,也会导致冲突,并且更容易找到和调试。
关于ruby - Rabin Karp Rolling Hash 生成的哈希未反射(reflect)在文本上,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8868124/