苏ICP备112451047180号-6
Web搜索引擎的分析与设计
摘 要
随着互联网的不断发展和日益普及，网上的信息量在爆炸式增长，如何在最短时间内找到我们所需要的资料就成了一个非常关键的问题。为了解决这个问题，Web搜索引擎就随之出现了，并得到了飞速发展，现在已经成为互联网上仅次于电子邮件的第二大网络服务。
首先，本文讲述了Web搜索引擎的历史和现状。
其次，本文介绍了Web搜索引擎的基本原理和技术。
再次，本文分析了Web搜索引擎的系统结构，并着重从网络蜘蛛，索引引擎和Web查询服务三个部分进行了详细的描述。与此同时，本文描述了在Java开发环境下，如何设计实现一个利用开源工具包的Web搜索引擎——WebCdf，包括Web信息搜集索引器WebSpider和Web查询服务器Search两个子系统。
WebCdf搜索引擎从指定的Web页面开始解析，把获得的链接放入工作队列，在万维网上进行广度优先搜索，并把每个页面的URL地址和文本进行索引存入数据库，然后Web服务器接收客户端请求，从数据库中返回页面信息。
本文介绍和研究了一系列与Web搜索引擎相关的技术，包括网页抓取、相关性排序（VSM）、信息提取、信息索引等，这些技术将被应用到文中提出的系统设计方案中。
最后，本文简单地讲述了搜索引擎的未来发展趋势。
关键词: 互联网，搜索引擎，信息提取，Java
Web搜索引擎的原理分析
3.1 基本原理
搜索引擎的基本原理是通过网络蜘蛛定期在web网页上爬行，然后发现新的网页，把它们取回来放到本地的数据库中，用户的查询请求可以通过查询本地的数据库来得到。
搜索引擎由网上蜘蛛自动在网页上按某种策略进行远程数据的搜索与获取，并生成本地索引。由于不需要人们的介入，速度得以极大的提高。其覆盖面和及时性也得以大大的提高。Spider沿着WWW文件的链接在网上漫游，记录 URL、文件的简明摘要、关键字或索引，形成一个很大的数据库，这种数据库包括标题、摘要、关键词和URL、文件的大小、语种以及词出现的频率。它的运行方式为：从一个或一组URL开始，访问该URL所指HTML文件中所有的URL锚链，然后再以这些新的URL为起始点，继续进行本地索引，直到再也没有满足条件的新的URL 为止。在记录新的URL时，可以进行分析和判断，从中去掉不需要或不想要的URL，这不但提高了本地索引的速度，也减少了索引文件在本地所占用的磁盘空间。
搜索引擎将HTML 格式文件取到本地后，由一个小程序将其中的辅助部分去掉，如各种HTML标签、脚本程序，并按一定策略将其中可用于查询的部分 (如关键字和一些指定词等 )存储到数据库中，形成本地查询数据库，以后再查时就不必到远地去重新获取HTML 格式文件了 。
当用户输入关键词（Keyword）查询时，该搜索引擎会告诉用户包含该关键词信息的所有网址，并提供通向该网络的链接。搜索引擎的数据检索方式主要是关键字的匹配方式：如泛匹配、模糊匹配、正则匹配以及多关键字的处理方式等 。能为用户提供全文索引、约束性检索、基于布尔关系的查询方式，并对查询结果根据某种算法和规则评分和排序。
通常一个 Web搜索引擎的架构[7]分为前端和后端两部分，就像图2-2中所示。在前端流程中，用户在搜索引擎提供的界面中输入要搜索的关键词，这里提到的用户界面一般是一个带有输入框的 Web 页面，然后应用程序将搜索的关键词解析成搜索引擎可以理解的形式，并在索引文件上进行搜索操作。在排序后，搜索引擎返回搜索结果给用户。在后端流程中，网络爬虫或者机器人从因特网上获取 Web 页面，然后索引子系统解析这些 Web 页面并存入索引文件中。
8 总结与展望
8.1 设计总结
本文实现的WebCdf搜索引擎性能如何？本人利用现有条件进行了测试，首先是WebSpider抓取网页生成索引效率的测试，表7-1的数据是1分钟内，在网络带宽1Mbps，默认10个蜘蛛线程获得的。
表8.1 WebSpider-GetHTMLPage抓取各网站的数据
表8.2 系统在各高校主页中查询测试（以GOOGLE为参考）
从表中的数据看出，如果我们排除网站服务器和网络线路的影响，针对不同网站页面大小的特点，采用不同的线程数可以获得更理想的效果。当网页平均大小较小时，适当提高线程数，可以更充分的利用网络带宽，当网页平均大小比较大时，则线程数不宜过多，占用过多的系统资源反而影响速度。
其次是WebSpider生成索引的质量，本人用Luke打开索引文件，可以看到索引记录几乎没有重复的URL，对正文的抓取质量也不错，正文也实现了分词，索引的质量对查询是很关键的。
最后是Search查询服务器的表现。前文提到Web搜索引擎有几个主要的技术指标，由于本人到目前为止只积累了1万多个网页，网络覆盖率很低，无法保证每次查询的召回率。不过就本文抓取的内容进行搜索，返回的记录数以及前几页的准备率都比较高，可以满足小型应用的需要。查询时，可能记录还比较少，响应时间几乎感觉不到，从这里可以看出倒排索引结构的优势。
当然本文实现的WebCdf搜索引擎还有一些不足之处，如目前只能抓取静态网页，无法抓取动态网页；无法区分相同IP不同网址的情况，只能根据网址区分；正文解析时对一些标签还不能完全过滤，会影响索引质量；还有面对复杂的网络环境，处理异常的能力还不够等等。同时在MP3搜索方面的独立性较差，资源有效性难以保证。这些都是需要不断完善和改进的地方。
通过对Web搜索引擎的分析和设计，本人了解了Web搜索引擎的原理和结构，掌握了Web搜索引擎的基本技术，最后也实现了自己的搜索引擎，这是一件很受益的事情。对于自己实现的搜索引擎，本人会进一步学习研究，不断地完善它，希望能找到它应用的一片空间。
8.2 未来展望
搜索引擎伴随着网络信息爆炸而诞生，随着互联网的不断发展，将对搜索引擎的技术要求越来越高，以满足用户的需要。
为了让大多数用户方便地使用搜索，要求搜索引擎具有处理自然语言输入的功能，而且作为面向全球服务的搜索引擎必须面对不同语言的用户，即未来的搜索引擎应该具有满足对多种语言输入的功能。
随着语音识别技术和多媒体技术的发展，未来的搜索引擎应该可以利用语音作为输入，可以搜索的内容也不再局限于文字信息，而可以拓展到多媒体信息。
一个理想的搜索引擎还应该对不同的用户在相同的检索请求下有不同的检索结果，即对用户具有自适应能力。
根据上文的分析，未来搜索引擎将有如下主要发展趋势：
1． 自然语言，精度更高；
2． 多种语言搜索；
3． 善解人意，学习个人喜好；
4． 多通道输入和多媒体输出[18]；
5． 个性化和本地化。
总之，未来的搜索引擎应该信息量更大、搜索速度更快、搜索精度更高和能够满足用户个性化的要求，发展趋势将是智能化的、个性化的。
参考文献
[1] 中国互联网络信息中心（CNNIC）.《2003 年中国互联网络信息资源数量调查报告》,2004
http://www.cnnic.com.cn/index/0E/00/12/index.htm
[2] 徐宝文，张卫丰. 搜索引擎与信息获取技术[M]. 北京：清华大学出版社，2003.
[3] Scott C. Deerwester, Susan T. Dumais, Thomas K. Landauer, George W. Furnas,and Richard A. Harshman. Indexing by Latent Semantic Analysis. Journal ofthe American Society of Information Science, 41(6):391--407, 1990
[4] Landauer, T. K., Foltz, P. W., and Laham, D. Introduction to Latent SemanticAnalysis. Discourse Processes, 25, 259-284, 1998
[5] J. Zobel, A. Moffat, and K. Ramamohanarao. Inverted files versus signature files for text indexing. ACM Transactions on Database Systems, 23(4):453--490,Dec. 1998
[6] 孙宾，“现代汉语文本的词语切分技术”，技术报告，北京大学计算语言学研究所
[7] 李小明，闫宏飞，王继民. 搜索引擎——原理、技术与系统[M]. 北京：科学出版社，2005.
[8] 李争，陆正中. JBuilder精髓[M]. 北京：电子工业出版社，2004.
[9] 车东. 在应用中加入全文检索功能——基于Java的全文索引引擎Lucene简介[DB/OL]. http://www.chedong.com/tech/lucene.html,2002-08.
[10] 谢希仁. 计算机网络. 北京： 电子工业出版社，2005
[11] 李宇. 开放源代码的全文检索引擎Lucene――介绍、系统结构与源码实现分析[DB/OL].
[12] （美）Bruce Eckel著；陈昊鹏 饶若楠等译 java编程思想（Thinking in java Third Edition）[M].机械工业出版社，2006
[13] 李刚. 宋伟. 邱哲编著； Ajax+lucene构建搜索引擎[M].人民出版社，2006
[14] M.Hall，L.Brown著；赵学良译. Servlet与JSP核心编程（第2版）[M]. 北京：清华出版社，2004.
[15]（美）高斯帕那（Gospodnetic,O,）,(美)哈特赫(Hatcher,E,)著，谭鸿等译; lucene in action 中文版[M].电子工业出版社，2007
[16] 胡伏湘.雷军环编著java程序设计实用教程[M].清华大学出版社，2005
[17] 赵江华，闫宏飞，王建勇，李晓明，“天网中的并行与分布处理”，
PKU_CS_NET_TR2002001，2002 年1月
[18] 于敦德. 从Larbin看互联网爬虫设计[DB/OL].
http://www.example.net.cn/archives/2005/12/aioeaee.html,2005-12-16.
http://liyu2000.nease.net/article/Lucene/bachelor-paper.htm,2003-02.
摘 要
随着互联网的不断发展和日益普及，网上的信息量在爆炸式增长，如何在最短时间内找到我们所需要的资料就成了一个非常关键的问题。为了解决这个问题，Web搜索引擎就随之出现了，并得到了飞速发展，现在已经成为互联网上仅次于电子邮件的第二大网络服务。
首先，本文讲述了Web搜索引擎的历史和现状。
其次，本文介绍了Web搜索引擎的基本原理和技术。
再次，本文分析了Web搜索引擎的系统结构，并着重从网络蜘蛛，索引引擎和Web查询服务三个部分进行了详细的描述。与此同时，本文描述了在Java开发环境下，如何设计实现一个利用开源工具包的Web搜索引擎——WebCdf，包括Web信息搜集索引器WebSpider和Web查询服务器Search两个子系统。
WebCdf搜索引擎从指定的Web页面开始解析，把获得的链接放入工作队列，在万维网上进行广度优先搜索，并把每个页面的URL地址和文本进行索引存入数据库，然后Web服务器接收客户端请求，从数据库中返回页面信息。
本文介绍和研究了一系列与Web搜索引擎相关的技术，包括网页抓取、相关性排序（VSM）、信息提取、信息索引等，这些技术将被应用到文中提出的系统设计方案中。
最后，本文简单地讲述了搜索引擎的未来发展趋势。
关键词: 互联网，搜索引擎，信息提取，Java
Web搜索引擎的原理分析
3.1 基本原理
搜索引擎的基本原理是通过网络蜘蛛定期在web网页上爬行，然后发现新的网页，把它们取回来放到本地的数据库中，用户的查询请求可以通过查询本地的数据库来得到。
搜索引擎由网上蜘蛛自动在网页上按某种策略进行远程数据的搜索与获取，并生成本地索引。由于不需要人们的介入，速度得以极大的提高。其覆盖面和及时性也得以大大的提高。Spider沿着WWW文件的链接在网上漫游，记录 URL、文件的简明摘要、关键字或索引，形成一个很大的数据库，这种数据库包括标题、摘要、关键词和URL、文件的大小、语种以及词出现的频率。它的运行方式为：从一个或一组URL开始，访问该URL所指HTML文件中所有的URL锚链，然后再以这些新的URL为起始点，继续进行本地索引，直到再也没有满足条件的新的URL 为止。在记录新的URL时，可以进行分析和判断，从中去掉不需要或不想要的URL，这不但提高了本地索引的速度，也减少了索引文件在本地所占用的磁盘空间。
搜索引擎将HTML 格式文件取到本地后，由一个小程序将其中的辅助部分去掉，如各种HTML标签、脚本程序，并按一定策略将其中可用于查询的部分 (如关键字和一些指定词等 )存储到数据库中，形成本地查询数据库，以后再查时就不必到远地去重新获取HTML 格式文件了 。
当用户输入关键词（Keyword）查询时，该搜索引擎会告诉用户包含该关键词信息的所有网址，并提供通向该网络的链接。搜索引擎的数据检索方式主要是关键字的匹配方式：如泛匹配、模糊匹配、正则匹配以及多关键字的处理方式等 。能为用户提供全文索引、约束性检索、基于布尔关系的查询方式，并对查询结果根据某种算法和规则评分和排序。
通常一个 Web搜索引擎的架构[7]分为前端和后端两部分，就像图2-2中所示。在前端流程中，用户在搜索引擎提供的界面中输入要搜索的关键词，这里提到的用户界面一般是一个带有输入框的 Web 页面，然后应用程序将搜索的关键词解析成搜索引擎可以理解的形式，并在索引文件上进行搜索操作。在排序后，搜索引擎返回搜索结果给用户。在后端流程中，网络爬虫或者机器人从因特网上获取 Web 页面，然后索引子系统解析这些 Web 页面并存入索引文件中。
8 总结与展望
8.1 设计总结
本文实现的WebCdf搜索引擎性能如何？本人利用现有条件进行了测试，首先是WebSpider抓取网页生成索引效率的测试，表7-1的数据是1分钟内，在网络带宽1Mbps，默认10个蜘蛛线程获得的。
表8.1 WebSpider-GetHTMLPage抓取各网站的数据
| 网站名称 | 抓取网页数 | 生成索引数 | 下载总量 |
| 世纪前线 | 299 | 292 | 3865KB |
| 中国教育曙光网 | 295 | 251 | 3012KB |
| Matrix-与java共舞 | 221 | 161 | 3604KB |
| 人民网 | 150 | 148 | 4678KB |
| 中国学生网 | 158 | 143 | 4850KB |
| 学生大 | 142 | 139 | 4947KB |
| 阿里巴巴 | 39 | 31 | 5649KB |
| 搜房网 | 29 | 28 | 5515KB |
表8.2 系统在各高校主页中查询测试（以GOOGLE为参考）
| 关键字 | 查准率 | 查全率 | 评价 |
| 广东工业大学 | 0.95 | 0.95 | 良好 |
| 华南理工大学 | 0.93 | 0.96 | 良好 |
| 中山大学 | 0.96 | 0.87 | 良好 |
| 暨南大学 | 0.89 | 0.91 | 良好 |
| 广州大学 | 0.90 | 0.94 | 良好 |
| 深圳大学 | 0.99 | 0.93 | 良好 |
| 华南师范大学 | 0.97 | 0.94 | 良好 |
| 广州美术学院 | 0.94 | 0.94 | 良好 |
从表中的数据看出，如果我们排除网站服务器和网络线路的影响，针对不同网站页面大小的特点，采用不同的线程数可以获得更理想的效果。当网页平均大小较小时，适当提高线程数，可以更充分的利用网络带宽，当网页平均大小比较大时，则线程数不宜过多，占用过多的系统资源反而影响速度。
其次是WebSpider生成索引的质量，本人用Luke打开索引文件，可以看到索引记录几乎没有重复的URL，对正文的抓取质量也不错，正文也实现了分词，索引的质量对查询是很关键的。
最后是Search查询服务器的表现。前文提到Web搜索引擎有几个主要的技术指标，由于本人到目前为止只积累了1万多个网页，网络覆盖率很低，无法保证每次查询的召回率。不过就本文抓取的内容进行搜索，返回的记录数以及前几页的准备率都比较高，可以满足小型应用的需要。查询时，可能记录还比较少，响应时间几乎感觉不到，从这里可以看出倒排索引结构的优势。
当然本文实现的WebCdf搜索引擎还有一些不足之处，如目前只能抓取静态网页，无法抓取动态网页；无法区分相同IP不同网址的情况，只能根据网址区分；正文解析时对一些标签还不能完全过滤，会影响索引质量；还有面对复杂的网络环境，处理异常的能力还不够等等。同时在MP3搜索方面的独立性较差，资源有效性难以保证。这些都是需要不断完善和改进的地方。
通过对Web搜索引擎的分析和设计，本人了解了Web搜索引擎的原理和结构，掌握了Web搜索引擎的基本技术，最后也实现了自己的搜索引擎，这是一件很受益的事情。对于自己实现的搜索引擎，本人会进一步学习研究，不断地完善它，希望能找到它应用的一片空间。
8.2 未来展望
搜索引擎伴随着网络信息爆炸而诞生，随着互联网的不断发展，将对搜索引擎的技术要求越来越高，以满足用户的需要。
为了让大多数用户方便地使用搜索，要求搜索引擎具有处理自然语言输入的功能，而且作为面向全球服务的搜索引擎必须面对不同语言的用户，即未来的搜索引擎应该具有满足对多种语言输入的功能。
随着语音识别技术和多媒体技术的发展，未来的搜索引擎应该可以利用语音作为输入，可以搜索的内容也不再局限于文字信息，而可以拓展到多媒体信息。
一个理想的搜索引擎还应该对不同的用户在相同的检索请求下有不同的检索结果，即对用户具有自适应能力。
根据上文的分析，未来搜索引擎将有如下主要发展趋势：
1． 自然语言，精度更高；
2． 多种语言搜索；
3． 善解人意，学习个人喜好；
4． 多通道输入和多媒体输出[18]；
5． 个性化和本地化。
总之，未来的搜索引擎应该信息量更大、搜索速度更快、搜索精度更高和能够满足用户个性化的要求，发展趋势将是智能化的、个性化的。
参考文献
[1] 中国互联网络信息中心（CNNIC）.《2003 年中国互联网络信息资源数量调查报告》,2004
http://www.cnnic.com.cn/index/0E/00/12/index.htm
[2] 徐宝文，张卫丰. 搜索引擎与信息获取技术[M]. 北京：清华大学出版社，2003.
[3] Scott C. Deerwester, Susan T. Dumais, Thomas K. Landauer, George W. Furnas,and Richard A. Harshman. Indexing by Latent Semantic Analysis. Journal ofthe American Society of Information Science, 41(6):391--407, 1990
[4] Landauer, T. K., Foltz, P. W., and Laham, D. Introduction to Latent SemanticAnalysis. Discourse Processes, 25, 259-284, 1998
[5] J. Zobel, A. Moffat, and K. Ramamohanarao. Inverted files versus signature files for text indexing. ACM Transactions on Database Systems, 23(4):453--490,Dec. 1998
[6] 孙宾，“现代汉语文本的词语切分技术”，技术报告，北京大学计算语言学研究所
[7] 李小明，闫宏飞，王继民. 搜索引擎——原理、技术与系统[M]. 北京：科学出版社，2005.
[8] 李争，陆正中. JBuilder精髓[M]. 北京：电子工业出版社，2004.
[9] 车东. 在应用中加入全文检索功能——基于Java的全文索引引擎Lucene简介[DB/OL]. http://www.chedong.com/tech/lucene.html,2002-08.
[10] 谢希仁. 计算机网络. 北京： 电子工业出版社，2005
[11] 李宇. 开放源代码的全文检索引擎Lucene――介绍、系统结构与源码实现分析[DB/OL].
[12] （美）Bruce Eckel著；陈昊鹏 饶若楠等译 java编程思想（Thinking in java Third Edition）[M].机械工业出版社，2006
[13] 李刚. 宋伟. 邱哲编著； Ajax+lucene构建搜索引擎[M].人民出版社，2006
[14] M.Hall，L.Brown著；赵学良译. Servlet与JSP核心编程（第2版）[M]. 北京：清华出版社，2004.
[15]（美）高斯帕那（Gospodnetic,O,）,(美)哈特赫(Hatcher,E,)著，谭鸿等译; lucene in action 中文版[M].电子工业出版社，2007
[16] 胡伏湘.雷军环编著java程序设计实用教程[M].清华大学出版社，2005
[17] 赵江华，闫宏飞，王建勇，李晓明，“天网中的并行与分布处理”，
PKU_CS_NET_TR2002001，2002 年1月
[18] 于敦德. 从Larbin看互联网爬虫设计[DB/OL].
http://www.example.net.cn/archives/2005/12/aioeaee.html,2005-12-16.
http://liyu2000.nease.net/article/Lucene/bachelor-paper.htm,2003-02.
目 录
1 概述 1
1.1引言 1
1.2 搜索引擎的发展历史 2
1.3 搜索引擎的现状介绍 3
1.4 小结 4
2 相关技术 5
2.1 相关抓取技术 5
2.2 相关排序技术 6
2.3 信息索引技术 8
2.4 提高索引性能 8
2.5 其它相关技术 9
2.5.1数据存储 9
2.5.2 中文分词 10
2.6 小结 10
3 Web搜索引擎的原理分析 11
3.1 基本原理 11
3.2 网页搜集 12
3.3 预处理 13
3.4 查询服务 14
3.5 搜索引擎的技术指标 15
3.6 小结 15
4 Web搜索引擎的系统结构 16
4.1系统概述 16
4.2系统各个部分功能 17
4.2.1网络蜘蛛 17
4.2.2 索引与检索 18
4.2.3 Web查询服务器 18
4.3 系统开发工具及资源 18
4.4 小结 19
5 两种Spider的实现 20
5.1 Pages-Spider的实现 20
5.1.1 Pages-Spider介绍 20
5.1.2 Pages-Spider结构分析 20
5.1.3 Pages-Spider程序结构 22
5.1.4 Pages-Spider实现 26
5.1.5小结 28
5.2 Mp3-Spider的实现 29
5.2.1 Pages-Spider程序结构 29
5.2.2 Mp3s-Spider结构分析 29
5.2.3 Mp3s-Spider实现 31
5.2.1 小结 33
6 基于Lucene的全文索引实现 34
6.1 Lucene全文检索介绍 34
6.2 Lucene的特性分析 34
6.2.1 Lucene的核心部分——索相与排序 34
6.2.2 Lucene相关度积分公式 35
6.2.3 Lucene特性 36
6.3 Lucene的工作原理 37
6.3.1 全文检索的实现机制 37
6.3.2 Lucene的索引效率 37
6.3.3 中文分词问题 38
6.4索引功能的实现 39
6.4.1 分词实现 39
6.4.2 PAGES-索引功能实现 39
6.4.3 MP3S-索引功能实现 40
6.5索引合并的实现 41
7 基于Tomcat的服务器实现 43
7.1 Tomcat介绍 43
7.2 客户端设计 43
7.3 服务端设计 46
7.4 部署Tomcat项目 48
7.5 小结 49
8 总结与展望 50
8.1 设计总结 50
8.2 未来展望 51
参考文献 53
致 谢 55
