浅析搜索引擎抓取算法.doc

浅析搜索引擎抓取算法
搜索引擎技术是一种信息技术,主要包括抓取算法和排名算法。为公平起见,搜索引擎公司一般不会公开其算法的细节,因为如果公开这些算法,某些网站可能会利用它来改善其排名,搜索结果将会被网站的站长们操纵,从而影响搜索结果的中立性。
搜索引擎采用的算法可以被看做是一个黑盒,但是通过多种分析之后,就可以对主要内容和策略进行推测。
搜索引擎的抓取算法
搜索引擎工作的第一步就是获得互联网上的信息。现在的互联网是如此庞大,信息量每天都在飞速增长,检索和分类将是一项非常巨大的工程,必须采用自动化的方式来实现。网络内容抓取器就是这样的工具,它访问网页上的超链接,像"一传十,十传百…"一样,从少数几个网页开始,逐步延伸到互联网的其他网页。
网络蜘蛛
网络内容抓取器常被形象地称为"蜘蛛",而互联网就是一个蜘蛛网,蜘蛛就在这张网上不断获取信息。
蜘蛛从网站中的某个页面(通常是首页)开始,读取网页的内容,并找到该网页中的链接地址,然后通过它们寻找下一个网页,这样一直循环下去,直到把所有的网页都访问并抓取下来。
每个主流的搜索引擎都有自己的蜘蛛,例如:Googlebot(Google蜘蛛)、baiduspider(百度蜘蛛)、Yahoo Slurp(Yahoo蜘蛛)、Msnbot(MSN蜘蛛)、Scooter(Altavista蜘蛛)、Lycos_Spider_(T-Rex)、FAST-WebCrawler(Alltheweb蜘蛛)、ia_archiver(alexa蜘蛛)、Slurp(INKTOMI蜘蛛)等。
抓取规则

在抓取的过程中可以采用两种方式:广度优先和深度优先。
(1)广度优先是指先抓取起始网页中链接的所有网页,然后再选择其中的一个链接网页,继续抓取在此网页中链接的所有网页,以图A所示的网页链接结构为例,蜘蛛的抓取顺序如下:
◆从A页面出发,首先抓取BCDEF页面。
◆从E页面出发,抓取H页面。
◆从F页面出发,抓取G页面。
◆从H页面出发,抓取I页面。
◆没有发现更多可抓取的页面,抓取过程结束。
图A
广度优先是目前常用蜘蛛抓取方式,因为此方法可以并行处理,提高抓取速度。
(2)深度优先是指蜘蛛从起始页开始,逐个链接跟踪下去,处理完这条线路之后再转入下一个页面,继续跟踪链接。以图A所示的页面链接结构为例,蜘蛛的抓取顺序如下:
◆从A页面出发,抓取F页面。
◆从F页面出发,抓取G页面,发现没有更多可链接的页面,于是回到F页面,发现F页面也没有更多的页面链接,于是回到A页面。
◆从A页面出发,抓取E页面,从E页面出发抓取H页面,从H页面出发抓取I页面。
◆回到A页面,抓取D页面。
◆从A页面出发,抓取C页面。
◆从A页面出发,抓取B页面。
◆没有发现更多可抓取的页面,抓取过程结束。
深度优先的算法一般采用堆栈结构实现,其优点在于设计蜘蛛时比较容易。

对于搜索引擎来说,要抓取互联网上所有的网页几乎是不能的。从目前公布的数据来看,容量最大的搜索引擎也只能抓取整个互联网中40%左右的网页,主要原因如下:
◆现有的抓取技术无法遍历所有的网页,有许多网页无法从其他网页的链接中找到。
◆信息的存储技术存在瓶颈,如果按照每个页面的平均大小为20KB计算,100亿