搜索引擎的设计与实现-胡书山
更新时间：2024-05-16 19:34:01 阅读量： 综合文库 文档下载
学号200532580261 密级________________
武汉大学本科毕业论文
web搜索引擎的设计与实现
院（系）名 称：国际软件学院 专 业 名 称 ：软件工程 学 生 姓 名 ：胡书山 指 导 教 师 ：冯晶 讲师
王飞
项目经理
二○○九年五月
BACHELOR'S DEGREE THESIS OF WUHAN UNIVERSITY
The design and implementation of web
search engineer
College ：Wuhan university Subject ：Software engineering Name ： Hushushan
Directed by ： Fengjing Lecturer
Wangfei Project manager
May 2009
郑 重 声 明
（宋体粗体2号居中）
本人呈交的学位论文，是在导师的指导下，独立进行研究工作所取得的成果，所有数据、图片资料真实可靠。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确的方式标明。本学位论文的知识产权归属于培养单位。
本人签名： 胡书山 日期： 2009-5-10
摘 要
随着网络的迅猛发展。网络成为信息的极其重要的来源地，越来越多的人从网络上获取自己所需要的信息，这就使得像Google引擎变成了人们寻找信息必不可少的工具。
本文在深入研究了通用搜索引擎基本原理、架构设计和核心技术的基础上，结合小型搜索引擎的需求，参照了天网，lucene等搜索引擎的原理，构建了一个运行稳定，性能良好而且可扩充的小型搜索引擎系统，本文不仅仅完成了对整个系统的设计，并且完成了所有的编码工作。
本文论述了搜索引擎的开发背景以及搜索引擎的历史和发展趋势，分析了小型搜索引擎的需求，对系统开发中的一些问题，都给出了解决方案， 并对方案进行详细设计，编码实现。论文的主要工作及创新如下：
1.在深刻理解网络爬虫的工作原理的基础上，使用数据库的来实现爬虫部分。
2.在深刻理解了中文切词原理的基础之上，对lucene的切词算法上做出了改进的基础上设计了自己的算法，对改进后的算法实现，并进行了准确率和效率的测试，证明在效率上确实提高。
3.在理解了排序索引部分的原理之后，设计了实现索引排序部分结构，完成了详细流程图和编码实现，对完成的代码进行测试。
4.在完成搜索部分设计后，觉得效率上还不能够达到系统的要求，于是为了提高系统的搜索效率，采用了缓存搜索页面和对搜索频率较高词语结果缓存的两级缓存原则来提高系统搜索效率。
关键词：搜索引擎，网络爬虫，中文切词，排序索引
[40]
，百度这样的通用搜索
[39]
ABSTRACT
With the rapidly developing of the network. Network became a vital information source, more and more people are obtaining the information that they need from the network,this making web search engine has become essential tool to people when they want to find some information from internet.
In this paper, with in-depth study of the basic principles of general search engines, the design and core technology architecture, combining with the needs of small search engine and in the light of the \lucene search engine, I build a stable, good performance and can be expanded small-scale search engine system, this article not only completed the design of the entire system, but also basically completed all the coding work.
This article describle not only the background of search engines, but also the history of search engine developing and developing trends,and analyse the needs of small search engines and giving solutionsthe to the problems which was found in the development of the system ,and making a detailed program design, coding to achieve. The main thesis of the article and innovation are as follows:
1.with the deep understanding of the working principle of the network spider.I acheived network spider with using database system.
2.with the deep understanding of Chinese segmentation and segmentation algorithm of lucene system,I made my own segmentation algorithm,and give a lot of tests to my segmentation algorithm to provide that my segmentation algorithm is better.
3.with the deep understanding of sorted and index algorithm,I designed my own sorted and index algorithm with the data-struct I designed and coding it ,it was provided available after lots of tests.
4.after design of search part,I foud the efficiency of the part is not very poor,so I designed two-stage cache device to impove the efficiency of the system.
Key words: search engine,net spider, Chinese segmentation,sorted and index
目录
第一章 绪论.................................................................................................................. 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.3 URL存储...................................................................................................... 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]，数量之庞大让我们震惊。这么巨大的数字导致了一个问题，\。我们就好像处在一个信息的迷宫，因此，如何有效快速的找到自己需要的信息成为了一个极其重要的问题。
在没有搜索引擎的时代，用户希望寻找某方面的信息，就必须通过各种途径或者是网站之间的连接寻找，可以这样说，脱离的搜索引擎的网站，就像是信息海洋中的一个一个的孤岛，用户必将面临巨大的搜索成本，同时必须付出大量的时间和精力。
搜索引擎的出现改变了上述的现象[4]，它通过程序的自动搜寻并建立索引，将这些信息孤岛联系起来，形成了一张巨大的信息网，并且运用分布式计算的巨大力量，能够让用户从海量数据中摒除垃圾信息，获取想要的知识。搜索引擎不仅仅是节省了用户的时间，通过挖掉搜寻成本这座墙，它让许许多多的不可能成为可能。
1.2搜索引擎的发展历史及趋势
搜索经历了三代的更新和发展:[8]
第一代搜索引擎出现于1994年。这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。第二代搜索出现在1996年。
1
Web搜索引擎的设计与实现 绪论
第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50,000,000网页的索引数据库，每天能够响应10,000,000次用户检索请求。
第三代搜索引擎年代的划分和主要特性至今没有统一的认识，不过至少可以肯定的是：第三代搜索引擎是对第二代搜索引擎在搜索技术上的改进，主要增加了互动性和个性化等高级的技术，为用户使用搜索引擎获取信息获得更好的体验。至于互动性的评价标准是什么，以及第三代搜索引擎到底比第二代搜索引擎增加了多少价值——尤其是为企业利用搜索引擎开展网络营销增加了哪些价值，目前并没有非常令人信服的研究结论。这也就是目前所谓的第三代搜索引擎并没有表现出太多优势的原因之一。
现在，网络上有很多著名的搜索引擎，百度，google，yahoo等等，百度从2005年诞生到现在成为全球最大的中文搜索引擎，可想而知，发展的速度的多么的快，人们对搜索引擎的的需求的多大，百度的日点击率我无法在找到确切的数字，但是我们可以计算一下，截至2008年底，中国网民规模达到2.98亿人[9]，每个网民上网点击百度的次数应该不少于十次吧，像我们要在百度上找资料的网名点击率百次不止，所以百度的日点击率是多么惊人。
搜索引擎经过几年的发展和摸索，越来越贴近人们的需求，搜索引擎的技术也得到了很大的发展。搜索引擎在将来的的发展趋势大概有以下几个方面：[10]
1.提高对用户输入的理解
为了提高搜索引擎对用户检索提问的理解，就必须有一个好的检索提问语言，为了克服关键词检索和目录查询的缺点，现在已经出现了自然语言智能答询。用户可以输入简单的疑问句，比如“how can kill virus of computer?”。搜索引擎在对提问进行结构和内容的分析之后，或直接给出提问的答案，或引导用户从几个可选择的问题中进行再选择。自然语言的优势在于，一是使网络交流更加人性化，二是使查询变得更加方便、直接、有效。就以上面的例子来讲，如果用关键词查询，多半人会用“virus”这个词来检索，结果中必然会包括各类病毒的介绍、病毒是怎样产生的等等许多无效信息，而用“how can kill virus of computer?”，搜索引擎会将怎样杀病毒的信息提供给用户，提高了检索效率。
2.对检索的结果进行处理
对检索的结果处理，有以下几个方向：其一，使用链接评价，就是将网页的
2
Web搜索引擎的设计与实现 绪论
链接数量算作网页评分因素之一，这样搜索的结果就更加的能够满足用户的要求，在这个方面google（www.google.cn）的“链接评价体系”已经做出了相当出色的成绩。其二，使用大众访问性，就是将访问数量（也可以叫做点击数量）算作网页评分的因素之一，这样想www.sina.com.cn这样的网站的分数会很高，而这样的网站很多时候都是用户想找的，这样能够提高搜索引擎的准确率。其三，去掉结果中的附加信息。有调查指出，过多的附加信息加重了用户的信息负担，为了去掉这些过多的附加信息，可以采用用户定制、内容过滤等检索技术。
3.确定搜集返回，提高针对性
在这个方面现在的发展的方向是：其一，垂直主题搜索。垂直主题的搜索引擎以其高度的目标化和专业化在各类搜索引擎中占据了一系席之地，比如象股票、天气、新闻等类的搜索引擎，具有很高的针对性，用户对查询结果的满意度较高。我认为，垂直主题有着极大的发展空间。其二，非www信息的搜索。搜索引擎提供了例如ftp等非www信息的搜索。其三，多媒体搜索。搜索引擎还提供了例如包括声音、图像等等多媒体信息的检索。
4.提供更优化的检索结果
在这个方面有两个主要的发展方向：其一，纯净搜索引擎。这类搜索引擎没有自己的信息采集系统，利用别人现有的索引数据库，主要关注检索的理念、技术和机制等。其二，元搜索引擎。元搜索引擎(metasearch enging)是将用户提交的检索请求到多个独立的搜索引擎上去搜索，并将检索结果集中统一处理，以统一的格式提供给用户，因此有搜索引擎之上的搜索引擎之称。它的主要精力放在提高搜索速度、智能化处理搜索结果、个性搜索功能的设置和用户检索界面的友好性上，查全率和查准率都比较高。
1.3本文主要工作
本文在深入分析通用搜索引擎基本原理、架构设计和核心技术的基础上，结合开源搜索引擎lucene和天网搜索引擎的实现原理，设计并实现了一个可扩展，可复用的小型搜索引擎系统，本文的具体工作有以下几个方面：
1.详细论述了系统结构，系统的设计原则以及目标。明确系统的功能，设计出详细的系统流程图。
3
Web搜索引擎的设计与实现 绪论
2.分析了网络爬虫的工作原理，利用数据库设计出爬虫部分的详细流程图，并实现了系统的爬虫部分。
3.详细设计了系统的信息处理部分，并且给出了设计的流程图，在中文切成部分参照lucene的原理，做出了算法上的改进，对改进后的算法实现，并进行了准确率和效率的测试，证明在效率上确实提高。
4.根据排序和索引的原理，自己详细设计了这个部分，完成了详细流程图，并实现。
5.为了提高系统的搜索效率，采用了缓存搜索页面和对搜索频率较高词语结果缓存的两级缓存原则。
1.4论文结构
本文共分为七章
第一章，绪论。主要阐述了论文的研究背景与意义、搜索引擎的发展现状、发展趋势、论文的主要工作和组织结构。
第二章，系统结构。主要对整个系统进行的概念和功能进行了描述，并且对系统的各个部分进行了一个大概的介绍，并给出系统流程图。
第三章，爬虫。对系统中的爬虫部分的原理进行了详细的说明，对爬虫部分详细设计了流程图，并给出对爬虫部分的代码实现和对代码进行一定程度的讲解。
第四章，信息处理。对信息处理部分的原理进行详细的描述，详细设计了流程图，给出了信息处理部分各种切词部分代码实现，并且对代码进行了一定程度了解说。
第五者，排序索引。对系统的排序和索引两个部分的原理进行详细的描述，并对用来实现排序和索引的数据结构进行详细的说明。给出流程图。
第六章，搜索。对系统的最后一个环节-------搜索进行了描述，给出实现搜索的消息步骤，并且对提高效率的两级缓存策略给出了详细的讲解。给出流程图。
第七章，总结。对整个毕业设计的过程和项目进行了总结，并且分析了系统现有的不足，对不足之处给出了将进行改进的建议。
4
Web搜索引擎的设计与实现 系统结构
第二章 系统结构
2.1概述
搜索引擎[41]（Search Engines）就是指在WWW（World Wide Web）环境中能够响应用户提交的搜索请求，返回相应的查询结果信息的技术和系统，是互联网上的可以查询网站或网页信息的工具[2]。它包括信息搜集、信息整理和用户查询三部分。搜索引擎的服务方式分为两种：目录服务和关键字检索服务。目录服务是由分类专家将网络信息按照主题分成若干个大类，用户可以根据分类清晰地找到自己所需要的内容。关键字检索服务可以查找包含一个或多个特定关键字或词组的WWW站点。搜索引擎是互联网的第二大核心技术，涉及到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术，所以具有综合性和挑战性。
2.2系统结构
搜索引擎系统结构[1]分为爬虫，信息处理，排序索引，搜索四个部分，系统结构图如图2-1所示；
图2-1系统流程图
5
Web搜索引擎的设计与实现 系统结构
2.2.1爬虫
爬虫也可以称作“网络爬虫程序”，“web爬虫”，“网络蜘蛛”，“网络机器人”。网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引擎的重要组成。传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。 2.2.2信息处理
信息处理指的是当爬虫从万维网上下载了网页，对网页中包含的信息进行处理，其中包括提取网页中包含的url。为爬虫的继续提供所需要的url，这个事很重要的，因为没有新的url出现的话，爬虫程序就会停止，这样就无法获得全面的信息。信息处理还必须得网页显示的内容进行分析处理，把网页的内容切成词语。为下面的排序和索引部分提供相应的信息。 2.2.3排序和索引
在信息处理完成之后，每个网页都会被切成很多个关键词，同时每个词语都会有很过个相关的网页。排序所要做的事就是把每个词语的相关的网页按词语的出现次数进行排序，这样在进行搜索时结果的出现顺序提供依据。接下来的索引程序就是以词库为索引关键字建立索引，这样在搜索的时候就能够在最短的时间找出我们想要的结果。 2.2.4搜索
在上述的工作完成之后，便可以为用户提供搜索服务了，按照用户的关键字或词的输入，按照所建立的索引在最短的时间内找到相应的结果，返回相应的数据，然后在网页上显示返回的结果，是用户能够选择自己想要的信息。
2.3搜索引擎主要指标及分析
搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。这些指标决
6
Web搜索引擎的设计与实现 系统结构
定了搜索引擎的技术指标。搜索引擎的技术指标决定了搜索引擎的评价指标。好的搜索引擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。
召回率：一次搜索结果中符合用户要求的数目与用户查询相关信息的总数之比 准确率：一次搜索结果中符合用户要求的数目与该次搜索结果总数之比 相关度：用户查询与搜索结果之间相似度的一种度量
精确度：对搜索结果的排序分级能力和对垃圾网页的抗干扰能力
2.4开发语言
本文在开发语言上选择的是c#语言[5]，因为C#在带来对应用程序的快速开发能力的同时，并没有牺牲C与C++程序员所关心的各种特性。它忠实地继承了C和C++的优点。C#语言还有以下的优点：1.简洁的语法。
语法中的冗余是C++中的常见的问题，比如\和\、各种各样的字符类型等等。C#对此进行了简化，只保留了常见的形式，而别的冗余形式从它的语法结构中被清除了出去。 2.精心设计面向对象
在C#的类型系统中，每种类型都可以看作一个对象。C#提供了一个叫做装箱(boxing)与拆箱(unboxing)的机制来完成这种操作，而不给使用者带来麻烦，这在以后的章节中将进行更为详细的介绍。
C#只允许单继承，即一个类不会有多个基类，从而避免了类型定义的混乱。在后面的学习中你很快会发现，C#中没有了全局函数，没有了全局变量，也没有了全局常数。一切的一切，都必须封装在一个类之中。你的代码将具有更好的可读性，并且减少了发生命名冲突的可能。 3.完整的安全性与错误处理
语言的安全性与错误处理能力，是衡量一种语言是否优秀的重要依据。。C#的先进设计思想可以消除软件开发中的许多常见错误，并提供了包括类型安全在内的完整的安全性能。.NET运行库提供了代码访问安全特性，它允许管理员和用户根据代码的ID来配置安全等级。变量是类型安全的。
[15]
7
Web搜索引擎的设计与实现 系统结构
4.灵活性与兼容性
在简化语法的同时，C#并没有失去灵活性。正是由于其灵活性，C#允许与C风格的需要传递指针型参数的API进行交互操作，DLL的任何入口点都可以在程序中进行访问。C#遵守.NET公用语言规范(Common Language Specification,CLS)，从而保证了C#组件与其它语言组件间的互操作性。元数据(Metadata)概念的引入既保证了兼容性，又实现了类型安全。
2.5小结
本章对基于因特网的搜索引擎结构和性能指标进行了分析，在这些原来的理解基础之上利用c#技术完成了一个小的web搜索引擎，在接下来的章节将对搜索引擎结构中的网络爬虫设计进行说明，并给出关键部分的实现代码。
8
Web搜索引擎的设计与实现 信息处理
第四章 信息处理
4.1概述
图4-1信息处理流程图
经过上面的处理程序已经成功的获得了网页代码，但是程序需要的只是网页中包含的信息的词语，只有得到这些词语，才能够对词语相关的网页进行排序和完成索引，在这本章就将对网页进行一系列的处理，以尽可能快的速度得到这些词语。这些处理过程包含：转换，切词。信息处理的流程图如图4-1所示：
14
Web搜索引擎的设计与实现 信息处理
4.2转换
图4-2内容转换流程图
根据上述所知程序要得到是组成一个网页的词语，程序现在拥有的是网页的代码，当然代码中肯定包含了网页中所有的文字信息
[25]
，但是不要忘记，代码同
时也包含了许多的html标签。这些标签不仅仅只是html的标准标签，同时还有用户自定义的标签，对这些标签的处理我试过了如下的几种方法：
1. 去掉标签本身，但是对标签中间包含的内容还是进行正常的处理，例如：
a) 首先，这样的方式程序会对html中的每个标签都进行如上的处理，
一个html有时候标签所占得字符是远远的多于它所包含的文字信息。这样的话程序的效率会因为处理很多无用的标签而浪费支援，减低了效率。
b) 面对像这样标签，它中间的内容是无用的，
它只是对网页的显示效果有用，但是上面的程序还是会对它中间的内容进行我们的切词程序，这样不仅大大的减低了程序的效率，还切刀了许多根本于网页的内容无关的词语，这样就会降低搜索引擎的准确性。
c) 面对像这样的标签，必须对它进行解析，
15
Web搜索引擎的设计与实现 信息处理
才知道它运行后会得到什么结果，暂且不管能不能实现对它的解析，即使能够写出这样的程序，但是不得不花大量的时间去想这个程序，而其最后这个程序也得花大量的资源堆网页的进行解析，所以这个问题否定了上面的方法的可行性。
2. 面对