基于启发式搜索策略的主题网络爬虫算法的设计与实现

河北工业大学硕士学位论文基于启发式搜索策略的主题网络爬虫算法的设计与实现姓名：刘玮申请学位级别：硕士专业：计算机应用技术指导教师：沈西挺20081101河北工业大学硕士学位论文i基于启发式搜索策略的主题网络爬虫算法的设计与实现摘要随着全球信息化的进程逐渐加快,网络信息量的爆炸式增长，人们查找信息越来越难。Web搜索引擎的出现在一定程度上解决了这种矛盾。然而现行的大型通用搜索引擎无法根据用户所指定的主题进行针对性的搜索，主题搜索引擎应运而生。主题搜索引擎主要针对某一特定领域、某一特定主题或某一特定人群，提供内容集中而深入的信息与服务。主题网络爬虫作为主题搜索引擎的重要组成部分,它的好坏直接关系到所搜索到资源的质量，因此如何设计一个高质量的主题网络爬虫就成为了主题搜索引擎研究的一个重要课题。通用搜索引擎设计的目的是在网络上搜索尽可能多的高质量网页，然而Web信息容量的巨大使得网络爬虫不可能提取所有的Web页面，即使能够全部提取，也没有足够大的空间来存放。通用网络爬虫的信息采集方式是盲目的，通常使用宽度优先搜索，深度优先搜索和有限深度的宽度搜索三种策略。主题搜索引擎与通用搜索引擎不同，它的设计目标是尽可能多的搜索与主题相关的网页，尽可能少的搜索与主题无关的内容，提高采集主题资源的效率。主题网络爬虫设计的关键是如何将待爬行的URL按照某种策略进行排序，使得与主题相关的、质量高的URL优先爬行，爬行的过程逐渐向主题领域聚焦。论文首先分析了主题搜索引擎与通用搜索引擎体系结构的异同,主题搜索引擎的信息采集策略，即主题网络爬虫的实现方式。目前比较有代表性的主题搜索策略如：基于启发式搜索算法和基于文本分类的搜索算法。论文通过分析各种搜索算法的优缺点，进行整合和改进，设计出一个基于启发式搜索策略的主题网络爬虫。在主题表示中利用向量空间模型提取主题关键词的算法，并且根据反比文档频率计算出关键词的权重。在预测链接价值的算法中，采用启发式搜索算法，即先通过在线获得的领域知识评价待访问链接的价值，借以推断信息资源的分布情况，然后按一定的原则选择价值昀大的链接进行下一步的搜索，找到到达目标节点的昀佳路径，删除不好的节点，保留那些好的节点。论文设计了一个基于启发式搜索策略的主题网络爬虫，对其执行流程给出了精确的算法描述，提出了若干关键算法的解决方案。详细阐述了链接主题相关度预测算法和网页主题相关度分析算法的实现。昀后通过实验，证明了论文设计的主题网络爬虫具有较高的搜索效率。关键词：主题网络爬虫，搜索策略，启发式搜索，VSM，页面过滤基于启发式搜索策略的主题网络爬虫的设计与实现iiDESIGNANDIMPLEMENTATIONOFALGORITHMONTOPIC－SPECIFICWEBCRAWLERBASEDONHEURISTICSEARCHSTRATEGYABSTRACTWiththeprocessofglobalinformationtechnologyspeedingupgradually,theamountofwebinformationexplosivegrowth,it’smoreandmoredufficultytofindinformation.TheemergenceofwebsearchEnginecansolvethiscontradictioninsomedegree.However,existinglargegeneralsearchenginecann’tbespecifiedbyuserbasedonthethemeoftargetedsearch.Thetopic-specificsearchengineemerged.Topic-specificsearchenginetargetaspecificarea,aspecificthemeoraspecificgroupofpeople,toprovidefocusedanddeep-goinginformationandservices.Focusedwebcrawlerisanimportantpartoftopic-specificsearchengine.Goodorbadoftopic-specificwebcrawlerisdirectlyrelativetothequalityofcollectedinformation.Howtodesignahigh-qualityfocusedwebcrawlerbecameaimportantthemeontopic-specificsearchengine.Thegoalofdesigninggeneralengineistosearchasmanyhigh-qualitypagesaspossible,sotheinformationretrievalstrategyofgeneralwebcrawlerisblind,commonlyuseswidth-firstsearchstrategy,depth-firstsearchordepth-limitedwidthsearch.Topic-specificsearchengineisdifferentfromgeneralsearchengine,itsgoalofdesignistothelargestpossiblenumberofsearchpagesassociatedwiththetheme,thelowestpossiblenumberofsearchhasnothingtodowiththetheme,canimprovetheefficiencyofcollectedtopic-specificinformation.Thecriticalpointofdeginetopic-specificwebcrawlerishowtocomputethepriorityofURLs,makehigh-qualityURLrelevanttospecificsubjectcrawl,thecrawlingprocessgraduallyfocusonthesubjectfield.Firstly,thispapeanalysesimilaritiesanddifferencesaboutarchitecturesoftopic-specificsearchengineandgeneralsearchengine,informationretrievalstrategyoftopic-specificsearchengine,thatis,theimplementationoftopic-specificwebcrawler.Thecurrentrepresentativesearchstrategyoftopic-specificwebcrawlerisasfollows:heuristicsearchalgorithmandonthebasisofclassifysearchalgorithm.Inthispaper,byanalyzingtheadvantagesanddisadvantages河北工业大学硕士学位论文iiiofvarioussearchalgorithm,tointegrateandimprove,designatopic-specificwebcrawlerbasedonheuristicsearchstrategy.ItusesVectorSpaceModeltoextractsubjectkeywordsandcomputetheweightsofkeywordsbasedoninversedocumentfrequencyinsubjectexpression.Thepredictionofhyperlink’salgorithmvalue,usingheuristicsearchalgorithm,thatis,firstthroughaccesstoacquiredknowledgeofthefieldonlinetoevaluatethevalueoflinkshasn’tbeenvisited,toinferthedistributionofinformationresources,accordingtocertainprinciplesandthenchoosethelargestvalueofthelinktothenextstepofthesearch,foundthebestpathaccessingtotargetednode,deletebadnodes,toretainthosegoodnodes.Thispaperdesignedatopic-specificwebcrawlerbasedonheuristicsearchstrategy,giveaprecisedescriptionofthealgorithmtoitsimplementationprocess,madeanumberofcriticalalgorithmforthesolution.ItelaboratesthepredictivealgorithmsonvalueoftheLinksandtheanalysisalgorithmofwebpagesrelatedtothespecificsubject.Finally,accordingtoanalyzingtheexperimentaldata,itshowsthatthetopic-specificwebcrawlerwhichthispaperdesignedisrelativelymoreefficient.KEYWORDS:topic-specificwebcrawler,searchstrategy,heuristicsearch,VSM,pagefiltering河北工业大学硕士学位论文1第一章绪论§1-1课题的研究背景随着信息技术的不断发展，互联网技术也得到了迅猛发展，而在互联网上大家每天用的频率昀高的就是搜索引擎，人们已经把它当作日常学习、工作、休闲不可缺少的一个工具。大家都知道用搜索引擎可以快速的找到自己想找的资料或信息。Google、百度、雅虎等众多搜索引擎的强大搜索功能给我们的生活带来了莫大便捷。但随着网民对搜索引擎的依赖程度越来越高，满意度却越来越低。虽然今天的搜索引擎看起来已经非常的强大，但是当我们查询一个确切的信息时，还是会有大量的时间浪费在搜索上。根据iResearch艾瑞市场咨询昀新发布的《个人门户发展趋势研究报告》，其中57.9%的网民表达了对搜索引擎结果中冗余信息多的不满，艾瑞通过网络调研和街访方式获得的1809份有效样本中，网民对搜索引擎主要不满意的内容主要集中在冗余信息多、找不到足够的资料、有价值信息太少等多个方面。据赛迪网调查，有六成的网民认为面向某一领域的搜索引擎对其非常或比较重要，因此当网民有了例如租房、吃饭、找工作等某种特定需求时，他自然希望能够使用面向这些特定需求的搜索引擎。但这些需求的复杂性与多样性都是传统搜索引擎无法满足的。所以要找到更加公益性、更加客观和真实的内容，必须有更多精细化、专业化、非商业性的搜索引擎出现，主题搜索引擎应运而生，并逐渐展露侵蚀和霸占细分市场的趋势[1]。主题搜索引擎是由主题爬行器，索引器，检索器和数据库几部分组成的。主题爬行器负责从网络上自动抓取页面，索引器负责对页面内容及其关键词进行索引，并存储到数据库中。检索器负责从数据库中取出用户需要的网页内容。其中主题爬行器作为主题搜索引擎的重要组成部分，决定了整个搜索引擎的页面来源，对主题爬行器的研究是至关重要的。§1-2课题的研究意义在现代信息社会中，人们需要在浩如烟海的信息世界中找到自己想要的有用信息，优秀的通用搜索引擎的广泛应用，在很多方面给人们利用Web信息提供了大量帮助。然而，随着人们对Web搜索服务的种类要求越来越专业化，对搜索服务的