假设我们拥有一大批文档，希望找出其中哪些文档彼此近似相同。例如，我们可能在一段时间内爬取了网络，预期会多次抓取到“同一个页面”，但每次抓取到的元数据会有细微差异，或者同一个页面经过小幅修改后产生了多个版本。

在本文中，我想探讨一种通过 Jaccard 相似度与 MinHash 近似技巧实现近似去重的方法。这是解决该问题的一种常用手段（例如，GPT-3 论文就提到在数据集准备流程中使用了该方法），但我直到最近才接触到它，并觉得它相当有意思。

相似度

我们进行近似去重的基本思路是，先在任意两篇文档之间定义一种“相似度”，然后寻找相似度超过某一阈值的文档对。也就是说，如果存在一个由所有可能文档构成的全集 \(U\)，我们可以定义文档对之间的相似度度量：$$S: U \times U \rightarrow [0,1]$$并将满足 \(S(A,B) \geq S_\textrm{crit}\) 的两篇文档视为“近似重复”。

值得注意的是，这个定义一般不满足传递性：完全可能存在三篇文档 \(A, B, C\)，使得 \(S(A,B)\geq{}S_\textrm{crit}\) 且 \(S(B,C) \geq{} S_\textrm{crit}\)，但 \(S(A,C) < S_\textrm{crit}\)。这意味着“近似相同”并不是一个等价关系，这也是近似去重在逻辑上和大规模实现上都比精确匹配更为棘手的原因之一。

Jaccard 相似度

Jaccard 指数（也称 Jaccard 相似系数）是一种在多个领域——包括大规模文本处理——被广泛使用的相似度度量。

Jaccard 指数是一个用于比较集合的函数，它将两个有限集合的相似度刻画为二者交集大小与并集大小之比：

$$J(A,B) = \frac{|A\cap{}B|}{|A\cup{}B|}$$

我觉得这种计算方式很符合直觉：如果两个集合相似，它们应该包含大多相同的元素。这意味着两个集合大小相近，并集只比它们稍大，交集也只比它们稍小。如果两个集合差异很大，或大小悬殊，那么并集就会很大而交集很小。

它有两个非常自然的极限点，决定了其取值范围：对于两个不相交的集合，分子 \(|A\cap{}B|\) 为零，指数趋于零；而如果两个集合完全相同，则 \(A\cap{}B = A\cup{}B = A = B\)，Jaccard 相似度为 1。

注意，Jaccard 相似度作用于集合，而我们的起点是文档（通常以 Unicode 字符串表示）。文末我会再回到如何将文本文档转换为集合的问题，这里先假设这一步已经完成。我会将这些集合称为“特征集”，其中的每个元素则是文档的一个“特征”。

扩展 Jaccard 相似度的计算规模

现在我们已经有了“近似相似”的定义：将文档转换为特征集，然后寻找具有高 Jaccard 相似度的集合。

对于非常小的语料库，我们或许可以直接套用这一定义。但要考察所有文档对，其计算量会随着语料规模呈 \(O(n^2)\) 增长，很快就会变得不可行。

对于精确去重，我们通过哈希来避免二次方的开销：对文档进行哈希并按哈希值分组，这样就能让相同的文档（并且以很高的概率只有相同的文档）落入同一个哈希桶。我们希望为近似重复也找到类似的捷径；用该领域的术语来说，我们想要一种局部敏感哈希。

幸运的是，针对 Jaccard 相似度确实存在这样的技术！我们来看看它是如何工作的。

近似计算 Jaccard 相似度

我们首先考虑近似计算两篇文档之间 Jaccard 相似度的问题。我们将找到一种无需检查整个集合、只需一个预先为每篇文档独立计算好的、大小固定的小“签名”即可完成的近似方法。随后，我们会利用该签名的结构来寻找分组策略，使得（以很高的概率）相似的文档、且基本只有相似的文档会被分到同一组。

MinHash 签名

回想一下，Jaccard 相似度是两个大小的比值：即两个输入集合的交集与并集之比。

$$J(A,B) = \frac{|A\cap{}B|}{|A\cup{}B|}$$

要估计这类面积之比，一种经典策略是采样。如果我们能（在适当意义上均匀地）生成随机元素，并能查询这些元素是否存在于比值的两侧，我们就能得到一个会趋近真实值的经验估计。

