Loading... ## 前言 SimHash是一种广泛用于文档或者文本相似性检测的技术,常见于`检测网页重复内容`或者`版权侵犯`场景。它是一种局部敏感哈希算法(`Locality Sensitive Hashing, LSH`),由Google在2007年发表的论文《Detecting Near-Duplicates for Web Crawling》提出。SimHash能够将文档转换为一个较短的固定长度的指纹(或哈希值, 比如64/128位),使得相似的文档具有相似的哈希值。[该算法目前存在专利, 但允许非商业使用.](https://stackoverflow.com/questions/27712472/choosing-between-simhash-and-minhash-for-a-production-system) 对于文本去重这个问题,常见的解决办法有`余弦算法`、`欧式距离`、`Jaccard相似度`、`最长公共子串`等方法。但是这些方法并不能对海量数据高效的处理。 比如说,在搜索引擎中,会有很多相似的关键词,用户所需要获取的内容是相似的,但是搜索的关键词却是不同的,如"北京好吃的火锅"和"哪家北京的火锅好吃",是两个可以等价的关键词,然而通过普通的hash计算,会产生两个相差甚远的hash串。而通过SimHash计算得到的Hash串会非常的相近,从而可以判断两个文本的相似程度。 --- ## 局部敏感哈希(Locality Sensitive Hashing) 说到hash可能我们第一个想到的是md5这种信息摘要算法,可能两篇文本只有一个标点符号的差距,但是两篇文本A和B的md5值差异就非常大,感兴趣的可以试验一下看看。 有时候我们希望的是原本相同的文章做了微小改动之后的哈希值也是相似的,这种哈希算法称为局部敏感哈希`LSH(Locality Sensitive Hashing)`,这样我们就能从哈希值来推断相似的文章。 局部敏感哈希算法使得在原来空间相似的样本集合,进行相关运算映射到特定范围空间时仍然是相似的,这样还不够,还需要保证原来不相似的哈希之后仍然极大概率不相似,这种双向保证才让LSH的应用成为可能。 --- ## SimHash基本过程 SimHash的基本思想是将高维的特征向量转换为一个低维的哈希值,这个过程如下: 1. **分词**:首先从文档中提取特征,这些特征通常是词项或短语(比如使用jieba等工具分词结果),并可能基于其重要性(如TF-IDF权重)进行加权。 2. **哈希**:将每个特征映射到一个固定长度的位串(通常是二进制数),例如使用常规的哈希函数(通常为64/128位)。 3. **加权**:根据每个特征的权重,对其哈希后的位串进行加权(Hash串中1处对应值+weight, 0处对应值-weight)。权重较高的特征对最终的SimHash值影响较大。 4. **累加**:将所有加权后的位串向量累加起来,形成一个向量。 5. **降维**:通过观察累加后的向量的每一位,如果该位的总和大于0,则在最终的SimHash值的相应位置放置1,否则放置0。 整个过程的流程图为: ![](https://zoe.red/usr/uploads/2024/04/3948738997.png) 得到文档的SimHash值后,我们还需要判断两个文档是否相似。对相同长度的数字序列,我们采用海明距离来衡量其相似性。 根据经验,对于64位的 `SimHash` ,汉明距离在3以内的都可以认为相似度比较高,认为这两个文档基本相同。 可以参考此视频或者对照参考部分博文: https://www.bilibili.com/video/BV1cv4y1A7h4 --- ## 汉明距离(Hamming Distance) 海明距离,又名汉明距离,为两串向量中,对应元素 **不一样的个数**。 比如 `101010` 与 `101011` 的最后一位不一样,那么汉明距离即为1, 同理 `000` 与 `111` 的汉明距离为3。 但这没有考虑到向量的长度,如 `111111000` 与 `111111111` 的距离也是3, 尤其是比较文本的相似时,这样的结果肯定不合理,因此我们可以用向量长度作为分母。 Python 中的 `hamming distance` 即这么计算的。 汉明距离也是值越小越相似,但除以长度之后的海明距离, 最大值为1(完全不相似),最小值为0(完全一致)。 > 小技巧 > > 如果两个向量长度相同,汉明距离可以是异或运算结果中1的个数。(即SimHash中的使用的) --- ## 大规模数据下的海明距离计算 以64位的`SimHash`签名来说,把它以每16位划分块,共4块。 如果两个`SimHash`签名海明距离小于等于3,则至少有一个16位块完全相同。 但是我们不知道具体是哪两个块相同,所以要进行枚举,这里只需要枚举4次。 [![../../_images/simhash2.png](https://zoe.red/usr/uploads/2024/04/1406544714.png)](https://www.zhangzhenhu.com/_images/simhash2.png) SimHash 签名分捅检索的过程 **存储**: 1. 将一个64位的simhash签名拆分成4个16位的二进制码。(图上红色的16位) 2. 分别拿着4个16位二进制码查找当前对应位置上是否有元素。(放大后的16位) 3. 对应位置没有元素,直接追加到链表上;对应位置有则直接追加到链表尾端。(图上的 S1 — SN) **查找**: 1. 将需要比较的simhash签名拆分成4个16位的二进制码。 2. 分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。 3. 如果有元素,则把链表/集合拿出来顺序查找比较,直到simhash的海明距离小于一定大小的值(一般64位编码的SimHash值对应的海明距离阈值设为3),整个过程完成。 * 如果上一个命中的key未找到相似文本,则继续遍历剩下的key,重复相同的过程,直至所有的key全部遍历完或者命中相似文本,则结束。 *注意:* 1. 当文本内容较长时(500字+),使用 `SimHash` 准确率很高,`SimHash` 处理短文本内容准确率往往不能得到保证; 2. 文本内容中每个term对应的权重如何确定要根据实际的项目需求,一般是可以使用IDF权重来进行计算。 ## 代码 看到Github上的开源示例 * 官网讲解: https://leons.im/posts/a-python-implementation-of-simhash-algorithm/ * 代码链接: `https://github.com/1e0ng/simhash/blob/master/simhash/__init__.py` 下面是一些流行的SimHash实现的开源库: 1. **Simhash by 1e0ng** * **GitHub链接**:[seomoz/simhash-cpp](https://github.com/seomoz/simhash-cpp) * 这是一个用C++编写的SimHash库,具有Python绑定,因此可以方便地在Python环境中使用。它是由SEOmoz开发的,适用于大规模数据集。 2. **simhash-py** * **GitHub链接**:[leonsim/simhash](https://github.com/leonsim/simhash) * 这是一个纯Python实现的SimHash库,它提供了一个简单的接口来计算SimHash值并比较它们之间的距离。它对大数据集的效率较低,但对于小型项目或学习目的非常适合。 3. **simhash-java** * **GitHub链接**:[avngr/simhash-java](https://github.com/avngr/simhash-java) * 如果你在Java环境中工作,这个库提供了SimHash的Java实现。它可以轻松集成到Java或者基于JVM的项目中。 4. **simhash-db** * **GitHub链接**:[seomoz/simhash-db](https://github.com/seomoz/simhash-db) * 这个库用于存储和检索SimHash值,并支持大规模的数据集。它依赖于之前提到的`simhash-cpp`库,并提供了数据库支持来管理SimHash值。 --- <div class="hideContent">此处内容需要评论回复后(审核通过)方可阅读。</div> THE END 本文作者:将夜 本文链接:https://zoe.red/2024/503.html 版权声明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。 最后修改:2024 年 04 月 17 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