基于JAVA的搜索引擎设计与实现.doc

1、仰恩大学毕业设计 (论文 ) I 摘 要 网络中的资源非常丰富，但是如何有效的搜索信息却是一件困难的事情。建立搜索引擎就是解决这个问题的最好方法。本文首先详细介绍了基于英特网的搜索引擎的系统结构，然后从网络机器人、索引引擎、 Web 服务器三个方面进行详细的说明。为了更加深刻的理解这种技术，本人还亲自实现了一个自己的搜索引擎 新闻搜索引擎。 新闻搜索引擎是从指定的 Web 页面中按照超连接进行解析、搜索，并把搜索到的每条新闻进行索引后加入数据库。然后通过 Web 服务器接受客户端请求后从索引数据库中搜索出所匹配的新闻。 本人在介绍搜索引擎的章节 中除了详细的阐述技术核心外还结合了新闻搜索引擎的

2、实现代码来说明，图文并茂、易于理解。 关键词： 搜索引擎； 网络 蜘蛛 ； 搜索 策略 仰恩大学毕业设计 (论文 ) II Abstract The resources in the internet are abundant, but it is a difficult job to search some useful information. So a search engine is the best method to solve this problem. This article fist introduces the system structure of search eng

3、ine based on the internet in detail, then gives a minute explanation form Spider search, engine and web server. In order to understand the technology more deeply, I have programmed a news search engine by myself. The news search engine is explained and searched according to hyperlink from a appointe

4、d web page, then indexes every searched information and adds it to the index database. Then after receiving the customers requests from the web server, it soon searches the right news form the index engine, In the chapter of introducing search engine, it is not only elaborate the core technology, bu

5、t also combine with the modern code, pictures included, easy to understand. Key Words： Search engine； Web spider； Search strategy 仰恩大学毕业设计 (论文 ) III 目 录 摘 要 . I Abstract. II 引 言 . 1 1 搜索引擎的结构 . 2 1.1 搜索引擎系统概述 . 2 1.2 搜索引擎的构成 . 2 1.2.1 网络蜘蛛 . 2 1.2.2 索引与搜索 . 2 1.2.3 Web 服务器 . 3 1.3 搜索引擎的主要指标及分析 . 3 2

6、 网络机器人 . 4 2.1 什么是网络机器人 . 4 2.2 网络机器人的结构分析 . 4 2.2.2 Spider 程序结构 . 4 2.2.3 如何构造 Spider 程序 . 5 2.2.4 如何提高程 序性能 . 7 2.2.5 网络机器人的代码分析 . 7 3 基于 lucene 的索引与搜索、 tomcat 服务器 . 10 3.1 什么是 LUCENE全文检索 . 10 3.2 LUCENE的原理分析 . 10 3.2.1 客户端设计 . 10 3.2.2 全文检索的实现机制 . 11 3.2.3 Lucene 的索引效率 . 11 3.2.4 中文切分词机制 . 13 3.2

7、.5 服务端设计 . 14 3.3 LUCENE与 SPIDER的结合 . 15 3.3.1 如何解析 HTML . 16 3.4 基于 TOMCAT 的 WEB 服务器 . 19 3.5 在 TOMCAT 上部署项目 . 19 4 搜索引擎策略 . 21 4.1 简介 . 21 4.2 面向主题的搜索策略 . 21 4.2.1 导向词 . 21 4.2.2 网页评级 . 21 4.2.3 权威网页和中心网页 . 22 结 论 . 23 参考文献 . 24 致 谢 . 25 仰恩大学毕业设计 (论文 ) 1 引 言 面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，

8、所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。 搜索引擎技术伴随着 WWW 的发展是引人注目的。搜索引擎大约经历了三代的更新发展： 第一代搜索引擎出现于 1994 年前后。以 Altavista， Yahoo 和 Infoseek 为代表，注重反馈结果的数量，主要特征是“求全”。它主要依靠人工分拣的分类目录搜索，通常由网页制作人自行 建立网站名称、网站内容的文字摘要，并将其加入到搜索引擎的资料库中。搜索引擎根据用户键入的信息，根据预先设定的规则进行简单的匹配、排序和显示。这种方法只能进行简单的字符串匹配，无法进行全文搜索。研究表明，

9、搜索引擎性能并没有想象中的那么优秀，在全球 11 个主要的搜索引擎中，搜索引擎仅能搜索到国际互联网上全部页面的 16%，甚至更低，造成这种情况的原因，主要是这些搜索引擎没有及时更新资料。 第二代搜索引擎，利用超链接分析为基础的机器抓取技术，由搜索引擎使用一个程序在网络上撷取资料，并自动将得到的结果存入索引库中。搜 索引擎根据用户键入的信息进行匹配、排序和显示。这些引擎的主要特点是提高了查准率，可以用“求精”来描述它的优点，即不需要网站制作人单独键入供搜索的信息，并且从理论上讲，可将任意网站的所有网页加入到它的资料库中。第二代搜索引擎的大多数查询都会返回成千上万条信息，查询结果中无关信息太多，而