在这里，我们知道并集至少和交集一样大，因此我们想要从 \(A\cup{}B\) 中进行均匀随机采样。仅凭集合本身，怎么做并不直观，但如果允许对每个集合进行预计算，我们其实可以很廉价地实现它！

• 首先，我们把问题看似搞得更复杂一些。假设特征是某个有限区间 \(0 \leq f_i \leq F\) 内的整数，然后在 \(\mathbb{Z}_F\) 上随机选取一个置换，记作 \(P(x)\)。现在，我们可以通过选取在该置换下取值最小的那个特征，来选出一个随机元素¹：

$$ x_{\textrm{random}} \leftarrow{} \argmin_{x\in{}A\cup{}B}{P(x)} $$

• 直接使用真正的随机置换并不现实，但我们可以用一个好的哈希函数来近似它。这样也不再需要将特征表示为固定范围的整数；只需接受极小的冲突风险并仅存储哈希值，我们就能把任何合理的特征空间映射为固定大小的哈希值：

$$ x_{\textrm{sig}} \leftarrow{} \min_{x\in{}A\cup{}B}{H(x)} $$

• 接下来，我们利用 \(\min\) 运算满足结合律这一事实，将上式改写为对每个集合分别预处理的形式：

\begin{align*} a_{\textrm{min}} &\leftarrow{} \min_{x\in{}A}H(x) \\ b_{\textrm{min}} &\leftarrow{} \min_{x\in{}B}H(x) \\ x_{\textrm{sig}} &\leftarrow{} \min(a_\textrm{min},b_\textrm{min}) \end{align*}

我们回过头来，看看已经做到了什么。如果我们在特征上选一个好的哈希函数，就可以为每个集合单独计算一个“签名”，即其所有特征的最小哈希值。给定任意两个集合，我们只需取这两个签名中的较小者，就得到了（某个元素的哈希值）——该元素是从它们的并集中均匀随机抽取的。

我们想知道该元素是否存在于交集中，还是在某一边缺失。而这一构造也让这个问题变得平凡！我们知道 \(x_\textrm{sig}\) 是任一集合中任意元素的最小哈希值。因此，如果它存在于比如集合 \(A\) 中，它必定也是该集合中的最小哈希值。而我们恰好知道每个集合的最小哈希值——这正是我们已有的！

因此，我们实际上并不需要计算 \(x_\textrm{sig}\)；只需判断是否 \(a_\textrm{min} = b_\textrm{min}\)！对于任意两个集合，该等式成立的概率恰好等于 \(J(A, B)\)！

使用更多哈希函数

该概率是在 \(\mathbb{Z}_F\) 的所有置换空间上取的（严格来说，带一些限定，也就是“在我们对哈希函数的选择上”）。仅用一个哈希函数和单个最小哈希值，对于每一对文档我们只能得到一个二值的估计——“相等”或“不相等”。

我们可以通过从某个合适的哈希函数族中选取 \(k\) 个不同的哈希函数，并将每篇文档概括为一个 \(k\) 元向量来改进这一点：

$$ A_\textrm{sig} = \begin{pmatrix} \displaystyle\min_{x\in{}A}H_1(x) & \displaystyle\min_{x\in{}A}H_2(x) & \cdots{} & \displaystyle\min_{x\in{}A}H_k(x) \end{pmatrix} $$

给定两个这样的签名，我们可以通过统计有多少个哈希值相等来近似 Jaccard 相似度：

$$ J(A,B) \approx{} \frac{1}{k}\sum_{i=1}^{k} (A_\textrm{sig}[i] = B_\textrm{sig}[i]) $$

需要提醒的一点是：这里哈希函数族的选择有些微妙。我们试图近似特征全集上的一个随机置换，但这类置换的数量增长极快，因此我们的哈希函数族只能代表所有可能置换中的极小一部分。我们必须确保哈希族中的成员不会产生不恰当的相关性——形式上，这里关键的性质被称为“最小值独立性”。幸运的是，这个问题已有相当充分的研究，文献中也有高效的解决方案。

在全量文档中比较

至此，我们已将每篇文档压缩为一个由 \(k\) 个哈希值组成的指纹，这使得 Jaccard 相似度的近似计算变得高效。

下一个问题是在整个语料库中寻找近似重复——即相似度很高的文档——而无需考察每一对文档。如前所述，我们的策略是定义一组可用于分组的键，然后仅在每个组内进行完整的比较。我们的目标是构造分组键，使得相似的文档以很高的概率被分到一起，而不相似的则不会。

