algorithm - 一个minhash算法需要多少个哈希函数

Question

我热衷于尝试实现最小哈希来查找几乎重复的内容。 http://blog.cluster-text.com/tag/minhash/写得很好，但问题是您需要在文档中的带状疱疹上运行多少哈希算法才能获得合理的结果。

上面的博文提到了大约 200 种哈希算法。 http://blogs.msdn.com/b/spt/archive/2008/06/10/set-similarity-and-min-hash.aspx列出 100 作为默认值。

显然随着哈希数量的增加准确率有所提高，但是多少哈希函数才是合理的呢？

引用自博客

It is tough to get the error bar on our similarity estimate much smaller than [7%] because of the way error bars on statistically sampled values scale — to cut the error bar in half we would need four times as many samples.

这是否意味着将哈希值的数量减少到 12 (200/4/4) 会导致 28% (7 * 2 * 2) 的错误率？

Answer 1

生成 200 个散列值的一种方法是使用良好的散列算法生成一个散列值，然后通过将良好的散列值与 199 组长度与良好的散列值相同的随机位进行异或来廉价地生成 199 个值(即，如果您的好散列是 32 位，则构建一个包含 199 个 32 位伪随机整数的列表，并将每个好散列与 199 个随机整数中的每一个进行 XOR)。

如果您使用无符号整数(带符号整数很好)，请不要简单地旋转位以生成哈希值，这通常会一遍又一遍地选择相同的木瓦。将位向下循环一位与除以 2 并将旧的低位复制到新的高位位置相同。大约 50% 的好散列值的低位为 1，因此当低位旋转到高位位置时，它们将具有巨大的散列值，而无需祈祷成为最小散列。当您移动一位时，其他 50% 的好散列值将简单地等于它们的原始值除以 2。除以 2 不会改变最小值。因此，如果给出具有良好哈希函数的最小哈希值的木瓦恰好在低位有 0(50% 的可能性)，当您移动一位时，它会再次给出最小哈希值。举个极端的例子，如果从好的散列函数中获得最小散列值的木瓦恰好有一个散列值 0，那么无论你如何旋转位，它总是具有最小散列值。有符号整数不会出现此问题，因为最小散列值具有极负值，因此它们往往在最高位为 1，后跟零 (100...)。因此，只有最低位为1的哈希值才有机会向下旋转一位后成为新的最低哈希值。如果具有最小哈希值的 shingle 的最低位为 1，则向下旋转一位后它看起来像 1100...，因此它几乎肯定会被具有 10... 的不同 shingle 击败。轮换后，避免了同一个木瓦有50%的概率连续被采摘两次的问题。