学号________________
密级________________ 武汉大学本科毕业论文 WEB搜索引擎分析设计与实现
BACHELOR'S DEGREE THESIS OF WUHAN UNIVERSITY
The analysis, design and accomplishment of the WEB Search Engine
College ：International School of Software
Subject ：Software Engineering
Name ：WU Pan
Directed by ：YANG Zongliang
June 2009
郑重声明
本人呈交的学位论文，是在导师的指导下，独立进行研究工作所取得的成果，所有数据、图片资料真实可靠。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确的方式标明。本学位论文的知识产权归属于培养单位。
本人签名：日期：
毕业设计（论文）原创性声明和使用授权说明
原创性声明
本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。
作者签名：日期：
指导教师签名：日期：
使用授权说明
本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名：日期：
学位论文原创性声明
本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。
作者签名：日期：年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
涉密论文按学校规定处理。
作者签名：日期：年月日
导师签名：日期：年月日
摘要
随着互联网的高速发展，信息在海量的增长。用户想要寻找到一些有用的知识非常困难，于是搜索引擎应运而生，满足广大用户的需要,现在人们已经把搜索引擎当做日常学习、工作、休闲不可缺少的一个工具。大家都知道用搜索引擎可以快速地找到自己所要的资料或信息，那么搜索引擎是怎么工作的呢？本文将会对这个问题进行解答。
本文首先介绍了基于Internet的搜索引擎的系统结构以及主流搜索引擎的工作原理，并利用目前流行的Heritrix+Lucene框架，分析、设计、实现了“SoEdu”搜索引擎。论文中附上了搜索引擎的实现代码，并配上贴图，力图使本文生动，容易理解。
关键词：搜索引擎索引Heritrix Lucene
Abstract
Along with the high speed development of the Internet, the information in the Internet is increasing m agnanimity. It’s very difficult for users to find some useful information in the Internet. So the Search Engine appeals to meet the users’ requirements. The people already treated it as an essential tool for study, work and the leisure activities. Everybody knows with the search engine one may get the material or information that he wants to find, and then how does the search engine work? The thesis will answer this question.
First of all, the thesis introduces the system structure of the search engine based on the Internet and the theory of the popular search engine, and uses the popular framework of Heritrix and Lucene. Then analyze, design and implement ”SoEdu”search engine. In the thesis there are some core code and pictures to make my thesis vivid and understanding.
Key words：Search Engine Index Heritrix Lucene
目录
第1章绪论 (2)
1.1 课题背景 (2)
1.2 国内外关于该论题的研究现状和发展趋势 (2)
1.3 本文内容安排 (3)
第2章搜索引擎概述 (4)
2.1 搜索引擎定义 (4)
2.2 搜索引擎起源及发展 (4)
2.3 搜索引擎分类 (5)
2.3.1 全文搜索引擎 (6)
2.3.2 目录索引 (6)
2.3.3 元搜索引擎 (6)
第3章搜索引擎的原理 (8)
3.1 网络蜘蛛 (8)
3.2 索引与搜索 (10)
第4章搜索引擎的分析 (11)
4.1 heritrix介绍、分析 (11)
4.1.1 heritrix介绍 (11)
4.1.2 Heritrix分析 (11)
4.2 Lucene介绍、分析 (16)
4.2.1 Lucene介绍 (16)
4.2.2 Lucene 分析 (17)
第5章搜索引擎的设计及实现 (19)
5.1 系统功能描述 (19)
5.2 系统架构 (20)
5.3 实现过程 (20)
5.3.1 数据采集 (20)
5.3.2 索引子系统 (24)
5.3.3 检索子系统 (28)
第6章项目总结以及未来工作展望 (34)
6.1 项目总结 (34)
6.2 未来工作展望 (34)
参考文献 (35)
致谢 (36)
第1章绪论
1.1 课题背景
在信息大爆炸时代下，全球信息量每隔20个月就增加一倍，而这个增长速度还会进一步增加，信息增长呈现速度惊人，来源广泛，种类繁多，数量巨大的状态。2006年制造、复制出的数字信息量共计1610亿GB，开启了前所未有的信息增长时期。这些数字信息大约是现有书籍所含信息的300万倍，如果将书籍排列起来，总长度为地球到太阳距离（约1.5亿公里）的12倍。据IDC报告显示，至2010年，这个数字将猛增到6倍，达9880亿GB，年复合增长率为57％[1]。面对极度膨胀的信息量，人们受到“信息爆炸”、“混沌信息空间（Information Chaotic Space）”和“数据过剩（Data Gult）”[2]的巨大压力。这种爆发性增长将改变机构和IT专业人员的工作方式以及消费者使用信息的方式，因此，如何从海量的信息得到有用的信息是大家关注的焦点。
从上世纪90年代互联网开始兴起，人们在方便的获得网上信息的同时，也越来越难搜索到对自己有价值的信息。显然，通过浏览一个又一个的网页寻找所需要的信息已经不太现实，于是大多数人依赖搜索引擎来帮助自己来获得有用的信息，因此搜索引擎成为继电子邮件之后最典型的WEB应用。
早在WEB出现以前，互联网上就已经存在很多旨在让人们共享的信息资源了。那些资源当时主要存在于各种允许匿名访问的FTP站点（anonymous ftp），内容以学术技术报告、研究性软件居多，它们以计算机文件的形式存在，文字材料的编码通常是PostScript或者纯文本。为了便于人们在分散的FTP资源中找到所需的东西，1990年出现了一个软件Archie，它可以说是所有搜索引擎的始祖。
1.2 国内外关于该论题的研究现状和发展趋势
WWW中文搜索引擎带有的数据库容量小，尚未形成大型的检索系统，大型、综合、?集成的元搜索引擎还没有开发出来，专业性和专题性中文搜索引擎亟需
研究开发[3]。
因特网搜索引擎既是一门技术，又是一项服务，因此搜索引擎的发展应该包括搜索引擎产品技术的研发及其服务方式的改进与发展。但是，不管搜索引擎技术如何发展，服务方式如何改进，都不应偏离用户快速、准确、方便查找信息的主导方向。提供经过甄别、筛选、评价和专家推荐的网站信息无疑是高质量搜索引擎永恒不懈的追求，是搜索引擎智能化与专家系统交汇融合的结果。基于问题的搜索技术可能将成为未来搜索引擎发展的新趋势，同时方便使用与查全率、查准率的协调发展也是不可忽视的方面。
1.3 本文内容安排
本文章节安排如下：第2章介绍了搜索引擎的定义，搜索引擎起源及发展和搜索引擎的分类；第3章介绍了搜索引擎的原理，其中着重介绍了网络蜘蛛“Spider”，索引和搜索；第4章从分析并设计“SoEdu” 搜索引擎，先介绍heritrix 和Lucene的基本原理从而分析将要实现的搜索引擎；第5章将深入设计“SoEdu”并实现“SoEdu”搜索引擎，伴以代码及贴图；第6章总结本系统的开发过程中遇到的问题，并对搜索引擎发展趋势进行讨论。
第2章搜索引擎概述
2.1 搜索引擎定义
到目前为止还没有比较确切的搜索引擎的定义，在本文中搜索引擎指的是一中在Web上应用的软件系统，它以一定的策略在Web上搜集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询系统[4]。
2.2 搜索引擎起源及发展
如前面所说搜索引擎的起源点，是1990年由Montreal的McGill University三名学生（Alan Emtage、Peter Deutsch、Bill Wheelan）发明的Archie（Archie FAQ）。Archie是第一个自动索引互联网上匿名FTP网站文件的程序，但它还不是真正的搜索引擎。Archie是一个可搜索的FTP文件名列表，用户必须输入精确的文件名搜索，然后Archie会告诉用户哪一个FTP地址可以下载该文件。
1994年4月，斯坦福大学（Stanford University）的两名博士生，美籍华人Jerry Yang（杨致远）和David Filo共同创办了Yahoo！。随着访问量和收录链接数的增长，Yahoo目录开始支持简单的数据库搜索。因为Yahoo！的数据是手工输入的，所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。
1994年初，华盛顿大学（University of Washington）的学生Brian Pinkerton开始了他的小项目WebCrawler。WebCrawler是互联网上第一个支持搜索文件全部文字的全文搜索引擎，在它之前，用户只能通过URL和摘要搜索，摘要一般来自人工评论或程序自动取正文的前100个字。
1994年7月，卡内基·梅隆大学（Carnegie Mellon University）的Michael Mauldin将John Leavitt的spider程序接入到其索引程序中，创建了Lycos。除了相关性排序外，Lycos还提供了前缀匹配和字符相近限制，Lycos 第一个在搜索结果中使用了网页自动摘要。
1995年，一种新的搜索引擎形式出现了——元搜索引擎（A Meta Search Engine Roundup）。用户只需提交一次搜索请求，由元搜索引擎负责转换处理，提交给多个预先选定的独立搜索引擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给用户。第一个元搜索引擎，是Washington大学硕士生Eric Selberg和Oren Etzioni的Metacrawler。
1995年12月，DEC的正式发布AltaVista。AltaVista是第一个支持自然语言搜索的搜索引擎，第一个实现高级搜索语法的搜索引擎（如AND、OR、NOT等)。用户可以用AltaVista搜索新闻组（Newsgroups）的内容并从互联网上获得文章，还可以搜索图片名称中的文字、搜索Titles、搜索Java applets、搜索ActiveX objects。
1998年10月之前，Google只是斯坦福大学（Stanford University）的一个小项目BackRub。1995年博士生Larry Page开始学习搜索引擎设计，于1997年9月15日注册了https://www.doczj.com/doc/5d10669117.html,的域名，1997年底，在Sergey Brin 和Scott Hassan、Alan Steremberg的共同参与下，BachRub开始提供Demo。1999年2月，Google完成了从Alpha版到Beta版的蜕变。Google公司则把1998年9月27日认作自己的生日。Google以网页级别（Pagerank）为基础，判断网页的重要性，使得搜索结果的相关性大大增强。Google公司的奇客（Geek）文化氛围、不作恶（Don’t be evil）的理念，为Google赢得了极高的口碑和品牌美誉。
2000年1月，两位北大校友，超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇（加州伯克利分校博士后）在北京中关村创立了百度（Baidu）公司。2001年8月发布https://www.doczj.com/doc/5d10669117.html,搜索引擎Beta版（此前Baidu只为其它门户网站搜狐、新浪、Tom等提供搜索引擎），2001年10月22日正式发布Baidu搜索引擎，专注于中文搜索[5]。
2.3 搜索引擎分类
搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎（Full Text Search Engine）、目录索引类搜索引擎（Search Index/Directory）和元搜索引擎（Meta Search Engine）[6]。
2.3.1 全文搜索引擎
全文搜索引擎是名副其实的搜索引擎，国外具代表性的有Google、Fast/AllTheWeb、AltaVista、Inktomi、Teoma、WiseNut等，国内著名的有百度（Baidu）。它们都是通过从互联网上提取的各个网站的信息（以网页文字为主）而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，因此他们是真正的搜索引擎。
从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己的检索程序（Indexer），俗称“蜘蛛”（Spider）程序或“机器人”（Robot）程序，并自建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的7家引擎；另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如Lycos 引擎。
2.3.2 目录索引
目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词（Keywords）查询，仅靠分类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的Yahoo雅虎。其他著名的还有Open Directory Project（DMOZ）、LookSmart、About等。国内的搜狐、新浪、网易搜索也都属于这一类。
2.3.3 元搜索引擎
元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果返回给用户。著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo等（元搜索引擎列表），中文元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如Dogpile，有的则按自定的规则将结果重新排列组合，如Vivisimo。
2.3.4 其它非主流形式：
(1)集合式搜索引擎：如HotBot在2002年底推出的引擎。该引擎类似META 搜索引擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的4个引擎当中选择，因此叫它“集合式”搜索引擎更确切些。
(2)门户搜索引擎：如AOL Search、MSN Search等虽然提供搜索服务，但自身即没有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。
(3)免费链接列表（Free For All Links，简称FFA）：这类网站一般只简单地滚动排列链接条目，少部分有简单的分类目录，不过规模比起Yahoo等目录索引来要小得多。
由于上述网站都为用户提供搜索查询服务，为方便起见，我们通常将其统称为搜索引擎。
第3章搜索引擎的原理
现今主流的搜索引擎是上面讨论过的基于Robot的搜索引擎,其构成一般由网络机器人程序，网页过滤分析器，查询器，网页数据库，索引数据库，用户接口等部分组成，如图3.1所示：
图3.1 搜索引擎结构图
3.1 网络蜘蛛
网络蜘蛛即Web Spider，是一个很形象的名字。把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。
对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的问题，如果按照每个页面的平均大小为20K计算（包含图片），100亿网页的容量是100×2000G字节，即使能够存储，下载也存在问题（按照一台机器每秒下载20K计算，需要340台机器不停的下载一年时间，才能把所有网页下载完毕）。同时，由于数据量太大，在提供搜索时也会有效率方面的影响。因此，许多搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。
在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先(图3.2-A)。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页，所以抓取的顺序是：ABCDEFGHIJK(图3.2-B)。这是最常用的方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接,所以抓取的顺序是：ABEHICDFJKG(图3.2-C)。这个方法有个优点是网络蜘蛛在设计的时候比较容易。
图 3. 2-A URL关系图图 3. 2-B广度优先图 3. 2-C深度优先
由于不可能抓取所有的网页，有些网络蜘蛛对一些不太重要的网站，设置了访问的层数。例如，在上图中，A为起始网页，属于0层，B、C、D、属于第1层，E、F、G属于第2层，H、I、J属于第3层,K属于第四层。如果网络蜘蛛设置的访问层数为2的话，网页H、I、J、K是不会被访问到的。这也让有些网站上一部分网页能够在搜索引擎上搜索到，另外一部分不能被搜索到。对于网站设计者来说，扁平化的网站结构设计有助于搜索引擎抓取其更多的网页。
网络蜘蛛在访问网站网页的时候，经常会遇到加密数据和网页权限的问题，有些网页是需要会员权限才能访问。当然，网站的所有者可以通过协议让网络蜘蛛不去抓取（下小节会介绍），但对于一些出售报告的网站，他们希望搜索引擎能搜索到他们的报告，但又不能完全免费的让搜索者查看，这样就需要给网络蜘蛛提供相应的用户名和密码。网络蜘蛛可以通过所给的权限对这些网页进行网页抓取，从而提供搜索。而当搜索者点击查看该网页的时候，同样需要搜索者提供相应的权限验证。
3.2 索引与搜索
蜘蛛程序将爬到的网页放到网页数据库里面，然后对网页数据库建立索引，一般是用倒排索引的方法，形成索引数据库。
当用户进行搜索时，搜索引擎程序将根据用户输入的关键字通过索引数据库进行检索，将检索到的结果以一定的排序方式返回给用户。
蜘蛛程序需要定期搜索在网络上爬去网页以适应网络信息的更新，搜索引擎也需要及时的建立索引。
第4章搜索引擎的分析
“SoEdu”总体上将分为两个模块，分别是“数据采集”模块和“搜索”模块，如前面所介绍，“数据采集”模块采用heritrix，“搜索”模块采用Lucene，本章将围绕这两个开源的搜索引擎技术进行“SoEdu”的分析与设计。
4.1 heritrix介绍、分析
4.1.1 heritrix介绍
Heritrix是IA（Internet Archive）开放源代码的、可扩展的、基于整个Web的归档网络爬虫工程[7]，可加入一些可互换的组件，是由互联网档案馆和北欧国家图书馆联合规范化编写于2003年初。第一次正式发布是在2004年1月，并不断的被互联网档案馆和其他感兴趣的第三方改进着。到现在已经成为一个成熟的开源爬虫，并被广泛使用。
Internet Archive的目的是开发一个特殊的爬虫，对网上的资源进行归档，建立网络数字图书馆，在过去的6年里，IA已经建立了400TB的数据。IA期望他们的crawler包含以下几种：
宽带爬虫：能够以更高的带宽去站点爬。
主题爬虫：集中于被选择的问题。
持续爬虫：不仅仅爬更当前的网页还负责爬日后更新的网页。
实验爬虫：对爬虫技术进行实验，以决定该爬什么，以及对不同协议的爬虫爬行结果进行分析的[8]。
4.1.2 Heritrix分析
4.1.2.1 抓取任务CrawlOrder
图 4. 1 CrawlOrder集成关系图
从继承关系图（图4.1）中可以看到，CrawlOrder继承自一系列的与属性设置相关的基类。另外，它的最顶层基类是javax.management.Attribute，这是一个JMX中的类，它可以动态的反映出Java容器内某个Mbean的属性变化。关于这一部分的内容不是我们所要讨论的重点，只需知道，CrawlOrder中的属性，是需要被随时读取和检测的。那么究竟使用什么工具来读取order.xml文件中的各种属性呢？另外，一个CrawlOrder的对象又该如何构建呢？Heritrix提供了很好的工具支持对于order.xml的读取。在org.archive.crawler.settings包下有一个XMLSettingsHandler类，它可以用来帮助读取order.xml,如下所示：
代码 4. 1
在XMLSettingsHandler的构造函数中，其所传入的参数orderFile正式一个经过对象封装的order.xml的File。这样，就可以直接调用其构造函数，来创建一个XMLSettingsHandler的实例，以此做为一个读取order.xml的工具。
当一个XMLSettingsHandler的实例被创建以后，可以通过getOrder()
方法来获取CrawlOrder的实例，这样也就可以进行下一步的工作了。
4.1.2.2 中央控制器CrawlController
中央控制器是一次抓取任务中的核心组件。它将决定整个抓取任务的开始和结束。事实上CrawlController有一个不带参数的构造函数，开发者可以直接通过它的构造函数来构造一个CrawlController的实例。但是值得注意的一点，在构造一个实例并进行抓取任务时，有几个步骤需要完成(如图4.2)：
(1)首先构造一个XMLSettingsHandler对象，将order.xml内的属性信息装入。
(2)调用CrawlController的构造函数，构造一个CrawlController的实例。
(3)调用CrawlController的intialize(SettingsHandler)方法，初始化CrawlController
实例。其中，传入的参数是在第一步是构造的XMLSettingsHandler实例。（4）当上述3步完成后，CrawlController 就已经具备运行的条件，可以开始运行了。此时，只需调用它的requestCrawlStart()方法，就可以启运线程池和Frontier，然后就可以开始不断的抓取网页了。
4.1.2.3链接制造工厂Frontier
根据描述，可知道Frontier是用来向线程提供链接的。它使用两个ArrayList来保存链接。第一个保存的是等待处理的链接，第二个中保存的也是链接，只不过它里面的每个链接的优先级都要高于第一个里面的链接。通常，在第二个ArrayList中保存的都是诸如DNS之类的链接，只有当这些链接被首先解析后，其后续的链接才能够被解析。
除了两个ArrayList外，还有一个名为alreadyIncluded的HashMap。它用于记录哪些已经被处理过的链接。每当调用Frontier的schedule()方法来加入一个新的链接时，Frontier总要先检查这个正要加入到队列中的链接是不是已经被处理过了[9]。