基于 simhash 的文本去重原理

本文首发于：行者AI

互联网网页存在大量的内容重复的网页，文本，无论对于搜索引擎，爬虫的网页去重和过滤、新闻小说等内容网站的内容反盗版和追踪，还是社交媒体等文本去重和聚类，都需要对网页或者文本进行去重和过滤。为此必须有一套高效的去重算法，要不然爬虫将做非常多的无用功，时效性等都无法得到保证，更重要的是用户体验也不好。业界关于文本指纹去重的算法众多，如 k-shingle 算法、google 提出的 simhash 算法、Minhash 算法、百度 top k 最长句子签名算法等等，下面介绍下 simhash 算法以及 python 应用。

1. simhash 与传统 hash 的区别

simhash 是 google 用来处理海量文本去重的算法。 simhash 可以将一个文档转换成一个 64 位的字节，暂且称之为特征字。判断文档是否重复，只需要判断文档特征字之间的汉明距离。根据经验，一般当两个文档特征字之间的汉明距离小于 3， 就可以判定两个文档相似。

传统的 Hash 算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上仅相当于伪随机数产生算法。传统的 hash 算法产生的两个签名，如果原始内容在一定概率下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别很大。所以传统的 Hash 是无法在签名的维度上来衡量原内容的相似度，而 simHash 本身属于一种局部敏感哈希算法，它产生的 hash 签名在一定程度上可以表征原内容的相似度。

我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了 hash 签名也是用于这个目的。看到这里估计大家就明白了，我们使用的 simhash 就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的 hash 却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦” 和 “你妈妈叫你回家吃饭啦”。

通过 simhash 计算结果为：

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过传统 hash 计算为：

0001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的 hash 却不能做到，这个就是局部敏感哈希的魅力。

2. simhash 实现的主要步骤

在新拿到文本之后需要先进行分词，这是因为需要挑出 TopN 个词来表征这篇文本，并且分词的权重不一样，可以使用相应数据集的 tf-idf 值作为分词的权重，这样就分成了带权重的分词结果。

之后对所有分词进行哈希运算获取二值化的 hash 结果，再将权重与哈希值相乘，获得带权重的哈希值，最后进行累加以及二值化处理。

2.1 分词

使用分词手段将文本分割成关键词的特征向量，分词方法有很多一般都是实词，也就是把停用词等都去掉之后的部分，使用者可以根据自己的需求选择.最后形成去掉噪音词的单词序列并为每个词加上权重. 例如:

行者AI 专注 于 游戏 领域 多年 AI技术 积淀 一站式 提供 文本 图片 音视频 内容 审核 游戏AI 以及 数据 平台 服务

目前的词只是进行了分割，但是词与词含有的信息量是不一样的，比如行者AI 游戏 审核 这三个词就比 专注 服务 以及更能表达文本的主旨含义，这也就是所谓信息熵的概念。

为此我们还需要设定特征词的权重，简单一点的可以使用绝对词频来表示，也就是某个关键词出现的次数，但是事实上出现次数少的所含有的信息量可能更多.总之需要选择一种加权方法，否则效果会打折扣。

2.2 哈希和权重化

前面我们使用分词方法和权重分配将文本就分割成若干个带权重的实词，比如权重使用 1-5 的数字表示，1 最低 5 最高。

行者AI(5) 专注(2) 于(1) 游戏(3) 领域(1) 多年(1) AI技术(4) 积淀(1) 一站式(2) 提供(1) 文本(2) 图片(2) 音视频(2) 内容(1) 审核(2) 游戏AI(4) 以及(1) 数据(3) 平台(1) 服务(2)

对各个特征词进行二值化哈希值计算, 再将所有的哈希值累加，最后将累加结果二值化。

2.3 汉明距离

在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。

对于二进制字符串 a 与 b 来说，它等于 a 异或 b 后所得二进制字符串中“1”的个数。

汉明距离是以理查德·卫斯里·汉明的名字命名的，汉明在误差检测与校正码的基础性论文中首次引入这个概念。

在通信中累计定长二进制字中发生翻转的错误数据位，所以它也被称为信号距离。汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。但是，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离等算法。

谷歌经过工程验证认为当两个 64bit 的二值化 simhash 值的汉明距离超过 3 则认为不相似，所以判重问题就转换为求两个哈希值的汉明距离问题。

3. python 实现

pip 源中有数种 simhash 的实现，simhash，使用起来十分方便，直接使用 pip 就可以安装

pip install simhash

使用例子

from simhash import Simhash

def simhash_demo(text1, text2):"""求两文本的相似度:param text1::param text2::return:"""a_simhash = Simhash(text1)b_simhash = Simhash(text2)max_hashbit = max(len(bin(a_simhash.value)), (len(bin(b_simhash.value))))# 汉明距离distince = a_simhash.distance(b_simhash)print(distince)similar = 1 - distince / max_hashbitreturn similar

if __name__ == '__main__':text1 = "行者AI专注于游戏领域,多年的AI技术积淀,一站式提供文本、图片、音/视频内容审核,游戏AI以及数据平台服务"
text2 = "行者AI专注于游戏领域,多年的AI技术积淀,二站式提供文本、图片、音 视频内容审核,游戏AI以及数据平台服务"
similar = simhash_demo(text1, text2)print(similar)