34

我热衷于尝试实施 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) 的错误率？

4

5 回答 5

24

生成 200 个散列值的一种方法是使用良好的散列算法生成一个散列值，并通过将好散列值与 199 组具有与好散列值相同长度的随机位进行异或运算来廉价地生成 199 个值（即，如果您的好的散列是 32 位，建立一个 199 个 32 位伪随机整数的列表，并将每个好的散列与 199 个随机整数中的每一个进行异或）。

不要_如果您使用无符号整数（有符号整数很好），只需旋转位即可廉价地生成哈希值——这通常会一遍又一遍地选择相同的瓦。将位向下循环一位与除以 2 并将旧的低位复制到新的高位位置相同。大约 50% 的好散列值的低位为 1，因此当低位旋转到高位位置时，它们将具有巨大的散列值，而不会祈祷成为最小散列。当您移动一位时，其他 50% 的良好哈希值将简单地等于它们的原始值除以 2。除以 2 不会改变哪个值最小。所以，如果给出具有良好散列函数的最小散列的木瓦恰好在低位中有一个 0（50% 的机会），当您移动一位时，它将再次给出最小散列值。举个极端的例子，如果来自良好散列函数的具有最小散列值的瓦的散列值恰好为 0，那么无论您旋转多少位，它都将始终具有最小散列值。有符号整数不会出现此问题，因为最小哈希值具有极端负值，因此它们往往在最高位有 1，后跟零（100...）。因此，只有最低位为 1 的哈希值在向下旋转一位后才有机会成为新的最低哈希值。如果具有最小哈希值的木瓦的最低位为 1，则在向下旋转一位后，它将看起来像 1100...，

于 2013-10-31T16:14:47.563 回答
18

差不多.. 但 28% 将是“误差估计”，这意味着报告的测量结果通常会不准确 +/- 28%。

这意味着报告的 78% 的测量值很容易仅来自 50% 的相似性。或者 50% 的相似性很容易被报告为 22%。对我来说，对于商业预期来说，这听起来不够准确。

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

为什么要将哈希函数的数量减少到 12 个？“200 个哈希函数”的真正含义是，为每个 shingle/string 计算一次质量不错的哈希码 - 然后应用 200 个廉价且快速的转换，以强调某些因素/将某些位放在前面。

我建议将按位旋转（或洗牌）和XOR 操作结合起来。每个散列函数可以通过一些位组合旋转，然后通过随机生成的整数进行异或。

这既“传播”了 min() 函数在位周围的选择性，也传播了 min() 最终选择的值。

轮换的基本原理是，“min(Int)”将在 256 次中的 255 次中仅选择 8 个最高有效位。只有当所有高位都相同时，低位才会在比较中产生任何影响。因此，扩展对于避免过度强调瓦片中的一两个字符很有用。

XOR 的基本原理是，就其本身而言，按位旋转 (ROTR) 可以 50% 的时间（当从左侧移入 0 位时）收敛到零，这将导致“单独的”散列函数显示不受欢迎的倾向于一起趋向于零 - 因此他们过度倾向于最终选择相同的带状疱疹，而不是独立的带状疱疹。

有符号整数有一个非常有趣的“按位”怪癖，其中 MSB 是负数，但所有后续位都是正数，这使得有符号整数的旋转收敛趋势不太明显——这对于unsigned很明显。无论如何，在这些情况下仍必须使用 XOR。

Java 内置了 32 位哈希码。如果您使用 Google Guava 库，则可以使用 64 位哈希码。

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

于 2013-10-31T08:17:44.370 回答
12

你想要的东西可以很容易地从通用散列中得到。像Corman 等人这样的流行教科书在 11.3.3 pp 265-268 节中作为非常易读的信息。简而言之，您可以使用以下简单等式生成哈希函数族：

h(x,a,b) = ((ax+b) mod p) mod m
  • x 是您要散列的键
  • a 是您可以在 1 到 p-1 之间选择的任何奇数。
  • b 是您可以在 0 到 p-1 之间选择的任何数字。
  • p 是大于 x 的最大可能值的素数
  • m 是您想要的哈希码 + 1 的最大可能值

通过选择不同的 a 和 b 值，您可以生成许多相互独立的哈希码。

这个公式的优化版本可以在 C/C++/C#/Java 中实现如下：

(unsigned) (a*x+b) >> (w-M)

这里， - w 是机器字的大小（通常为 32） - M 是您想要的哈希码的大小（以位为单位） - a 是适合机器字的任何奇数 - b 是小于 2^(wM) 的任何整数

以上适用于散列数字。要散列字符串，请使用 GetHashCode 等内置函数获取可以获取的散列码，然后在上述公式中使用该值。

例如，假设您需要 200 个字符串 s 的 16 位哈希码，则可以编写以下代码作为实现：

public int[] GetHashCodes(string s, int count, int seed = 0)
{
    var hashCodes = new int[count];
    var machineWordSize = sizeof(int);
    var hashCodeSize = machineWordSize / 2; 
    var hashCodeSizeDiff = machineWordSize - hashCodeSize;
    var hstart = s.GetHashCode();
    var bmax = 1 << hashCodeSizeDiff;
    var rnd = new Random(seed);     

    for(var i=0; i < count; i++) 
    {
        hashCodes[i] = ((hstart * (i*2 + 1)) + rnd.Next(0, bmax)) >>  hashCodeSizeDiff;
    }
}

笔记：

  1. 我使用哈希码字长作为机器字长的一半，在大多数情况下为 16 位。这并不理想，而且发生碰撞的可能性要大得多。这可以通过将所有算术升级到 64 位来使用。
  2. 通常，您希望在上述范围内随机选择 a 和 b。
于 2014-08-03T11:06:43.447 回答
4

只需使用 1 个哈希函数！（并保存1/(f ε^2)最小值。）

查看这篇文章，了解最先进的实践和理论界限。它有这个漂亮的图表（下图），解释了为什么您可能只想使用一个 2 独立哈希函数并保存k最小值。

在估计集合大小时，该论文表明您可以获得一个相对误差，大约ε = 1/sqrt(f k)是fJaccard 相似度和k保留值的数量。因此，如果你想要 error ε，你需要k=1/(fε^2)或者如果你的集合有相似性1/3并且你想要一个10%相对错误，你应该保留300最小值。

图形

于 2016-10-06T12:23:40.620 回答
1

似乎获得 N 个良好散列值的另一种方法是用 N 个不同的盐值对相同的散列进行加盐。

在实践中，如果第二次应用盐，您似乎可以散列数据，然后“克隆”散列器的内部状态，添加第一个盐并获得第一个值。您将此克隆重置为干净的克隆状态，添加第二个盐，并获得第二个值。冲洗并重复所有 N 项。

可能不如对 N 值的 XOR 便宜，但似乎有可能以最小的额外成本获得更好的质量结果，特别是如果被散列的数据远大于盐值。

于 2015-01-28T20:13:20.230 回答