如何在局部敏感哈希 (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 的魔力（为什么它比许多其他常数更有效，无论是否为素数）从未得到充分解释。

Answer 2

@Kuzeko：我和楼主有同样的问题。在您的回复中，您避免使用变量“val”来回答问题。这是否指的是列中的每个值？或者它是该列元素中所有值的总和？

如果引用该列所有元素的所有值，那么如何将它们合并为一个值与其他列进行比较？

我认为我们必须假设您回复中的“val”是指所有列元素的总和，因为这似乎是解释它的唯一有用方法。