10、且查询结果显示比较混乱，使用者仍然难以找到真正想要的资料。 第三代搜索引擎是对第二代搜索引擎的改进，相对于前两代，其更注重智能化和用户使用的个性化，主要增加了互动性和个性化等高级的技术，采用了中文自动分类、自动聚类等人工智能技术 ，而且使用了中文内容分析技术以及区域智能识别技术，增强了搜索引擎的查询能力。同时，搜索技术将更加智能化，可搜索资源将更加广泛，搜索方式也将更加便捷有效，为用户使用搜索引擎获取信息获得更好的体验。 在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的全文检索。著名的因特网搜索引擎包括 F

11、irst Search、 Google、 HotBot 等。本人这里研究的就是基于因特网的搜索技术。 仰恩大学毕业设计 (论文 ) 2 1 搜索引擎 的 结构 1.1 搜索引擎 系统概述 搜索引擎 是 根据用户的查询请求，按照一定算法从索引数据中查找信息返回给用户。为了保证用户查找信息的精度和新鲜度，搜索引擎需要建立并维护一个庞大的索引数据库。 一般的搜索引擎由网络机器人程序、索引与搜索程序、索引数据库等部分组成。 系统结构图 1.2 搜索引擎的构成 1.2.1网络 蜘蛛 网络蜘蛛也称为 “ 网络机器人 ” (Spider)，是一个功能很强的 WEB 扫描 程序。它可以在扫描 WEB 页面的同

12、时检索其内的超链接并加入扫描队列等待以后扫描。因为 WEB 中广泛使用超链接，所以一个 Spider 程序理论上 可以访问整个 WEB 页面。 为了保证网络机器人遍历信息的广度和深度需要设定一些重要的链接并制定相关的扫描策略。 1.2.2索引与搜索 网络机器人将遍历得到的页面存放在临时数据库中，如果通过 SQL 直接查询信息速度将会难以忍受。为了提高检索效率，需要建立索引，按照倒排文件的格式存放。如果索引不及时跟新的话，用户用搜索引擎也不能检索到。 WWW 文档 网络机器人程序 建立 Lucene 索引 从数据库中搜索信息 Tomcat 服务器 Lucene 索引数据库 WWW 浏览器 WWW

13、 浏览器 JSP 网络机器人程序 仰恩大学毕业设计 (论文 ) 3 用户输入搜索条件后搜索程序将通过索引数据库进行检索 然后把符合查询要求的数据库按照一定的策略进行分级排列并且返回给用户。 1.2.3 Web 服务器 客户一般通过浏览器进行查询，这就 需要系统提供 Web服务器并且与索引数据库进行连接。客户在浏览器中输入查询条件， Web服务器接收到客户的查询条件后在索引数据库中进行查询、排列然后返回给客户端。 1.3 搜索引擎 的主要指标及分析 搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。这些指标决定了搜索引擎的技术指标。 搜索引擎的技术指标决定了搜索引擎的评价指标。好的搜索引擎

14、应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。 召回率：一次搜索结果中符合用户要求的数目与用户查询相关信息的总数之比。 准确率：一次搜索 结果中符合用户要求的数目与该次搜索结果总数之比。 相关度：用户查询与搜索结果之间相似度的一种度量。 精确度：对搜索结果的排序分级能力和对垃圾网页的抗干扰能力。 仰恩大学毕业设计 (论文 ) 4 2 网络机器人 2.1 什么是网络机器人 网络机器人又称为 Spider 程序，是一种专业的 Bot 程序。用于查找大量的Web 页面。它从一个简单的 Web 页面上开始执行，然后通过其超链接在访问其他页面，如此反复理论上可以扫描

