搜索引擎判断复制网页一般都基于这么一个思想:为每个网页计算出一组信息指纹(Fingerprint)
,若两个网页有一定数量相同的信息指纹,则认为这两个网页的内容重叠性很高,也就是说两个网页是内容复制的。
很多搜索引擎判断内容复制的方法都不太一样,主要是以下两点的不同:
1、计算信息指纹(Fingerprint)
的算法;
2、判断信息指纹的相似程度的参数。
在描述具体的算法前,先说清楚两点:
1、什么是信息指纹?
信息指纹就是把网页里面正文信息,提取一定的信息,可以是关键字、词、句子或者段落及其在网页里面的权重等,对它进行加密,如MD5加密,从而形成的一个字符串。信息指纹如同人的指纹,只要内容不相同,信息指纹就不一样。
2、算法提取的信息不是针对整张网页,而是把网站里面共同的部分如导航条、logo、版权等信息(这些称之为网页的“噪音”)过滤掉后剩下的文本。
分段签名算法
这种算法是按照一定的规则把网页切成N段,对每一段进行签名,形成每一段的信息指纹。如果这N个信息指纹里面有M个相同时(m是系统定义的阙值),则认为两者是复制网页。
这种算法对于小规模的判断复制网页是很好的一种算法,但是对于像google这样海量的搜索引擎来说,算法的复杂度相当高。
基于关键词的复制网页算法
像google这类搜索引擎,他在抓取网页的时候都会记下以下网页信息:
1、网页中出现的关键词(中文分词技术)以及每个关键词的权重(关键词密度);
2、提取meta
descrīption或者每个网页的512个字节的有效文字。
关于第2点,baidu和google有所不同,google是提取你的meta
descrīption,如果没有查询关键字相关的512个字节,而百度是直接提取后者。这一点大家使用过的都有所体会。
在以下算法描述中,我们约定几个信息指纹变量:
Pi表示第i个网页;
该网页权重最高的N个关键词构成集合Ti={t1,t2,...tn},其对应的权重为Wi={w1,w2,...wi}
摘要信息用Des(Pi)表示,前n个关键词拼成的字符串用Con(Ti)表示,对这n个关键词排序后形成的字符串用Sort(Ti)表示。
以上信息指纹都用MD5函数进行加密。
基于关键词的复制网页算法有以下5种:
1、MD5(Des(Pi))=MD5(Des(Pj))
,就是说摘要信息完全一样,i和j两个网页就认为是复制网页;
2、MD5(Con(Ti))=MD5(Con(Tj))
,两个网页前n个关键词及其权重的排序一样,就认为是复制网页;
3、MD5(Sort(Ti))=MD5(Sort(Tj))
,两个网页前n个关键词一样,权重可以不一样,也认为是复制网页。
4、MD5(Con(Ti))=MD5(Con(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某个阙值a
,则认为两者是复制网页。
5、MD5(Sort(Ti))=MD5(Sort(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某个阙值a
,则认为两者是复制网页。
关于第4和第5的那个阙值a,主要是因为前一个判断条件下,还是会有很多网页被误伤,搜索引擎开发根据权重的分布比例进行调节,防止误伤。
这
个是北大天网搜索引擎的去重算法(可以参考:《搜索引擎--原理、技术与系统》一书),以上5种算法运行的时候,算法的效果取决于N,就是关键词数目的选
取。当然啦,选的数量越多,判断就会越精确,但是谁知而来的计算速度也会减慢下来。所以必须考虑一个计算速度和去重准确率的平衡。据天网试验结果,10个
左右关键词最恰当。
网页去重的算法
1. I-Match
2. Shingliing
3. SimHashing( locality sensitive hash)
4. Random Projection
5. SpotSig
6. combined
I-Match算法
I-Match算法有一个基本的假设说:不经常出现的词和经常出现的词不会影响文档的语义,所以这些词是可以去掉的。
算法的基本思想是:将文档中有语义的单词用hash的办法表示成一个数字,数字的相似性既能表达文档的相似性
算法的框架是:
1. 获取文档(或者是主体内容)
2. 将文档分解成token流,移除格式化的标签
3. 使用term的阈值(idf),保留有意义的tokens
4. 插入tokens到升序排列的排序树中
5. 对每一个token,相加得到一个hash值,知道文档结束为止
6. 将元组(doc_id,SHA hash) 插入到某一词典中,如果词典有冲突,这两个文档相似。
算法有一个缺点是稳定性差。如果文档的某个词改变了,最终的hash值就会发生显著的变化。对空文档,算法是无效的。
有一个解决办法是,用随机化的方法,参考Lexicon randomization for near-duplicate
detection with I-Match。具体细节这里就不提了
Shingling算法
Shingling算法说,I-Match以词为单位做hash显然是不准确的,因为它忽略了文档之间书顺序。另,一个Shingle为连续的若干个单词的串。
Shingling算法有个很少神奇的数学背景。如果一个shingle的长度为k,那么长度为n的文档就有n-k+1个shingle,每一个
shingle可以用MD5或者其他算法表示成一个fingerprint,而两个文档的相似性Jacard相似性来表示,Jarcard公式是指两个集
合的相似性=集合之交/集合之并。为了估计两个文档的相似性,有时候n-k+1个fingerprint还是太大了,所以取m个fingerprint函
数,对每一个函数fi,都可以计算出n-k+1个fingerprint,取其中的最小的fingerprint,成为i-minvalue.
那么一个文档机会有m个i-minvalue。数学上,Broder大师说:
平均来讲,两个文档中相同的唯一single的比率和两个文档中相同的i-minvalue的比率是一样的
Shingling的算法框架是:
1. 获取文档(或者是主体内容)
2.
将文档分解成n-k+1个shingle,取m个fingerprint函数,对每一个fingerpint函数计算i-minvalue值
3. 将m个i-minvalue值组合成更少m’个surpersingle
4.计算两个文档相同的surpergingle的个数a。
5. 如果a大于某一个值b(say:2),那么两个文档Jarcard 相似
一般的参数设置为:m=84,m’=6,b=2
SimHash 算法
locality sensitive
hash算法博大精深。基本思想是,如果两个东西相似,我可以用一个hash函数把他们投影到相近的空间中LSH。用到near
duplication detection上,算法框架是:
1. 将文档转换为特征的集合,每一个特征有一个权重
2. 利用LSH函数把特征向量转换为f位的fingerprint,如:64
3. 查找fingerprint的海明距离
haha,看,多么简单和明朗,这里的几个问题及时寻找正确的LSH
Random Projection算法
shingling关注了文档顺序,但是忽略了文档单词出现的频率,random projection说我要讨论文档的频率。
Random Projection也是很有意思的一种算法,它是一种随机算法。简单描述为:
1. 将每一个token映射到b位的空间。每一个维度是由{-1,1}组成。对所有页面投影函数是一样的
2. 每一个页面的b维度向量,是所有token的投影的简单加和
3. 最后把b维向量中的正数表示为1,负数和0都写成0
4. 比较两个page的b维向量一致的个数
Charikar最牛的地方是,证明,两个b位变量一致的位数的比率就是文档向量的consine相似性。这里的数学基础还是很有意思的,如果感兴趣,可以参考M.S.
Charikar. Similarity Estimation Techniques for Rounding
Algorithm(May 2002)
SpotSig算法
ref:SpotSigs:Robust and Efficient Near Duplicate Detection in
Large Web Collection
SpotSig是个比较有意思的算法,它说,我为什么要关注所有的单词啊,我要关注的单词是有语义的词,哪些是有语义的词呢?哦,想 the
a this an
的等虚词后面的就是我要关注的东西罗。Spot就是指这些虚词的后面的词串。然后呢,每一个文档我都有很多很多Spot了,现在一个文档就是一个Spot
的集合,两个文档是相似程度就是集合的Jaccard相似度。算法虽然简单,但是我想重点是两个比较有借鉴意义的工程上的性能考虑。
1. Optimal Partition
Sim(A,B) = | A B交集| / | A B 并集| <= min(A,B)/max(A,B)
<= |A|/|B| say: |A|<|B|
好了,这是一个很好的枝剪条件,如果文档spot vector的个数比小于某个值(当然是,小 /
大),就可以完全不用求交,并了。Optimal Partition就是说,好啊,我把每一个文档的spot
vector的长度都投影到相应的从小到大的bucket中,保证|d1|/|d2| >=r if |d1|
< |d2| .
且不存在这样的反例。另一个保证是这个bucket是满足条件的最小的。有了这个partition,我们最多只用关心相邻的三个bucket了
2. Inverted Index
Pruning
说,两个文档,如果能相似,起码有一个公共的spot。逆向索引说的就是把spot做为index,包含它的所有文档作为其value。
有了这两个工具,计算复杂度可以明显下降,因为它不会计算不能是duplication的文档。
转自:http://blog.sina.com.cn/s/blog_48299b340100jsfg.html
相关推荐
### 基于新闻网页主题要素的网页去重方法研究 #### 概述 随着互联网技术的迅猛发展,网络信息量急剧增长,其中新闻类网页是互联网上信息的重要组成部分之一。由于新闻信息的时效性和重要性,很多新闻事件会被多家...
"设计装置-消息队列大数据去重处理方法"的主题聚焦于如何有效地去除大数据流中的重复信息,以确保数据的准确性和效率。消息队列作为中间件,常常被用于这种场景,因为它能够提供异步处理、负载均衡以及容错能力。 ...
Linux运维-运维课程d2-MySQL基本SQL语句(下)-14-DISTINCT去重操作.mp4
在IT行业中,数据实时写入去重处理方法是大数据处理领域的一个重要环节,尤其是在高并发、大规模数据流处理的场景下。数据去重是确保数据质量和有效性的关键步骤,它防止了重复数据对分析结果的影响,提高了存储效率...
标题《论文研究-基于词语权重的改进DSC中文网页去重算法.pdf》表明本文主要研究的对象是中文网页去重领域中的算法改进。具体来说,作者屠辉和刘刚在已有的DSC(Dynamic Self-Clustering)网页去重算法基础上,引入了...
标题“行业分类-物理装置-一种数据去重系统中的冷热索引识别与分类管理方法”暗示了我们讨论的主题集中在数据去重系统中如何区分并管理不同类型的数据,特别是冷热数据的识别和分类。 首先,我们需要理解什么是冷热...
### 基于特征句抽取的网页去重研究:一项深度探索 #### 摘要与背景 在信息爆炸的时代背景下,互联网成为人们获取信息的主要渠道。然而,互联网上信息的重复性问题日益严重,这不仅增加了搜索引擎的负担,降低了...
python编写的一些测试可以用到的小工具 会持续更新这个小工具系列哦~
在数据备份系统中,使用重复数据删除技术在消除重复数据提高系统存储的空间效率时,将必然会有多个逻辑映像共享去重后的数据实例,如果某个数据实例丢失或者数据被更改,将导致所有引用该实例的逻辑映像均发生错误,...
综上所述,哈尔滨工业大学信息检索研究室提出的大规模网页快速去重算法,通过创新的特征码技术与B-Tree索引策略,成功解决了传统聚类方法在处理大规模网页去重问题上的局限,展现了卓越的处理能力和精确度,对优化...
下面我们将深入探讨这个主题,了解不同的去重方法,并通过实践代码加深理解。 一、数组去重的重要性 在处理数据集合时,我们可能会遇到重复元素,这可能导致计算错误或资源浪费。例如,如果在用户列表中去重,可以...
网页去重是搜索引擎技术中的重要环节,旨在消除网络上的重复内容,提高搜索质量和效率。本文主要探讨了搜索引擎如何发现和处理重复网页,包括技术分析、基本...未来的研究可能会继续探索更加高效和精确的网页去重策略。
"电信设备-产品信息的实时去重方法和装置"这一主题聚焦于解决这些问题,通过创新的技术手段确保信息的唯一性,提高运营效率。以下是关于这个主题的详细解释: 一、产品信息的重要性 在电信领域,产品信息包括但不...