搜索引擎的设计与实现.doc
《搜索引擎的设计与实现.doc》由会员分享，可在线阅读，更多相关《搜索引擎的设计与实现.doc（54页珍藏版）》请在冰点文库上搜索。
web搜索引擎的设计与实现
摘要
随着网络的迅猛发展。
网络成为信息的极其重要的来源地，越来越多的人从网络上获取自己所需要的信息，这就使得像Google[40]，百度[39]这样的通用搜索引擎变成了人们寻找信息必不可少的工具。
本文在深入研究了通用搜索引擎基本原理、架构设计和核心技术的基础上，结合小型搜索引擎的需求，参照了天网，lucene等搜索引擎的原理，构建了一个运行稳定，性能良好而且可扩充的小型搜索引擎系统，本文不仅仅完成了对整个系统的设计，并且完成了所有的编码工作。
本文论述了搜索引擎的开发背景以及搜索引擎的历史和发展趋势，分析了小型搜索引擎的需求，对系统开发中的一些问题，都给出了解决方案，并对方案进行详细设计，编码实现。
论文的主要工作及创新如下：
1.在深刻理解网络爬虫的工作原理的基础上，使用数据库的来实现爬虫部分。
2.在深刻理解了中文切词原理的基础之上，对lucene的切词算法上做出了改进的基础上设计了自己的算法，对改进后的算法实现，并进行了准确率和效率的测试，证明在效率上确实提高。
3.在理解了排序索引部分的原理之后，设计了实现索引排序部分结构，完成了详细流程图和编码实现，对完成的代码进行测试。
4.在完成搜索部分设计后，觉得效率上还不能够达到系统的要求，于是为了提高系统的搜索效率，采用了缓存搜索页面和对搜索频率较高词语结果缓存的两级缓存原则来提高系统搜索效率。
关键词：
搜索引擎，网络爬虫，中文切词，排序索引
ABSTRACT
Withtherapidlydevelopingofthenetwork.Networkbecameavitalinformationsource,moreandmorepeopleareobtainingtheinformationthattheyneedfromthenetwork,thismakingwebsearchenginehasbecomeessentialtooltopeoplewhentheywanttofindsomeinformationfrominternet.
Inthispaper,within-depthstudyofthebasicprinciplesofgeneralsearchengines,thedesignandcoretechnologyarchitecture,combiningwiththeneedsofsmallsearchengineandinthelightofthe"tianwang",lucenesearchengine,Ibuildastable,goodperformanceandcanbeexpandedsmall-scalesearchenginesystem,this
articlenotonlycompletedthedesignoftheentiresystem,butalsobasicallycompletedallthecodingwork.
Thisarticledescriblenotonlythebackgroundofsearchengines,butalsothehistoryofsearchenginedevelopinganddevelopingtrends,andanalysetheneedsofsmallsearchenginesandgivingsolutionsthetotheproblemswhichwasfoundinthedevelopmentofthesystem,andmakingadetailedprogramdesign,codingtoachieve.
Themainthesisofthearticleandinnovationareasfollows:
1.withthedeepunderstandingoftheworkingprincipleofthenetworkspider.Iacheivednetworkspiderwithusingdatabasesystem.
2.withthedeepunderstandingofChinesesegmentationandsegmentationalgorithmoflucenesystem,Imademyownsegmentationalgorithm,andgivealotofteststomysegmentationalgorithmtoprovidethatmysegmentationalgorithmisbetter.
3.withthedeepunderstandingofsortedandindexalgorithm,Idesignedmyownsortedandindexalgorithmwiththedata-structIdesignedandcodingit,itwasprovidedavailableafterlotsoftests.
4.afterdesignofsearchpart,Ifoudtheefficiencyofthepartisnotverypoor,soIdesignedtwo-stagecachedevicetoimpovetheefficiencyofthesystem.
Keywords:
searchengine,netspider,Chinesesegmentation,sortedandindex
目录
第一章绪论 1
1.1搜索引擎出现的背景及意义 1
1.2搜索引擎的发展历史及趋势 1
1.3本文主要工作 3
1.4论文结构 4
第二章系统结构 5
2.1概述 5
2.2系统结构 5
2.2.1爬虫 6
2.2.2信息处理 6
2.2.3排序和索引 6
2.2.4搜索 6
2.3搜索引擎主要指标及分析 6
2.4开发语言 7
2.5小结 8
第三章爬虫 9
3.1概述 9
3.2爬虫结构分析 9
3.2.1爬虫初始化 10
3.2.2从网页中提取url 11
3.2.3URL存储 12
3.2.4从数据库中提取url 12
3.3小结 13
第四章信息处理 14
4.1概述 14
4.2转换 15
4.3切词 18
4.3.1中文切词 19
4.3.2中文切词测试 25
4.3.3英文切词 27
4.3.4数字切词 28
4.3.5符号处理 29
4.3.6词语存储 30
4.4小结 31
第五章排序索引 33
5.1概述 33
5.2统计相关url 33
5.3排序 34
5.4索引 36
5.5小结 37
第六章搜索 38
6.1概述 38
6.2实现搜索 38
6.3性能优化 41
6.4小结 42
第七章总结与展望 43
7.1总结 43
7.3展望 44
参考文献 47
致谢 49
Web搜索引擎的设计与实现 绪论
第一章绪论
1.1搜索引擎出现的背景及意义
网络的出现以及发展对于世界发展的意义是极其重要的，它让地球村的理念变成的现实，信息的传输不再受到时间和空间的限制。
随着网络技术和应用的不断发展，互联网已经成为了信息的重要来源地，人们越来越依靠网络来查找他们所需要的信息。
我们所处的是一个信息爆炸的时代，Google的索引在1998年开始工作,当时他们收集了2600万个页面,2000年就突破了10亿,到10年后的2008年达到了1,000,000,000,000,Google的数据库变成了全球最庞大的索引之一[8]，数量之庞大让我们震惊。
这么巨大的数字导致了一个问题，"RichData,PoorInformation"。
我们就好像处在一个信息的迷宫，因此，如何有效快速的找到自己需要的信息成为了一个极其重要的问题。
在没有搜索引擎的时代，用户希望寻找某方面的信息，就必须通过各种途径或者是网站之间的连接寻找，可以这样说，脱离的搜索引擎的网站，就像是信息海洋中的一个一个的孤岛，用户必将面临巨大的搜索成本，同时必须付出大量的时间和精力。
搜索引擎的出现改变了上述的现象[4]，它通过程序的自动搜寻并建立索引，将这些信息孤岛联系起来，形成了一张巨大的信息网，并且运用分布式计算的巨大力量，能够让用户从海量数据中摒除垃圾信息，获取想要的知识。
搜索引擎不仅仅是节省了用户的时间，通过挖掉搜寻成本这座墙，它让许许多多的不可能成为可能。
1.2搜索引擎的发展历史及趋势
搜索经历了三代的更新和发展:
[8]
第一代搜索引擎出现于1994年。
这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。
而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。
第二代搜索出现在1996年。
第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50,000,000网页的索引数据库，每天能够响应10,000,000次用户检索请求。
第三代搜索引擎年代的划分和主要特性至今没有统一的认识，不过至少可以肯定的是：
第三代搜索引擎是对第二代搜索引擎在搜索技术上的改进，主要增加了互动性和个性化等高级的技术，为用户使用搜索引擎获取信息获得更好的体验。
至于互动性的评价标准是什么，以及第三代搜索引擎到底比第二代搜索引擎增加了多少价值——尤其是为企业利用搜索引擎开展网络营销增加了哪些价值，目前并没有非常令人信服的研究结论。
这也就是目前所谓的第三代搜索引擎并没有表现出太多优势的原因之一。
现在，网络上有很多著名的搜索引擎，百度，google，yahoo等等，百度从2005年诞生到现在成为全球最大的中文搜索引擎，可想而知，发展的速度的多么的快，人们对搜索引擎的的需求的多大，百度的日点击率我无法在找到确切的数字，但是我们可以计算一下，截至2008年底，中国网民规模达到2.98亿人[9]，每个网民上网点击百度的次数应该不少于十次吧，像我们要在百度上找资料的网名点击率百次不止，所以百度的日点击率是多么惊人。
搜索引擎经过几年的发展和摸索，越来越贴近人们的需求，搜索引擎的技术也得到了很大的发展。
搜索引擎在将来的的发展趋势大概有以下几个方面：
[10]
1.提高对用户输入的理解
为了提高搜索引擎对用户检索提问的理解，就必须有一个好的检索提问语言，为了克服关键词检索和目录查询的缺点，现在已经出现了自然语言智能答询。
用户可以输入简单的疑问句，比如“howcankillvirusofcomputer?
”。
搜索引擎在对提问进行结构和内容的分析之后，或直接给出提问的答案，或引导用户从几个可选择的问题中进行再选择。
自然语言的优势在于，一是使网络交流更加人性化，二是使查询变得更加方便、直接、有效。
就以上面的例子来讲，如果用关键词查询，多半人会用“virus”这个词来检索，结果中必然会包括各类病毒的介绍、病毒是怎样产生的等等许多无效信息，而用“howcankillvirusofcomputer?
”，搜索引擎会将怎样杀病毒的信息提供给用户，提高了检索效率。
2.对检索的结果进行处理
对检索的结果处理，有以下几个方向：
其一，使用链接评价，就是将网页的链接数量算作网页评分因素之一，这样搜索的结果就更加的能够满足用户的要求，在这个方面google（）的“链接评价体系”已经做出了相当出色的成绩。
其二，使用大众访问性，就是将访问数量（也可以叫做点击数量）算作网页评分的因素之一，这样想这样的网站的分数会很高，而这样的网站很多时候都是用户想找的，这样能够提高搜索引擎的准确率。
其三，去掉结果中的附加信息。
有调查指出，过多的附加信息加重了用户的信息负担，为了去掉这些过多的附加信息，可以采用用户定制、内容过滤等检索技术。
3.确定搜集返回，提高针对性
在这个方面现在的发展的方向是：
其一，垂直主题搜索。
垂直主题的搜索引擎以其高度的目标化和专业化在各类搜索引擎中占据了一系席之地，比如象股票、天气、新闻等类的搜索引擎，具有很高的针对性，用户对查询结果的满意度较高。
我认为，垂直主题有着极大的发展空间。
其二，非www信息的搜索。
搜索引擎提供了例如ftp等非www信息的搜索。
其三，多媒体搜索。
搜索引擎还提供了例如包括声音、图像等等多媒体信息的检索。
4.提供更优化的检索结果
在这个方面有两个主要的发展方向：
其一，纯净搜索引擎。
这类搜索引擎没有自己的信息采集系统，利用别人现有的索引数据库，主要关注检索的理念、技术和机制等。
其二，元搜索引擎。
元搜索引擎（metasearchenging）是将用户提交的检索请求到多个独立的搜索引擎上去搜索，并将检索结果集中统一处理，以统一的格式提供给用户，因此有搜索引擎之上的搜索引擎之称。
它的主要精力放在提高搜索速度、智能化处理搜索结果、个性搜索功能的设置和用户检索界面的友好性上，查全率和查准率都比较高。
1.3本文主要工作
本文在深入分析通用搜索引擎基本原理、架构设计和核心技术的基础上，结合开源搜索引擎lucene和天网搜索引擎的实现原理，设计并实现了一个可扩展，可复用的小型搜索引擎系统，本文的具体工作有以下几个方面：
1.详细论述了系统结构，系统的设计原则以及目标。
明确系统的功能，设计出详细的系统流程图。
2.分析了网络爬虫的工作原理，利用数据库设计出爬虫部分的详细流程图，并实现了系统的爬虫部分。
3.详细设计了系统的信息处理部分，并且给出了设计的流程图，在中文切成部分参照lucene的原理，做出了算法上的改进，对改进后的算法实现，并进行了准确率和效率的测试，证明在效率上确实提高。
4.根据排序和索引的原理，自己详细设计了这个部分，完成了详细流程图，并实现。
5.为了提高系统的搜索效率，采用了缓存搜索页面和对搜索频率较高词语结果缓存的两级缓存原则。
1.4论文结构
本文共分为七章
第一章，绪论。
主要阐述了论文的研究背景与意义、搜索引擎的发展现状、发展趋势、论文的主要工作和组织结构。
第二章，系统结构。
主要对整个系统进行的概念和功能进行了描述，并且对系统的各个部分进行了一个大概的介绍，并给出系统流程图。
第三章，爬虫。
对系统中的爬虫部分的原理进行了详细的说明，对爬虫部分详细设计了流程图，并给出对爬虫部分的代码实现和对代码进行一定程度的讲解。
第四章，信息处理。
对信息处理部分的原理进行详细的描述，详细设计了流程图，给出了信息处理部分各种切词部分代码实现，并且对代码进行了一定程度了解说。
第五者，排序索引。
对系统的排序和索引两个部分的原理进行详细的描述，并对用来实现排序和索引的数据结构进行详细的说明。
给出流程图。
第六章，搜索。
对系统的最后一个环节-------搜索进行了描述，给出实现搜索的消息步骤，并且对提高效率的两级缓存策略给出了详细的讲解。
给出流程图。
第七章，总结。
对整个毕业设计的过程和项目进行了总结，并且分析了系统现有的不足，对不足之处给出了将进行改进的建议。
2
Web搜索引擎的设计与实现 系统结构
第二章系统结构
2.1概述
搜索引擎[41]（SearchEngines）就是指在WWW（WorldWideWeb）环境中能够响应用户提交的搜索请求，返回相应的查询结果信息的技术和系统，是互联网上的可以查询网站或网页信息的工具[2]。
它包括信息搜集、信息整理和用户查询三部分。
搜索引擎的服务方式分为两种：
目录服务和关键字检索服务。
目录服务是由分类专家将网络信息按照主题分成若干个大类，用户可以根据分类清晰地找到自己所需要的内容。
关键字检索服务可以查找包含一个或多个特定关键字或词组的WWW站点。
搜索引擎是互联网的第二大核心技术，涉及到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术，所以具有综合性和挑战性。
2.2系统结构
搜索引擎系统结构[1]分为爬虫，信息处理，排序索引，搜索四个部分，系统结构图如图2-1所示；
图2-1系统流程图
2.2.1爬虫
爬虫也可以称作“网络爬虫程序”，“web爬虫”，“网络蜘蛛”，“网络机器人”。
网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引擎的重要组成。
传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。
2.2.2信息处理
信息处理指的是当爬虫从万维网上下载了网页，对网页中包含的信息进行处理，其中包括提取网页中包含的url。
为爬虫的继续提供所需要的url，这个事很重要的，因为没有新的url出现的话，爬虫程序就会停止，这样就无法获得全面的信息。
信息处理还必须得网页显示的内容进行分析处理，把网页的内容切成词语。
为下面的排序和索引部分提供相应的信息。
2.2.3排序和索引
在信息处理完成之后，每个网页都会被切成很多个关键词，同时每个词语都会有很过个相关的网页。
排序所要做的事就是把每个词语的相关的网页按词语的出现次数进行排序，这样在进行搜索时结果的出现顺序提供依据。
接下来的索引程序就是以词库为索引关键字建立索引，这样在搜索的时候就能够在最短的时间找出我们想要的结果。
2.2.4搜索
在上述的工作完成之后，便可以为用户提供搜索服务了，按照用户的关键字或词的输入，按照所建立的索引在最短的时间内找到相应的结果，返回相应的数据，然后在网页上显示返回的结果，是用户能够选择自己想要的信息。
2.3搜索引擎主要指标及分析
搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。
这些指标决定了搜索引擎的技术指标。
搜索引擎的技术指标决定了搜索引擎的评价指标。
好的搜索引擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。
毕业设计论文代做平台《580毕业设计网》是专业代做团队也有大量毕业设计成品提供参考QQ3449649974
召回率：
一次搜索结果中符合用户要求的数目与用户查询相关信息的总数之比
准确率：
一次搜索结果中符合用户要求的数目与该次搜索结果总数之比
相关度：
用户查询与搜索结果之间相似度的一种度量
精确度：
对搜索结果的排序分级能力和对垃圾网页的抗干扰能力
2.4开发语言
本文在开发语言上选择的是c#语言[5]，因为C#在带来对应用程序的快速开发能力的同时，并没有牺牲C与C++程序员所关心的各种特性。
它忠实地继承了C和C++的优点。
C#语言还有以下的优点：
[15]
1.简洁的语法。
语法中的冗余是C++中的常见的问题，比如"const"和"#define"、各种各样的字符类型等等。
C#对此进行了简化，只保留了常见的形式，而别的冗余形式从它的语法结构中被清除了出去。
2.精心设计面向对象
在C#的类型系统中，每种类型都可以看作一个对象。
C#提供了一个叫做装箱（boxing）与拆箱（unboxing）的机制来完成这种操作，而不给使用者带来麻烦，这在以后的章节中将进行更为详细的介绍。
C#只允许单继承，即一个类不会有多个基类，从而避免了类型定义的混乱。
在后面的学习中你很快会发现，C#中没有了全局函数，没有了全局变量，也没有了全局常数。
一切的一切，都必须封装在一个类之中。
你的代码将具有更好的可读性，并且减少了发生命名冲突的可能。
3.完整的安全性与错误处理
语言的安全性与错误处理能力，是衡量一种语言是否优秀的重要依据。
。
C#的先进设计思想可以消除软件开发中的许多常见错误，并提供了包括类型安全在内的完整的安全性能。
.NET运行库提供了代码访问安全特性，它允许管理员和用户根据代码的ID来配置安全等级。
变量是类型安全的。
4.灵活性与兼容性
在简化语法的同时，C#并没有失去灵活性。
正是由于其灵活性，C#允许与C风格的需要传递指针型参数的API进行交互操作，DLL的任何入口点都可以在程序中进行访问。
C#遵守.NET公用语言规范（CommonLanguageSpecification,CLS），从而保证了C#组件与其它语言组件间的互操作性。
元数据（Metadata）概念的引入既保证了兼容性，又实现了类型安全。
2.5小结
本章对基于因特网的搜索引擎结构和性能指标进行了分析，在这些原来的理解基础之上利用c#技术完成了一个小的web搜索引擎，在接下来的章节将对搜索引擎结构中的网络爬虫设计进行说明，并给出关键部分的实现代码。
Web搜索引擎的设计与实现 爬虫
第三章爬虫
3.1概述
网络蜘蛛即WebSpider，是一个很形象的名字[3]。
把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。
网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。
如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。
对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的[6]，从公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。
这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的，如果按照每个页面的平均大小为20K（包含图片），100亿网页的容量是100×2000G字节，即使能够存储，下载也存在问题（按照一台机器每秒下载20K计算，需要340台机器不停的下载一年时间，才能把所有网页下载完毕）。
同时，由于数据量太大，在提供搜索时也会有效率方面的。
因此，许多搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。
3.2爬虫结构分析
爬虫部分分为爬虫初始化，从网页中提取url，对url进行存储，从数据中提取url四个部分，爬虫部分的流程图如图3-1所示，在本节将对爬虫的工作原理进行详细的描述：
图3-1爬虫流程图
3.2.1爬虫初始化
爬虫程序的开始是需要一个最初始的url，爬虫将先下载这个url的内容，然后提取里面所包含的url，所以这个最初始的url是很重要的，如果没有一个好的初始的url，这个url所包含的url会很少，那么爬虫所能爬下的网页的数量也将大受影响。
得到了初始的url以后，就可以下载网页的内容了。
以下就是下载网页的代码：
HttpWebRequestloHttp=（HttpWebRequest）WebRequest.Create（url）;//创建连接
loHttp.Timeout=500;//设置超时
HttpWebResponseloWe
升级会员 