搜索引擎网页去重算法

标签: 技术文摘 | 发表时间:2013-02-22 21:47 | 作者:alberttan
出处:http://blog.sina.com.cn/albertsem
  相关统计数据表明:互联网上近似重复的网页的数量占网页总数量的比例高达29%,完全相同的网页大约占网页总数量的22%.研究表明,在一个大型的信息采集系统中,30%的网页是和另外70%的网页完全重复或近似重复的。

    即:互联网的网页中相当高的比例的网页内容是近似相同或完全相同的!

搜索爬虫抓取会产生网页重复的类型
1.多个URL地址指向同一网页以及镜像站点  
    如:www.sina.com  和www.sina.com.cn
    指向同一个站点。
 
2. 网页内容重复或近似重复
    如抄袭、转摘的内容,垃圾信息等   
  
网页内容近似重复检测的两种应用场合:

 一:在用户搜索阶段
       
          目标是根据与用户给定的查询词找到已有索引列表中近似重复的文档,并排序输出。

二:爬虫抓取发现阶段
     对一个新的网页,爬虫程序通过网页去重算法,最终决定是否对其索引。
 

 
近似重复网页类型,根据文章内容和网页布局格式的组合分为4种形式:

一:两篇文档在内容和布局格式上毫无区别,则这种重复称为完全重复页面。

二:两篇文档内容相同,但布局格式不同,则这种重复称为内容重复页面。

三:两篇文档有部分重要的内容相同,并且布局格式相同,则这种重复称为布局重复页面。

四:两篇文档有部分重要内容相同,但布局格式不同,则这种重复称为部分重复页面。

重复网页对搜索引擎的不利影响:
正常情况下,非常相似的网页内容不能或只能给用户提供少量的新信息,但在对爬虫进行抓取、索引和用户搜索 会消耗大量的服务器资源。 

重复网页对搜索引擎的好处:
 如果某个网页重复性很高,往往是其内容比较比较受欢迎的一种体现,也预示着该网页相对比较重要。应予以优先收录。当用户搜索时,在输出结果排序时,也应给与较高的权重。

重复文档的处理方式:
1.删除
2.将重复文档分组

近似重复网页举例:
搜索引擎近似重复检测流程:
通用网页去重算法:
SimHash文档指纹计算方法 
1)从文档中提取具有权值的 特征集合来表示文档。如:假设特征都是由词组成的,词的权值由词频TF 来确定。  

2)对每一个词,通过哈希算法生成N位(通常情况是64位或更多)的二进制数值,如上图,以生成8位的二进制值为例。每个词都对应各自不同的二进制值。

3)在N维(上图为8维)的向量V中,分别对每维向量进行计算。如果词相应的比特位的二进制数值为1,则对其特征权值进行加法运算;如果比特位数值为0,则进行减法运算,通过这种方式对向量进行更新。

4)当所有的词都按照上述处理完毕后,如果向量V中第i维是正数,则将N位的指纹中第i位设置为1,否则为0。

  Jacccard相似性计算方法:
 如上图,A和B代表2个集合,集合C代表集合A和B相同的部分。 A集合包含5个元素,B集合包含4个元素,而两者相同的元素有2个,即集合C的大小是2. Jaccard计算两个集合相同的元素占总元素的比例。
如图中,集合A和集合B共有7个不同的元素,相同元素个数2个,所以集合A和集合B的相似性为:2/7

 

在实际应用中,集合A 和 集合B 的特征都会经过哈希计算,转化成N位(64位甚至更多)的二进制数值,从而将集合A和B的相似性比较转化为二进制数值的比较,称为“ 海明距离”的比较。两个位数相同(如均为64位)相同位置上不同的二进制数值的个数称为“海明距离”。


对给定的文档A,假设经过特征抽取--哈希指纹运算后的二进制数值是: 1 0 0 0 0 0 1 0

对给定的文档B,  假设经过特征抽取—哈希指纹运算后的二进制数值是:0 0 1 0 0 0 0 1


经过比较,文档A 和 B的 第1位、第3位、第7位、第8位四个位置的数值不同,即海明距离为4. 两个文档的二进制位数不同的个数越多,海明距离越大。海明距离越大,说明两个文档不相似性越大,反之,则越小。


不同搜索引擎可能会以不同的海明距离值 来判断两个网页内容是否近似重复。相关分析认为,一般情况下,对一个64位的二进制数值来说,将海明距离<=3作为判断是否近似重复的标准比较合理.



  青春就应该这样绽放   游戏测试:三国时期谁是你最好的兄弟!!   你不得不信的星座秘密

相关 [搜索引擎 网页 算法] 推荐:

搜索引擎网页去重算法

