架构师

您现在的位置是:首页 > 程序人生 > 网络爬虫

网络爬虫

Java爬虫第17课:网页(文本)去重之SimHash算法

架构师小跟班 2020-07-16 网络爬虫
流程介绍simhash是由 Charikar 在2002年提出来的,为了便于理解尽量不使用数学公式,分为这几步:1、分词,把需要判断文本分词形成这个文章的特征单词。2、hash,通过hash算法把每个

simhash

高效的文本相似度去重算法实现

simhash是什么

Google发明的的文本去重算法,适合于大批量文档的相似度计算。

流程介绍

simhash是由 Charikar 在2002年提出来的,为了便于理解尽量不使用数学公式,分为这几步:

1、分词,把需要判断文本分词形成这个文章的特征单词。

2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字。

3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”

“51区”计算为 “ 5 -5 5 -5 5 5”。

4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。

 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”

把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5”“9 -9 1 -1 1 9”

5、降维,把算出来的 “9 -9 1 -1 1 9”变成 0 1 串,形成最终的simhash签名。 

签名距离计算

我们把库里的文本都转换为simhash签名,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?

我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。

举例如下: 

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


文章评论