我了解通过应用哈希函数从瓦片创建签名矩阵背后的算法。然而,我不明白如何将签名矩阵中的特定带散列到桶中。假设在矩阵M的频带b1中,我们对文档C1-C5具有以下值:
C1 C2 C3 C4 C5
1 0 0 0 2
3 2 1 2 2
0 1 3 1 1
通过查看这些值,我们可以看到C2和C4在这个带中是相同的,它们应该散列到同一个桶中。但其他列将散列到不同的桶中。
我的问题是如何将这些列散列到桶中,并在不进行实际比较的情况下知道它们是否相同。我应该如何定义散列函数来将列映射到bucket?比如列中元素的总和?
简单的方法,假设您有1024个桶
hash = 1
for val in column:
hash = (( hash * 33 ) + val ) % 1024
% 1024
必然是您拥有的存储桶数。33
是一个神奇的数字,在实际应用中能很好地与字符串配合使用
数字33的神奇之处(为什么它比许多其他常数更好用,无论是否素数(从未得到充分解释。
请参阅http://www.cse.yorku.ca/~oz/hash.html