搜索引擎的设计与实现

WEB搜索引擎的设计与实现摘要随着网络的迅猛发展。网络成为信息的极其重要的来源地，越来越多的人从网络上获取自己所需要的信息，这就使得像GOOGLE40，百度39这样的通用搜索引擎变成了人们寻找信息必不可少的工具。本文在深入研究了通用搜索引擎基本原理、架构设计和核心技术的基础上，结合小型搜索引擎的需求，参照了天网，LUCENE等搜索引擎的原理，构建了一个运行稳定，性能良好而且可扩充的小型搜索引擎系统，本文不仅仅完成了对整个系统的设计，并且完成了所有的编码工作。本文论述了搜索引擎的开发背景以及搜索引擎的历史和发展趋势，分析了小型搜索引擎的需求，对系统开发中的一些问题，都给出了解决方案，并对方案进行详细设计，编码实现。论文的主要工作及创新如下1在深刻理解网络爬虫的工作原理的基础上，使用数据库的来实现爬虫部分。2在深刻理解了中文切词原理的基础之上，对LUCENE的切词算法上做出了改进的基础上设计了自己的算法，对改进后的算法实现，并进行了准确率和效率的测试，证明在效率上确实提高。3在理解了排序索引部分的原理之后，设计了实现索引排序部分结构，完成了详细流程图和编码实现，对完成的代码进行测试。4在完成搜索部分设计后，觉得效率上还不能够达到系统的要求，于是为了提高系统的搜索效率，采用了缓存搜索页面和对搜索频率较高词语结果缓存的两级缓存原则来提高系统搜索效率。关键词搜索引擎，网络爬虫，中文切词，排序索引ABSTRACTWITHTHERAPIDLYDEVELOPINGOFTHENETWORKNETWORKBECAMEAVITALINFORMATIONSOURCE,MOREANDMOREPEOPLEAREOBTAININGTHEINFORMATIONTHATTHEYNEEDFROMTHENETWORK,THISMAKINGWEBSEARCHENGINEHASBECOMEESSENTIALTOOLTOPEOPLEWHENTHEYWANTTOFINDSOMEINFORMATIONFROMINTERNETINTHISPAPER,WITHINDEPTHSTUDYOFTHEBASICPRINCIPLESOFGENERALSEARCHENGINES,THEDESIGNANDCORETECHNOLOGYARCHITECTURE,COMBININGWITHTHENEEDSOFSMALLSEARCHENGINEANDINTHELIGHTOFTHE“TIANWANG“,LUCENESEARCHENGINE,IBUILDASTABLE,GOODPERFORMANCEANDCANBEEXPANDEDSMALLSCALESEARCHENGINESYSTEM,THISARTICLENOTONLYCOMPLETEDTHEDESIGNOFTHEENTIRESYSTEM,BUTALSOBASICALLYCOMPLETEDALLTHECODINGWORKTHISARTICLEDESCRIBLENOTONLYTHEBACKGROUNDOFSEARCHENGINES,BUTALSOTHEHISTORYOFSEARCHENGINEDEVELOPINGANDDEVELOPINGTRENDS,ANDANALYSETHENEEDSOFSMALLSEARCHENGINESANDGIVINGSOLUTIONSTHETOTHEPROBLEMSWHICHWASFOUNDINTHEDEVELOPMENTOFTHESYSTEM,ANDMAKINGADETAILEDPROGRAMDESIGN,CODINGTOACHIEVETHEMAINTHESISOFTHEARTICLEANDINNOVATIONAREASFOLLOWS1WITHTHEDEEPUNDERSTANDINGOFTHEWORKINGPRINCIPLEOFTHENETWORKSPIDERIACHEIVEDNETWORKSPIDERWITHUSINGDATABASESYSTEM2WITHTHEDEEPUNDERSTANDINGOFCHINESESEGMENTATIONANDSEGMENTATIONALGORITHMOFLUCENESYSTEM,IMADEMYOWNSEGMENTATIONALGORITHM,ANDGIVEALOTOFTESTSTOMYSEGMENTATIONALGORITHMTOPROVIDETHATMYSEGMENTATIONALGORITHMISBETTER3WITHTHEDEEPUNDERSTANDINGOFSORTEDANDINDEXALGORITHM,IDESIGNEDMYOWNSORTEDANDINDEXALGORITHMWITHTHEDATASTRUCTIDESIGNEDANDCODINGIT,ITWASPROVIDEDAVAILABLEAFTERLOTSOFTESTS4AFTERDESIGNOFSEARCHPART,IFOUDTHEEFFICIENCYOFTHEPARTISNOTVERYPOOR,SOIDESIGNEDTWOSTAGECACHEDEVICETOIMPOVETHEEFFICIENCYOFTHESYSTEMKEYWORDSSEARCHENGINE,NETSPIDER,CHINESESEGMENTATION,SORTEDANDINDEX目录第一章绪论111搜索引擎出现的背景及意义112搜索引擎的发展历史及趋势113本文主要工作314论文结构4第二章系统结构521概述522系统结构5221爬虫6222信息处理6223排序和索引6224搜索623搜索引擎主要指标及分析624开发语言725小结8第三章爬虫931概述932爬虫结构分析9321爬虫初始化10322从网页中提取URL11323URL存储12324从数据库中提取URL1233小结13第四章信息处理1441概述1442转换1543切词18431中文切词19432中文切词测试25433英文切词27434数字切词28435符号处理29436词语存储3044小结31第五章排序索引3351概述3352统计相关URL3353排序3454索引3655小结37第六章搜索3861概述3862实现搜索3863性能优化4164小结42第七章总结与展望4371总结4373展望44参考文献47致谢49WEB搜索引擎的设计与实现绪论1第一章绪论11搜索引擎出现的背景及意义网络的出现以及发展对于世界发展的意义是极其重要的，它让地球村的理念变成的现实，信息的传输不再受到时间和空间的限制。随着网络技术和应用的不断发展，互联网已经成为了信息的重要来源地，人们越来越依靠网络来查找他们所需要的信息。我们所处的是一个信息爆炸的时代，GOOGLE的索引在1998年开始工作,当时他们收集了2600万个页面,2000年就突破了10亿,到10年后的2008年达到了1,000,000,000,000,GOOGLE的数据库变成了全球最庞大的索引之一8，数量之庞大让我们震惊。这么巨大的数字导致了一个问题，“RICHDATA,POORINFORMATION“。我们就好像处在一个信息的迷宫，因此，如何有效快速的找到自己需要的信息成为了一个极其重要的问题。在没有搜索引擎的时代，用户希望寻找某方面的信息，就必须通过各种途径或者是网站之间的连接寻找，可以这样说，脱离的搜索引擎的网站，就像是信息海洋中的一个一个的孤岛，用户必将面临巨大的搜索成本，同时必须付出大量的时间和精力。搜索引擎的出现改变了上述的现象4，它通过程序的自动搜寻并建立索引，将这些信息孤岛联系起来，形成了一张巨大的信息网，并且运用分布式计算的巨大力量，能够让用户从海量数据中摒除垃圾信息，获取想要的知识。搜索引擎不仅仅是节省了用户的时间，通过挖掉搜寻成本这座墙，它让许许多多的不可能成为可能。12搜索引擎的发展历史及趋势搜索经历了三代的更新和发展8第一代搜索引擎出现于1994年。这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常WEB搜索引擎的设计与实现绪论1慢，一般都要等待10秒甚至更长的时间。第二代搜索出现在1996年。第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50,000,000网页的索引数据库，每天能够响应10,000,000次用户检索请求。第三代搜索引擎年代的划分和主要特性至今没有统一的认识，不过至少可以肯定的是第三代搜索引擎是对第二代搜索引擎在搜索技术上的改进，主要增加了互动性和个性化等高级的技术，为用户使用搜索引擎获取信息获得更好的体验。至于互动性的评价标准是什么，以及第三代搜索引擎到底比第二代搜索引擎增加了多少价值尤其是为企业利用搜索引擎开展网络营销增加了哪些价值，目前并没有非常令人信服的研究结论。这也就是目前所谓的第三代搜索引擎并没有表现出太多优势的原因之一。现在，网络上有很多著名的搜索引擎，百度，GOOGLE，YAHOO等等，百度从2005年诞生到现在成为全球最大的中文搜索引擎，可想而知，发展的速度的多么的快，人们对搜索引擎的的需求的多大，百度的日点击率我无法在找到确切的数字，但是我们可以计算一下，截至2008年底，中国网民规模达到298亿人9，每个网民上网点击百度的次数应该不少于十次吧，像我们要在百度上找资料的网名点击率百次不止，所以百度的日点击率是多么惊人。搜索引擎经过几年的发展和摸索，越来越贴近人们的需求，搜索引擎的技术也得到了很大的发展。搜索引擎在将来的的发展趋势大概有以下几个方面101提高对用户输入的理解为了提高搜索引擎对用户检索提问的理解，就必须有一个好的检索提问语言，为了克服关键词检索和目录查询的缺点，现在已经出现了自然语言智能答询。用户可以输入简单的疑问句，比如“HOWCANKILLVIRUSOFCOMPUTER”。搜索引擎在对提问进行结构和内容的分析之后，或直接给出提问的答案，或引导用户从几个可选择的问题中进行再选择。自然语言的优势在于，一是使网络交流更加人性化，二是使查询变得更加方便、直接、有效。就以上面的例子来讲，如果用关键词查询，多半人会用“VIRUS”这个词来检索，结果中必然会包括各类病毒的介绍、病毒是怎样产生的等等许多无效信息，而用“HOWCANKILLVIRUSOFCOMPUTER”，搜索引擎会将怎样杀病毒的信息提供给用户，提WEB搜索引擎的设计与实现绪论2高了检索效率。2对检索的结果进行处理对检索的结果处理，有以下几个方向其一，使用链接评价，就是将网页的链接数量算作网页评分因素之一，这样搜索的结果就更加的能够满足用户的要求，在这个方面GOOGLE（WWWGOOGLECN）的“链接评价体系”已经做出了相当出色的成绩。其二，使用大众访问性，就是将访问数量（也可以叫做点击数量）算作网页评分的因素之一，这样想WWWSINACOMCN这样的网站的分数会很高，而这样的网站很多时候都是用户想找的，这样能够提高搜索引擎的准确率。其三，去掉结果中的附加信息。有调查指出，过多的附加信息加重了用户的信息负担，为了去掉这些过多的附加信息，可以采用用户定制、内容过滤等检索技术。3确定搜集返回，提高针对性在这个方面现在的发展的方向是其一，垂直主题搜索。垂直主题的搜索引擎以其高度的目标化和专业化在各类搜索引擎中占据了一系席之地，比如象股票、天气、新闻等类的搜索引擎，具有很高的针对性，用户对查询结果的满意度较高。我认为，垂直主题有着极大的发展空间。其二，非WWW信息的搜索。搜索引擎提供了例如FTP等非WWW信息的搜索。其三，多媒体搜索。搜索引擎还提供了例如包括声音、图像等等多媒体信息的检索。4提供更优化的检索结果在这个方面有两个主要的发展方向其一，纯净搜索引擎。这类搜索引擎没有自己的信息采集系统，利用别人现有的索引数据库，主要关注检索的理念、技术和机制等。其二，元搜索引擎。元搜索引擎METASEARCHENGING是将用户提交的检索请求到多个独立的搜索引擎上去搜索，并将检索结果集中统一处理，以统一的格式提供给用户，因此有搜索引擎之上的搜索引擎之称。它的主要精力放在提高搜索速度、智能化处理搜索结果、个性搜索功能的设置和用户检索界面的友好性上，查全率和查准率都比较高。13本文主要工作本文在深入分析通用搜索引擎基本原理、架构设计和核心技术的基础上，WEB搜索引擎的设计与实现绪论3结合开源搜索引擎LUCENE和天网搜索引擎的实现原理，设计并实现了一个可扩展，可复用的小型搜索引擎系统，本文的具体工作有以下几个方面1详细论述了系统结构，系统的设计原则以及目标。明确系统的功能，设计出详细的系统流程图。2分析了网络爬虫的工作原理，利用数据库设计出爬虫部分的详细流程图，并实现了系统的爬虫部分。3详细设计了系统的信息处理部分，并且给出了设计的流程图，在中文切成部分参照LUCENE的原理，做出了算法上的改进，对改进后的算法实现，并进行了准确率和效率的测试，证明在效率上确实提高。4根据排序和索引的原理，自己详细设计了这个部分，完成了详细流程图，并实现。5为了提高系统的搜索效率，采用了缓存搜索页面和对搜索频率较高词语结果缓存的两级缓存原则。14论文结构本文共分为七章第一章，绪论。主要阐述了论文的研究背景与意义、搜索引擎的发展现状、发展趋势、论文的主要工作和组织结构。第二章，系统结构。主要对整个系统进行的概念和功能进行了描述，并且对系统的各个部分进行了一个大概的介绍，并给出系统流程图。第三章，爬虫。对系统中的爬虫部分的原理进行了详细的说明，对爬虫部分详细设计了流程图，并给出对爬虫部分的代码实现和对代码进行一定程度的讲解。第四章，信息处理。对信息处理部分的原理进行详细的描述，详细设计了流程图，给出了信息处理部分各种切词部分代码实现，并且对代码进行了一定程度了解说。第五者，排序索引。对系统的排序和索引两个部分的原理进行详细的描述，并对用来实现排序和索引的数据结构进行详细的说明。给出流程图。第六章，搜索。对系统的最后一个环节搜索进行了描述，给出实现搜WEB搜索引擎的设计与实现绪论4索的消息步骤，并且对提高效率的两级缓存策略给出了详细的讲解。给出流程图。第七章，总结。对整个毕业设计的过程和项目进行了总结，并且分析了系统现有的不足，对不足之处给出了将进行改进的建议。WEB搜索引擎的设计与实现系统结构0第二章系统结构21概述搜索引擎41（SEARCHENGINES）就是指在WWW（WORLDWIDEWEB）环境中能够响应用户提交的搜索请求，返回相应的查询结果信息的技术和系统，是互联网上的可以查询网站或网页信息的工具2。它包括信息搜集、信息整理和用户查询三部分。搜索引擎的服务方式分为两种目录服务和关键字检索服务。目录服务是由分类专家将网络信息按照主题分成若干个大类，用户可以根据分类清晰地找到自己所需要的内容。关键字检索服务可以查找包含一个或多个特定关键字或词组的WWW站点。搜索引擎是互联网的第二大核心技术，涉及到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术，所以具有综合性和挑战性。22系统结构搜索引擎系统结构1分为爬虫，信息处理，排序索引，搜索四个部分，系统结构图如图21所示；图21系统流程图WEB搜索引擎的设计与实现系统结构1221爬虫爬虫也可以称作“网络爬虫程序”，“WEB爬虫”，“网络蜘蛛”，“网络机器人”。网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引擎的重要组成。传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。222信息处理信息处理指的是当爬虫从万维网上下载了网页，对网页中包含的信息进行处理，其中包括提取网页中包含的URL。为爬虫的继续提供所需要的URL，这个事很重要的，因为没有新的URL出现的话，爬虫程序就会停止，这样就无法获得全面的信息。信息处理还必须得网页显示的内容进行分析处理，把网页的内容切成词语。为下面的排序和索引部分提供相应的信息。223排序和索引在信息处理完成之后，每个网页都会被切成很多个关键词，同时每个词语都会有很过个相关的网页。排序所要做的事就是把每个词语的相关的网页按词语的出现次数进行排序，这样在进行搜索时结果的出现顺序提供依据。接下来的索引程序就是以词库为索引关键字建立索引，这样在搜索的时候就能够在最短的时间找出我们想要的结果。224搜索在上述的工作完成之后，便可以为用户提供搜索服务了，按照用户的关键字或词的输入，按照所建立的索引在最短的时间内找到相应的结果，返回相应的数据，然后在网页上显示返回的结果，是用户能够选择自己想要的信息。23搜索引擎主要指标及分析搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。这些指标WEB搜索引擎的设计与实现系统结构2决定了搜索引擎的技术指标。搜索引擎的技术指标决定了搜索引擎的评价指标。好的搜索引擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。毕业设计论文代做平台580毕业设计网是专业代做团队也有大量毕业设计成品提供参考WWWBYSJ580COMQQ3449649974召回率一次搜索结果中符合用户要求的数目与用户查询相关信息的总数之比准确率一次搜索结果中符合用户要求的数目与该次搜索结果总数之比相关度用户查询与搜索结果之间相似度的一种度量精确度对搜索结果的排序分级能力和对垃圾网页的抗干扰能力24开发语言本文在开发语言上选择的是C语言5，因为C在带来对应用程序的快速开发能力的同时，并没有牺牲C与C程序员所关心的各种特性。它忠实地继承了C和C的优点。C语言还有以下的优点151简洁的语法。语法中的冗余是C中的常见的问题，比如“CONST“和“DEFINE“、各种各样的字符类型等等。C对此进行了简化，只保留了常见的形式，而别的冗余形式从它的语法结构中被清除了出去。2精心设计面向对象在C的类型系统中，每种类型都可以看作一个对象。C提供了一个叫做装箱BOXING与拆箱UNBOXING的机制来完成这种操作，而不给使用者带来麻烦，这在以后的章节中将进行更为详细的介绍。C只允许单继承，即一个类不会有多个基类，从而避免了类型定义的混乱。在后面的学习中你很快会发现，C中没有了全局函数，没有了全局变量，也没有了全局常数。一切的一切，都必须封装在一个类之中。你的代码将具有更好的可读性，并且减少了发生命名冲突的可能。3完整的安全性与错误处理语言的安全性与错误处理能力，是衡量一种语言是否优秀的重要依据。C的先进设计思想可以消除软件开发中的许多常见错误，并提供了包括类型安全在内的完整的安全性能。NET运行库提供了代码访问安全特性，它允许管理员WEB搜索引擎的设计与实现系统结构3和用户根据代码的ID来配置安全等级。变量是类型安全的。4灵活性与兼容性在简化语法的同时，C并没有失去灵活性。正是由于其灵活性，C允许与C风格的需要传递指针型参数的API进行交互操作，DLL的任何入口点都可以在程序中进行访问。C遵守NET公用语言规范COMMONLANGUAGESPECIFICATION,CLS，从而保证了C组件与其它语言组件间的互操作性。元数据METADATA概念的引入既保证了兼容性，又实现了类型安全。25小结本章对基于因特网的搜索引擎结构和性能指标进行了分析，在这些原来的理解基础之上利用C技术完成了一个小的WEB搜索引擎，在接下来的章节将对搜索引擎结构中的网络爬虫设计进行说明，并给出关键部分的实现代码。WEB搜索引擎的设计与实现爬虫0第三章爬虫31概述网络蜘蛛即WEBSPIDER，是一个很形象的名字3。把互联网比喻成一个蜘蛛网，那么SPIDER就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的6，从公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的，如果按照每个页面的平均大小为20K（包含图片），100亿网页的容量是1002000G字节，即使能够存储，下载也存在问题（按照一台机器每秒下载20K计算，需要340台机器不停的下载一年时间，才能把所有网页下载完毕）。同时，由于数据量太大，在提供搜索时也会有效率方面的。因此，许多搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。32爬虫结构分析爬虫部分分为爬虫初始化，从网页中提取URL，对URL进行存储，从数据中提取URL四个部分，爬虫部分的流程图如图31所示，在本节将对爬虫的工作原理进行详细的描述WEB搜索引擎的设计与实现爬虫1图31爬虫流程图321爬虫初始化爬虫程序的开始是需要一个最初始的URL，爬虫将先下载这个URL的内容，然后提取里面所包含的URL，所以这个最初始的URL是很重要的，如果没有一个好的初始的URL，这个URL所包含的URL会很少，那么爬虫所能爬下的网页的数量也将大受影响。得到了初始的URL以后，就可以下载网页的内容了。以下就是下载网页的代码HTTPWEBREQUESTLOHTTPHTTPWEBREQUESTWEBREQUESTCREATEURL/创建连接LOHTTPTIMEOUT500/设置超时HTTPWEBRESPONSELOWEBRESPONSEHTTPWEBRESPONSELOHTTPGETRESPONSE/获取响应STREAMREADERLORESPONSESTREAMNEWSTREAMREADERLOWEBRESPONSEGETRESPONSESTREAM,SYSTEMTEXTENCODINGDEFAULT/获取返回的流HTMLLORESPONSESTREAMREADTOEND/读取流LOWEBRESPONSECLOSE/关闭连接有关于HTTPWEBREQUEST类说明如下12NETFRAMEWORK使用HTTPWEBREQUEST和HTTPWEBRESPONSE类来提供对HTTP协议的全面支持，而HTTP协议构成了所有INTERNET通信量中的绝大部分。每当静态方法WEBREQUESTCREATE遇到以“HTTP”或“HTTPS”开头的URI时，WEB搜索引擎的设计与实现爬虫2在默认情况下将返回这些从WEBREQUEST和WEBRESPONSE派生的类。在大多数情况下，WEBREQUEST和WEBRESPONSE类提供生成请求所需的一切，但如果需要访问作为属性公开的HTTP特定功能，则可以将这些类的类型转换为HTTPWEBREQUEST或HTTPWEBRESPONSE。HTTPWEBREQUEST和HTTPWEBRESPONSE封装“标准HTTP请求和响应”事务，并提供对通用HTTP头的访问。这些类还支持大部分的HTTP11功能，其中包括管线、块区、身份验证、预身份验证、加密、代理支持、服务器证书验证以及连接管理。自定义头和不是通过属性提供的头可存储在HEADERS属性中并可通过此属性访问。HTTPWEBREQUEST是WEBREQUEST使用的默认类，不需要注册它就可以将URI传递给WEBREQUESTCREATE方法。可以通过将ALLOWAUTOREDIRECT属性设置为TRUE（默认值），使应用程序自动遵循HTTP重定向。应用程序将重定向请求，而HTTPWEBRESPONSE的RESPONSEURI属性则将包含响应请求的实际WEB资源。如果将ALLOWAUTOREDIRECT设置为FALSE，则应用程序必须能够将重定向作为HTTP协议错误处理。应用程序通过捕捉STATUS设置为WEBEXCEPTIONSTATUSPROTOCOLERROR的WEBEXCEPTION来接收HTTP协议错误。RESPONSE属性包含由服务器发送的WEBRESPONSE，并指示遇到的实际HTTP错误。322从网页中提取URL当把网页的代码下载完毕后，就需要对代码进行一次遍历，找出并提取其中的URL，为爬虫的继续提供URL，对代码中的URL的提取采用的是正则表达式的方法，比较代码中所以匹配URL正则表达式的部分，然后遍历这个集合，逐条的读取其中的URL。以下为代码STRINGSTRREGEX“HTTP/WW/W/URL的正则表达式REGEXRNEWREGEXSTRREGEX,REGEXOPTIONSIGNORECASE/初始化一个REGEX对象，为比较作准备WEB搜索引擎的设计与实现爬虫3MATCHCOLLECTIONMRMATCHESHTMLCODE/比较并得出代码中匹配的集合FORINTI0ITHISISMYFIRSTWEBPAGE程序在处理的时候会自动的去掉和两个部分，然后对THISISMYFIRSTWEBPAGE这个部分进行正常的处理，这中处理的方式会很好的切到网页中所包含的文字信息，但是它有这样几个问题A首先，这样的方式程序会对HTML中的每个标签都进行如上的处理，一个HTML有时候标签所占得字符是远远的多于它所包含的文字信息。这样的话程序的效率会因为处理很多无用的标签而浪费支援，减低了效率。B面对像这样标签，它中间的内容是无用的，它只是对网页的显示效果有用，但是上面的程序还是会对它中间的内容进行我们的切词程序，这样不仅大大的减低了程序的效率，还切刀了许多根本于网页的内容无关的词语，这样就会降低搜索引擎的准确性。WEB搜索引擎的设计与实现信息处理2C面对像这样的标签，必须对它进行解析，才知道它运行后会得到什么结果，暂且不管能不能实现对它的解析，即使能够写出这样的程序，但是不得不花大量的时间去想这个程序，而其最后这个程序也得花大量的资源堆网页的进行解析，所以这个问题否定了上面的方法的可行性。2面对和这两个标签，采用的方法是过滤掉标签中间包含的内容，对其他标签，处理的方式与方法1是一样的。这个方法似乎解决了方法1中的B，C两个问题，但是真的是这样吗，我来分析一下这个方面的缺点A首先，跟方法1一样，这样的方式程序会对HTML中的每个标签都进行如上的处理，我们知道。一个HTML有时候标签所占得字符是远远的多于它所包含的文字信息。这样的话程序的效率会因为处理很多无用的标签而浪费支援，减低了效率。B过滤了标签中间包含的内容，会丢失一定得信息，因为网页的有些内容必须是在运行了脚本之后得到的，这样的话搜索引擎的准确率会因此降低。上面的两个方法都有效率的问题，而且各自也有着其他的问题。经过了几天的思考，找到了一个相对来说比较好的方法，这个方法如下首先程序会使用到一个控件，它叫WEBBROWSER，这个控件的功能是根据所给的HTML的代码，它可以将网页显示出来，跟使用的IE的效果是一样的，这样的话，似乎程序将爬虫下载好的代码放到WEBBROWSER中，在获得控件DOCUMENTBODYINNERTEXT属性就可以了，但是这其中还有一个问题那就是控件的加载的时间问题，经过测试，我发现控件的加载时间是整个程序执行完了之后，也就是说即使在程序的开始处你把HTML代码赋值到控件，然后在下面的程序中想使用DOCUMENTBODYINNERTEXT来获得网页内容，这个时候程序会报NULLREFERENCEEXCEPTION错误，因为在这个时候控件还没有加载，所以控件的内容还是空的。怎么解决个问题呢，本文使用了多进程使用另外一个程序来执行WEB搜索引擎的设计与实现信息处理3WEBBROWSER控件的加载，这样当这个程序执行完成之后加载了控件，可以在DOCUMENTCOMPLETED方法中得到DOCUMENTBODYINNERTEXT，然后程序进程间通信将转换了的内容传回原来的程序，进程间通信程序采用的消息队列13，关键代码如下所示转换代码WEBBROWSER1DOCUMENTTEXTHTMLCODE/把HTML代码赋值给控件WEBBROWSER1SELECT/选中控件WEBBROWSER1DOCUMENTCOMPLETEDNEWWEBBROWSERDOCUMENTCOMPLETEDEVENTHANDLERWEBBROWSER1_DOCUMENTCOMPLETED/将方法WEBBROWSER1_DOCUMENTCOMPLETED加到控件的事件中/当控件加载完成时调用的方法/PUBLICVOIDWEBBROWSER1_DOCUMENTCOMPLETEDOBJECTSENDER,WEBBROWSERDOCUMENTCOMPLETEDEVENTARGSEHTMLTEXWEBBROWSER1DOCUMENTBODYINNERTEXT进程间通信的代码INTERNALCLASSTRANSMITMESSAGEQUEUECODEQUEUENULL/申明一个消息队列STRINGCODEQUEUENAME“PRIVATEWEBSEARCHCODE“/消息队列的名字PUBLICTRANSMIT/初始化，对消息队列进行初始化IFMESSAGEQUEUEEXISTSCODEQUEUENAME/如果消息队列存在，获得它CODEQUEUENEWMESSAGEQUEUECODEQUEUENAMEWEB搜索引擎的设计与实现信息处理4ELSE/如果消息队列不存在，创建一个消息队列CODEQUEUEMESSAGEQUEUECREATECODEQUEUENAMEPUBLICVOIDSENDREFSTRINGHTMLTEXT,STRINGURLCODEQUEUESENDHTMLTEXT,URL/向消息队列中发送一个消息43切词经过了上述的程序的转换过后，现在程序已经得到了网页显示的内容，就像我们在IE中对网页进行全选，然后在复制，在记事本中粘贴出来的结果是一样的，接下来就需要对这些内容进行切词，网页的词语我们可以划分为以下几个部分，中文，英文，数字，其他的符号，对于不同的词语程序应该采用不同的处理方式，所以需要对当前词语做一个判断，然后分类进行处理，对词语类型的判断可以采用正则表达式来进行，代码如下PRIVATEINTJUDGESTRINGSTRREGEXREHANZINEWREGEX“U4E00U9FA50,“/初始化中文的正则表达式REGEXRESHUZINEWREGEX“09“/初始化数字的正则表达式REGEXREENGLISHNEWREGEX“AZAZ“/初始化英文的正则表达式IFSTR“N“|STR“T“|STR“R“RETURN3IFREHANZIMATCHSTRSUCCESSRETURN0/说明是汉字WEB搜索引擎的设计与实现信息处理5ELSEIFREENGLISHMATCHSTRSUCCESSRETURN1/说明是字母ELSEIFRESHUZIMATCHSTRSUCCESSRETURN2/说明是数字ELSERETURN3/说明是其他的一些符号RETURN1经过上述的判断，我们就可以对不同的词语采取不同的处理方式。431中文切词图43中文切词流程图WEB搜索引擎的设计与实现信息处理6中文切词19，就是要程序把中文的语句切成一个一个的词语，这个工作是相当复杂的，本文把它分成了初始化词库，词语定位，切词比较三个部分，下面我将对每个部分进行详细的讲解和给出关键的代码A初始化词库要进行中文切词，就需要一个中文的词库，没有这个词库程序是无法完成的。本文用的词库是从网上下载的一个词库，不是很大，2M左右，词库下载完了，那么怎么用这个词库变成了一个很大的问题，查看了LUCENCE（一个使用JAVA语言完成的搜索引擎）的代码，发现它是将整个词库导入到一个哈希表里面，然后把切下的词到这个哈希表中查找，找到了就说明当前词语是一个中文的词。但是这样的效率是很低下的，因为一个词库大概要有二十万到三十万个词语，把它导入一个哈希表，这个哈希表太大了，它的查找效率应该是很低的，还有在切词过程中，查找的次数是巨大了，如果每次查找哪怕多用很少的时间，对于整片文章来说，完成整个的切词工作耗费的时间也是很多的。因此，本文对词库进行了如下的改进，因为每个词语无论它的长度怎么变，它的首字是不会变的，这样针对一个词语，应该可以把查找的范围缩小，只要查找的范围缩小了，查找的效率也就能够提高了。于是，本文把词库按照词语的首字的拼音的前两个字母进行了一个划分，把原来的一个词库分成了93个，然后把词库导入到一个哈希表数组中，这样每个词库的平均大小只有20K左右，大大的减小了，每个哈希表中所包含的词语的数量也大大的减小了，针对一个词语，它的查找始终是定位在一个哈希表的，是不会改变的，所以没个词语，经过一次定位以后，就可以在一个很小的范围内进行查找。词库初始化的工作还没有结束，还有一个很重要的事，那就是最大长度匹配，我们对一条语句进行切词，应该要保证切下来的词语是最少的，也就是没个词语都要尽量的长，例如“中华人民共和国”，可以切成如下几个词语“中华”，“中华人民”，“中华人民共和国”但是最终选择的结果应该是最长的那个结果。这个就相当的困难了，因为切词，词语是一个字一个字加上去的，在以上面的例子为例，程序首先切下了“中华”两个字，组成一个词，然后在哈希表中进行查找，找到了，说明它是一个词语，我们在切下“人”字加到词语中，得到了“中华人”，这个词语在词库中是没有的，但是当在切下“民”加到词语中时，组成了“中华人民”。怎么样才能让程序切到“人”字的时候不停WEB搜索引擎的设计与实现信息处理7止，而是继续往下切词呢解决得办法就是程序在构造一个词库，原来的词库是一行存一个词，现在改变一下，把词语全部连起来，每个词语中间加上一个“，”，这样就可以区分词语了，然后把新构造的词库读到一个STRING数组中，这样就可以使用STRING类型特有的CONTAINS方法来判断词库当中是不是包含了这个词，还是上面的例子在STRING中会有这样一段“，中华人民共和国，”，当切词切到“中华人”的时候，调用STRING的CONTAINS方法，返回的TRUE，切词程序就会继续往下走了，通过这样就能够实现最大长度匹配了。关键代码如下PUBLICSTATICHASHTABLEMENULISTNEWHASHTABLE/存放用于查找词语属于的列表PUBLICSTATICSTRINGDICTEXTNEWSTRING93/存放不以行分的词库的字符串PUBLICSTATICVOIDSETWORDHTSTRINGPATH“STRINGCOPYPATH“STRINGWORDTEXT“FILESTREAMFCREATEFILESTREAMWORDFSSTREAMREADERWORDSRFILESTREAMFILEOPENSTREAMWRITERFILEWRITERBOOLNEEDWRITEFALSEFORINTI0IWORDTEXT“PATH“WORD“MENULISTITOSTRING“TXT“COPYPATH“WORD“MENULISTITOSTRING“COPYTXT“IFFILEEXISTSCOPYPATHFCREATEFILECREATECOPYPATHFCREATECLOSENEEDWRITETRUEWORDFSNEWFILESTREAMPATH,FILEMODEOPEN,FILEACCESSREADWORDSRNEWSTREAMREADERWORDFS,SYSTEMTEXTENCODINGDEFAULTSTRINGWORDNULLWHILEWORDWORDSRREADLINENULL/构造新的词库WORDHTIADDWORDTRIMWEB搜索引擎的设计与实现信息处理8STRINGTESTWORDTRIMTOSTRINGWORDTEXTWORDTRIM“,“FILEOPENNEWFILESTREAMCOPYPATH,FILEMODEOPEN,FILEACCESSREADWRITEFILEWRITERNEWSTREAMWRITERFILEOPEN,SYSTEMTEXTENCODINGDEFAULTIFNEEDWRITE/将新词库写到记事本中FILEWRITERWRITEWORDTEXTFILEOPENCLOSEWORDFSCLOSEPUBLICSTATICVOIDSETCOPYDICFILESTREAMDICCOPYSTREAMBINARYREADERDICCOPYBRSTRINGDICCOPYPATH“FORINTI0I这样的标签达到了解析的效果。3在处理中文分词的问题上，本文参照了LUCENE的切词原理，设计了新的切词算法，对词库进行了一个细分，并且在程序中能够对细分的词库进行准确的定位，采用了哈希表词库和STRING词库两个词库的共同使用来实现中文分词的正向最大长度匹配，在完成编码之后对程序的准确性和效率进行了反复的测试，证明程序在效率上的确是改进了。4在实现排序索引的部分，本文参照了LUCENE的排序索引原理，设计了新的排序索引数据结构，即用STRING来存储各个词语的相关URL，然后在将各个词语相关的URL进行排序，通过对程序的测试证明了程序的可运行性。5在搜索的效率上，本文采用了对搜索页面存储和对经常搜索词语的相关URL的存储两级缓存策略的方式来提高了系统的效率。尽管本文完成了整个系统的设计和实现，但是还是存在一些不足的地方，在下一节将对这些不足进行说明和提出改善的方向。WEB搜索引擎的设计与实现总结与展望173展望尽管本文完成了系统的设计和实现工作，但是系统还存在着一些不足1爬虫部分爬虫是搜索引擎的基础，没有爬虫不断的从网络中下载网页，后面的程序是没办法对网页进行分析给简历排序索引，尽管本文已经实现了爬虫部分，但是其中还存在着不足其一，本文实现的爬虫不是用SOCKET来实现下载的，用的C来实现的，所以无法获取GET的返回头报文，也就无法实现下载之前对网页的类型进行检测，如果下载的网页不是文本类型的话，就没必要浪费网络资源来下载它，这个是需要改进的地方。其二，在下载网页的过程中没有能够遵行ROBOTS规则35。ROBOTS规则是这样的，每个网站都会有您可以在您的网站中创建一个纯文本文件ROBOTSTXT，在这个文件中声明该网站中不想被ROBOT访问的部分，这样，该网站的部分或全部内容就可以不被搜索引擎收录了，或者指定搜索引擎只收录指定的内容。ROBOTSTXT（统一小写）是一种存放于网站根目录下的ASCII编码的文本文件，它通常告诉网络搜索引擎的漫游器（又称网络蜘蛛），此网站中的哪些内容是不能被搜索引擎的漫游器获取的，哪些是可以被（漫游器）获取的。因为一些系统中的URL是大小写敏感的，所以ROBOTSTXT的文件名应统一为小写。ROBOTSTXT应放置于网站的根目录下。如果想单独定义搜索引擎的漫游器访问子目录时的行为，那么可以将自定的设置合并到根目录下的ROBOTSTXT，或者使用ROBOTS元数据。ROBOTSTXT协议并不是一个规范，而只是约定俗成的。这个关系到网络的道德问题，是需要我在以后改进的地方。其三，我是采用数据库的方式来存储URL的，但是当我们的URL的数量达到了上亿之后，数据库的效率就会下降的，这就会影响我们整个系统的效率，所以这个也是需要改进的地方，估计可以采用哈希算法来解决这个问题。2信息处理部分其一，因为信息处理部分采用的词库是一个很小的词库，所以在切词的过程中会有很多的词语是程序无法识别的，这会影响系统的准确WEB搜索引擎的设计与实现总结与展望2率，所以应该对换一个比较大的词库，本文使用的词库需要改进。其二，现在的网络上“新词”出现的频率是很高的，这个“新词”指的是原来不在词典中的，但是他们经常挨在一起，而且出现的频率很高，例如“胡锦涛”这样的词语，肯定不是一个词语，但是我们必须把它当作一个词语来处理，因为它的出现频率很高，搜索的频率也很高，这就需要程序把它作为一个新词添加到词库当中。这个是本文需要改进的地方。3倒排索引部分。在这个部分存在一个网页评分的问题，排序就是按照这个评分来进行了，所以网页评分时很重要的，但是本文采用的只是简单的词语在网页中出现的次数来当作网页的评分，这样的评分规则是易于实现的，但是这样的评分规则在网页的评分上做的不是很合理，要改进这个部分，就需要改进评分规则，现实当中想GOOGLE使用的是PAGERANK算法来对网页进行评分，而且实践表明这样的算法效果是明显的。当然,现在存在着很多的著名的网络通用搜索引擎，他们都有自己的评分算法，而且他们的算法也是相对来说很合理的，这里就不一一介绍了。PAGERANK简介36PAGERANK，网页排名，又称网页级别、GOOGLE左侧排名或佩奇排名，是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术，以GOOGLE公司创办人拉里佩奇（LARRYPAGE）之姓来命名。此技术通常和搜索引擎优化有关，GOOGLE用它来体现网页的相关性和重要性。GOOGLE的创始人拉里佩奇和谢尔盖布林于1998年在斯坦福大学发明了这项技术。PAGERANK通过网络浩瀚的超链接关系来确定一个页面的等级。GOOGLE把从A页面到B页面的链接解释为A页面给B页面投票，GOOGLE根据投票来源（甚至来源的来源，即链接到A页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。4搜索部分。在搜索部分虽然使用了缓存策略来提高了程序的搜索效率，但是还存在一个问题，那就是网页重复的问题，也就是几个网页的内容是一样的，这样的网页只需要显示一个就可以了，显示多了就是浪费资源，在判断网页是否重复这个问题上现在很多的搜索引擎都是使用的MD5算法。这个算法很复杂，所以这个也是本文需要该机的地方。MD5算法简介38MD5的全称是MESSAGEDIGESTALGORITHM5（信息摘要算法），用于确保信息传输完整一致。MD5的典型应用是对一段信息WEB搜索引擎的设计与实现总结与展望3（MESSAGE）产生信息摘要（MESSAGEDIGEST），以防止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名为MD5的文件，在这个文件中通常只有一行文本，大致结构如MD5TANAJIYATARGZ0CA175B9C0F726A831D895E269332461这就是TANAJIYATARGZ文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。在程序根据算法得到摘要之后，我们只要对本两个网页的摘要是否相同就能够去掉内容一样的重复网页。WEB搜索引擎的设计与实现参考文献0参考文献1李晓明，闰宏飞，王继民搜索引擎一一原理、技术与系统、科学出版社、20042刘建国，搜索引擎概述，北京大学计算机与科学技术，19991020143华伟臣，张秀琼网络蜘蛛搜