（计算机应用技术专业论文）基于lucene的搜索引擎研究与实现.pdf

武汉理工大学硕士学位论文 摘要 随着信息技术的不断发展，互联网技术也得到了迅猛发展，而在互联网上大 家每天用的频率最高的就是搜索引擎，人们已经把它当作日常学习、工作、休闲 不可缺少的一个工具。大家都知道用搜索引擎可以快速的找到自己想找的资料 或信息，那么到底什么是搜索引擎呢? 网络上通常说的搜索引擎指的是收集了 因特网上几十亿到上百亿个网页，并对网页中的每一个词( 即关键词) 进行索引， 建立索引数据库的全文搜索引擎。当用户查找某个关键词的时候，所有在页面 内容中包含了该关键词的网页都会作为搜索结果被搜出来。在经过复杂的算法 进行排序后，这些结果将按照与搜索关键词的相关度高低，依次排列，呈现给用 户。 本文首先介绍了搜索引擎的发展现状，在上世纪九十年代以后以互联网为 基础的信息化进程中，面对浩瀚的网络信息资源，人们寻找自己需要的信息变 得越来越困难，大多数人很大程度上是依赖搜索引擎来帮助自己获得有用信息， 因此搜索引擎技术作为最典型的w e b 信息获取技术，其发展水平高低直接影响 人们获取信息的质量。接着介绍了搜索引擎的特点和分类，并对搜索引擎的原 理及网络机器人等技术进行了探讨，对g o o g l e 主流搜索引擎系统结构进行了分 析研究。在此基础上对开源代码项目l u c e n e 的历史，应用，特点，系统结构， l u c e n e 索引文件格式进行了论述。然后对搜索引擎中的关键技术进行了研究。 由于w e b 站点上的页面频繁更新，随着时间的推移，将会有许多页面过时或者 不存在，通过对网络机器人页面抓取过程进行分析，提出了递增式的网络机器 人页面变化模型。最后对中文分词的常见算法及中文分词岐义和末登录词进行 了相关分析论述。 关键字：搜索引擎，l e c e n e ，网络机器人，中文分词 武汉理工大学硕士学位论文 a b s t r a c t a 1 0 n gw i t ht h ei n f o r m a t i o nt e c h n o l o g yu n c e a s i n gd e v e l o p m e n t ，t h ei n t e m e t t e c h n o l o g yi s a l s od e v e l o p i n gs w i f t l y , b u tt h em o s th i 曲f r e q u e n c yt o o lw h i c h e v e r y b o d yn s e se v e r yd a yo nt h ei n t e m e ti s t h es e a r c he n g i n e ，t h ep e o p l ea l r e a d y i r e a t e di ta sa ne s s e n f i a lt o o lf o rs t u d y , w o r k , t h el e i s u r ea c t i v i t i e s e v e r y b o d yk n o w s w i t ht h es e a r c he n g i n eo n em a yg e tt h em a t e r i a lo ri n f o r m a t i o nt h a th ew a n t st of i n d , a n dt h e nw h a ti st h es e a r c he n g i n e ? o e n a r a l l yw er e f e r r e dt h es e a r c he n g i n eo nt h e i n t e r n e ta si th a sc o l l e c t e df r o ms e v e r a lb i l l i o n st o1 0b i l l i o n sw e bp a g e s a n di n d e x e a c hw o r d ( n a m e l yk e yw o r d ) o ft h ew h o l ew e b p a g e s ，e s t a b f i s h e dt h ef u l l - t e x ts e a r c h e n g i n co ft h ei n d e xd a t a b a s e a f t e rt h en s c l e n t e r i n gt h ek e yw o r d ，a l lt h ep a g e s c o n t a i n i n gt h ek e yw o r d sw o u l db ef i n do u ta st h es e a r c hr e s u l t s a f t e rs o r t i n g a c c o r d i n gt oc o m p l e xa l g o r i t h m ，t h e s er e s u l t sw i l lb ep r e s e n t e dt ot h eu s e r sb a s e do n t h ec o r r e l a t i o nd e g r e et ot h ek e yw o r d s f i r s to fa l l , t h et h e s i si n t r o d u c e sp r e s e n ts i t u a t i o no ft h ed e v e l o p m e n to fs e a r c h e n g i n e a f t e r1 9 9 0 s 。w h e nf a c i n gv a s tn e t w o r ki n f o r m a t i o nr e s o u r c e s ，i tb e c o m e m o r ea n dm o r ed i 街c u l tf o rp e o p l et os e e ki n f o r m a t i o nt h e yn e e di nt h ep r o c e s so f i n f o r m a t i o n i z a t i o nb a s e do i lt h ei n t e r n e t n 地m a j o r i t i e sw i l lr e l yo nt h es e a r c he n g i n e t oh e l d 也e m s e l v e st oo b t a i nt h eu s e f u li n f o r m a t i o nt oag r e a te x t e n d t h e r e f o r e , t h e d e v e l o p m e n to f t h es e a r c he n g i n et e c h n o l o g i e sa sat y p i c a lw e bi n f o r m a t i o na c c e s s i n g t e c h n o l o g yw i l lh a v ed i r e c t l yi m p a c to nt h eq u a l i t yo fp e o p l ea c c e s st 0i n f o r m a t i o n i nt h en e x tp l a c e ，w ei n l r o d u e e dt h es e a r c he n g i n ec h a r a c t e r i s t i c sa n dc l a s s i f i c a t i o n 。 h a v ead i s c u s s i o no ns e a r c he n g i n ep r i n c i p l e sa n dr o b o t ，a n a l y z ea n ds t u d yo nt h e a r c h i t e c t u r eo f t h eg o o g l es e a r c he n g i n e i nt h i sf o u n d a t i o n , w eh a v ee l a b o r a t e do nt h e o p e ns o u r c ec o d ep r o j e c tl u c e n e ，i t sh i s t o r y , a p p l i c a t i o n , c h a r a c t e r i s t i c s ，s y s t e m s t r u c t u r e t h el u c e n ei n d e xf o r m a t t h e n , w eh a v es t u d yo ns e v e r a lk e yt e c h n o l o g i 船 b e c a u s ew e bp a g e sf r e q u e n t l yu p d a t e d , a l o n gw i t ht i m ep a s s e d , s o m em a n yp a g e s w o u l db eo b s o l e t eo rd on o te x i s t t h r o u g ht h ea n a l y s i so np r o c e s so ft h er o b o t s f e t c h i n gw e b p a g e s ，w ep r o p o s e dt h er o b o t si n c r e m e n tp a g ec h a n g em o d e l f i n a l l y , w eh a v ed i s c u s s e do nt h ec o m m o na l g o r i t h m so nc h i n e s ew o r ds e g m e n t a t i o n t h e a m b i g u i t yo f c h i n e s ew b r ds e g m e n t a t i o na n du n r e g i s t e r e dw o r d s k e y w o r d s ：s e a r c he n g i n e ，l u c e n e ，r o b o t , c h i n e s ew o r ds e g m e n t a t i o n 武汉理工大学硕士学位论文 1 1 课题背景 第1 章绪论 上世纪八十年代以来，全球信息量每隔2 0 个月就增加近一倍。个不大的 企业每天要产生i o o m b 以上来自各方面的营业数据。面对极度膨胀的信息量， 人们受到“信息爆炸”、“混沌信息空间( i n f o r m a t i o nc h a o t i cs p a c e ) ”和“数 据过剩( d a t ag l u t ) “的巨大压力。信息爆炸带来了剧烈的市场变化。展现在 人们面前的已不是局限于本部门。本单位和本行业的庞大数据库，而是浩瀚无 垠的信息海洋。因此，如何从海量信息中得到有用信息是大家共同关注得热点 问题。 。 9 0 年代以后互联网的兴起，一方面使人们更加方便的获得信息，另一方面 也更进一步加快了信息量增长。起初，人们主要通过浏览网页的方式来咨询所 需信息，由于互连网中网页数量急剧膨涨，用这种方式来寻找自己所需的信息 变得越来越困难，大多数的人很大程度上依赖于搜索引擎来帮助自己获得有用 信息，因此搜索引擎技术作为最典型的w e b 信息获取技术，其发展直接影响人 们获取信息的质量。 1 2 搜索引擎的发展现状 面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口， 所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成 为除了电子邮件以外最多入使用的网上服务。 搜索引擎技术伴随着w w w 的发展是引入注目的。搜索引擎大约经历了三代 的更新发展： 第一代搜索引擎出现于1 9 9 4 年。这类搜索引擎一般都索引少于l ，0 0 0 ，0 0 0 个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要 等待1 0 秒甚至更长的时间。在实现技术上也基本沿用较为成熟的i r ( i n f o r m a t i o nr e t r i e v a l ) 、网络、数据库等技术，相当于利用一些已有技术 武汉理工大学硕士学位论文 实现的个w 啊上的应用。在1 9 9 4 年3 月到4 月，网络爬虫w o r l d w e b w o r m ( w w w w ) 平均每天承受大约1 5 0 0 次查询。 大约在1 9 9 6 年出现的第二代搜索引擎系统大多采用分布式方案( 多个微型 计算机协同工作) 来提高数据规模、响应速度和用户数量，它们一般都保持一 个大约5 0 ，0 0 0 ，0 0 0 网页的索引数据库，每天能够响应1 0 ，0 0 0 ，0 0 0 次用户 检索请求。1 9 9 7 年1 1 月，当时最先进的几个搜索引擎号称能建立从2 ，0 0 0 ， 0 0 0 到1 0 0 ，0 0 0 ，0 0 0 的网页索引。a l t a v i s t a 搜索引擎声称他们每天大概要承 受2 0 ，0 0 0 ，0 0 0 次查询”。 2 0 0 3 年搜索引擎2 0 0 3 年大会上，按照g o o g l e 公司总裁l a r r yp a g e 的演讲， g o o g l e 正在用1 5 ，0 0 0 台运行l i n u x 系统的个人电脑在搜集w e b 上的网页，而且 以每天6 0 台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。 每台微机运行多个爬虫程序搜集网页的峰值速度是每秒1 0 0 个网页，平均速度 是每秒4 8 5 个网页，一天可以搜集超过8 ，0 0 0 ，0 0 0 网页跚 搜索引擎一词在国内外因特网领域被广泛使用，然而他的含义却不尽相同。 在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序 收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的 全文检索。著名的因特网搜索引擎包括f i r s ts e a r c h 、g o o g l e 、h o t b o t 等。在 中国，搜索引擎通常指基于网站目录的搜索服务或是特定网站的搜索服务，本 人这里研究的是基于因特网的搜索技术。 1 3 本文各章内容安排 本文后续章节组织如下：第二章介绍了搜索引擎基本定义，搜索引擎的特点 及分类；搜索引擎的基本原理及性能指标和主流搜索引擎的介绍；。第三章介绍 了开源项目l u c e n e 的基本概念；它的应用和特点及优势；对l u c e n e 的系统结 构和索引文件格式进行了深入分析。第四章分析搜索引擎实现的关键技术，对 网络机器人进行了优化；分析了主流排序算法；对中文分词进行了比较全面的 论述。第五章对该研究工作进行了总结，提出了对进步研究工作的设想以及 本项目的搜索引擎的未来发展展望。 2 武汉理工大学硕士学位论文 第2 章搜索引擎概述 2 1 搜索引擎定义 搜索引擎，s e a r c he n g i n e s ，又称搜索机，w e b 搜索器，是伴随w w w 网络出现的 检索网上信息资源的新工具实质上是一种网页网址检索系统，有的提供分类和 关键词检索途径，有的仅提供关键词检索途径它根据检索规则和从其他信息服 务器上得到数据并对数据进行加工处理，自动建立索引，并通过检索接口为用户 提供信息查询服务，能够自动对w w w 资源建立索引或进行主题分类，并通过查询 语法为用户返回匹配资源的系统搜索引擎主要是由c r a w l e r ，r o b o t ，w o r m 等计 算机软件程序自动在因特网上漫游，不断搜集各类新网址及网页，形成数以千万 甚至上亿条记录的数据库它是通过采集标引众多网络站点来提供全局性网络 资源控制与检索机制，将全球w w w 网络中所有信息资源作一完整的集合，整理和 分类，方便用户查找所需信息的网络检索软件具有检索面广，信息量大，信息更 新速度快等特点。 2 2 搜索引擎的特点 从出现第一个搜索引擎至今，搜索引擎技术己获得了飞速的发展，现在的 搜索引擎功能越来越强大，提供的服务也越来越全面，他们的目标不仅仅是提 供单纯的查询功能，而是把自己发展成为用户首选的i n t e r n e t 入口站点。目前 的搜索引擎主要有以下几个主要特点嘲： 1 多样化和个性化的服务 现在绝大多数搜索引擎都提供多样化的服务，以吸引更多的用户，商业搜 索引擎尤其注重这一点。以y a h o o ! 为例，用户可以从它的首页中查看新闻、金 融证券、大气预报等信息，还可以进行网上购物、拍卖、或者使用e m a i l 等服 务。可以说多样化和个性化的服务既满足了用户更多的需求，也为搜索引擎网 站带来了更多的利润。 2 强大的查询功能 武汉理工大学硕士学位论文 与最早的搜索引擎相比，现在的搜索引擎在查询功能方面已有了很大的改 进。除了简单的a n d ，o r 和n o t 逻辑外，不少搜索引擎还支持相似查询，例如 a l t a v i s t a ，l y c o s 等支持短语查询，a l t a v i s t a 的高级搜索功能支持n e a r 逻辑 等。 3 目录和基于r o b o t 的搜索引擎相互结合 目录和基于r o b o t 的搜索引擎都具有自己的特点，在当前的技术条件下， 最好的选择是将两种技术进行结合，同时为用户提供这两种类型的服务。以 y a h o o ! 为例，用户既可以进行分类网站查询也可以进行全部网页查询，这两种 不同的查询方式很好的满足了不同用户的需求。 虽然搜索引擎已经为用户提供了快捷和便利的服务，但是也存在着许多问 题和不足。特别是在系统的稳定性、速度、易用性和返回的信息量及相关度方 面还与人们的要求存在着一定的差距，搜索引擎技术的发展任重而道远。 2 3 搜索引擎的分类 按照信息搜集方法和服务提供方式的不同，目前i n t e r n e t 上的搜索引擎大 致可分为基于r o b o t 的、基于目录( d i r e c t o r y ) 的、和基于m e t a 的三大类型。 2 3 1 基于网络机器人r o b o t 的搜索引擎 基于r o b o t 的搜索引擎利用一个称为r o b o t ( 也叫做r o b o t ，w e b c r a w l e r 或 w e bw a n d e r e r ) 的程序自动访问w e b 站点，提取站点上的网页，并根据网页中的 链接进一步提取其它网页，或转移到其它站点上嘲。r o b o t 搜集的网页被加入到 搜索引擎的数据库中，供用户查询使用。i n t e r n e t 上最早出现的搜索引擎就是 利用r o b o t 来建立数据库，“搜索引擎”这个词的原义也只是指这种狭义上的基 于r o b o t 的搜索引擎。基于r o b o t 的搜索引擎由三个主要部分构成：r o b o t ，i n d e x 和搜索软件。r o b o t 从一个事先制定好的u r l s 列表出发，这个列表中的u r l s 通 常是从以往访问记录中提取出来的，特别是一些热门站点和“w h a t s n e w ”网页， 从u s e n e t 等地方检索得到的u r l s 也常被用作起始u r l s ，此外，很多搜索引擎 还接受用户提交的u r l s ，这些u r l s 也会被安排在列表中供r o b o t 访问。r o b o t 访问了一个网页后，会对它进行分析，提取出新的u r l s 将之加入到访问列表中， 如此递归地访问整个w e b 。 4 武汉理工大学硕士学位论文 r o b o t 作为一个程序，可以用c ，p e r l ，j a v a 等语言来编写，可以运行在 u n i x ，s o l a r i s ，w i n d o w s ，n t ，0 s 2 和m a c 等平台上。r o b o t 设计是否合理将直 接影响它访问w e b 的效率，影响搜索数据库的质量，另外，在设计r o b o t 时还 必须考虑它对网络和被访问站点的影响，因为r o b o t 一般都运行在速度快、带 宽高的主机上，如果它快速访问一个速度比较慢的目标站点，就有可能会导致 该站点出现阻塞甚至当机。r o b o t 还应遵守一些协议，以便被访问站点的管理员 能够确定哪些内容能被访问，哪些不能。 i n d e x 是一个庞大的数据库，r o b o t 提取的网页将被放入到i n d e x 中以便建 立索引，不同的搜索引擎会采取不同方式来建立索引，有的对整个h t 札文件的 所有单词都建立索引，有的只分析h t m l 文件的标题或前几段内容，还有的能处 理h t m l 文件中的m e t a 标记或其它不可见的特殊标记。 基于r o b o t 的搜索引擎一般要定期访问大多数以前搜集的网页，刷新i n d e x ， 以反映出网页的更新情况，去除一些死链接，网页的部分内容和变化情况将会 反映到用户查询的结果中，这是基于r o b o t 的搜索引擎的一个重要特征。 i n d e x 在建立索引时，一般会给网页中每个关键词赋予一个等级值，表示 该网页与关键词之间的符合程度。当用户查询一个关键词时，搜索软件将搜索 i n d e x ，找出所有与关键词相符合的网页，有时候这些网页可能有成千上万， 等级值的用途就是作为一种排序的依据，搜索软件将按照等级值从高到低的顺 序把搜索结果送回到用户的浏览器中。 这类搜索引擎因为依靠程序搜集数据，所以其数据库相当庞大，搜索的结 果查全率较高，但查准率较低。例如著名的搜索引擎g o o g l e ，b a i d u ，a l t a v i s t a ， i n f o s e e k 等。 2 3 2 基于目录d ir e c t o r y 的搜索引擎 基于d i r e c t o r y 的搜索引擎由人工发现、抓取、辨别网上信息，然后编目 人员按照某种分类法，建立主题树分层目录，将采集、筛选后的信息分门别类 的放入各大类或子类b 面。目录的数据库是依靠专职编辑或志愿人员建立起来 的，这些编辑人员在访问了某个w e b 站点后撰写一段对该站点的描述，并根据 站点的内容和性质将其归为一个预先分好的类别，把站点的u r l 和描述放在这 个类别中，当用户查询某个关键词时，搜索软件只在这些描述中进行搜索。很 多目录也接受用户提交的网站和描述，当目录的编辑人员认可该网站及描述后， 武汉理工大学硕士学位论文 就会将之添加到合适的类别中。 目录的结构为树形结构，首页提供了最基本的几个大类的入口，用户可以 一级一级地向下访问，直至找到自己感兴趣的类别，另外，用户也可以利用目 录提供的搜索功能直接查找个关键词，不过，由于目录只在保存的对站点的 描述中进行搜索，因此站点本身的动态变化不会反映到搜索结果中来，这也是 目录与基于r o b o t 的搜索引擎之间的一大区别。 这类搜索引擎所收录的网络资源经过了专业人员的鉴别、选择和组织，所 以信息准确，导航质量高，但是由于采用了人工方式，成木较高，维护比较困 难。现在很多搜索站点都同时提供有目录和基于r o b o t 的搜索服务，以便尽可 能地为用户提供全而的查询结果。例如著名的搜索引擎y a h o o ! ，o r i e n d i r e c t o r y 等。 2 3 3 基于元m e t a 的搜索引擎 m e t a 搜索引擎也叫做m u l t i p l es e a r c he n g i n e ，它的特点是本身并没有存 放网页信息的数据库，当用户查询一个关键词时，它把用户的查询请求转换成 其它搜索引擎能够接受的命令格式，并行地访问数个搜索引擎来查询这个关键 词，将结果进行相关处理，以整体统一的格式反馈给用户。 严格意义上来讲，m e t a 搜索引擎只能算是一种用户代理，而不是真正的搜 索引擎。多数m e t a 搜索引擎在处理其它的搜索引擎返回结果时，只提取出每个 搜索引擎的结果中前面1 0 一5 0 条，并将这些条目合并在一起返回给用户，因此 最后结果的数量可能会远少于直接在一个搜索引擎上进行查找所得到的数量， 这就是为什么很多i n t e r n e t 用户都喜欢使用m e t a 搜索引擎来查找信息的原因。 m e t a 搜索引擎实现起来比较简单，但是它也有一定的局限性，例如多数m e t a 搜索引擎都只能访问少数几个搜索引擎，并且通常不支持这些搜索引擎的高级 搜索功能，在处理逻辑查询时也常常会出现错误。 主要的元搜索引擎有a l l - i n o n e ，b e s ts e a r c h ，w 3 s e a r e he n g i n e s ，m a m m a , a v e n u e s e a r c h , d o g p i l e ，k w i k s e e k , f i n d s p o t , b y t e s e a r c h , w e b f e r r e t , b l u e s q u i r r e l w e b s c c k c r 等”1 m c t a e r a w l e r ( h t t p ：w w w m e t a e r a w l e r e o m ) 能同时调用6 个搜索 引擎；s a v v y s e a r c h ( h t t p ：w w w s a v v y s e a r c h t o m ) 可有选择地调用2 1 个独立的搜索 引擎，检索w e b ，u s e n e t 新闻组，软件，参考工具，技术报告等信息，每次最多并行 检索5 个搜索引擎的数据库p r o f u s i o n ( h t i p ：伽唧vp r o f u s i o n c o m ) 最多同时调用 6 武汉理_ 大学硕士学位论文 9 个独立的搜索引擎，调用方式有全部调用，系统自动选择最好的3 个，系统自动 选择最快的3 个，用户从中选取任意个搜索引擎最新出现的桌面型离线式搜索 引擎如w 曲c o m p 船s ，w e b s e e k e r , w e b f e r r e t ，e c h o s e a r e h ，c o p e m i c 9 8 等也是元搜索 引擎 2 4 搜索引擎基本工作原理 现今主流的搜索引擎是上面讨论过的基于r o b o t 的搜索引擎嘲，其构成一般 由网络机器人程序，网页过滤分析器，索引器，查询器、网页数据库，索引数 据库，用户接口等部分组成。如下图2 4 所示： 图2 - 1 搜索引擎结构图 7 武汉理工大学硕士学位论文 2 4 1 网络机器人 2 4 i 1 什么是网络机器人 网络机器人r o b o t 又称为s p i d e r 程序，是一种专业的b o t 程序。用于查找 大量的w e b 页面。它从一个简单的w e b 页面上开始执行，然后通过其超链接在 访问其他页面，如此反复理论上可以扫描互联网上的所有页面。 基于因特网的搜索引擎是r o b o t 的最早应用。例如搜索巨头g o o g l e 公司， 就利用网络机器人程序来遍历w e b 站点，以创建并维护这些大型数据库。 网络机器人还可以通过扫描w e b 站点的主页来得到这个站点的文件清单和 层次机构。还可以扫描出中断的超链接和拼写错误等。 2 4 1 2 网络机器人的结构分析 i n t e r n e t 是建立在很多相关协议基础上的，而更复杂的协议又建立在系统 层协议之上。w e b 就是建立在h t t p ( h y p e r t e x tt r a n s f e rp r o t o c 0 1 ) 协议基 础上，而h t t p 又是建立在t c p i p ( t r a n s m i s s i o nc o n t r o lp r o t o c o l i n t e r n e t p r o t o c 0 1 ) 协议之上，它同时也是一种s o c k e t 协议。所以网络机器人本质上 是一种基于s o c k e t 的网络程序。 2 4 1 3 如何解析h t n l 因为w e b 中的信息都是建立在h t m l 协议之上的，所以网络机器人在检索网 页时的第一个问题就是如何解析h t m l 。在解决如何解析之前，先来介绍下h t m l 中的几种数据。 ( 1 ) 文本 除了脚本和标签之外的所有数据注释：程序员留下的说明文字，对用户是 不可见的简单标签：由单个表示的h t 儿标签开始标签和结束标签：用来控制 所包含的h t 舰代码。 我们在进行解析的时候不用关心所有的标签，只需要对其中几种重要的进 行解析即可。 ( 2 ) 超连接标签 超连接定义了w w w 通过i n t e r n e t 链接文档的功能。他们的主要目的是使用 户能够任意迁移到新的页面，这正是网络机器人最关心的标签。 ( 3 ) 图像映射标签 武汉理工大学硕士学位论文 图像映射是另一种非常重要的标签。它可以让用户通过点击图片来迁移到 新的页面中。 ( 4 ) 表单标签 表单是w e b 页面中可以输入数据的单元。许多站点让用户填写数据然后通 过点击按钮来提交内容，这就是表单的典型应用。 ( 5 ) 表格标签 表格是h t m l 的构成部分，通常用来格式化存放、显示数据。 我们在具体解析这些h t m l 标签有两种方法：通过j a v a 中的s w i n g 类来解 析或者通过b o t 包中的h t m l p a g e 类来解析 b o t 包中的h t m l p a g e 类用来从指定u r l 中读取数据并检索出有用的信息。 下面给出该类几种重要的方法。 h t m l p a g e 构造函数构造对象并指定用于通讯的h t t p 对象 p u b li ch t m l p a g e ( h t t ph t t p )g e t f o r m s 方法获取最后一次调用o p e n 方 法检索到的表单清单。 p u b l i cv e c t o rg e t f o r m s0 g e t h t t p 方法获取发送给构造函数的h t t p 对 象。 p u b l i ch t t pg e t h t t p ( ) g e t i m a g e 方法获取指定页面的图片清单。 p u b l i cv e c t o rg e t l m a g e0g e t l i n k s 方法获取指定页面的连接清单。 p u b l i cv e c t o rg e t l i n k s0o p e n 方法打开一个页面并读入该页面，若指 定了回调对象则给出所有该对象数据。 p u b l i cv o i do p e n ( s t r i n gu r l ，h t m l e d i t o r k i t p a r s e r c a l l b a c ka ) 2 4 1 4r o b o t 程序结构 网络机器人必须从一个网页迁移到另一个网页，所以必须找到该页面上的 超连接。程序首先解析网页的h t 札代码，查找该页面内的超连接然后通过递归 和非递归两种结构来实现r o b o t 程序。 ( 1 ) 递归结构 递归是在一个方法中调用自己本身的程序设计技术。虽然比较容易实现但 耗费内存且不能使用多线程技术，放不适合大型项目。 ( 2 ) 非递归结构 这种方法使用队列的数据结构，当r o b o t 程序发现超连接后并不调用自己 9 武汉理工大学硕士学位论文 本身而是把超连接加入到等待队列中。当r o b o t 程序扫描完当前页面后会根据 制定的策略访问队列中的下一个超连接地址。 虽然这里只描述了一个队列，但在实际编程中用到了三个队列，他们每个 队列都保存着同一处理状态的u r l 。? 等待队列在这个队列中，u r l 等待被r o b o t 程序处理。新发现的u r l 也 被加入到这个队列中处理队列当r o b o t 程序开始处理时，他们被送到这个队 列中。 错误队列如果在解析网页时出错，u r l 将被送到这里。该队列中的u r l 不能被移入其他队列中。 完成队列如果解析网页没有出错，u r l 将被送到这里。该队列中的u r l 不能被移入其它队列中。 在同一时间u p d 只能在一个队列中，我们把它称为u r l 的状态。 在这个过程中，当一个u r l 被加入到等待队列中时r o b o t 程序就会开始运 行。只要等待队列中有一个网页或r o b o t 程序正在处理一个网页，程序就会继 续它的工作。当等待队列为空并且当前没有任何网页时，r o b o t 程序就会停止它 的工作。 2 4 1 5 如何构造r o b o t 程序 在构造r o b o t 程序之前我们先了解下程序的各个部分是如何共同工作的。 以及如何对这个程序进行扩展。 i r o b o t r e p o r t a b l e 接口 这是一个必须实现的接口，可以通过回调函数接受r o b o t 所遇到的页面。 接口定义了r o b o t 向他的控制者发送的几个事件。通过提供对每个事件的处理 程序，可以创建各种r o b o t 程序。下面是他的接口声明： p u b li ci n t e r f a c ei r o b o t r e p o r t a b l e p u b li cb o o l e a nf o u n d i n t e r n a l l i n k ( s t r i n gu r l ) ： p u b l i cb o o l e a nf o u n d e x t e r n a l l i n k ( s t r i n gu r l ) ： p u b l i cb o o l e a nf o u n d o t h e r l i n k ( s t r i n gu r l ) ： p u b l i cv o i dp r o c e s s p a g e ( m 盯pp a g e ) ： p u b li cv o i dc o m p l e t e p a g e ( r r t pp a g e ，b o o l e a ne r r o r ) ： p u b l i cb o o l e a ng e t r e m o v e o u e r y ( ) ： p u b l i cv o i dr o b o t c o m p l e t e 0 ： l o 武汉理工大学硕士学位论文 2 4 1 6 网络机器人的代码分析 i n t e r n e t 中拥有海量的w e b 页面，如果开发出高效的r o b o t 程序是非常重 要的。下面就来介绍下几种提高性能的技术： j a v a 的多线程技术 线程是通过程序的一条执行路线。多线程是一个程序同时运行多个任务的 能力。它是在一个程序的内部进行分工合作。 优化程序的通常方法是确定瓶颈并改进它。瓶颈是一个程序中最慢的部分， 他限制了其他任务的运行。据个例子说明：一个r o b o t 程序需要下载十个页面， 要完成这一任务，程序必须向服务器发出请求然后接受这些网页。当程序等待 响应的时候其他任务不能执行，这就影响了程序的效率。如果用多线程技术可 以让这些网页的等待时间合在一起，不用互相影响，这就可以极大的改进程序 性能。 数据库技术 当r o b o t 程序访问一个大型w e b 站点时，必须使用一种有效的方法来存储 站点队列。这些队列管理r o b o t 程序必须维护大型网页的列表。如果把他们放 在内存中将会是性能下降，所以我们可以把他们放在数据库中减少系统资源的 消耗。 程序代码实现如下： 木丰奉r o b o t 唪版本1 0 木 i m p o r tc o m h e a t o n b o t h t t p ： i m p o r tc o m h e a t o n b o t h t t p s o c k e t ： i m p o r tc o m h e a t o n b o t i r o b o t r e p o r t a b l e ： i m p o r tc o m h e a t o n b o t i w o r k l o a d s t o r a b l e ： i m p o r tc o m h e a t o n b o t r o b o t ： i m p o r to o m h e a t o n b o t r o b o t i n t e r n a l w 0 r k l o a d ： 料 构造一个b o t 程序 p u b l i cc l a s ss e a r c h e ri m p l e m e n t si r o b o t r e p o r t a b l e p u b l i cs t a t i cv o i dm a i n ( s t r i n g a r g s ) t h r o w se x c e p t i o n ( i w o r k l o a d s t o r a b l ew l = n e wr o b o t i n t e r n a l w o r k l o a d ( ) 1 1 武汉理工大学硕士学位论文 s e a r c h e r s e a r c h e r5n e ws e a r c h e r0 ： r o b o tr o b o t = n e wr o b o t ( _ s e a r c h e r ，h t t p ：，n e wh t t p s o c k e t0 ， 1 0 0 。w 1 ) ：r o b o t s e t m a x b o d y ( 1 0 0 ) ： 一r o b o t s t a r t0 ； 发现内部连接时调用，u r l 表示程序发现的u r l 若返回t r u e 则加入作业中，否则不加入。 p u b l i cb o o l e a nf o u n d i n t e r n a l l i n k ( s t r i n gu r l ) r e t u r nf a l s e ： 发现外部连接时调用，u r l 表示程序所发现 的u r l ，若返回t r u e 则把加入作业中，否则不加入。 p u b l i cb o o l e a nf o u n d e x t e r n a l l i n k ( s t r i n gu r l ) ( r e t u r nf a l s e ： 当发现其他连接时调用这个方法。其他连接指的 是非h t m l 网页，可能是e - m a i l 或者f t p p u b li cb o o l e a nf o u n d o t h e r l i n k ( s t r i n gu r l ) r e t u r nf a l s e ： 用于处理网页，这是r o b o t 程序要完成的工作。 p u b l i cv o i dp r o c e s s p a g e ( h t t ph t t p ) ( s y s t e mo u t p r i n t l n ( ”扫描网页：+ h t t p g e t u r l ( ) ) ； n e wh t m l p a r s e ( h t t p ) s t a r t ( ) ：) 用来请求一个被处理的网 页。 p u b li cv o i dc o m p l e t e p a g e ( m ph t t p ，b o o l e a ne r r o r ) ) 由r o b o t 程序调 确定查询字符串是否应删除 如果队列中的字符串应当删除，方法返回真。 p u b l i cb o o l e a ng e t r e m o v e q u e r y ( ) r e t u r nt r u e ： 当r o b o t 程序没有剩余的工作时调用这个方法。 p u b l i cv o i dr o b o t c o m p l e t e0 ) 武汉理工大学硕士学位论文 2 4 2 索引与搜索 网络机器人将遍历得到的页面存放在网页数据库中，如果通过s q l 直接查 询信息速度将会难以忍受。为了提高检索效率，需要建立索引，按照倒排文件 的格式存放。如果索引不及时更新的话，用户用搜索引擎也不能检索到。 用户输入搜索条件后搜索程序将通过索引数据库进行检索，然后把符合查 询要求的数据库按照一定的策略进行分级排列并且返回给用户。 2 4 3w e b 服务器 客户一般通过浏览器进行查询，这就需要系统提供w e b 服务器并且与索引 数据库进行连接。客户在浏览器中输入查询条件，w e b 服务器接收到客户的查询 条件后在索引数据库中进行查询、排列然后返回给客户端。 2 5 搜索引擎的指标和术语 互联网上的搜索引擎众多，各具特色，要合理评价一个搜索引擎的性能 优劣并不是一件容易的事，因为搜索引擎涉及的因素很多，且各因素之间相 互影响，不管是强调哪方面都势必会忽略另一个方面的作用。下面将从几个 基本的衡量标准进行介绍。 ( 1 ) 查全率和查准率 查全率( r e c a l l ) 又称召回率，一次搜索结果中符合用户要求的数目与用户 查询相关信息的总数之比。 ( 2 ) 查准率 查准率( p r e c i s i o n ) 又称精确度，是检索出的相关文档数与检索出的文档 总数的比率。 ( 3 ) 覆盖率 覆盖率是搜索引擎的一个重要的衡量标准，一个搜索引擎收录的网页的 多少，索引的主题范围的大小，决定了它能为用户提供