simhash与重复信息识别(一)

el/2024/7/24 2:28:04
随着信息爆炸时代的来临,互联网上充斥着着大量的近重复信息,有效地识别它们是一个很有意义的课题。例如,对于搜索引擎的爬虫系统来说,收录重复的网页是毫无意义的,只会造成存储和计算资源的浪费;同时,展示重复的信息对于用户来说也并不是最好的体验。造成网页近重复的可能原因主要包括: 
  • 镜像网站
  • 内容复制
  • 嵌入广告
  • 计数改变
  • 少量修改
一个简化的爬虫系统架构如下图所示: 




事实上,传统比较两个文本相似性的方法,大多是将文本分词之后,转化为特征向量距离的度量,比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应,但这种方法的一个最大的缺点就是,无法将其扩展到海量数据。例如,试想像Google那种收录了数以几十亿互联网信息的大型搜索引擎,每天都会通过爬虫的方式为自己的索引库新增的数百万网页,如果待收录每一条数据都去和网页库里面的每条记录算一下余弦角度,其计算量是相当恐怖的。 

我们考虑采用为每一个web文档通过hash的方式生成一个指纹(fingerprint)。传统的加密式hash,比如md5,其设计的目的是为了让整个分布尽可能地均匀,输入内容哪怕只有轻微变化,hash就会发生很大地变化。我们理想当中的哈希函数,需要对几乎相同的输入内容,产生相同或者相近的hashcode,换句话说,hashcode的相似程度要能直接反映输入内容的相似程度。很明显,前面所说的md5等传统hash无法满足我们的需求。 

simhash是locality sensitive hash(局部敏感哈希)的一种,最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法实现网页文件查重的。我们假设有以下三段文本: 

  • the cat sat on the mat
  • the cat sat on a mat
  • we all scream for ice cream
使用传统hash可能会产生如下的结果: 
引用
irb(main):006:0> p1 = 'the cat sat on the mat' 
irb(main):005:0> p2 = 'the cat sat on a mat' 
irb(main):007:0> p3 = 'we all scream for ice cream' 
irb(main):007:0> p1.hash 
=> 415542861 
irb(main):007:0> p2.hash 
=> 668720516 
irb(main):007:0> p3.hash 
=> 767429688


使用simhash会应该产生类似如下的结果: 
引用
irb(main):003:0> p1.simhash 
=> 851459198 
00110010110000000011110001111110 

irb(main):004:0> p2.simhash 
=> 847263864 
00110010100000000011100001111000 

irb(main):002:0> p3.simhash 
=> 984968088 
00111010101101010110101110011000

海明距离的定义,为两个二进制串中不同位的数量。上述三个文本的simhash结果,其两两之间的海明距离为(p1,p2)=4,(p1,p3)=16以及(p2,p3)=12。事实上,这正好符合文本之间的相似度,p1和p2间的相似度要远大于与p3的。 

