我热衷于尝试实施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操作。每个哈希函数可以将旋转组合一定数量的位，然后对随机生成的整数进行XOR。
这既“扩展”了min（）函数在位周围的选择性，又使min（）最终选择了什么值。
旋转的理由是，“ min（Int）”将在256个值中进行255次选择，仅在8个最高有效位中进行选择。仅当所有高位相同时，低位才会对比较产生任何影响..因此，扩展可能会有用，以避免过多地强调木瓦中的一个或两个字符。
XOR的基本原理是，按位旋转（ROTR）本身可以在50％的时间内（当0位从左边移入时）收敛到零，这将导致“单独的”哈希函数显示不理想的值趋于同时趋于零的趋势-因此，他们过度倾向于最终选择相同的带状疱疹，而不是独立的带状疱疹。
有一个非常有趣的有符号整数的“按位”怪癖，其中MSB为负，但随后的所有位均为正，这使得旋转趋势趋于收敛，而对于有符号整数则不那么明显-对于无符号整数，这是显而易见的。无论如何，仍必须在这些情况下使用XOR。
Java具有内置的32位哈希码。而且，如果您使用Google Guava库，则可以使用64位哈希码。
感谢@BillDimm的投入和坚持，指出XOR是必要的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句