SimHash算法是Google在2007年发表的论文《Detecting Near-Duplicates for Web Crawling》中提到的一种指纹生成算法，被应用在Google搜索引擎网页去重的工作之中。SimHash值不但提供了原始值是否相等这一信息，还能通过该值计算出内容的差异程度。

简单的说，SimHash算法主要的工作就是将文本进行降维，生成一个SimHash值，也就是论文中所提及的“指纹”，通过对不同文本的SimHash值进而比较“海明距离”，从而判断两个文本的相似度。

对于文本相似度的问题，常见的解决办法有欧式距离、编辑距离、最长公共子串、余弦算法、Jaccard相似度等方法。但是这些方法并不能对海量数据高效的处理。

比如说，在搜索引擎中，会有很多相似的关键词，用户所需要获取的内容是相似的，但是搜索的关键词却是不同的，例如：
“年龄大于30岁的自然人？”
“年龄大于50岁的人？”
以上两个可以等价的关键词，然而通过普通的hash计算，会产生两个相差甚远的hash串。而通过SimHash计算得到的Hash串会非常的相近，从而可以判断两个文本的相似程度。

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

我们主要解决的是文本相似度计算，要比较的是两个文章是否相似，当然我们降维生成了hash签名也是用于这个目的。看到这里，估计大家就明白了，即使把文章中的字符串变成 01 串，我们使用的simhash算法也还是可以用于计算相似度，而传统的hash却不行。

SimHash是一种局部敏感hash。我们都知道什么是hash。那什么叫局部敏感呢，假定A、B具有一定的相似性，在hash之后，仍然能保持这种相似性，就称之为局部敏感hash。其主要思想是降维，将高维的特征向量转化成一个f位的指纹（fingerprint），通过算出两个指纹的海明距离（hamming distince）来确定两篇文章的相似度，海明距离越小，相似度越低（根据 Detecting Near-Duplicates for Web Crawling 论文中所说），一般海明距离为3就代表两篇文章相同。
    
举例：
比如，我们得到一个文档的关键词，取得一篇文章关键词集合，又会降低对比效率，我们可以通过hash的方法，把上述得到的关键词集合hash成一串二进制，这样我们直接对比二进制数，看其相似性就可以得到两篇文档的相似性，在查看相似性的时候我们采用海明距离，即在对比二进制的时候，我们看其有多少位不同，就称海明距离为多少。在这里，我是将文章simhash得到一串64位的二进制，一般取海明距离为3作为阈值，即在64位二进制中，只有三位不同，我们就认为两个文档是相似的。当然了，这里可以根据自己的需求来设置阈值。

就这样，我们把一篇文档用一个二进制代表了，也就是把一个文档hash之后得到一串二进制数的算法，称这个hash为simhash。

根据上边的原理，我们可以得到simhash也有其局限性，在处理小于500字的短文本时，simhash的表现并不是很好，所以在使用simhash前一定要注意这个细节。

海明距离是编辑距离其中之一，在信息编码中，两个合法代码对应位上编码不同的位数称为码距，又称海明距离。即两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。一个有效编码集中任意两个码字的海明距离的最小值称为该编码集的海明距离。例如： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为 3。
N位的码字可以用N维空间的超立方体的一个顶点来表示，两个码字之间的海明距离就是超立方体两个顶点之间的一条边，而且是这两个顶点之间的最短距离。

海明距离应用最多的是在海量短文、文本去重上，以其性能优的特点。海明距离主要就是对文本进行向量化，或者说是把文本的特征抽取出来映射成编码，然后再对编码进行异或计算出海明距离。

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

给定一段语句或者一段文本，进行分词，得到有效的特征向量，然后为每一个特征向量设置一个5个级别（1—5）权值。例如给定一段语句：“生活本没有路，走的人多了就成了路，要相信阳光总在风雨后”，分词后结果为：生活 没有 成了 相信 阳光 风雨，然后为每个特征向量赋予权值： 生活(5) 没有(2) 成了(1) 相信(2) 阳光(3) 风雨(2)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。

也可以根据不同的企业自己指定权重，反正就是个比例数字，下边也给出一种常规使用的权重值计算（TF-IDF算法）：
TF:词频
IDF:逆向词频

TF-IDF算法

TF-IDF算法是一种用于信息检索和文本挖掘的常用加权技术，其主要思想是：如果某个词或短语在一篇文章中出现的频率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。它由两部分组成：TF（词频）和IDF（逆向文件频率）。12

TF表示词条在文档中出现的频率，IDF表示词条在整个文档集合中的稀有程度。TF-IDF实际上是TF和IDF的乘积，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。

具体来说，IDF的具体算法是：IDF(t) = log(语料库中的文档总数 / (含有该词条的文档总数+1 ))。加1是为了防止分母为0，导致结果无法计算。最后，将TF和IDF相乘，就得到了TF-IDF值。

通过hash函数计算各个特征向量的hash值，hash值为二进制数01组成的n-bit签名。比如“生活”的hash值Hash(生活)为110101，“没有”的hash值Hash(没有)为“101001”。就这样，字符串就变成了一系列数字。

加权步骤是为了突出一些重要的词语，通常通过词频或TF-DF来进行加权处理。

在hash值的基础上，给所有特征向量进行加权，即W = Hash * weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。例如给“生活”的hash值“110101”加权得到：W(生活) = 110101 * 5 = 5 5 -5 5 -5 5，给“没有”的hash值“101001”加权得到：W(没有)=101001 * 2 = 2 -2 2 -2 -2 2，其余特征向量类似此般操作。

将上述各个特征向量的加权结果累加，变成只有一个序列串。拿前两个特征向量举例，例如“生活”的“5 5 -5 5 -5 5”和“没有”的“2 -2 2 -2 -2 2”进行累加，得到“5+2， 5-2， -5+2， 5-2， -5-2， 5+2，”，得到“7 3 -3 3 -7 7”。

对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 1 0 1 0 1”，从而形成它们的simhash签名。

对每条文本根据SimHash 算出签名后，再计算两个签名的海明距离（两个二进制异或后1的个数）即可，既两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。

举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数（普遍算法）。

在实际使用过程中，我们可以使用simhash 分块来操作，假设对64位的SimHash，查找海明距离在3以内的所有签名。可以把64位的二进制签名均分成4块，每块16位。根据鸽巢原理（也称抽屉原理，见组合数学），如果两个签名的海明距离在3以内，它们必有一块完全相同。
在此基础上我们可以使用redis和es来进行查询

redis：

• 我们需要将64位simhash均分为4份，然后每份作为key存储到redis
• 采用精确匹配的方式查找前16位
• 找到则拿出来计算与被比较的simahsh距离，小于3则判断为相似（当然具体问题具体分析，这个值可以调整）

es：

• 将每个文章的64位simhash的值分成四块存入一个数组字段中，创建倒排索引
• 将需要查询的文章的64位simhash的值分成四块进行terms 查找
• 只要有一个命中，那么将数据的simhash值取出，进行海明距离计算

首先添加依赖，使用HanLP分词，Jsoup提供正文HTML标签去除服务。

    以上就是本篇文章【一文了解Simhash原理和用法-计算文章相似度】的全部内容了，欢迎阅览 ！ 文章地址：http://www.gawce.com/news/9364.html 
     资讯      企业新闻      行情      企业黄页      同类资讯      首页      网站地图      返回首页 阁恬下移动站 http://22pru.gawce.com/ , 查看更多