15、互联网上的所有页面。 基于因特网的搜索引擎是 Spider 的最早应用。例如搜索巨头 Google 公司，就利用网络机器 人程序来遍历 Web 站点，以创建并维护这些大型数据库。 网络机器人还可以通过扫描 Web 站点的主页来得到这个站点的文件清单和层次机构。还可以扫描出中断的超链接和拼写错误等。 2.2 网络机器人的 结构分析 Internet 是建立在很多相关协议基础上的，而更复杂的协议又建立在系统层协议之上。 Web 就是建立在 HTTP ( Hypertext Transfer Protocol ) 协议基础上，而 HTTP 又是建立在 TCP/IP ( Transmission Co

16、ntrol Protocol / Internet Protocol ) 协议之上，它同时也是一种 Socket 协议。 所以网络机器人 本质上 是一种基于 Socket 的网络程序。 2.2.2 Spider程序结构 网络机器人必须从一个网页迁移到另一个网页，所以必须找到该页面上的超连接。程序首先解析网页的 HTML 代码，查找该页面内的超连接然后通过递归和非递归两种结构来实现 Spider 程序。 递归结构 ： 递归是在一个方法中调用自己本身的程序设计技术。 虽然比较容易实现但耗费内存且不能使用多线程技术， 故 不适合大型项目。 非递归结构 ： 这种方法使用队列的数据结构，当 Spider

17、 程序发现超 连接后并不调用自己本身而是把超连接加入到等待队列中。当 Spider 程序扫描完当前页面后会根据制定的策略访问队列中的下一个超连接地址。 虽然这里只描述了一个队列，但在实际编程中用到了四个队列，他们每个队列都保存着同一处理状态的 URL。 （ 1） 等待队列 ： 在这个队列中， URL 等待被 Spider 程序处理。新发现的 URL也被加入到这个队列中 。 （ 2） 处理队列 ： 当 Spider 程序开始处理时，他们被送到这个队列中 。 （ 3） 错误队列 ： 如果在解析网页时出错， URL 将被送到这里。该队列中的URL 不能被移入其他队列中 。 （ 4） 完 成队列 ：

18、如果解析网页没有出错， URL 将被送到这里。该队列中的仰恩大学毕业设计 (论文 ) 5 URL 不能被移入其它队列中 。 在同一时间 URL 只能在一个队列中，我们把它称为 URL 的状态。 以上的图表示了队列的变化过程，在这个过程中，当一个 URL 被加入到等待队列中时 Spider 程序就会开始运行。只要等待队列中有一个网页或 Spider 程序正在处理一个网页，程序就会继续他的工作。当等待队列为空并且当前没有任何网页时， Spider 程序就会停止它的工作。 2.2.3如何构造 Spider 程序 在构 造 Spider 程序之前我们先了解下 程序的各个部分是如何共同工作的。以及如何对

19、这个程序进行扩展。 IspiderReportable 接口 ： 这是一个必须实现的接口，可以通过回调函数接受 Spider 所遇到的页面。接口定义了 Spider 向他的控制者发送的几个事件。通过提供对每个事件的处理程序，可以创建各种 Spider 程序。 下面是他的接口声明： public interface IspiderReportable public boolean foundInternalLink(String url); public boolean foundExternalLink(String url); public boolean foundOtherLink(St

20、ring url); public void processPage(HTTP page); public void completePage(HTTP page,boolean error); public boolean getRemoveQuery(); public void SpiderComplete(); 发现 URL 等待队列 运行队列 完成队列 错误队列 完 成 URL 仰恩大学毕业设计 (论文 ) 6 程序扩展 流程图 如下所示： 把 URL 加入等待队列 Spider 程序工作完成 等待队列中是否有 URL？ 否 下载从等待队列中得到的网页，并将他送入运行队列中。 是 这

21、个网页包含其他超级连接吗？ 将这一网页送入完成队列并继续 查看网页上的下一个超连接 是 否 为 指 向Web 的连接？ 报告其他类型连接 连接是否与网页所在主机不同且只处理本地连接？ 报告外部连接 报告网页连接 将连接加入等候队列 否 是 否 是 否 是 仰恩大学毕业设计 (论文 ) 7 2.2.4 如何提高 程序 性能 Internet 中拥有海量的 Web 页面，如果开发出高效的 Spider 程序是非常重要的。下面就来介绍下几种提高性能的技术： (1)Java 的多线程技术 线程是通过程序的一条执行路线。多线程是一个程序同时运行多个任务的能力。它是在一个程序的内部进行分工合作。 优化程序

22、的通常方法是确定瓶颈并改进他。瓶颈是一个程序中最慢的部分，他限制了其他任务的运行。据个例子说明：一个 Spider 程序需要下载十个页面，要完成这一任务， 程序必须向服务器发出请求然后接受这些网页。当程序等待响应的时候其他任务不能执行，这就影响了程序的效率。如果用多线程技术可以让这些网页的等待时间合在一起，不用互相影响，这就可以 极大的改进程序性能。 (2)数据库技术 当 Spider 程序访问一个大型 Web 站点时，必须使用一种有效的方法来存储站点队列。这些队列管理 Spider 程序必须维护大型网页的列表。如果把他们放在内存中将会是性能下降，所以我们可以把他们放在数据库中减少系统资源的消耗。 2.2.5网络机器人的 代码 分析 程序结构图如下：