随着信息爆炸时代的来临,互联网上充斥着着大量的近重复信息,有效地识别它们是一个很有意义的课题。例如,对于搜索引擎的爬虫系统来说,收录重复的网页是毫无意义的,只会造成存储和计算资源的浪费;同时,展示重复的信息对于用户来说也并不是最好的体验。造成网页近重复的可能原因主要包括:
一个简化的爬虫系统架构如下图所示:
事实上,传统比较两个文本相似性的方法,大多是将文本分词之后,转化为特征向量距离的度量,比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应,但这种方法的一个最大的缺点就是,无法将其扩展到海量数据。例如,试想像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://grunt1223.iteye.com/blog/964564
- 大小: 96.7 KB
- 大小: 66.7 KB
- 大小: 74.7 KB
- 大小: 62.4 KB
- 大小: 22.8 KB
- 大小: 86.5 KB
- 大小: 94.8 KB
分享到:
相关推荐
thinkphp5-使用SimHash进行海量内容数据查重
通过这种方式,您可以快速识别所有被视为接近重复的文档。 您甚至可以构建表来非常快速地执行这些查询。 可悲的是,它会消耗相当数量的 RAM,尤其是当您将数亿或数十亿个哈希插入已知哈希的语料库中时。 因此,...
simhash论文
专门针对中文文档的simhash算法库 简介 此项目用来对中文文档计算出对应的 simhash 值。 simhash 是谷歌用来进行文本去重的算法,现在广泛应用在文本处理中。 详见SimhashBlog 特性 使用 CppJieba 作为分词器和...
simhash 算法的 java 实现。特点计算字符串的 simhash通过构建智能索引来计算所有字符串之间的相似性,因此可以处理大数据使用使用输入文件和输出文件运行 Maininputfile 的格式(参见 src / test_in):一个文件每...
simhash, Simhash算法的python 实现 simhash这是 Simhash的python 实现。正在启动http://leons.im/posts/a-python-implementation-of-simhash-algorithm/插件生成状态
SimHash源码.docx
Simhash算法在文本去重中的应用-信息熵词频加权
文本相似度计算的Simhash算法的实现与改进
Java实现simHash算法
simhash-java Java实现simhash算法的简单实现.zip
pyspark 基于simhash做相似聚合代码工程
Algorithm-simhash.zip,simhash算法的go实现,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
用flask写了一个简单的web程序,前端页面有两个输入框,输入两段文字后,点击提交按钮,服务端收到两段文字后,调用simhash算法来计算两段文字的海明距离,注意,simhash计算短文本时效果不好
基于SimHash与神经网络的网络异常检测方法研究.pdf
使用simhash算法对Excel中各行文本进行相似度检验,并输出文本相似度的相似矩阵
simhash算法分为5个步骤:分词、hash、加权、合并、降维。具体C++代码实现打包,希望对大家有帮助。
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
simhash算法对字符串计算权重时,对中文要做特殊操作,及先分词,请自行下载sanford中文分词jar包及中文分词库
SIMHASH算法改进及应用研究