1、2000年搜索引擎2000年大会上，按照Google公司总裁Larry Page的演讲，Google正在用3,000台运行Linux系统的个人电脑在搜集Web上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。每台微机运行多个爬虫程序搜集网页的峰值速度是每秒100个网页，平均速度是每秒48.5个网页，一天可以搜集超过4，000，000网页 搜索引擎一词在国内外因特网领域被广泛使用，然而他的含义却不尽相同。在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的全文检索。著名的因特网搜
2、索引擎包括First Search、Google、HotBot等。在中国，搜索引擎通常指基于网站目录的搜索服务或是特定网站的搜索服务，本人这里研究的是基于因特网的搜索技术。第二章 搜索引擎的结构 2.1系统概述 搜索引擎是根据用户的查询请求，按照一定算法从索引数据中查找信息返回给用户。为了保证用户查找信息的精度和新鲜度，搜索引擎需要建立并维护一个庞大的索引数据库。一般的搜索引擎由网络机器人程序、索引与搜索程序、索引数据库等部分组成。系统结构图 2.2搜索引擎的构成 2.2.1网络机器人 网络机器人也称为“网络蜘蛛”（Spider），是一个功能很强的WEB扫描程序。它可以在扫描WEB页面的同时检
3、索其内的超链接并加入扫描队列等待以后扫描。因为WEB中广泛使用超链接，所以一个Spider程序理论上可以访问整个WEB页面。为了保证网络机器人遍历信息的广度和深度需要设定一些重要的链接并制定相关的扫描策略。2.2.2索引与搜索 网络机器人将遍历得到的页面存放在临时数据库中，如果通过SQL直接查询信息速度将会难以忍受。为了提高检索效率，需要建立索引，按照倒排文件的格式存放。如果索引不及时跟新的话，用户用搜索引擎也不能检索到。用户输入搜索条件后搜索程序将通过索引数据库进行检索然后把符合查询要求的数据库按照一定的策略进行分级排列并且返回给用户。2.2.3 Web服务器 客户一般通过浏览器进行查询，这
4、就需要系统提供Web服务器并且与索引数据库进行连接。客户在浏览器中输入查询条件，Web服务器接收到客户的查询条件后在索引数据库中进行查询、排列然后返回给客户端。2.3搜索引擎的主要指标及分析 搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。这些指标决定了搜索引擎的技术指标。搜索引擎的技术指标决定了搜索引擎的评价指标。好的搜索引擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。召回率：一次搜索结果中符合用户要求的数目与用户查询相关信息的总数之比 准确率：一次搜索结果中符合用户要求的数目与该次搜索结果总数之比 相关度：用户查询与搜索结果之间相似度的一种度
5、量 精确度：对搜索结果的排序分级能力和对垃圾网页的抗干扰能力 2.4小节 以上对基于因特网的搜索引擎结构和性能指标进行了分析，本人在这些研究的基础上利用JavaTM技术和一些Open Source工具实现了一个简单的搜索引擎新闻搜索引擎。在接下来的几章里将会就本人的设计进行详细的分析。第三章 网络机器人 3.1什么是网络机器人 网络机器人又称为Spider程序，是一种专业的Bot程序。用于查找大量的Web页面。它从一个简单的Web页面上开始执行，然后通过其超链接在访问其他页面，如此反复理论上可以扫描互联网上的所有页面。基于因特网的搜索引擎是Spider的最早应用。例如搜索巨头Google公司，
6、就利用网络机器人程序来遍历Web站点，以创建并维护这些大型数据库。网络机器人还可以通过扫描Web站点的主页来得到这个站点的文件清单和层次机构。还可以扫描出中断的超链接和拼写错误等。3.2网络机器人的结构分析 Internet是建立在很多相关协议基础上的，而更复杂的协议又建立在系统层协议之上。Web就是建立在HTTP （ Hypertext Transfer Protocol ） 协议基础上，而HTTP又是建立在TCP/IP （ Transmission Control Protocol / Internet Protocol ） 协议之上，它同时也是一种Socket协议。所以网络机器人本质上是
7、一种基于Socket的网络程序。3.2.1如何解析HTML 因为Web中的信息都是建立在HTML协议之上的，所以网络机器人在检索网页时的第一个问题就是如何解析HTML。在解决如何解析之前，先来介绍下HTML中的几种数据。文本：除了脚本和标签之外的所有数据 注释：程序员留下的说明文字，对用户是不可见的 简单标签：由单个表示的HTML标签 开始标签和结束标签：用来控制所包含的HTML代码 我们在进行解析的时候不用关心所有的标签，只需要对其中几种重要的进行解析即可。超连接标签 超连接定义了WWW通过Internet链接文档的功能。他们的主要目的是使用户能够任意迁移到新的页面，这正是网络机器人最关心的
8、标签。图像映射标签 图像映射是另一种非常重要的标签。它可以让用户通过点击图片来迁移到新的页面中。表单标签 表单是Web页面中可以输入数据的单元。许多站点让用户填写数据然后通过点击按钮来提交内容，这就是表单的典型应用。表格标签 表格是HTML的构成部分，通常用来格式化存放、显示数据。我们在具体解析这些HTMl标签有两种方法：通过JavaTM中的Swing类来解析或者通过Bot包中的HTMLPage类来解析，本人在实际编程中采用后者。Bot包中的HTMLPage类用来从指定URL中读取数据并检索出有用的信息。下面给出该类几种重要的方法。HTMLPage构造函数 构造对象并指定用于通讯的HTTP对象
9、 Public HTMLPage（HTTP http） GetForms方法 获取最后一次调用Open方法检索到的表单清单 Public Vector getForms（） GetHTTP方法 获取发送给构造函数的HTTP对象 Public HTTP getHTTP（） GetImage方法 获取指定页面的图片清单 Public Vector getImage（） GetLinks方法 获取指定页面的连接清单 Public Vector getLinks（） Open方法 打开一个页面并读入该页面，若指定了回调对象则给出所有该对象数据 Public void open（String url,H
10、TMLEditorKit.ParserCallback a） 3.2.2 Spider程序结构 网络机器人必须从一个网页迁移到另一个网页，所以必须找到该页面上的超连接。程序首先解析网页的HTML代码，查找该页面内的超连接然后通过递归和非递归两种结构来实现Spider程序。递归结构 递归是在一个方法中调用自己本身的程序设计技术。虽然比较容易实现但耗费内存且不能使用多线程技术，故不适合大型项目。非递归结构 这种方法使用队列的数据结构，当Spider程序发现超连接后并不调用自己本身而是把超连接加入到等待队列中。当Spider程序扫描完当前页面后会根据制定的策略访问队列中的下一个超连接地址。虽然这里只
11、描述了一个队列，但在实际编程中用到了四个队列，他们每个队列都保存着同一处理状态的URL。等待队列 在这个队列中，URL等待被Spider程序处理。新发现的URL也被加入到这个队列中 处理队列 当Spider程序开始处理时，他们被送到这个队列中 错误队列 如果在解析网页时出错，URL将被送到这里。该队列中的URL不能被移入其他队列中 完成队列 如果解析网页没有出错，URL将被送到这里。该队列中的URL不能被移入其它队列中 在同一时间URL只能在一个队列中，我们把它称为URL的状态。以上的图表示了队列的变化过程，在这个过程中，当一个URL被加入到等待队列中时Spider程序就会开始运行。只要等待队
12、列中有一个网页或Spider程序正在处理一个网页，程序就会继续他的工作。当等待队列为空并且当前没有任何网页时，Spider程序就会停止它的工作。3.2.3如何构造Spider程序 在构造Spider程序之前我们先了解下程序的各个部分是如何共同工作的。以及如何对这个程序进行扩展。流程图如下所示：IspiderReportable接口 这是一个必须实现的接口，可以通过回调函数接受Spider所遇到的页面。接口定义了Spider向他的控制者发送的几个事件。通过提供对每个事件的处理程序，可以创建各种Spider程序。下面是他的接口声明：public interface IspiderReportabl
13、e public boolean foundInternalLink（String url）;public boolean foundExternalLink（String url）;public boolean foundOtherLink（String url）;public void processPage（HTTP page）;public void completePage（HTTP page,boolean error）;public boolean getRemoveQuery（）;public void SpiderComplete（）; 3.2.4如何提高程序性能 Inter
14、net中拥有海量的Web页面，如果开发出高效的Spider程序是非常重要的。下面就来介绍下几种提高性能的技术：Java的多线程技术 线程是通过程序的一条执行路线。多线程是一个程序同时运行多个任务的能力。它是在一个程序的内部进行分工合作。优化程序的通常方法是确定瓶颈并改进他。瓶颈是一个程序中最慢的部分，他限制了其他任务的运行。据个例子说明：一个Spider程序需要下载十个页面，要完成这一任务，程序必须向服务器发出请求然后接受这些网页。当程序等待响应的时候其他任务不能执行，这就影响了程序的效率。如果用多线程技术可以让这些网页的等待时间合在一起，不用互相影响，这就可以极大的改进程序性能。数据库技术
15、当Spider程序访问一个大型Web站点时，必须使用一种有效的方法来存储站点队列。这些队列管理Spider程序必须维护大型网页的列表。如果把他们放在内存中将会是性能下降，所以我们可以把他们放在数据库中减少系统资源的消耗。3.2.5网络机器人的代码分析 程序结构图如下：程序代码实现如下：package news; /* * 新闻搜索引擎 * 版本 1.0 */ import com.heaton.bot.HTTP;import com.heaton.bot.HTTPSocket;import com.heaton.bot.ISpiderReportable;import com.heaton.b
16、ot.IWorkloadStorable;import com.heaton.bot.Spider;import com.heaton.bot.SpiderInternalWorkload; /* * 构造一个Bot程序 */ public class Searcher implements ISpiderReportable public static void main（String args） throws Exception IWorkloadStorable wl = new SpiderInternalWorkload（）;Searcher _searcher = new Sear
17、cher（）;Spider _spider = new Spider（_searcher, http:/127.0.0.1/news.htm, new HTTPSocket（）, 100, wl）; _spider.setMaxBody（100）;_spider.start（）; / 发现内部连接时调用，url表示程序发现的URL，若返回true则加入作业中，否则不加入。public boolean foundInternalLink（String url） return false; / 发现外部连接时调用，url表示程序所发现的URL，若返回true则把加入作业中，否则不加入。public
18、 boolean foundExternalLink（String url） / 当发现其他连接时调用这个方法。其他连接指的是非HTML网页，可能是E-mail或者FTP public boolean foundOtherLink（String url） / 用于处理网页，这是Spider程序要完成的实际工作。public void processPage（HTTP http） System.out.println（扫描网页： + http.getURL（）;new HTMLParse（http）.start（）; / 用来请求一个被处理的网页。public void completePage
19、（HTTP http, boolean error） / 由Spider程序调用以确定查询字符串是否应删除。如果队列中的字符串应当删除，方法返回真。public boolean getRemoveQuery（） return true; / 当Spider程序没有剩余的工作时调用这个方法。public void spiderComplete（） 3.3小节 在本章中，首先介绍了网络机器人的基本概念，然后具体分析了Spider程序的结构和功能。在最后还结合具体代码进行了详细说明。本人在编程中运用了JavaTM技术，主要涉及到了net和io两个包。此外还用了第三方开发包Bot（由Jeff Heat
20、on提供的开发包）。第四章 基于lucene的索引与搜索 4.1什么是Lucene全文检索 Lucene是Jakarta Apache的开源项目。它是一个用Java写的全文索引引擎工具包，可以方便的嵌入到各种应用中实现针对应用的全文索引/检索功能。4.2 Lucene的原理分析 4.2.1全文检索的实现机制 Lucene的API接口设计的比较通用，输入输出结构都很像数据库的表=记录=字段，所以很多传统的应用的文件、数据库等都可以比较方便的映射到Lucene的存储结构和接口中。总体上看：可以先把Lucene当成一个支持全文索引的数据库系统。索引数据源：doc（field1,field2.） do
21、c（field1,field2.） indexer / _ | Lucene Index| - searcher 结果输出：Hits（doc（field1,field2） doc（field1.） Document：一个需要进行索引的“单元”，一个Document由多个字段组成 Field：字段 Hits：查询结果集，由匹配的Document组成 4.2.2 Lucene的索引效率 通常书籍后面常常附关键词索引表（比如：北京：12, 34页，上海：3,77页），它能够帮助读者比较快地找到相关内容的页码。而数据库索引能够大大提高查询的速度原理也是一样，想像一下通过书后面的索引查找的速度要比一页一
22、页地翻内容高多少倍而索引之所以效率高，另外一个原因是它是排好序的。对于检索系统来说核心是一个排序问题。由于数据库索引不是为全文索引设计的，因此，使用like %keyword%时，数据库索引是不起作用的，在使用like查询时，搜索过程又变成类似于一页页翻书的遍历过程了，所以对于含有模糊查询的数据库服务来说，LIKE对性能的危害是极大的。如果是需要对多个关键词进行模糊匹配：like%keyword1% and like %keyword2% .其效率也就可想而知了。所以建立一个高效检索系统的关键是建立一个类似于科技索引一样的反向索引机制，将数据源（比如多篇文章）排序顺序存储的同时，有另外一个排好
23、序的关键词列表，用于存储关键词=文章映射关系，利用这样的映射关系索引：关键词=出现关键词的文章编号，出现次数（甚至包括位置：起始偏移量，结束偏移量），出现频率，检索过程就是把模糊查询变成多个可以利用索引的精确查询的逻辑组合的过程。从而大大提高了多关键词查询的效率，所以，全文检索问题归结到最后是一个排序问题。由此可以看出模糊查询相对数据库的精确查询是一个非常不确定的问题，这也是大部分数据库对全文检索支持有限的原因。Lucene最核心的特征是通过特殊的索引结构实现了传统数据库不擅长的全文索引机制，并提供了扩展接口，以方便针对不同应用的定制。可以通过一下表格对比一下数据库的模糊查询： Lucene全
24、文索引引擎 数据库 索引 将数据源中的数据都通过全文索引一一建立反向索引 对于LIKE查询来说，数据传统的索引是根本用不上的。数据需要逐个便利记录进行GREP式的模糊匹配，比有索引的搜索速度要有多个数量级的下降。匹配效果 通过词元（term）进行匹配，通过语言分析接口的实现，可以实现对中文等非英语的支持。使用：like %net% 会把netherlands也匹配出来， 多个关键词的模糊匹配：使用like %com%net%：就不能匹配词序颠倒的 匹配度 有匹配度算法，将匹配程度（相似度）比较高的结果排在前面。没有匹配程度的控制：比如有记录中net出现5词和出现1次的，结果是一样的。结果输出 通过特别的算法，将最匹配度最高的头100条结果输出，结果集是缓冲式的小批量读取的。返回所