使用完整签名

最简单的选择就是直接将全部 \(k\) 个 MinHash 值一起作为分组键，仅当两篇文档的所有 MinHash 值都相等时，才将其视为“近似重复”。我相当确定，这正是上文引用的 GPT-3 论文所说的“我们使用 Spark 的 MinHashLSH 实现（10 个哈希）对文档进行模糊去重……”的含义。他们将每篇文档拆成特征，为每篇文档计算 10 个 MinHash 值（使用 10 个不同的哈希²），然后按这个 10 维向量对文档分组，每组只保留一篇。

这种方法最大的优点在于简单高效。按单个高基数的字节串对文档分组是一项高效的操作，也很容易水平扩展，几乎在任何数据处理工具包中都被作为基础原语提供（可以说它是 MapReduce 的核心原语，体现为 map 与 reduce 阶段之间的“shuffle”）。

这种方法表现如何？对于单对文档，每个 MinHash 值相等的概率为 \(J(A,B)\)，因此 10 个全部相等的概率为 \(p=J(A,B)^k\)。当 \(k=10\) 时，情况如下图所示：

以及一些分位数：

可以看到，相似度在 0.6 左右以下的文档几乎不会发生碰撞，而当相似度在 0.95 左右时，匹配的概率就会变得很大。如果我们主要关心的是彼此非常接近的文档，这种方法或许就足够了。事实上我推测——但尚未验证——在许多语料库中，Jaccard 值会呈现相当明显的双峰分布——聚集在 1 和 0 附近。不相关的文档相似度接近 0，而相似的文档则大多是“几乎完全相同”——例如同一篇文章的两次轻微修订，或同一内容带不同时间戳或元数据的两个副本。

同样值得注意的是，\(J^{k}\) 的计算针对的是单对文档。如果有许多彼此相似的文档，这些两两之间的概率完全不是独立的。实际上，给定许多高度相似的文档，它们很可能会被哈希到至多两三个桶中，因此在某种意义上，我们会找到“几乎所有”的重复。

更模糊的匹配

（注：本节讨论主要参考《Mining of Massive Datasets》第 3.4 节。我尚未实践过这一策略，也不太清楚它在实际中是否、何时被使用。）

如果我们想检测“更模糊”的重复呢？也许经过一些实证研究后，我们确定希望找出相似度在 0.8 或 0.7 以上的文档对，而不仅仅是“接近 1”的那些。

通过将 \(k\) 个 MinHash 哈希中的一个子集用作分组键，我们可以提高在较低相似度下发生碰撞的可能性，然后在每个桶内再用完整的签名来比较，以剔除虚假碰撞。例如，我们可以按前 4 个 MinHash 值分组，然后——在每个发生碰撞的组内——再使用全部 MinHash 值来估计真实相似度。

使用更少的哈希是有帮助的，但作用有限；\(J^r\) 始终小于 \(J\)，如果把 \(r\) 压得过小，误匹配率就会变得不可接受。

我们可以转而为每篇文档生成多个键，将每篇文档放入多个桶中，每个键对应一个桶，且每个键使用不同的 MinHash 子集来构造。如果我们计算 \(k=20\) 个哈希作为签名，可以将每篇文档放入 \(b=4\) 个不同的桶中，每个键使用 \(r=5\) 个哈希来构造，然后比较每个桶内的每一对文档。

那么，两篇文档在至少一个桶中被哈希到一起的概率是多少呢？

• 使用单个键时两篇文档发生碰撞的概率为 \(J^r\)
• 因此基于该键不发生碰撞的概率为 \(1-J^r\)
• 因此在所有桶中都不发生碰撞的概率为 \((1-J^r)^b\)

因此，它们至少碰撞一次的概率为：

\[ p = 1 - (1-J^r)^b \]

例如，上面的例子——使用 4 组、每组 5 个哈希——会产生如下概率曲线：

这条曲线不如之前的例子那么陡峭，但我们已成功将其向左平移——大约在 \(J=0.7\) 附近，碰撞概率就达到了 50%。

事实证明，对于任意大于 1 的 \(r\) 和 \(b\) 取值，所得曲线大体上都呈类似的 S 形，因此调整这些值可以在灵敏度、召回率和性能开销之间提供丰富的权衡空间。