如何实现这种hash算法呢?以上述三个文本为例,整个过程可以分为以下六步: 
1、选择simhash的位数,请综合考虑存储成本以及数据集的大小,比如说32位 
2、将simhash的各位初始化为0 
3、提取原始文本中的特征,一般采用各种分词的方式。比如对于"the cat sat on the mat",采用两两分词的方式得到如下结果:{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"} 
4、使用传统的32位hash函数计算各个word的hashcode,比如:"th".hash = -502157718 
,"he".hash = -369049682,…… 
5、对各word的hashcode的每一位,如果该位为1,则simhash相应位的值加1;否则减1 
6、对最后得到的32位的simhash,如果该位大于1,则设为1;否则设为0 

整个过程可以参考下图: 



按照Charikar在论文中阐述的,64位simhash,海明距离在3以内的文本都可以认为是近重复文本。当然,具体数值需要结合具体业务以及经验值来确定。 
  
使用上述方法产生的simhash可以用来比较两个文本之间的相似度。问题是,如何将其扩展到海量数据的近重复检测中去呢?譬如说对于64位的待查询文本的simhash code来说,如何在海量的样本库(>1M)中查询与其海明距离在3以内的记录呢?下面在引入simhash的索引结构之前,先提供两种常规的思路。第一种是方案是查找待查询文本的64位simhash code的所有3位以内变化的组合,大约需要四万多次的查询,参考下图: 



另一种方案是预生成库中所有样本simhash code的3位变化以内的组合,大约需要占据4万多倍的原始空间,参考下图: 



显然,上述两种方法,或者时间复杂度,或者空间复杂度,其一无法满足实际的需求。我们需要一种方法,其时间复杂度优于前者,空间复杂度优于后者。 

假设我们要寻找海明距离3以内的数值,根据抽屉原理,只要我们将整个64位的二进制串划分为4块,无论如何,匹配的两个simhash code之间至少有一块区域是完全相同的,如下图所示: 



由于我们无法事先得知完全相同的是哪一块区域,因此我们必须采用存储多份table的方式。在本例的情况下,我们需要存储4份table,并将64位的simhash code等分成4份;对于每一个输入的code,我们通过精确匹配的方式,查找前16位相同的记录作为候选记录,如下图所示: 



让我们来总结一下上述算法的实质: 
1、将64位的二进制串等分成四块 
2、调整上述64位二进制,将任意一块作为前16位,总共有四种组合,生成四份table 
3、采用精确匹配的方式查找前16位 
4、如果样本库中存有2^34(差不多10亿)的哈希指纹,则每个table返回2^(34-16)=262144个候选结果,大大减少了海明距离的计算成本 

我们可以将这种方法拓展成多种配置,不过,请记住,table的数量与每个table返回的结果呈此消彼长的关系,也就是说,时间效率与空间效率不可兼得,参看下图: 



事实上,这就是Google每天所做的,用来识别获取的网页是否与它庞大的、数以十亿计的网页库是否重复。另外,simhash还可以用于信息聚类、文件压缩等。 




http://www.ngui.cc/el/5557109.html

相关文章

simhash与重复信息识别(二)

Simhash 传统IR领域内文本相似度比较所采用的经典方法是文本相似度的向量夹角余弦,其主要思想是根据一个文章中出现词的词频构成一个向量,然后计算两篇文章对应向量的向量夹角。但由于有可能一个文章的特征向量词特别多导致整个向量维度很高,…

文本相识度算法(余弦相似性、简单共有词、编辑距离、SimHash、汉明距离、Jaccard相似性系数、欧几里得距离、曼哈顿距离 )

文本相似度计算在信息检索、数据挖掘、机器翻译、文档复制检测等领域有着广泛的应用。 比如舆论控制,我们假设你开发了一个微博网站,并且已经把世界上骂人的句子都已经收录进了数据库,那么当一个用户发微博时会先跟骂人句子的数据库进行比较&…

余弦方法计算相似度算法--Python实现 Java实现

(1)余弦相似性 通过测量两个向量之间的角的余弦值来度量它们之间的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。所以,它…

Python与shell交互os.system、 os.popen、 subprocess

这篇文章主要介绍了Python与shell的3种交互方式介绍,本文讲解了 os.system、 os.popen、 subprocess 模块等3种方法,需要的朋友可以参考下。 问题概述 考虑这样一个问题,有hello.py脚本,输出”hello, world!”;有TestInput.py脚本&#…

浏览器页面的缓存设置(不缓存设置)

HTML的HTTP协议头信息中控制着页面在几个地方的缓存信息,包括浏览器端,中间缓存服务器端(如:squid等),Web服务器端。本文讨论头信息 中带缓存控制信息的HTML页面(JSP/Servlet生成好出来的也是HTML页面)在中间缓存服务器中的缓存情…

信号、信号量、进程的状态的区别你知道吗?

信号量(Semaphore),有时被称为信号灯,是在多环境下使用的一种设施,是可以用来保证两个或多个关键代码段不被并发调用。 在进入一个关键代码段之前,线程必须获取一个信号量;一旦该关键代码段完成了,那么该线…

网关的作用(两个内网主机通信原理)

网关是一种充当转换重任的计算机系统或设备。在使用不同的通信协议、数据格式或语言,甚至体系结构完全不同的两种系统之间,网关是一个翻译器。与网桥只是简单地传达信息不同,网关对收到的信息要重新打包,以适应目的系统的需求。同时&#xff…

python中 if __name__ == '__main__': 的解析

当你打开一个.py文件时,经常会在代码的最下面看到 if __name__ __main__: ,现在就来介绍一下它的作用. 模块是对象,并且所有的模块都有一个内置属性 __name__。一个模块的 __name__ 的值取决于您如何应用模块。( 1 )如果 import 一个模块&a…

正则表达式 学习手册三

javascript表达式举例: 举例:匹配IP地址 100.4.5.6 var reg /^ ( (?: (?: 25[0-5] | 2[0-4] \d | ( (1\d{2}) |([1-9]?\d)) ) \. ) {3} (?:25[0-5]|2[0-4] \d | ( (1\d{2}) | ([1-9]?\d) ) ) ) $/; if (!reg.test($(#master).val())) …

区块链技术介绍----分布式总帐

区块链(Blockchain)是比特币的底层技术,像一个数据库账本,记载所有的交易记录。这项技术也因其安全、便捷的特性逐渐得到了银行与金融业的关注。 ​区块链(Blockchain)是比特币的一个重要概念,区块链是一串使用密码学方法相关联产生的数据块&…