爬行蜘蛛搜索引擎

收稿日期:2010唱07唱03;修回日期:2010唱08唱20作者简介:滕召生(1982唱),男,湖南怀化人,硕士,主要研究方向为网络信息检索(zstengusst@gmail.
com);胡德敏,男,上海人,副教授,博士,主要研究方向为生产过程控制、软件理论.
网络蜘蛛在网络论坛领域的研究与设计滕召生,胡德敏(上海理工大学光电信息与计算机工程学院,上海200093)摘要:为了提高网络蜘蛛在爬行网络论坛时的爬行效率,从论坛布局结构特点出发,分析论坛所具有的普遍特征,设计了一个针对论坛的特殊的网络蜘蛛爬行策略.
通过对大量论坛的布局结构分析发现,用户感兴趣的信息都使用设计者事先设计好的布局结构展现给用户.
而这种布局结构可以通过DOM树体现出来,对DOM树进行操作,提取出URL,然后对重复的URL进行过滤.
实验表明该爬行策略提高了网络蜘蛛爬行效率,节省网络带宽及本地存储空间.
关键词:网络蜘蛛;文档对象模型树;页面重复区域;爬行策略;重复模板中图分类号:TP311畅1文献标志码:A文章编号:1001唱3695(2011)02唱0492唱03doi:10.
3969/j.
issn.
1001唱3695.
2011.
02.
023StudyanddesignonWebspiderinInternetforumsTENGZhao唱sheng,HUDe唱min(SchoolofOptical唱Electrical&ComputerEngineering,UniversityofShanghaiforScience&Technology,Shanghai200093,China)Abstract:ToimprovethecrawlingefficiencywhenWebspideriscrawlingforums,fromthelayoutandstructureofforums,Thispaperanalyzedtheuniversalfeatureofallforums,anddesignedatargetingWebspidercrawlingstrategy.
Theanalysisofmanyforumsprovedthatamajorityofinformationwasshowedtotheusersbythepre唱designedlayoutandstructurewhichcouldbereflectedbyDOMtree.
Throughtheoperationtothetree,URLcouldbecollected,andthentherepeatedURLbefiltrated.
ExperimentresultsshowthatspidercrawlingstrategyinthispapercanincreasetheefficiencyofthecrawlingofWebspidersandsavessubstantialnetworkbandwidthandspacesoflocal唱storage.
Keywords:Webspider;DOM(documentobjectmodel)tree;repetitiveregion;crawlingstrategies;repetitivetemplate0引言网络蜘蛛即Webspider,是一个很形象的名字.
把互联网比喻成一个蜘蛛网,那么spider就是在网上爬来爬去的蜘蛛.
网络蜘蛛是通过网页的链接地址来寻找网页,从网站某一个页面开始,读取网页的内容,找到在网页中的其他链接地址,然后通过这些链接地址寻找下一个网页,这样一直循环下去,直到把这个网站所有的网页都抓取完为止.
如果把整个互联网当成一个网站,那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来.
普通的网络蜘蛛的爬行策略有广度优先、深度优先和最佳优先搜索策略.
在实际应用中,广度优先策略和最佳优先搜索策略应用比较广泛.
随着互联网的迅速发展,以用户为中心的、所有的或大部分由用户贡献内容的Web作为数据资源变得越来越重要.
网络论坛是一个典型代表,每天有成千上万的网络用户在论坛上进行各方面的讨论,发表数不清的贴子.
这些贴子涉及到人们日常生活的每一个方面,是人类知识的一个数据库.
因此,论坛抓取对搜索引擎、网络数据挖掘等有着非常高的应用价值.
一些商业搜索引擎、网络数据挖掘公司也都已在研究如何更高效地抽取论坛数据,以提高其搜索结果的质量,如百度、雅虎、谷歌、微软等公司.
传统的网络蜘蛛[1]广泛应用于各种网络场合,然而对于不同的网站(如论坛),有着不同的结构特征,普通单一的网络蜘蛛则不能有效地对其进行爬行.
如何高效地抽取论坛数据,首先要对论坛网站的特征进行深入的研究,然后再针对其具有的特征设计出一套有效的、高效的爬行策略.
网络论坛有着与一般网站不一样的特征,具体表现在两个方面:a)它的数据是存储在数据库中,当用户访问到论坛网站时,系统把存储在数据库中的数据按事先设计好的模板展示给用户,这种模板可能是设计人员专门设计出来的或是某种软件生成的,而这些模板都是以重复的形式出现的,也称之为重复模板[2];b)网络论坛里有非常多的链接是重复的,即是许多超链接是链接到同一个URL[3]的,如一个网络论坛网站有一百个主题,而每页只能显示十个主题,每个页面上都有导航链接分别指向一到十页,并且还有如上一页、下一页之类的导航链接,这样十个页中有一百多个链接,而这一百多个链接真正只指向十个页面.
因此如果设计一套针对上述特征的网络蜘蛛的爬行策略,过滤掉指向相同页面的URL并重点爬行重复区域里的URL地址,就会提高网络蜘蛛的爬行效率.
1问题描述及相关研究工作由于以上所述的特征,对于单一的普通的网络蜘蛛来说,第28卷第2期2011年2月计算机应用研究ApplicationResearchofComputersVol畅28No畅2Feb畅2011它不能有效地对网络论坛进行有效的爬行,如广度优先爬行策略的蜘蛛[4],一些主题包含的贴子量非常大,会需要数十甚至数百个页面才能够全部显示出来,而一些重要的信息可能就是在最深的那些贴子里.
而广度优先蜘蛛根本不可能爬行所有的页面,因为这个主题里的贴子量太大,包含贴子的页面太多,因而需要很多页面才能显示出来,对网络蜘蛛来说是太深.
而深度优先蜘蛛会爬行很多重复的页面,如一个注册的用户登录论坛失败时,会重复出现相同的一个页面,导致网络蜘蛛重复爬行此页面.
另外,如图1中圆角矩形,在作者一栏和下面的页面导航中,在作者栏中对于单一的普通蜘蛛来说每个链接它都会爬行一次,当一个作者写多个主题时,如果作者栏圆角矩形所示,有四个主题是为同一个作者.
在这种情况下,普通蜘蛛会对每一个链接进行一次爬行,其实这样是没有必要的,因为每一个链接都是链接到同一个页面.
对于图1的底部的页面导航链接地址,此论坛中共有十页这样的主题,而每一页都有这样的导航链接,对于普通蜘蛛来说,在每一个页面中都会去进行爬行,就造成了大量的重复爬行.
正如上所说,如果按单一的普通蜘蛛的爬行策略,会有大量的重复爬行,这样对于提高蜘蛛效率、节省网络带宽、本地的存储容量造成很大的损失.
在国内外已有很多公司开始着力于网络论坛的爬行策略的研究,但是由于商业机密等因素的影响,较详细介绍网络蜘蛛技术的文章并不多.
北大天网是国内高性能网络爬虫的先行者,它的架构经历了集中式向分布式的改进,能够胜任10亿级的网页搜索,其基于站点的两阶段哈希机制有效地解决了搜索过程中Crawler动态加入和退出的问题.
IRLBOT是TAMU开发的大规模网络Crawler,它们宣称已经抓取了60亿网页.
该爬虫能胜任100亿级网页爬行,可伸缩性很强,在礼貌爬行和反垃圾页面上做了很多工作.
康柏系统研究中心设计的名叫Mercator的爬行器.
系统采用多线程同步方式实现并行处理,并加入了很多优化策略如DNS缓冲、延迟存储等以提升爬行器运行效率.
它采用的数据结构可以不管爬行规模的大小,在内存中只占有限的空间.
这些数据结构的大部分都在磁盘上,在内存中只存放有限的部分,伸缩性很强.
但这些爬虫都不是针对网络论坛这个领域进行设计的,因此当其在爬行网络论坛时并不能达到非常好的效果.
这些蜘蛛都可以归为单一的普通蜘蛛,根本没有针对网络论坛的特征进行分析,从而在网络论坛的爬行上效率低,占网络带宽大,对本地存储空间要求也大.
在针对网络论坛的蜘蛛中最具代表性的是微软亚洲研究院设计的iRobot[2],是一个智能的网络论坛爬行程序.
这个系统由两部分组成:a)离线建立网站地图和爬行路径选择部分;b)在线爬行部分.
第一部分通过监控接口事先准备好的样板页面里挖掘出有用的信息,如建图、指导接下来的爬行和选路径.
通过对样板页面的分析处理把具有相似布局和URL地址的页面分到一个类簇里,这样每个簇里的页面布局和URL格式都相似,然后再把每一个簇当成是一网站地图的一个顶点,并且同时把边也都加进去.
通过相关模块选择有最优的爬行路径.
在线抓取部分在上面的基础上可以进行爬行了,当抓到一个页面后,把其送到traversalpathlookup模块,同时把下一个要爬行的URL送入这个模块,通过这个模块,把抓取下来的页面通过与图上的所有顶点进行对比,如果在图中有其对应的顶点,并把其加入到这个顶点中,如果没有,就在图上新建一个顶点并且加入它的链接.
同时把下一个要抓取的URL提取出来,并抓取.
在文献[2]中,它得利用监控接口使其达到一个更好的效果,并且需要事先在目标站点爬行一些页面,以抓取到一些有代表性的页面,利用这些页面建立一个页面链接图,然后利用此链接图来决定如何爬行.
此方法的不足之处在于需要监控接口和事先建立页面链接图所需爬行的页,且它没有很好地解决上面所述的第二个问题,造成很多重复爬行.
在文献[5]中,它没有针对性地对所有URL进行爬行,进行了大量的重复爬行,而且爬行的URL可用性比较低,没有根本解决提高爬行效率和节省带宽这些问题.
在文献[6~8]中也同样存在和文献[5]这样的问题.
2爬行策略通过对大量的论坛布局结构的研究发现,所有的论坛都具有如下共同的点的特征:a)论坛的所有数据都是存储在数据库里,当用户登录或访问到论坛网站时,系统会根据用户的请求把相关的数据从数据库里提取出来,然后放到事先设计好的模板中,展现给用户;b)基本上所有展现给用户的模板都会与图1中的相似,而且以重复模板的形式展现出来,这些模板都是论坛设计者事先设计好的.
如此以来会发现,其实用户正下载感兴趣的或需要从中获取知识基本上是重复区域中的内容.
所以如果网络蜘蛛只爬行这些重复区域,这就把爬行的范围在很大的程度上减小了,因此就可以提高爬行效率、节省网络带宽.
本文中用重复模板来描述重复区域,在不同的页面中可能包含几个重复区域,但每个重复区域的结构可能有所区别,每个模板所包含的项目不同,且每项里用来存放的内容也不同.
如图1中,有的模板可能只包含主题、作者,最后回复.
而另一些模板可能包含更多或更少的项.
重复模板是一个重复区域的抽象,重复区域是重复模板的实例,它们的关系与面向对象中的类和实例之间的关系是类似的.
如何把页面中的重复区域检测出来并提取出相应的URL地址在论坛页面中,重复区域一般是按图1的形式展现出来,网络蜘蛛要怎样才能检测出这些重复区域在文献[9]中描述了如何刻画重复区域,用DOM树来描述一个重复区域,并用页面所包含的DOM树数量及DOM树的特征来描述一个页面.
在本文中也利用DOM树来描述重复模板,把论坛页面的HTML文件转换成相应的DOM树,然后对DOM树进行遍历,找出树中的重复子树,此子树就对应于页面中的重复模板,然后只提取出重复区域中的URL地址.
在文献[10]中详细描·394·第2期滕召生,等:网络蜘蛛在网络论坛领域的研究与设计述了如何检测出重复区域,并用DOM树来描述重复模板.
图1中椭圆的重复区域所对应的重复模板的DOM树,如图2所示.
图2中节点a表示此节点是有超链接的节点,当蜘蛛在爬行此页面时只提取出a节点所对应的超链接地址,并对其进行爬行.
这样就避免了对其他的一些不重要链接地址的爬行,提高网络蜘蛛的爬行效率.
上一章中提到,当在同一页面中的或者是同一类页面里的几个超链接都指向相同的一个页面,如果网络蜘蛛分别对其进行爬行是没有必要的,是资源的浪费,不利于提高网络蜘蛛的效率和节省空间.
同一类页面在本文中是指具有相同特征的一些页面的集合,共同特征主要指页面里包含相同重复模板.
从图1中可以看到,当前是第一页,共有十页.
这十页里都包含有椭圆里的重复区域,因此都具有相同重复模板,所以把这十个页面看成是同一类.
为了把具有相同特征的页面进行聚类,需要把每一个页面都表示成某一形式,以便于聚类操作.
本文中把具有相同重复模板的页面看成是一类,在描述一个页面时就可以把它描述成此页面包含哪些重复模板及数量.
为了使网络蜘蛛不爬行重复的页面,在每一个类中设置两个用来存储URL地址的容器,一个用来存放已经爬行过的URL地址,另一个用来存放待爬行的URL地址.
当网络蜘蛛从一个页面提取出一个URL地址时,首先在此类中已经爬行过的URL地址和待爬行的URL地址进行查询,如果已在这些URL地址中,就丢弃此URL地址,否则,则将它放入待爬行的URL地址容器中.
这样就实现了对一个URL地址只爬行一次.
综合上述,得到网络蜘蛛对论坛网站的爬行策略,具体的过程是:首先网络蜘蛛对网络论坛上一个种子页面爬行,然后把此页面中的重复区域检测出来并把重复区域中的URL地址提取出来,接着把此页面的重复区域用相应的重复模板表示,把此页面用重要模板来描述,因此该页面就表示成拥有什么样的重复模板及模板的数量,然后再用此页面到已有的页面类簇中去检索与自己相似的类(方法见文献[2]),如果没有找到相似的,就把此页面作为一个新的类增加到类簇中去,并把从重复区域中提取出来的URL地址与已爬行的和待爬行的URL地址进行匹配,如果已存在就丢弃,否则将其存放到待爬行的URL地址中.
如果找到了与其相似的页面类,就把此页面放到此类中,并把重复区域的URL地址和本类中已爬行的和待爬行的进行匹配,如果已存在就丢弃,否则将其存放到待爬的URL地址中.
具体算法流程如图3所示.
每爬行一个页面都迭代地进行图3中算法的操作.
详细的伪代码如下:WPUwill_parse_url=seed唱site'surl,PUparsed_url=0,Ppage_feature=0,PCpage_cluster=0foreachurlinWPUwill_parse_urlCrawling(url);Changetheparsedpage(htmlfile)toDOMPpage_feature=repetitiveDOMtemplateandcorrespondingquantityURLS=allurlsincludeinPpage_featureifPpage_featureinPCpage_clusterifURLnotinWPUwill_parse_urlandPUparsed_urlWPUwill_parse_url=URLSendifelseaddthispagetoPCpage_clusterWPUwill_parse_url=URLSendifPUparsed_url=urlendfor注:WPUwill_parse_url表示待爬行url,PUparsed_url表示爬行过的url,Ppage_feature表示每个页面的特征,PCpage_cluster表示页面簇,URLS表示用来存储url的一个临时变量.
3实验结果与性能分析所有的实验都是在以下的环境下运行:处理器为Intel溎CoreTM2DuoCPUT7250@2.
0GHz(2CPUs);内存为2046MB;操作系统为:MicrosoftWindowsXPProfessional(5.
1,版本2600).
为了进行对比,用普通的广度优先的爬虫对一些论坛进行爬行,如表1所示.
表1普通蜘蛛下载的页面数论坛网站下载的总页面数包含帖子的页面数bbs.
usst.
edu.
cn132426347www.
l唱ok.
com73254098bbs.
itclubs.
net2567412765bbs.
gmv.
cn216776134645由于网络蜘蛛最终要下载的是包含贴子的那些页面,在实验中,把下载的总页面数据统计出来,然后再把包含贴子的页面统计出来.
接下来用本文提出的爬行策略的爬行对相同的论坛进行爬行,并对相应的数据进行统计如表2所示.
表2普通蜘蛛和本文的爬行策略的下全率论坛网站①②普通蜘蛛③④本文的爬行策略③④bbs.
usst.
edu.
cn132429794634764.
8%726874.
3%www.
l唱ok.
com73256460409863.
4%519080.
3%bbs.
itclubs.
net25674194371276565.
6%1557380.
1%bbs.
gmv.
cn21677620508813464565.
7%14460470.
5%注:①下载的总页面数;②该论坛包含帖子的页面数;③下载的包含帖子的页面数;④下全率.
在表2中用了下全率来描述本文提出的爬行策略的下载精确度,即下载下来的页面占总页面的比率.
论坛中实际包含的含有贴子的页面是通过人工统计出来的.
(下转第520页)·494·计算机应用研究第28卷下,每轮选择的active节点较DELIC少,剩余alive的节点较DELIC多,覆盖率比DELIC高.
4结束语本文根据内分泌激素的作用机理,提出了基于激素调节的传感器网络覆盖算法,节点之间通过发送和接收相应的激素来选择一组active节点检测环境.
仿真实验表明,在满足区域有效覆盖的条件下,HCA选出的active节点分布均匀,且产生ac唱tive节点的个数较UC和DELIC少,HCA有效地延长了传感器网络的寿命.
本文下一步的研究任务是,如何对这些active节点进行合理的分簇,使得每个簇包含一个簇头和若干个成员节点,各个成员节点将检测到的环境信息发给其所在的簇头,然后簇头将收集到的信息发送给sink节点,这样可进一步地减少传感器网络总体能量的消耗.
参考文献:[1]张万会,王复周.
神经、免疫及内分泌系统间的关系[J].
生理科学进展,1993(3):261唱268.
[2]HUANGChi唱fu,TSENGYC.
Thecoverageprobleminawirelesssensornetwork[C]//Procofthe2ndACMInternationalConferenceonWirelessSensorNetworksandApplications.
2003.
[3]毛莺池,刘明,陈力军,等.
一种高效节能的与节点位置无关的传感器网络覆盖协议[J].
计算机研究与发展,2006,43(2):187唱195.
[4]ZHANGYi唱peng.
Ahormonebasedtrackingstrategyforwirelesssen唱sornetwork[C]//ProcofIEEEInternationalConferenceonIntelligentComputingandIntelligentSystems.
2009:104唱108.
[5]DONGDa唱yuan,YOUHai唱feng.
Ahormone唱basedclusteringalgorithminwirelesssensornetworks[C]//Procofthe2ndInternationalConfe唱renceonComputerEngineeringandTechnology.
2010:555唱559.
[6]YOUNISO,FAHMYS.
HEED:ahybrid,energy唱efficient,distribu唱tedclusteringapproachforAdhocsensornetworks[J].
IEEETransonMobileComputing,2004,3(4):366唱379.
[7]HEINZELMANW,CHANDRAKASANA,BALAKRISHNANH.
Application唱specificprotocolarchitectureforwirelessmicrosensornet唱works[J].
IEEETransonWirelessCommunications,2002,1(4):660唱670.
(上接第494页)表3列出了本文提出的爬行策略以及普通网络爬虫的时间代价.
从实验结果可以看出,本文提出的针对论坛的网络蜘蛛爬行策略比一般普通蜘蛛下全率要相对高些,并且在时间上所花的代价要小.
表3爬行的时间代价论坛网站普通蜘蛛所用的时间/s本文的爬行策略所用的时间/sbbs.
usst.
edu.
cn4235www.
l唱ok.
com2920bbs.
itclubs.
net9340bbs.
gmv.
cn6003004结束语本文提出了网络蜘蛛对网络论坛爬行的一种新的爬行策略,特点在于它爬行了包含有大量的有价值的数据的页面,而且在爬行效率和节省网络带宽方面都有很大的提高.
通过实验结果可以看出,本文提出的针对论坛的蜘蛛爬行策略是有效的和经济的,此策略对应用于真正的项目中有一定的应用价值.
本文提出的策略都是基于中文的且基本有一定的固定结构布局的论坛网站进行的研究和实验.
在今后,还会对本策略进行进一步的研究以提高其效率等各方面.
参考文献:[1]BRINS,PAGEL.
Theanatomyofalarge唱scalehypertextualWebsearchengine[J].
ComputerNetworks,1998,30(1唱7):107唱117.
[2]CAIR,YANGJM,LAIW,etal.
iRobot:anintelligentcrawlerforWebforums[C]//ProcofWWW.
[S.
l.
]:ACM,2008.
[3]RFC1738,Uniformresourcelocators(URL)[S/OL].
(2009唱10唱25).
http://www.
faqs.
org/rfcs/rfc1738.
html.
[4]BAEZA唱YATESRA,CASTILLOC,MARINM,etal.
Crawlingacountry:betterstrategiesthanbreadth唱firstforWebpageordering[C]//Procofthe14thWWW.
2005:864唱872.
[5]GUOY,LIK,ZHANGK,etal.
Boardforumcrawling:aWebcraw唱lingmethodforWebforum[C]//ProcofIEEE/WIC/ACMInterna唱tionalConferenceonWebIntelligence.
2006:745唱748.
[6]ZHANGJ,ACKERMANMS,ADAMICL.
Expertisenetworksinon唱linecommunities:structureandalgorithms[C]//Procofthe16thWWW.
2007:221唱230.
[7]GLANCEN,HURSTM,NIGAMK,etal.
Derivingmarketingintel唱ligencefromonlinediscussion[C]//Procofthe11thKDD.
2005:419唱428.
[8]SHIB,XUG,MAWY.
Webforumcrawler:US,7599931[P].
2009.
[9]ZHENGS,SONGR,WENJR,etal.
Jointoptimizationofwrappergenerationandtemplatedetection[C]//Procofthe13thKDD.
2007:894唱902.
[10]ZHAIY,LIUB.
StructureddataextractionfromtheWebbasedonpartialtreealignment[J].
IEEETransonKnowlDataEng,2006,18(12):1614唱1628.
·025·计算机应用研究第28卷