搜索引擎对网页去重技术算法- 用来解析伪原创与网页相似度

 首先,搜索引擎对所索引的所有网页进行页面净化和内部消重。

任何一家搜索引擎在尚未进行复制网页判断这一操作之前都定然会有个网页净化和内部消重的过程。搜索引擎首先要清除噪音内容,对网页内部的广告、版权信息、共同的页眉页脚部分等进行净化,然后提取出该页面的主题以及和主题相关的内容,用以排名工作,噪音内容是不计入排名权重之中的。

消重也差不多是这个意思,搜索引擎对其所收集的网页集里面主题相同或极端相似的,比如同一模板之中多次出现的共同代码,将其作为冗余内容,进行消除。

我们可以这样理解,最理想的状态之下,一篇原创文章,搜索引擎仅将标题和内容计入排名之中,其他全部都消除。

DocView模型就是一个自动分类和消重的模型,当然,不是非常准确。大家可以简单了解一下,DocView模型包括网页表识、网页类型、内容类别、标题、关键词、摘要、正文、相关链接等要素,它通过提取DocView模型要素的方法应用在网页自动分类和网页消重之中。

通过了解以上内容,我们就能大致明白,同一篇文章,为什么放到两个完全不同模板的站点之上,搜索引擎仍然能够正确识别出这是一个复制页面的原因了吧。

其次,搜索引擎对净化的页面进行重复内容的判断。

那么搜索引擎具体是如何判断复制页面的呢?以下内容是北大天网搜索引擎的去重算法,大部分来自对《搜索引擎——原理、技术与系统》相关知识的整理,大家可以自行参考相关文档。

现有方法大致可以分为以下三类:

1、利用内容计算相似

2、结合内容和链接关系计算相似

3、结合内容,链接关系以及url文字进行相似计算

现有绝大部分方法还是利用文本内容进行相似识别,其它两种利用链接关系以及URL文字的方法还不是很成熟,而且从效果看引入其它特征收效并不明显,所以从实际出发还是选择利用内容进行相似计算的算法。

搜索引擎判断复制网页一般都基于这么一个思想:为每个网页计算出一组信息指纹(信息指纹,英文是Fingerprint,就是把网页里面正文信息,提取一定的信息,可以是关键字、词、句子或者段落及其在网页里面的权重等,对它进行加密,如MD5加密,从而形成的一个字符串。信息指纹如同人的指纹,只要内容不相同,信息指纹就不一样。搜索引擎在对爬取的网页建立索引的时候需要对重复内容的网页进行识别和消重,这就要用到信息指纹),若两个网页有一定数量相同的信息指纹,则认为这两个网页的内容重叠性很高,也就是说两个网页是内容复制的。注意一点,算法提取的信息不是针对整张网页,而是把网站里面共同的部分如导航条、logo、版权等这些网页的噪音信息过滤掉后剩下的文本。

很多搜索引擎判断内容复制的方法都不太一样,主要是以下两点的不同:

1、计算信息指纹的算法;

2、判断信息指纹的相似程度的参数。

部分算法简介:

1、分段签名算法

这种算法是按照一定的规则把网页切成N段,对每一段进行签名,形成每一段的信息指纹。如果这N个信息指纹里面有M个相同时(m是系统定义的阙值),则认为两者是复制网页。这种算法对于小规模的判断复制网页是很好的一种算法,但是对于像Google这样海量的搜索引擎来说,算法的复杂度相当高。

2、基于关键词的复制网页算法

像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个左右关键词最为恰当。

当然,以上算法只是给SEO一个思路而已,并非搜索引擎判断复制网页的全部算法。只要在SEO的过程中注意原创和“伪原创”,大可不必太在乎这个算法。

网页去重技术之i-match算法

网页去重是网页预处理技术的一种,而网页预处理技术是搜索引擎工作的一个重要环节,这个环节处理的好不好直接影响到搜索引擎的终端客户的用户体验问题,也是判断一个搜索引擎好坏的重要标志。
当前网页去重的方法可分为三类:
1 基于内容(content-based)的去重,网页之间的重复度可以通过网页的内容来比较。
2 基于链接信息(anchor-based)的去重,链接信息,是指出现或邻近于指向网页的链接附近的文字。链接信息窗口通常包含一个人工创建的目标文档的摘要。这个摘要包含了很明显的人工总结信息和人工分类信息。
3 基于链接 (link-based)的去重,是通过网页的入链来比较网页是否重复。
根据内容重复的大小可以大致分为以下四类:主要从内容和格式来区分
1.full-layout duplicate 意为内容和格式完全相同。这种最悲剧了,完全就是ctrl+c,ctrl+v。
2.partial-layout duplicates 意为文档部分重要内容格式相同。
3.partial-content duplicates 意为文档部分重要内容格式不同,但内容相同。
4.full-content duplicates 意为内容完全相同,但格式不同

i-match算法历史和介绍说明

I-Match算法是Abdur chowdhury et al.在2002提出的,这种算法是对去重算法的复杂度降到O(d*logd),I-Match算法有一个基本的假设说“在文档集中高频词和低频词不太会影响文章语义”意思是在文挡中,特别高频的词和特别低频的词无法反应这一个文挡的真实内容。

