Similarity

David Liu12/12/25About 4 min

Similarity

日前接到一个对名言警句这种短文本进行去重的小任务。

如何设计一个比较两篇文章相似度的算法？

来自于 Google Moses Charikar 发表的一篇论文“detecting near-duplicates for web crawling”中提出了 simhash 算法，专门用来解决亿万级别的网页的去重任务。

Simhash

simhash 作为 locality sensitive hash(LSH)（局部敏感哈希）的一种：

其主要思想是降维，将高维的特征向量映射成低维的特征向量，通过两个向量的 Hamming Distance 来确定文章是否重复或者高度近似。

其中，Hamming Distance，又称汉明距离，在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。也就是说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：1011101 与 1001001 之间的汉明距离是 2。至于我们常说的字符串编辑距离则是一般形式的汉明距离。

如此，通过比较多个文档的 simHash 值的海明距离，可以获取它们的相似度。

步骤

simhash 算法分为 5 个步骤：分词、hash、加权、合并、降维，具体过程如下所述：

分词

给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置 1-5 等 5 个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。

例如给定一段语句：“CSDN 博客结构之法算法之道的作者 July”，分词后为：“CSDN 博客结构之法算法之道的作者 July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。

hash

通过普通的 hash 函数计算各个特征向量的 hash 值，hash 值为二进制数 01 组成的 n-bit 签名（一般是 64 或 128 位，以根据实际需求增大位数）。

例如“CSDN”的 hash 值 Hash(CSDN)为 100101，“博客”的 hash 值 Hash(博客)为“101011”。就这样，字符串就变成了一系列数字。

加权

在 hash 值的基础上，给所有特征向量进行加权，即W=Hash*weight，且遇到 1 则 hash 值和权值正相乘，遇到 0 则 hash 值和权值负相乘。

例如给“CSDN”的 hash 值“100101”加权得到：W(CSDN) = 100101*4 = 4 -4 -4 4 -4 4，给“博客”的 hash 值“101011”加权得到：W(博客)=101011*5 = 5 -5 5 -5 5 5，其余特征向量类似此般操作。

合并

将上述各个特征向量的加权结果累加，变成只有一个序列串。

例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。

降维

对于 n-bit 签名的累加结果，如果大于 0 则置 1，否则置 0，从而得到该语句的 simhash 值，最后我们可以根据不同语句 simhash 的海明距离来判断相似度。

例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于 0 记为 1，小于 0 记为 0），得到的 01 串为：“1 0 1 0 1 1”，从而形成它们的 simhash 签名。

Shingle 算法的空间和计算复杂性高，相似性精度也高，适合数据量不大且对精度要求高的应用。Simhash 和 bloom filter 算法在空间消耗和计算复杂性方面都优于 Shingle 算法，但是精度有所损耗，取决于 simhash 的长度和 bloom filter 的大小。simhash 的长度通常为 64 位或 128 位，这个基本可以满足应用的需求，可以根据实际需求增大位数。bloomfilter 要大于 simhash 长度，可以根据最大 shingle 数的两倍来估算，精度方面也要优于 simhash。由于 hash 函数的碰撞问题，simhash 和 bloom filter 算法可能出现误判现象，即不相似的文件可能会判定为相似的。

总结一下，通常情况下，文件特征值

空间消耗方面，Shingle > bloom filter > simhash；

计算精度方面，Shingle < bloom filter < simhash。

Bloomfilter 算法往往是比较折中的相似数据检测方法选择，但海量数据集的相似性计算往往采用 simhash 算法，在计算性能方面具有很大优势，而且更加适合 MapReduce 计算模型。