- - 醉清风
  相关统计数据表明:互联网上近似重复的网页的数量占网页总数量的比例高达29%,完全相同的网页大约占网页总数量的22%.研究表明,在一个大型的信息采集系统中,30%的网页是和另外70%的网页完全重复或近似重复的.     即:互联网的网页中相当高的比例的网页内容是近似相同或完全相同的. 搜索爬虫抓取会产生网页重复的类型:.

搜索引擎链接算法之:HITS算法解析

- - CSDN博客推荐文章
本文节选自《 这就是搜索引擎:核心技术详解》第六章.       HITS算法也是链接分析中非常基础且重要的算法,目前已被Teoma搜索引擎(www.teoma.com)作为链接分析算法在实际中使用. 6.4.1 Hub页面与Authority页面.      Hub页面和Authority页面是HITS算法最基本的两个定义.

Google公布调整搜索引擎算法的细节

- tt5ryan - Solidot
淘宝网女装秋装 写道 "尽管Google拥有很多开放的产品和项目,但搜索引擎算法一直是保密的. 换句话说,搜索是Google的一个黑盒子. Google此前表示,如果Google向外界公布搜索引擎算法,那么将会引起搜索结果排序的混乱. 但Google周五在官方博客上发布了一则视频,视频给出了Google工程师调整搜索引擎算法的细节.

简易垂直搜索引擎的核心算法总结

- - CSDN博客架构设计推荐文章
倒排索引源于实际应用中需要根据属性值(字段)来查找记录(所在的文件位置). 这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址. 目前主流的索引技术有三种:倒排索引、后缀数组以及签名. 后缀数组虽然快,但是维护困难,代价高昂,不适合作为搜索引擎的索引. 而签名的速度和性能都不如倒排索引.

Goolge十年对搜索引擎算法做出的改善

- - CSDN博客互联网推荐文章
谷歌过去十年,在搜索引擎上做出了巨大的努力,其努力的方向就是不断完善搜索引擎算法,不断打击非真实的数据,从PR、nofollow、企鹅新算法的出现也是必然的. 2000年12月 – Google工具条. Google发布了浏览器工具条,正是这个工具条上绿色小条(PR值),日后让无数的站长为之疯狂,形成了买卖产业链.

JavaScript解析:让搜索引擎看到更真实的网页

- - 搜索研发部官方博客
长期以来,站长们选择使用JavaScript来实现网页的动态行为,这样做的原因是多种多样的,如加快页面的响应速度、降低网站流量、隐藏链接或者嵌入广告等. 由于早期的搜索引擎没有相应的处理能力,导致在索引这类网页上往往出现问题,可能无法收录有价值的资源,也可能出现作弊. 引入JavaScript解析的目的,正是为了解决上述两方面的问题,其结果也就是使搜索引擎可以更为清晰的了解用户实际打开该网页时看到的效果.

uSniff:BT种子搜索引擎

- leqoqo - 软件志
一、uSniff相关信息: 1、官方主页:http://www.usniff.com/ 2、简介:uSniff是一个BT种子搜索引擎,简单、易用、实时是其最大的优点,其搜索引擎数据库包含了17个知名种子站点的种子信息,目的是想发展成为世界上最大的BT种子搜索引擎,而且对于每个种子,该搜索引擎都会进行安全认证,以保证用户的正常使用.

人眼启发视觉搜索引擎

- feng823 - Solidot
Google上周宣布将支持声音和图片进行搜索,但一家创业公司在图像搜索方面走在了Google前面. 源自伦敦帝国学院研究项目的创业公司Cortexica,开发出视觉搜索工具,通过手机拍摄产品照片,它会自动呈现价格信息. Cortexica已经发布了一个用于比较酒价格的工具WINEfindr. Cortexica的视觉搜索技术是受到了人眼视觉系统的启发,它能识别出一个目标的关键特征,不受方位、大小、光线亮暗的影响.

比较好的学术搜索引擎

- hfut_chen - C++博客-首页原创精华区
     摘要: 1、http://scholar.google.com/. Google学术搜索滤掉了普通搜索结果中大量的垃圾信息,排列出文章的不同版本以及被其它文章的引用次数. 略显不足的是,它搜索出来的结果没有按照权威度(譬如影响因子、引用次数)依次排列,在中国搜索出来的,前几页可能大部分为中文的一些期刊的文章.

Blekko 对搜索引擎的新探索

- thinkingit - 知乎的博客
Blekko 这款搜索产品做的如何. 从目前我的使用过程来看,Blekko还是很让人激动的. 在谈Blekko之前就要先问:为何在搜索这个看似已经垄断的行业还会有人想去分一杯羹,这些小团队能与Google或微软这样的巨头抗衡吗. 比如之前的Powerset,后来的Cuil,和现在的Blekko. 在Google之前Yahoo是靠人工收录网页,Google的算法和蜘蛛革了搜索的命,一直垄断搜索业十余年,而现在随着WEB 2.0的发展,让人又看到了搜索业革命的火种,可以说Blekko就是这样的一个产品.