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

我热衷于尝试实施minhashing以查找几乎重复的内容。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列为默认值。

显然，随着散列数量的增加，准确性也有所提高，但是多少个散列函数是合理的呢？

引用博客

要使我们的相似性估计值上的误差条远小于[7％]，是很困难的，因为统计抽样值尺度上的误差条的方式-将误差条减少一半，我们将需要四倍的样本。

这是否意味着将哈希数减少到12（200/4/4）左右会导致28％（7 * 2 * 2）的错误率？

差不多..但是28％是“误差估计”，这意味着报告的测量值经常不准确+/- 28％。

这意味着所报告的78％的度量很容易仅来自50％的相似性。或者50％的相似性很容易被报告为22％。对我来说，听起来不够准确，无法满足业务期望。

从数学上讲，如果要报告两位数，则第二位应该有意义。

为什么要将哈希函数的数量减少到12个？“ 200个哈希函数”的真正含义是，为每个带状疱疹/字符串一次计算一个质量不错的哈希码-

然后应用200个廉价，快速的转换，以强调某些因素/将某些位放在前面。

我建议结合（或混排）和。每个哈希函数可以将旋转组合一定数量的位，然后对随机生成的整数进行XOR。

这既“扩展”了min（）函数在位周围的选择性，又使min（）最终选择了什么值。

旋转的基本原理是，“

min（Int）”将在256个中的255次中仅在8个最高有效位中进行选择。仅当所有高位相同时，低位才会对比较产生任何影响..因此，扩展可用于避免过分强调带状疱疹中的一个或两个字符。

XOR的基本原理是，按位旋转（ROTR）本身可以在50％的时间（当0位从左边移入时）收敛到零，这将导致“单独的”哈希函数显示不理想的值趋于同时趋于零的趋势-

因此，他们过度倾向于最终选择相同的带状疱疹，而不是独立的带状疱疹。

有一个非常有趣的有符号整数的“逐位”怪癖，其中MSB为负，但随后的所有位均为正，这使得旋转趋势趋于收敛，而对有 符号整数 则不那么明显-对于 无符号

整数，这是显而易见的。无论如何，在这些情况下仍必须使用XOR。

Java具有内置的32位哈希码。而且，如果您使用Google Guava库，则可以使用64位哈希码。

感谢@BillDimm的投入和坚持，指出XOR是必要的。