下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 基于Larbin的网络爬虫体系结构的研究与改进

基于Larbin的网络爬虫体系结构的研究与改进.doc

基于Larbin的网络爬虫体系结构的研究与改进

Bert平
2018-04-05 0人阅读 举报 0 0 暂无简介

简介:本文档为《基于Larbin的网络爬虫体系结构的研究与改进doc》,可适用于综合领域

基于Larbin的网络爬虫体系结构的研究与改进Larbin基于的网络爬虫体系结构的研究与改进,李跃健朱程荣(,)同济大学计算机科学与技术系上海arbin,。rl,,:Lu摘要是一种开源的网络爬虫网络蜘蛛抓取效率极高它的去重方法的设计效率极高占用的内存非常,,M,,url小理论上下载万网页使用的内存只有然而它的冲突将会对它的性能大打折扣实际上当达到的时就已,。rlhash,u经有很大的冲突概率导致内存利用率的降低以及很多网页不能被抓取通过研究布隆过滤器将的算法进行改,,,Larbinurl。进把原本一对一的映射变成多对一的映射减小了冲突概率同时也将大大地提高在内存方面的利用率经,,M,url,,,过实验检验使用布隆过滤器同样内存当达到的占有率时采用个映射可以使得冲突概率最小达到,,Bloomfilter。而没采用的冲突概率则达到了:Larbinurl关键词爬虫哈希算法去重布隆过滤器,,,:TP:A:X()中图分类号文献标识码文章编号StudyandmpovementonSystemAchtectuesIrrirofeeLarbinWbCrawlr,,LIYuean,ZHUChengrongji(DepartmentofComputerScenceandTechnoogy,TongUnversty,Shangha,Chna)iljiiiiiAbstract:Larbinisanopensourcewebcrawler,itscratchespagesveryefficiently,Onurlcomparingalgorithm,ithasgreatefficiencyandcostverylittlememory,Intheory,downloadingmillionpagescostonlyMmemory,butitsurlconflictwillgreatlyaffectitsperformance,Infact,whenoftheurlsareinmemory,thenewurlwillhavepossibilitytoconflict,resultinginlowermemoryusageandmanypages,,cannotbecrawed,BystudyngtheBoomfter,wththehashagorthmofurdstngushmprovestheorgnantoamanytoonelililililiiiiiilimappng,reducngtheprobabtyofconfct,andasogreatyenhancetheLarbn,smemoryutzaton,Fromtheexperment,ntheMmemoryiiilililliiliiiiwithusedbyurl,ifmakethemapnumbertobe,theconflictpercentagereachestonlyo,whileitremainsifnobloomfilterisappliedtothealgorithm,eosLarbnwebcrawerhashurdstngushBoomfterKywrd:illiiililoogle,YahooG来的再到后来的搜索引擎也经历了重引言,,大的发展特别是到目前由于互联网信息的急剧膨胀,,经过二十多年的发展互联网经历了蓬勃的发展www,,在这当中最为显著的便是也即万维网的壮大如Inktomi(:已搜索引擎也开始进行细化分工像国外的Yahoo),。今已经完全融入到人们日常生活的方方面面从最初被收购它本身并不是直接面向用户的搜索引,只有几个网站到现今已经超过亿而且仍在不断增,Overture(GoTo,Yahoo)、擎但像包括原已被收购。加当中网站的丰富给人们带来了更多交流信息的渠LookSmartMSNHotBot、、等在内的其他搜索引擎提供全,:道同时也提出了一个很大的挑战如何能够快速地找,。文网页搜索服务国内的百度也属于这一类到所需要的有效信息:,一般来讲搜索引擎主要分两部分搜和索搜指的,Archie为此搜索引擎便应运而生从最初的到后,。是爬虫索便是收录系统,爬虫作为搜索引擎的数据采集器是搜索引擎的,最初数据来源对于一个搜索引擎能否很好收录网站,,,,。:有着至关重要的作用:收稿日期修回日期:(AA)基金项目国家高技术发展计划项目上海市,Larbni目前开源的爬虫中无论在性能上还是在()科委国际合作项目,,稳定性上都出类拔粹文中重点研究它的体系结构并,:(),,,作者简介李跃健男硕士研究方向为计算机应用朱程url,url。将写入磁盘等功能它采用了多级队列的方Larbin的工作原理,,,,url式有效地实现了缓存当内存中的超过一定的数TCPIP,对于网络而言基于的通信编程有几,,量时便将队列写入磁盘当需要解析时再读取回来保:种方法named证速度与内存开销的平衡另外还初始化了:,单线程阻塞这是最简单也最容易实现的一种一,,:Shellcurl个例子在中通过系统命令可以直接实现一SiteList,dns。,数组用来存放解析的前面已经说过,:个简单的爬虫然而效率问题也显而易见由于采用阻LarbinDNS,的模块是独立出来的这样可以充分降低,dns,塞方式读取每次的连接伴随着重新解析另外在,解析次数理论上只要解析过一次就不需要再进行解,,建立连接写入请求读取结果这些步骤也会产生一定,。析大大提高了效率,。的延时从而无法有效地利用服务器的全部资源startThread(startWebserv接下来就是服务器开启,,:,多线程阻塞建立多个阻塞的线程分别请求不同er,),,进程启动微型服务器便于用户查看url。,的相对于单线程阻塞它能更有效地利用机器资Larbin,,的运行状态它能每过一段时间便刷新状态所,。,源特别是网络资源无数线程在同时工作所以网络。以客户端打开浏览时都能查看到即时的情况,CPU能够比较充分的利用但无数的线程会很快把资URL,然后服务器开始进入队列调度和处理过程,。源消耗线程的频繁切换也会带来性能上的损失cron()队列调度由函数执行:单线程非阻塞这是目前使用的比较多的一种做==if((global::now)){,。法无论在客户端还是服务器都有着广泛的应用在,=global::readPriorityWaitglobal::URLsPriorityWaitgetLe,pollepollse一个线程内打开多个非阻塞连接通过ngth()ect,,l对连接状态进行判断在第一时间响应请求不但,=global::readWaitglobal::URLsDiskWaitgetLength(),CPU充分利用了网络资源同时也将本机资源的消耗}。dns,,降至最低这种方法需要对请求连接读写操作==if((global::now)){,都采用异步非阻塞操作它一方面能够建立尽量多的=global::readPriorityWait,,连接另一方面又不会占用大量的服务器资源特别是=global::readWaitCPU,Larbin。资源就是采用了这种编程模式}rl,u这段代码是调度的核心代码调度的过程如,,:global::nowwait图所示是判断这次是对r,watuli。里的进行处理还是对不是里的进行处理Larbin的模块结构,,,为或者的概率都是所以大约次arbin。L图为体系各模块关系。,url换一次处理时将加NamedSiteList,入队列同时DNS,更新这个主机的调用transfer()IP函数将解析的,,IPSiteList。地址存入队列*Getthenexutrl*hereisdefinedhowprioritiesarehandled*arbinL图体系各模块关系Larbn,istaticboolcanGetUrl(bool*testPriority){采用了模块化的程序设计系统分为以下,,:urDNShtml、、、lurl*u几大模块模块文件操作模块模块、、解析模块后台读取链接服务器模块后台统计信息服if(goba::readPrortyWat)lliii{,,。goba::readPrortyWatlliii务器模块=,Larbinuglobal::URLsPriorityWaitget()下面通过服务器运行的一整个流程来剖析,:global::namedSiteList,uhostHashCode(),,putPriorityUrl各模块的运作情况Wait(u),glob():服务器启动后调用函数进行初始化首先,larbin,conf,建立系统需要用的各全局变量然后打开returntrue,。读取相应的参数传给相应的全局变量比较重要的有,=}elseif(*testPriority,,(uglobal::URLsPriorityURLsDisk、URLsDiskWait,PersistentFifo,类型为主要管理=tryGet())!){url,url、,的调度包括的插入较验从磁盘读取We,vegotoneurl(priority),global::namedSiteList,uhostHashCode(),,putPriorityUrl(u)Larbnuril对队列的去重处理已经在各队列索引当中returntruehash,。普遍采用了算法所以运行效率非常高另外由}else{,于采用了单线程非阻塞的模式并发的线程可以达到=*testPriorityfalse,,很快的下载速度在带宽允许的条件下一天就能下载TrytogetanordinaryurlG,hash的网页但同时也正由于它的算法没有对if(goba::readWat)lli,,冲突进行解决只是采取了简单的无视直接导致了一,,{global::readWaitr,,ul些不被抓取而且特别是当队列里的数量更大时=,uglobal::URLsDiskWaitget(),,。冲突的概率更大,goba::namedSteLst,uhostHashCode(),,putUrWatlliiliurl:下面来看看它所采用的去重算法(u)Larbinhash,中表的定义是先建立一个数组长度returntruehashSze,hashSzetype,h,ii为其中定义在中大小为ese}l{=,,,Mugoba:ULsDstryGet()ll:Rik所以根据定义首先会申请大约的空=。ashTablehashcode:hif(u!){间这是的的算法,goba::namedSteLst,uhostHashCode(),,putUr(u)lliiluinturl::hashCode()returntrue={unsignedinthport}else{=unsignedintireturnfalse=whe(host,,!)ili{}=h*ost,,hhi}i}}}=iwhe(fe,,ilili!=){=h*hfeil,i,i}returnhhashSize},根据推算bit个需M,要的空间理论上可以存放大约rlu的调度图url,url万个然而假如算起来一个网站有个main()fetchDns(),接下来函数中开始执行从,,,的话这样理论上来说就只能存放万个网站然而dnsSites,newQuery中取得解析测试的站点名然后用url,伴随着的增多会导致冲突概率的增大当数据达(),,dnsAns(),提出解析请求当检测状态通过时调用,到个网站的时候冲突概率便能达到而且DNS。更新列表url。会随着增多冲突可能性急剧恶化fetchOpen(),下一个调用的是得到站点后调用,dns解析fetch(),url,html对将指向的文件下载下来并对代码dns,dns同一站点内请求可以只做一次可以采用,,,url。进行解析提取其中的地址加入队列rl,IPu解析完成的存入缓冲的方式将主机名独立于,接下来又开始重复执行以上各步骤不段地爬下,arbin。,L队列用于发起连接使用同样在存储时也采。去hash,,用了码的映射存储优点是速度快缺点也与上。type,hnamedSiteListSize面的情况类似在里定义了,为万也就是说当达到个网站时冲突概率便会Larbin的特点,Larbin有所以从这个角度上说会产生误判的概url处理,=m),(n如果哈希表满半即每次搜索需要改进方案,,探测次每个元素占位总空间是arbinhash,L可以看出源代码当中多处涉及到算,,*bytes,,法对于一个企业级搜索引擎来说如何更高效地=,GBhash提高它的效率与正确性呢这当中改进算法就,nm,,如果采用新的算法同样的达到因为采是一个比较好的选择它能在多方面提高它的整体性,,M,用的是位操作所以只有的空间为所需的,:url、、dns。能包括去重队列赋值解析等等,。空间小很多而且误判的概率为百万分之一误判的哈希算法是将任意长度的二进制值映射为固定长,,,,度的较小二进制值这个小的二进制值称为哈希值然:(K)概率为指映射的数量:,而接下来会遇到比较大的问题如何解决冲突接下来nkk,m,=f(x)(e)发现很多人把绝大的精力花在了如何处理冲突这个问,,,kk,,题上问题是解决了但是性能也会受到非常大的影,====,KP(error)()通过运算当,响而如何针对实际应用绕开冲突倒不失为一个很好mm,ln。的方法nn,,mn时误判率最低也就是说值保持,对于搜索引擎而言一定数量的误判是可以忍受。线性就能保证误判率的稳定,,,的譬如说而如何按照传统的哈希算法即使哈,,希函数足够精妙设想要抓取一万个网站每个网站平结束语arbnLi文中深入研究了这个开源网络爬虫的源代=,**均个网页还是需要,,码分析了其体系架构深入探讨了它的一些核心算,,M,,法总结了它在爬虫算法上的一些优点同时也发现了左右的空间这还是保守估计所以如何有效地,利用空间同时保证较低的误判经过研究发现可以url,它在去重算法的不足于是研究了一套多维哈希,。采用多个哈希码映射这样能够大大降低冲突的概率。去重算法以弥补原先算法高内存消耗的不足经过论,,,,如图所示对地址进行多个哈希运算计算出url证采用新的算法后可以大大地提高队列的内存利,四位地址用来存储哈希这样可以大大减少冲突的概。用率并减小误判率。率:参考文献,,,,,,EPOLLLNUXI崔滨万旺根余小清等基于机制的网,J,,,,():络游戏服务器实现方法微计算机信息,,,,larbin,J,,,孟时王彦网络爬虫的体系结构电脑学习,,,():,,,,,Lnuxi王锋王伟张璟等基于的网络爬虫系统,,,,J,,,():,计算机工程rul图将映射到向量空间,,,,Web李刚周立柱郭奇等领域相关的网站抓取方法,,,,J,,,():,计算机科学改进方案的优势,,,J,,王小林刘宏申搜索引擎的设计研究计算机技术与发,,,这种方法继承了本身哈希表的高效性包括空间,,,():,展、,上采用位运算查找时间为线性复杂度等等另外也避,,Web王芳陈海建深入解析主题爬虫的关键性原理,,,,。免了处理冲突所带来的异构及维护的复杂性,,J,,,,():,微型电脑应用,,,,,J,,,mbit,袁浩黄烟波网页标题分析对主题爬虫的改进计算根据这个算法对于有个位的哈希表,,,bitarray如果想要保证的误判率则这个只能存储,,,():,机技术与发展m,,K个元素因而有大量的空间被浪费而采用了,,DNS薛峰赵问道基于最大网络收益的内容路由算法,,,hash,khashfunctoni,J,,,,():,个映射即个将每个元素改为对浙江大学学报,,,Web张帆李琳娜杨炳儒基于的智能信息采集及处kbits,,k应于个因为误判度会降低很多并且如果参数,,,,J,,,,():理系统设计与实现计算机工程m,m,m和选取得好一半的可被置为举例来说如果值,,,:为亿传统的哈希算法会处理冲突时间复杂度为,,,,,Hash王后珍张焕国杨飚多变元函数的构造与分析,,J,,,,():,电子学报,,,,,BloomFilter丁振国吴宝贵辛友强基于的大规模网页n,()下转第页m,,,,。,令只要向相应的主节点提出即可如图所示结束语igBee,Z在文中设计和实现了基于技术的无线温。,湿度传感器网络监测系统采用星型网络结构集成CC了内核的无线射频芯片以及高集成度的SHT,数字温湿度传感器构建硬件节点设计并实现。,了节点软件通过在实验室的实际测试表明本系统、、,具有低功耗低成本易于维护扩展等优点具有很好。的实用性是现有有线温湿度监测系统的理想替代设。计:参考文献,,,,,,王殊阎毓杰胡富平等无线传感器网络的理论及应,,M,,:,:用北京北京航空航天大学出版社,CPCON,CCPLMNdatasheetHIREIIARY,,图终端节点程序流程图(rev,,)SWRSA,M,,,s,,,:CHPCON,,lIMhatreV,RosenbergC,DesignGuidelinesforWirelessSensor,,系统的测试结果NetworksCommuncaton,CusterngandAggregaton,J,,Adiilii,CCSHT将上述系统配置好后使用和构,ocNetworksJourna,():,Hl,建的温湿度监测系统就可以正常运行了将主节点连,,HillJL,SystemArchtectureforWreessSensorNetworksiilPCRS,接到机的串口打开串口调试软件或者超,D,,Berkeley:UCA,,,级终端就可以获得主节点汇聚的来自子节点的温湿,,SHT,J,,张艳丽杨仁弟数字温湿度传感器及其应用,,,,度数据同时还可以获得各个子节点的唯一位短地,():,工矿自动化,,,,杜鹏雷吴晓杨丽平等面向精准农业的感知节点传,。址用来区分各个子节点在实验室内部署了个,,,J,,,,():感器驱动与控制计算机技术与发展ZigBee,,。无线传感模块包括个主节点个子节点,,:某一时刻获得的温湿度信息数据如表所示,,王戈张效义可用于环境监测的无线传感器网络节点,,表实验室某时刻测得的温湿度信息,,J,,,,():,,的设计传感器与微系统刘子京,ZigBee裴文江基于协议的无线传感器网络研究,,短地址温度值湿度值,,J,,,,():,,计算机技术与发展敬海霞胡向,,J,,东无线传感器网络的路由协议研究计算机技术与发x,,,,,():,展x,,,,杨永雷朱军无线传感器网络中异步成簇算法的研究,,J,,,,():,计算机技术与发展x,,,,饶云华代莉基于无线传感器网络的环境监测系统x,,J,,,,():,武汉大学学报,,,,,,唐旋来汪秉文汤强等无线传感器网络在桥梁健康监x,J,,,,():测中的应用研究计算机技术与发展,,x檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪()上接第页,,J,,,():,,去重策略研究现代图书情报技术,,,,R,,hash,吴军布隆过滤器一种新的海量信息的算法,,MtzenmacherM,CompressedBoomFters,J,,EEEACMililI,s,l,,:google,,研究院,TransactionsonNetworking,,():,,,BroderA,MitzenmacherM,Networkapplicationsofbloomfil,,MitzenmacherM,Asecondlookatbloomfilters,J,,Commu,ters:asurvey,J,,InternetMathematics,,():,nicationsoftheACM,,():,

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/14

基于Larbin的网络爬虫体系结构的研究与改进

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利