拉宾卡普滚动哈希生成的哈希不反映在文本

注意：很多可能的重复，但似乎没有解决我的问题。拉宾卡普滚动哈希生成的哈希不反映在文本

我正在根据MOSS进行抄袭检测。

后成功实现一个过滤器剥离了所有必要的细节（注释，标点符号等）1散列使用滚动哈希实现（拉宾卡普）

内容然而散列其匹配在两个文本文件源代码，有非常不同的基础文本（没有抄袭，但相同的哈希值）

算法我实现了（红宝石） - > （部分摘录）

#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

是否有ISS与我的实施？或者我指定的参数可能有问题？（我不知道它是否是正确的值，我假设剥去的文本将只包含字母+一些特殊字符，如'+'，' - '，'*'， “/”，因此共有34个字符的粗略估计）

我拿着q（总理）是101

这是我处理的冲突问题？任何关于如何解决问题的指针？

来源

2012-01-15 Nitish Upreti

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

当然，你也应该测试你的程序，在有重复字符串的情况下找到 - 失败可能会导致任何问题的另一个症状，这也会导致冲突，并且它会更容易找到和调试。

来源

2012-01-15 08:07:38 mcdowella

将q增加到1001肯定会进一步限制比赛，但仍然存在与底层文本不同的虚假匹配。 – 2012-01-15 08:52:44

你认为什么是基数的最佳值？ – 2012-01-15 08:59:03

我会让基数比您期望的最大字符值大。然后，文本散列将由其散列的字符序列唯一确定，除了它是计算mod q的事实。请注意，即使对于非常大的q值，您也可能会发生一些碰撞 - 这是http://en.wikipedia.org/wiki/Birthday_problem的示例。 – mcdowella 2012-01-15 12:50:23

拉宾卡普滚动哈希生成的哈希不反映在文本

回答

相关问题