hash - 如何在局部敏感散列 (LSH) 中将签名矩阵散列到存储桶

Question

我了解通过应用哈希函数从带状疱疹创建签名矩阵背后的算法。但是我不明白如何将签名矩阵中的特定波段散列到桶中。假设在矩阵 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 在这个波段中是相同的，它们应该散列到同一个桶中。但其他列将散列到不同的桶中。

我的问题是如何将这些列散列到桶中，并在不实际比较它们的情况下知道它们是否相同。我应该如何定义哈希函数以将列映射到存储桶？像列中元素的总和？

Answer 1

简单的方法，假设你有 1024 个桶

hash = 1 
for val  in column:
   hash = (( hash * 33 )  +  val ) % 1024

这% 1024必然是您拥有的桶数。 33是一个神奇的数字，在字符串的实践中效果很好

数字 33 的魔力（为什么它比许多其他常数工作得更好，无论是否素数）从未得到充分解释。

见http://www.cse.yorku.ca/~oz/hash.html