结语

在从事 AI 工作之前，我自认为对常见的算法技巧，包括大多数常见的 sketch 算法，都比较熟悉。但不知为何，我从未接触过 MinHash，甚至不知道这类算法（局部敏感哈希）竟然存在且切实可用！

深入了解这一技巧的原理让我乐在其中。希望这篇博文能让更多工程师初次认识它，或帮助某些人填补理解上的空白。我就是喜欢这些精巧的数学/算法技巧！

后记：MinHash 与 HyperLogLog

在调研和撰写本文的过程中，我意识到 MinHash 的核心技巧让我联想到了一个经典且相当有名的 sketch：HyperLogLog。

HyperLogLog 的核心思想（可追溯到一个更早的算法）是对流中的每个元素进行哈希，并保存哈希结果流中“前导零个数”的运行最大值。

该算法在细节上与 MinHash 截然不同，但二者有明显的相似之处：在这两种情况下，我们都使用哈希函数将输入元素映射到均匀分布，然后计算一个运行极值——通过适当的计算，仅用一个大小固定的输入摘要就能估计某种分布特性。

事实上，我认为这两种算法的相似程度甚至超出初看时的印象：HyperLogLog 统计前导零（低有效位中的零）。然而，我们假设哈希函数输出在 \([0, 2^N)\) 范围内均匀分布的值，因此不妨将位序反转，转而统计最高位一侧零的个数。但对于一个 N 位数 \(x\)，高位零的个数与 \(\log_2(x)\) 密切相关——前导零越多，\(x\) 越小。因此，我们完全可以把 HyperLogLog 看作是在计算 \(log_2(H(x))\) 的运行最小值，而 MinHash 计算的是 \(H(x)\) 的运行最小值。

此外，在某种意义上，HyperLogLog 与 MinHash 是（在一定程度上）对偶的：给定两个不同集合的 HyperLogLog 结构，我们可以将其合并并估计它们并集的大小；而给定这两个集合的 MinHash 结构，我们可以对其进行比较并估计它们交集的（相对）大小。

因此，如果将这两种结构结合起来，就可以得到一个能够对任意集合的交集和并集进行提问的 sketch！这一想法至少在 2013 年就已被注意到（见此），事实上，关于以有趣方式融合这两种数据结构思想的 sketch，至今仍有持续的 研究文献。我觉得这很巧妙！

附录：将文档表示为集合

我曾承诺会回到如何将文档表示为集合的问题，因此这里也简要介绍两种常见方法。

首先，在采用这两种策略中的任何一种之前，我们可能都想以某种方式对文档进行规范化。例如，我们很可能希望转换为标准的 Unicode 规范化形式，也可能希望进行大小写折叠、合并连续空白字符，或执行类似的转换。

n-gram（亦称“shingle”）

我们可以将文档表示为其中出现的所有 n-gram 组成的集合，并选取一个合适的 \(n\) 值。在大规模文本处理领域，文献中常常用“shingle”一词来代替“n-gram”，但我觉得这徒增混淆。我们可以选择任意 \(n\) 值，主要的权衡在于：较小的值往往会更粗粒度地比较文档（例如，通过二元组（bigram）的视角，大多数英文文本看起来可能都相当相似），而较大的值则会产生更多不同的特征，从而形成更大的集合。在某种极限情况下，我预计灵敏度也会下降，但我推测性能问题会更早出现。

据我找到的一份资料显示³，在一系列应用中，\(n\) 在 5 到 9 之间的取值似乎是常见的选择。

按词切分

我们也可以尝试将输入拆分为“单词”或“词元”，并将其作为特征。上文来自 GPT-3 论文的摘录中提到的“Spark 的标准分词器”，我认为指的就是这个类，它只是将输入转为小写，然后按空白字符进行切分。

我们可以使用更复杂的分词器，也可以将两种方法结合起来——先分词，再对词元取 n-gram。在这种情况下，我们会使用更小的 \(n\) 值，因为单个词元的熵应该远高于字节或字符。

1. 如果你曾写过 SELECT ... FROM table ORDER by random() LIMIT 1，你就已经用过类似的技巧了！↩︎

2. 如果你感兴趣，Spark 在文档中说明了其对哈希函数族的选择及相关文献参考。↩︎

3. Mining of Massive Datasets §3.2.2 ↩︎