通俗点讲我们在比较两件事物的相似性时,往往都会拿能均衡的反应这事物本质的东西来比较,就像比赛时,要去除一个最高分和最低分,然后再变算总分一样。I-Match算法是给予特征取样,特征提取是基于长期收集的统计资料。特征是以关键词作为网页的特征项,清华大学使用的提取关键词的方法是在文章中逗号,句号的前后各取1 个汉字,作为字符串。哈工大使用的方法是在文章中各个句号的前后各取2 个汉字。

虽然提取关键词的方法不同,但是都是以标点作为文中的提取标记,这种方法效率较高,然后统计每个关键词在所有网页中出现的次数,与出现该关键词的网页数,并进一步根据每个关键词的IDF(Inverse Document Frequency)值判断其取舍,关键词x的IDF值tx的计算为tx=log(N/n),其中N是收集的网页总数,n是其中含有关键词x的网页数。去掉IDF值较小的词,从而获得了更好的文档表示。

经过过滤的关键词按降序排列构成文档的“指纹”(fingerprint),指纹相同的文档被视为近似文档。

i-match算法框架:

1. 获取文档(或者是主体内容)
2. 将文档分解成token流,移除格式化的标签
3. 使用term的阈值(idf),保留有意义的tokens
4. 插入tokens到升序排列的排序树中
5. 计算tokens的SHA1
6. 将元组(doc_id,SHA hash) 插入到某一词典中,如果词典有冲突,这两个文档相似。

i-match算法缺陷:

1 如果文档内容较少可能所有文档都是相似文档
2 精度不是很高
3 处理数据比较大因为他是需要特征取样的需要硬盘空间大

搜索引擎消重算法之scma算法

关于消重主要是针对搜索引擎在抓取或者索引或者排序的过程中对内容相似或者重复的网页进行过滤和删除的操作,当然这里面比较复杂这篇主要说下搜索引擎是如何利用SCMA算法进行消除重复页面的。
SCAM(Stanford Copy Analysis Mechanism)是由斯坦福大学Narayanan Shivakumar等人提出,用于检测复制文件和剽窃文件的一种算法。SCAM的方法受到了信息检索技术的启示,提取的特征是基于单词在文件中出现的频率。
SCMA算法大致是这样的首先是计算出每篇文档中各个单词的词频,然后将文档用词频向量的方法表示出来,计算每个词频向量之间的距离,在一定的范围之内就判断为相似的文档。
具体来讲就是,SCAM首先统计文件中各单词出现的频率,然后按照信息检索中常用的倒排索引存储法(Inverted Index Storage),存储文件与其词频信息。
最后,SCAM算法在特征比较阶段,参照了向量空间模型VSM(Vector Space Model),提出了相关频率模型RFM(Relative Frequency Model),用以度量文件的相似性。其中VSM是采用余弦公式来度量两个文件的相似性;而RFM是对余弦公式进行了改动,如公式(1)所示。
公式(1)sim(R,S)=max{subset(R,S), subset(S,R)
(其中wi∈c(R,S)满) 其中,sim(R,Q)代表两个文件的相似性,N表示单词总数,ai表示单词i的权值,Fi(R)表示单词i在文件R中出现的次数,wi表示单词i。
SCAM算法特征提取步骤是采用的基于单词出现的频率,也就是说特征提取的粒度是单词级别,其空间复杂度是O(mn),时间复杂度是O(mn)2,其中,m表示单词总数,n表示网页数目。

搜索引擎消重算法之SCMA算法
关于消重主要是针对搜索引擎在抓取或者索引或者排序的过程中对内容相似或者重复的网页进行过滤和删除的操作,当然这里面比较复杂这篇主要说下搜索引擎是如何利用SCMA算法进行消除重复页面的。
SCAM(Stanford Copy Analysis Mechanism)是由斯坦福大学Narayanan Shivakumar等人提出,用于检测复制文件和剽窃文件的一种算法。SCAM的方法受到了信息检索技术的启示,提取的特征是基于单词在文件中出现的频率。
SCMA算法大致是这样的首先是计算出每篇文档中各个单词的词频,然后将文档用词频向量的方法表示出来,计算每个词频向量之间的距离,在一定的范围之内就判断为相似的文档。
具体来讲就是,SCAM首先统计文件中各单词出现的频率,然后按照信息检索中常用的倒排索引存储法(Inverted Index Storage),存储文件与其词频信息。
最后,SCAM算法在特征比较阶段,参照了向量空间模型VSM(Vector Space Model),提出了相关频率模型RFM(Relative Frequency Model),用以度量文件的相似性。其中VSM是采用余弦公式来度量两个文件的相似性;而RFM是对余弦公式进行了改动,如公式(1)所示。
公式(1)sim(R,S)=max{subset(R,S), subset(S,R)
(其中wi∈c(R,S)满) 其中,sim(R,Q)代表两个文件的相似性,N表示单词总数,ai表示单词i的权值,Fi(R)表示单词i在文件R中出现的次数,wi表示单词i。
SCAM算法特征提取步骤是采用的基于单词出现的频率,也就是说特征提取的粒度是单词级别,其空间复杂度是O(mn),时间复杂度是O(mn)2,其中,m表示单词总数,n表示网页数目。

原文 http://www.cnblogs.com/mfryf/archive/2013/06/06/3122290.html

发表评论

必填

选填

选填

必填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。