基于SimHash算法的文本相似度计算原理

背景

上周某一天，笔者搜遍全网，综合各种不完整的代码片段、GitHub 上几十个 SimHash 项目、几十个相关网络资源文章后，终于搞定了一个还算精确的 SimHash 算法的 Java 版本。

输出是检验掌握一个知识点的简单标准，本文就来详细介绍一下基于 SimHash 算法的相似文本检索的原理和实现过程。

文本相似度的应用

最近在搞一个漏洞库爬虫项目，需要综合分析并合并几个漏洞网站的漏洞信息，不同漏洞的发布基本上是相似的，但是不同网站可能稍有差异，怎么将不同网站发布的、本质是同一种漏洞的记录合并呢？

这就涉及到了文本相似度计算问题。基本思路是：对网页漏洞解析时，先以漏洞简介或者标题去系统的漏洞库中检索，是否有相似的漏洞，如果存在，视为同一条漏洞信息，追加漏洞来源即可。

这个问题的经典解决方案就是 Google 用来处理海量文本去重的算法 SimHash ，它是一种局部敏感 hash 【全称： Locality Sensitive Hashing】，全称和缩写的 Sim 有些出入，不知道为什么呢！

利用 SimHash 判断文本相似度的基本流程为：

1. 分别计算两个文本的 SimHash 值，得到两个定长的二进制序列；
2. 对两个二进制数进行异或计算，得到两个文本的海明距离；
3. 海明距离小等于 3 ，视为相似。

SimHash 算法简介

Java 里有 HashMap ，想必大家都不陌生，它通过一个函数得到值来标识某项数据的位置，为了避免 Hash 冲突，选中的函数应该尽量让数据分散。

SimHash 与我们熟悉的 Hash 不太一样，它要求对相同或相似的文本，产生相同或者相近的哈希值，值得相似程度同时能反映输入得文本得相似度。

它的原理是：

SimHash 原理

基本流程是：

1. 分词：对文本进行分词，得到 N 个 词 word1，word2，word3 …… wordn​；
2. 赋权重：对文本进行词频统计，为各个词设置合理的权重 weight1​，weight2​，weight3​ …… weightn​；
3. 哈希：计算每个分词的哈希值 hashi​，得到一个定长的二进制序列，一般是 64 位，也可以是 128 位；
4. 加权重：变换每个分词 wordi​ 的 hashi​，将 1 变成正的权重值 weighti​，0 变成 −weighti​，得到一个新的序列 weightHashi​；
5. 叠加权重：对每个 weightHashi​ 各个位上的数值做累加，最终得到一个序列 lastHash，序列的每一位都是所有分词的权重的累加值；
6. 降维：再将 lastHash 变换成 01 序列 simHash ，方法是：权重值大于零的位置设置为 1，小于 0 的位置设置为 0，它就是整个文本的局部哈希值，即指纹。

从文本到 SimHash 指纹的过程，有一个经典的示例：

算法示例

算法实现需要解决的三个技术点：

1. 分词，有 hanlp 分词、IKAnalyzer 分词 和 word 分词等工具可以用；
2. 权重，为各个分词赋上合理的权重，可以自定义统计算法，也可以借助 word 的词频统计；
3. 哈希算法，这个可以自己选择，也可以用现有的算法，如 Murmur 哈希，JDK 的 hash 。

汉明距离

看看来自百度百科的解释：

汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

从其定义上来看，就是二进制序列异或计算时相异为 1 ，异或的结果中 1 的总数，就是两个字符串的汉明距离，所以实现汉明距离计算的方法也很简单。

启示录

本篇先介绍基础概念，下一篇笔者将继续介绍具体的算法实现。从 SimHash 算法的流程来看，比较难理解的是，为什么可以直接对哈希值中的 0 或 1 替换为权重值，然后对所有分词累加权重呢？