（计算机应用技术专业论文）JAVA技术与人工智能在搜索引擎上的应用.pdf

五邑大学硕士论文 摘要 1 9 9 0 年1 2 月2 5 日w e b 上线，1 9 9 3 年3 月1 5 日图形浏览器诞生，人们由此开 始彻底改变了网上查阅信息、获取资料的习惯，w e b 已经成为人们获取信息的一条 重要途径。由于w e b 页面的日益增加，获取特定信息就成为一个难题，搜索引擎应 运而生，并改变了人们获取网络信息的方式。 j a v a 是由美国s u n 公司( s u nm i c r o s y s t e m s ，i n e ) 研发的计算机编程语言，其最大 的特点是可移植性，它的出现引发了开源的浪潮，因此，j a v a 世界有许多优秀的开 源项目。本文在对w e b 搜索引擎工作原理和体系结构详细阐述的基础上，重点分析 了n u t c h 这一优秀的j a v a 开源分布式搜索引擎，并在此引擎上用b p 神经网络改进 了中文分词算法，使得该引擎在中文分词上有一定的人工智能。根据测试分析、比 较，该分词算法在处理有语义歧义的句子上，分词效果要优于传统的机械分词算法。 关键词：搜索引擎：中文分词；n u t c h ；l u c e n e ；h a d o o p ；b p 神经网络 五邑大学硕士论文 a b s t r a c t d e c e m b e r2 5 ，19 9 0w e bc a m ei n t ot h ew o r l da n dm a r c h15 ，19 9 3g r a p h i c a lb r o w s e rw a s b r o u g h to u t f r o mt h e no np e o p l eh a dc o m p l e t e l yc h a n g e dt h e i rh a b i to fr e q u i r i n gi n f o r m a t i o no n l i n e w e bb e c a m eo n eo ft h em o s ti m p o r t a n ta p p r o a c h sb yw h i c hp e o p l ec a no b t a i ni n f o r m a t i o n b e c a u s e t h ep a g e so nw e ba r eg r o w i n gs t e a d i l y , o b t a i n i n gs p e c i f i ci n f o r m a t i o nh a sb e c o m ead i f f i c u l t p r o b l e m s e a r c he n g i n ec a m e i n t ob e i n g i ts o l v e dt h i sp r o b l e ma n dc h a n g e dt h ew a yp e o p l ea c c e s s t on e t w o r ki n f o r m a t i o n j a v ai sac o m p u t e rp r o g r a m m i n gl a n g u a g ew h i c hw a sc r e a t e db ys u nm i c r o s y s t e m s p r o g r a m p o r t a b i l i t y i si t sm o s tn o t a b l ec h a r a c t e r i s t i c a f t e ri t sa p p e a r a n c e ，l o t so fe x c e l l e n to p e ns o u r c e p r o j e c tc a m ei n t ot h ej a v aw o r l d t h i sp a p e ra m p l yd e s c r i b e st h ew o r k i n gp r i n c i p l ea n da r c h i t e c t u r e o fw e bs e a r c he n g i n ea tf i r s t w i t ht h e s ep r i n c i p l e s ，id e t a i l e d l ya n a l y s en u t c h ao u t s t a n d i n g d i s t r i b u t e dj a v ao p e ns o u r c es e a r c he n g i n e t h e nii m p r o v et h ew o r d ss e g m e n t a t i o na l g o r i t h mw i t h b pn e t w o r ko nt h i ss e a r c he n g i n e ，w h i c hm a d et h ec h i n e s ew o r d ss e g m e n t a t i o no fn u t c hh a ss o m e k i n do fa r t i f i c i a li n t e l l i g e n c e a c c o r d i n gt oa n a l y s i sa n dc o m p a r i s o no ft e s td a t a , t h ee f f e c to fb p s e g m e n t a t i o ni sb e t t e rt h a nt h et r a d i t i o n a ls e g m e n t a t i o na l g o r i t h mw h e nt h em e a n i n go fs e n t e n c e si s a m b i g u i t y k e y w o r d s ：s e a r c he n g i n e ；w o r ds e g m e n t a t i o n ；n u t c h ；l u c e n e ；h a d o o p ；b pn e t w o r k u 本人声明 我声明，本论文及其研究工作由本人在导师指导下独立完成，完成论文所用的。 一切资料均已在参考文献中列出。 作者：汪杨林 签字：形扬抓 2 0 0 8 年4 月15 日 五邑大学硕士论文 1 1搜索引擎的历史 第一章绪论 随着互联网网页数量的迅速增加，信息也越来越分散，用户想要搜索特定的信 息变得十分困难，搜索引擎正是为了解决这个问题而出现的技术，它以一定的策略 在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供 检索服务，从而起到信息导航的目的。 搜索引擎包括信息搜集、信息整理和用户查询三部分。从用户的角度来看，它 就是一个帮助人们进行信息检索的工具。搜索引擎提供的导航服务己经成为互联网 上非常重要的网络服务，提供搜索服务的站点也被美誉为“网络门户”。因而搜索 引擎技术成为计算机工业界和学术界争相研究、开发的对象。 1 9 9 0 年以前，没有任何人能搜索互联网。1 9 9 0 年m o n t r e a l 的m c g i l lu n i v e r s i t y 学生a l a ne m t a g e 、p e t e rd e u t s c h 、b i l lw h e e l a n 发明了a r c h i e ( a r c h i ef a q ) ，它是所 有搜索引擎的祖先。a r c h i e 是第一个自动索引互联网上匿名f t p 网站文件的程序， 但它还不是真正的搜索引擎。 最早意义上的搜索引擎出现于1 9 9 4 年7 月【l 】，当时m i c h a e lm a u l d i n 将j o h n l e a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。 1 9 9 5 年1 2 月，a l t a v i s t a 的诞生对搜索引擎领域具有跨时代的意义i z j ，a l t a v i s t a 是第一个支持自然语言搜索的搜索引擎，也是第一个实现高级搜索语法的搜索引擎 ( 如a n d 、o r 、n o t 等) 。用户可以用a l t a v i s t a 搜索新闻组( n e w s g r o u p s ) 的内容并 从互联网上获得文章，还可以搜索图片名称中的文字、搜索标题( t i t l e s ) 、搜索j a v a 小 程序、搜索a c t i v e x 控件等。 1 9 9 8 年，g o o g l e 在p a g e r a n k 、动态摘要、网页快照：d a i l yr e f r e s h 、多文档格 式支持、地图、股票、词典、寻人等集成搜索、多语言支持、用户界面等功能上的 革新，象a i t a v i s t a 一样，对搜索引擎领域具有非常深远的影响。 1 2搜索引擎的现状 目前搜索引擎领域的商业开发非常活跃，各大搜索引擎公司都在投巨资研制搜 索引擎系统，同时也不断地涌现出新的具有鲜明特色的搜索引擎产品，搜索引擎己 经成为信息领域的产业之一。在这种情况下，对搜索引擎技术相关领域的学术研究 五邑大学硕士论文 得到了大学和科研机构的重视，如s t a n f o r d 大学在其数字图书馆项目中开发了 g o o g l e 搜索引擎1 3 】，在w 曲信息的高效搜索、文档的相关度评价、大规模索引等方 面作了深入的研究，取得了很好的成果。 国内在文本分类方向上起步较晚，由于中文与英文存在较大的差异，因此不能 照搬国外的研究成果，有必要研究并开发出实用化的中文文本分类系统【4 】。国内对 文本表示模型及文本分类算法方面的研究较多，其中一项值得注意的研究是在采用 n g r a m ( n 取1 、2 、3 、4 ) h j 信息表示文本，使用该方法进行中文文本自动分类的尝 试，摆脱了对词典的依赖，实现文本分类的领域无关性和时间无关性，取得了一定 的成果。 到目前为止，国内先后有北京大学、清华大学、国家智能研究中心等高校和研 究单位对搜索引擎技术开展研究，并开发出了几个较好的系统，如由北京大学计算 机系网络研究室开发的“天网 中英文搜索引擎、百度公司的“百度 搜索引擎等。 由于汉语本身的特点，仍然存在很多待解决的问题，如分词效果不理想、缺乏 统一的中文语料库、特征提取算法及文本分类算法的研究不十分完整、测试标准不 统一等问题。 1 3j a v a 技术介绍 s u n 公司于1 9 9 6 年年初发布了j a v a 的第一个版本，在1 9 9 8 年召开的j a v a o n e 大会上，又发布了j a v a1 2 版，这就是常说的j a v a2 ，它以功能全面、具有高度扩 展能力的新版本替换了原来的g u i 界面和图形工具包。 1 9 9 9 年，s u n 宣布了以j a v a2 平台为核心的j 2 e e 、j 2 s e 和j 2 m e 三大平台。 今天，这三大平台迅速推进，满足着不断增长的市场需求。2 0 0 2 年2 月，s u n 发布 了j 2 s e1 4 版，成为最具竞争优势的企业级应用与服务的快速开发平台。该产品已 通过中文编码国家标准g b l 8 0 3 0 的检测，标志着j a v a 丌发在中国提速。 j a v a 语言是一种优秀的编程语言，它最大的优点就是平台无关性，在w i n d o w s 2 0 0 0 、w i n d o w sx p 、s o l a r i s 、l i n u x 、m a co s 及其他平台上，都可以使用相同的代 码。j a v a 这种“一次编写，到处运行 的特点，使得系统的移植、平台的迁移变得 十分容易。简而言之，j a v a 具有简洁性、面向对象、分布式运算、健壮性、安全性， 跨平台、可移植等特性。 s u n 公司开放了j a v a 基础类库的源代码，在s u n 公司的影响和感召下，j a v a 世 界涌现出许多优秀的开源项目。本论文使用了n u t c h 、l u c e n e 、h a d o o p 、h e t r i t r i x 和j o o n e 等j a v a 开源项目。 2 五邑大学硕士论文 1 4神经网络与人工智能 人工智能( a r t i f i c i a li n t e l l i g e n c e ) ，英文缩写为a i ，是一f - j 由计算机科学、控 制论、信息论、语言学、神经生理学、心理学、数学、哲学等多种学科相互渗透而 发展起来的综合性新学科。自问世以来a i 经过许多波折，作为一门边缘新学科终 于得到世界的承认并且日益引起人们的兴趣和关注。不仅许多其他学科开始引入或 借用a i 技术，而且a i 中的专家系统、自然语言处理和图象识别己成为新兴的知识 产业的三大突破口。 神经网络是人工智能的一个重要分支，它于上世纪8 0 年代末发展起来。1 9 8 7 年，美国召开第一次神经网络国际会议，宣告了这一新学科的诞生。此后，各国在 神经网络方面的投资逐渐增加，神经网络迅速发展起来。 神经网络是在研究人脑的奥秘中得到启发，试图用大量的处理单元( 人工神经 元、处理元件、电子元件等) 模仿人脑神经系统工程结构和工作机理。在人工神经 网络中，信息的处理是由神经元之间的相互作用来实现的，知识与信息的存储表现 为网络元件互连间分布式的物理联系，网络的学习和识别取决于和神经元连接权值 的动态演化过程。 本文采用b p 神经网络处理中文分词，使得中文分词具有一定的人工智能。 1 5本文的研究内容及论文的组织 主要研究内容 本文在对w e b 搜索引擎工作原理和体系结构详细阐述的基础上，重点分析了 n u t c h 这一优秀的纯j a v a 开发的分布式搜索引擎，并在此引擎上用b p 神经网络改 进了中文分词算法，使得该引擎在中文分词上有一定的人工智能。该b p 神经网络 样本的期望值来自j e a n a l y s i s ( 采用j 下向最大匹配的中文分词算法，并可以加入自 己的词库) ，并在样本空间中加入一些有语意歧义的句子，实验表明该b p 分词算法 在处理歧义句子的时候，分词效果比传统机械分词要好。 论文的结构安排如下 第一章绪论。介绍了搜索引擎的历史和现状，提出作者的研究内容。 第二章w e b 搜索引擎工作原理和体系结构。对w e b 搜索引擎的工作原理和体 系结构做了详细的介绍。 第三章n u t c h 分布式搜索引擎的分析。详细地分析了n u t c h 这一开源分布式搜 索引擎，主要介绍了它的两个重要组成部分l u c e n e 和h a d o o p 。 五邑大学硕士论文 第四章l u c e n e 中文分词算法的改进。在分析了常用中文分词算法的基础上， 提出b p 神经网络的分词算法。 第五章实验与结果分析。介绍实验平台的搭建步骤及测试结果。 最后是结束语，对本文作了总结，指出系统的不足，并就进一步需要研究的问 题和研究方向进行了讨论。 4 五邑大学硕士论文 第二章w e b 搜索引擎工作原理和体系结构 2 1工作原理 一个搜索引擎程序主要由搜索器( c r a w l e r ) 、索引器( i n d e x ) 、检索器( s e a r c h e r ) 和 用户接1 3 ( u i ，u s e ri n t e r f a c e ) 等四个部分组成，主要存储设备由页面存储器 ( r e p o s i t o r y ) 和存储桶( b a r r e l ) 两部分组成。 搜索器( c r a w l e r ) 本质上是一种计算机爬虫( s p i d e r ) 程序，它自动从i n t e r n e t 上不 断抓取各种w e b 网页信息，再将页面原始内容经过压缩处理，存入本地页面存储库， 以备索引器所用。 索引器( i n d e x e r ) 程序定期从页面存储库中取出网页原始信息，对其页面内容进 行分析和分解，以单词为主关键字进行索引，并初步进行排序处理，结果存入适当 的“存储桶( b a r r e l ) ，即硬件存储单元中。 当互联网用户通过用户接1 3u i 提交查询时，检索器( s e a r c h e r ) 程序根据用户输 入的查询关键词，在已由索引器( i n d e x e r ) 完成索引和初步排序的存储桶( b a r r e l ) 中进 行查找，并采用特定的页面优先级算法对其结果进行最终排序，使之尽可能符合用 户查询需求。最后，用户接口u i 将最终查询结果呈现在互联网用户面前。 2 2基本要求 搜索引擎是一个网络应用软件系统，如图2 1 所示。搜索引擎能够接受用户通过 浏览器提交的查询词或者短语，记作g d ，例如“体育明星”、“奥运圣火”、“床 前明月光等，并在一个可以接受的时间内返回一个和该用户查询匹配的网页信息 列表，记作三。这个列表的每一条目至少包含三个元素( 标题，网址链接，摘要) 。 图2 1 搜索引擎示意图 5 厶，乞 正= = 二= = ： 五邑大学硕士论文 可以接受的时间也就是响应时间。对于w e b 应用来说，这个时间不能太长， 通常在“秒级，这是衡量搜索引擎可用性的一个基本指标，也是和传统信息检索 系统的一个差别。而且，这个响应时间不仅要能满足单个用户查询，而且要能在不 超过系统设计负载的情况下满足所有的用户。 匹配指的是网页中以某种形式包含有g d 的内容，其中最简单、最常见的形式 就是g d 在其中直接出现。不过如果一个搜索引擎就是以百分之百满足这种简单的包 含关系为目标，即使实现了也并不意味着能达到了最好的效果。 列表这蕴含着一种“序 ( r a n k ) ，即排列的顺序。在绝大多数情况下，三是相 当长的，例如“超过1 万个条目( 这和图书馆全文检索系统不同，图书馆全文检索 返回的列表通常较短) ，这不仅因为w e b 上的信息量大，也由于搜索引擎的查询方 式简单。简单，意味着抽象；抽象，意味着有更多的具体事物可能是它的体现。对 于一个长长的列表，很少有用户有耐心都审视一遍( 不仅是因为长，还因为大多数 使用搜索引擎的用户通常都是“找到为止 ，而不是“不全部找到不罢休”，加上 这个列表中的内容用户关心的其实只占很小的比例) 。有分析统计表明，用户平均 察看返回结果不超过2 页【5 j 。 现代大规模高质量搜索引擎一般采用如图2 2 所示的称之为三段式的工作流 程，即网页搜集、预处理和查询服务。 2 3 网页搜集 图2 2 搜索引擎三段式工作流程 搜索引擎系统操作的数据不仅包括内容不可预测的用户查询，而且包括在数量 上动态变化的海量网页，并且这些网页不会主动送到系统里来，而是需要系统主动 去抓取。 首先，要考虑网页的抓取时机，是事先还是及时。在网络比较通畅的情况下， 从网上下载一篇网页大约需要1 秒钟左右，因此如果在用户查询的时候即时去网上 抓取成千上万的网页，一个个页面分析处理，和用户的查询进行匹配，不可能满足 搜索引擎的响应时间要求。不仅如此，这样的系统效益也不高( 会重复抓取太多的 6 五邑大学硕士论文 网页) 。面对大量的用户查询，不可能想象每来一个查询，系统就到网上“搜索”一 次。因此，大规模搜索引擎服务的基础应该是一批预先搜集好的网页( 直接或者间 接) ，网页搜集方式可以是定期搜集或者增量搜集。 定期搜集每次搜集替换前一次搜集到的内容，亦称之为“批量搜集。由于 每次都是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花相当长 的时间，开销较大。这样做的好处是系统实现比较简单，主要缺点是“时新性” ( f r e s h n e s s ) 不高，还有重复搜集所带来的额外带宽的消耗。 增量搜集开始时搜集一批，以后只是搜集新出现的网页、或上次搜集后修改 过的网页，对自上次搜集后已经不再存在的网页从库中删除。通常除新闻网站外， 许多网页的内容变化并不是很经常的，这样做每次搜集的网页量不会很大，可以经 常启动搜集过程( 例如每天) 。增量搜集的系统表现出来的信息时新性会比较高， 主要缺点是系统实现比较复杂。 上面讨论的是系统网页数据库维护的基本策略。在这两种极端的情况之间也可 能有一些折中的方案。j c h o 博士在这方面做过深入的研究，他根据一种网页变化 模型和系统所含内容时新性的定义，提出了相应优化的网页搜集策略【6 l 。其中一个 有趣的结论是在系统搜集能力一定的情况下，若有两类网页( 例如“商业和“教 育 ) ，它们的更新周期差别很大( 例如“商业类网页平均更新周期是“天 ， 而“教育”类网页平均更新周期是“月”) ，则系统应该将注意力放在更新慢的网 页上，以使系统整体的时新性达到比较高的取值【_ 7 1 。 在具体搜集过程中，如何抓取网页，也可以有不同的考虑。最常见的一种是所 谓“爬取 ，将w e b 上的网页集合看成是一个有向图，搜集过程从给定起始u r l 集合s ( 或者说“种子刀) 开始，沿着网页中的链接，按照先深、先宽或者某种别 的策略遍历，不停地从s 中移除u r l 、下载相应的网页，解析出网页中的超链接 u r l ，看是否已经被访问过，将未访问过的那些u r l 加入集合s 。整个过程可以形 象地想象为一个蜘蛛( s p i d e r ) 在蜘蛛网( w e b ) 上爬行( c r a w l ) 。真正的系统其实是多个 “蜘蛛同时在爬。 这种方式的好处除了概念很清晰，一般实现起来也不困难外，还有很重要的一 个原因是容易通过一定的策略，使搜集到的网页相对比较“重要，。前面提过，任 何搜索引擎是不可能将w e b 上的网页搜集完全的，通常都是在其他条件的限制下决 定搜集过程的结束( 例如磁盘满，或者搜集时间已经太长了) 。因此就有一个尽量 使搜索到的网页比较重要的问题，这对于那些并不追求很大的数量覆盖率的搜索引 擎特别重要。研究表明【8 】，按照先宽搜索方式得到的网页集合要比先深搜索得到的 集合重要，这种方式的一个困难是要从每一篇网页中提取出所包含的u r l 。由于 h t m l 的灵活性，其中出现u r l 的方式各种各样，要使这个环节做得彻底并不容 易。同时，由于w e b 的“蝴蝶结形状，这种方式搜集到的网页不大会超过所有目 7 五邑大学硕士论文 标网页数量平方的2 31 引。 另外一种可能的方式是在第一次全面网页搜集后，系统维护相应的u r l 集合s ， 往后的搜集直接基于这个集合。每搜到一个网页，如果它发生变化并含有新的u r l ， 则将它们对应的网页也抓回来，并将这些新u r l 也放到集合s 中；如果s 中某个 u r l 对应的网页不存在了，则将它从s 中删除。这种方式也可以看成是一种极端的 先宽搜索，即第一层是一个很大的集合，往下最多只延伸一层。 还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址( 为了宣传自己， 通常会有这种积极性) ，系统在一定时间内( 2 天到数月不等) 定向向那些网站派 出“蜘蛛”程序，扫描该网站的所有网页并将有关信息存入数据库中。大型商业搜 索引擎一般都提供这种功能。 2 4网页预处理 得到海量的原始网页集合，距离面向网络用户的检索服务之间还有相当的距离。 宏观地看，服务子系统是一个程序。采用w i r t h 关于“程序= 算法+ 数据结构 的观 点来考察这个程序，一个合适的数据结构是查询子系统工作的核心和关键。现行最 有效的数据结构是“倒排文件”( i n v e r t e df i l e ) ，倒排文件是用文档中所含关键词作 为索引，文档作为索引目标的一种结构( 类似于普通书籍中，索引是关键词，书的 页面是索引目标) 。下面讨论从网页集合到形成这样的倒排文件过程中的几个关键 步骤，包括关键词的提取、“镜像网页( 网页的内容完全相同，未加任何修改) 或“转载网页 ( n e a r r e p l i c a s ，主题内容基本相同但可能有一些额外的编辑信息等， 转载网页也称为“近似镜像网页 ) 的消除、链接分析和网页重要程度的计算，即 “预处理 。 2 4 1 关键词提取 网页的源文件除了从浏览器中能够正常看到的文字内容外，还有大量的h t m l 标记。另外，由于h t m l 文档产生来源的多样性，许多网页在内容上比较随意，不 仅文字不讲究规范、完整，而且还可能包含许多和主要内容无关的信息( 例如广告、 导航条、版权说明等) 。这些情况既给有效的信息查询带来了挑战，也带来了一些 新的机遇。这里只是指出，为了支持后面的查询服务，需要从网页源文件中提取出 能够代表它的内容的一些特征。从人们现在的认识和实践来看，所含的关键词即为 这种特征最好的代表。于是，作为预处理阶段的一个基本任务，就是要提取出网页 源文件的内容部分所含的关键词。对于中文来说，就是要根据一个词典，用一个 3 五邑大学硕士论文 所谓“切词软件 ，从网页文字中切出所含的词语来，之后一篇网页主要就由一 组词来近似代表了，p = t l ，t z , ，“ ( p 表示查询词汇表，j 表示词) 。一般来讲，可 能得到很多词，同一个词可能在一篇网页中多次出现。从效果( e f f e c t i v e n e s s ) 和效率 ( e f f i c i e n c y ) 考虑，不应该让所有的词都出现在网页的表示中，要去掉诸如“的”， “在 等没有内容指示意义的“停用词 ( s t o pw o r d ) 。 2 4 2 重复或转载网页的消除 与生俱来的数字化和网络化给网页的复制以及转载和修改再发表带来了便利， 因此可以看到w e b 上的信息存在大量的重复现象。这种现象对于广大的网民来说是 有正面意义的，因为有了更多的信息访问机会。但对于搜索引擎来说，则主要是负 面的：它不仅在搜集网页时要消耗机器时间和网络带宽资源，而且如果在查询结果 中出现，便无意义地消耗了计算机显示屏资源。因此，消除内容重复或主题内容重 复的网页是预处理阶段的一个重要任务。 2 4 3 链接分析 前面提到，大量的h t m l 标记既给网页的预处理造成了一些麻烦，也带来了一 些新的机遇。从信息检索的角度讲，如果系统面对的文件内容仅仅是文字，依据就 是“共有词汇假设( s h a r e db a go f w o r d s ) ，即内容所包含的关键词集合，加上词频 ( t e r mf r e q u e n c y 或t f 、t f ) 和词在文档集合中出现的文档频率( d o c u m e n tf r e q u e n c y 或 d f 、d f ) 之类的统计量。t f 和d f 这样的频率信息能在一定程度上表明词语在一篇 文档中的相对重要性或者和某些内容的相关性。有了h t m l 标记后，情况还可能进 一步改善，例如在同一篇文档中， 和 之问的信息很可能就比在 和 之间的信息更重要。特别地，h t m l 文档中所含的指向其他文档的链接信息 是人们近几年来特别关注的对象，认为它们不仅给出了网页之间的关系，而且还对 判断网页的内容有很重要的作用。例如“邑大学报”这几个字在五邑大学学报社会 科学版的主页上是没有的，因此一个仅靠内容文字分析的搜索引擎就不可能返回该 主页作为结果。但是五邑大学主页上是用“邑大学报( 社) 作为链接信息指向了 五邑大学学报社会科学版的主页。因此在很好利用链接信息的搜索引擎中应该能返 回五邑大学学报社会科学版的主页。 9 五邑大学硕士论文 2 4 4 网页重要程度的计算 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。由于面对各种各 样的用户，加之查询的自然语言风格，对同样的q o ( 查询) 返回相同的列表肯定是不 能使所有提交卯的用户都满意的。因此搜索引擎实际上追求的是一种统计意义上的 满意。人们认为g o o g l e 目前比百度好，是因为在多数情况下前者返回的内容要更符 合用户的需要，而不是所有情况下都如此。网页的排序一般而言是由网页的重要度 决定的，那如何判别网页的重要程度? 人们参照科技文献重要性的评估方式，核心 想法就是被引用多的就是重要的。引用这个概念恰好可以通过h t m l 超级链接标签 在网页之间体现得非常好，作为g o o g l e 创立核心技术的p a g e r a n k 就是这种思路的 成功体现【l 叭。除此以外，人们还注意到网页和文献的不同特点，即一些网页主要是 大量对外的链接，其本身基本没有一个明确的主题内容，而另外有些网页则被大量 的其他网页链接。从某种意义上讲，这形成了一种对偶的关系，这种关系使得人们 可以在网页上建立另外一种重要性指标【l l 】。这些指标有的可以在预处理阶段计算， 有的则要在查询阶段计算，但都是作为在查询服务阶段最终形成结果排序的部分参 数。 2 5 查询服务 如上述，从一个原始网页集合s 开始，预处理过程得到的是对s 的一个子集的 元素的某种内部表示，这种表示构成了查询服务的直接基础。对每个元素来说，这 种表示至少包含原始网页文档、u r l 和标题、编号、所含的重要关键词的集合( 以 及它们在文档中出现的位置信息) 、其他一些指标( 例如重要程度，分类代码等) ， 而系统关键词总体的集合和文档的编号一起构成了一个倒排文件结构，使得一旦得 到一个关键词输入，系统能迅速给出相关文档编号的集合输出。 然而，用户通过搜索引擎看到的不是一个“集合，而是一个“列表。如何 从集合生成一个列表，是服务子系统的主要工作。从搜索引擎系统功能划分的角度， 有时候将倒排文件的生成也作为服务子系统的一部分功能，但这里将它划分到预处 理阶段中觉得更方便些。换句话讲，服务子系统是在服务进行的过程中涉及的相关 软件程序，而为这些软件程序事先准备数据的程序都算在预处理子系统中。 2 5 1 查询方式和匹配 查询方式指的是系统允许用户提交查询的形式。考虑到各种用户的不同背景和 1 0 五邑大学硕士论文 不同的信息需求，不可能有一种普适的方式。一般认为，对于普通网络用户来说， 最自然的方式就是“要什么就输入什么”。但这是一种相当模糊的说法。例如用户 输入“五邑大学 ，可能是他想了解五邑大学目前有些什么信息向外发布、想看看 今年的招生政策( 于是希望看的是邑大网站上的内容) 、也可能是他想了解外界目 前对五邑大学有些什么评价( 于是希望看到的是其他权威网站上关于邑大的消息) 。 在其他一些情况下，用户可能关心的是间接信息，例如“喜马拉雅山的高度”，8 8 4 8 米应该是他需要的，但不可能包含在这短语中。而用户输入“惊起一滩鸥鹭 则很 可能是想知道该词的作者是谁，或者希望能提醒前面几句是什么。尽管如此，用一 个词或者短语来直接表达信息需求，希望网页中含有该词或者该短语中的词，依然 是主流的搜索引擎查询模式。这不仅是因为它的确代表了大多数的情况，还因为它 比较容易实现。一般来讲，系统面对的是查询短语。就英文来说，它是一个词的序 列；就中文来说，它是包含若干个词的一段文字。用吼表示用户提交的原始查询， 例如，吼= “网络与分布式系统实验室 。它首先需要被“切词 ( s e g m e n t ) 或称“分 词”，即把它分成一个词的序列，然后删除那些没有查询意义或者几乎在每篇文档 中都会出现的词( 例如“的 ) ，在本例中即为“与一。最后形成一个用于参加匹 配的查询词汇表g ，g = ，j ，t 2 , ，厶 ( f f 表示词) ，在本例中就是q = 网络，分布式， 系统，实验室，。前面讲过，倒排文件就是用词来作为索引的一个数据结构，显然， 口中的词必须是包含在倒排文件词表中才有意义。有了这样的g ，它的每一个元素都 对应倒排文件中的一个倒排表( 文档编号的集合) ，记作l ( t ，) ( “表示词) ，它们的 交集即为对应查询的结果文档集合，从而实现了查询和文档的匹配。上述过程的基 本假设是用户希望得到的网页是包含所输入查询文字的。 2 5 2 结果排序 前面分析了得到和用户查询相关的文档集合的过程。这个集合的元素需要以一 定的形式通过计算机显示屏呈现给用户。就目前的技术情况看，列表是最常见的形 式( 但人们也在探求新的形式，如v i v i s i m o 引擎将结果页面以类别的形式呈现) 。 给定一个查询结果集合r ，r - ，j ，仫，h ) ( n 表示一个结果) ，所谓列表，就是按 照某种评价方式，确定出r 中元素的一个顺序，让这些元素以某种顺序呈现出来。 笼统地讲，厂f 和g d 的相关性( r e l e v a n c e ) 是形成这种顺序的基本因素。但是，有效 地定义相关性本身是很困难的，从原理上讲它不仅和查询词有关，而且还和用户的 背景以及用户的查询历史有关。不同需求的用户可能输入同一个查询，同一个用户 在不同的时间输入相同的查询可能是针对不同的信息需求。为了形成一个合适的顺 序，在搜索引擎出现的早期人们采用了传统信息检索领域很成熟的基于词汇出现频 五邑大学硕士论文 度的方法。大致上讲就是一篇文档中包含的g d 中的哪些词越多，则该文档就应该排 在越前面。再精细一些的考虑则是若一个词在越多的文档中有出现，则该词用于区 分文档相关性的作用就越小。当通过前述关键词的提取过程，形成一篇文档的关键 词集食p ，p = t l ，t 2 , ，岛 的时候，很容易同时得到每一个“在该文档中出现的次 数，即词频，而倒排文件中每个倒排表的长度则对应着一个词所涉及的文档的篇数， 即文档频率，因此很容易实现倒排文件数据结构。然而，由于网页编写的自发性、 随意性较强，仅仅针对词的出现来决定文档的顺序，在w e b 上做信息检索表现出明 显的缺点，需要有其他技术的补充。这方面最重要的成果就是前面提到过的 p a g e r a n k 。通过在预处理阶段为每篇网页形成一个独立于查询词( 也就和网页内容 无关) 的重要性指标，将它和查询过程中形成的相关性指标结合形成一个最终的排 序，是目前搜索引擎给出查询结果排序的主要方法。 除上述外，查询服务返回的内容还有一些细节的支持。例如，对应一个查询往 往会有成千上万的结果，返回给用户的内容通常都是按页组织的，一般每页显示1 0 个结果。统计表明l l 引，网络用户一般没有耐心一页页看下去，平均翻页数小于2 。 将第一页的内容组织好非常重要，如果希望用户多用搜索引擎，就要让第一页的内 容尽量有吸引力。 2 5 3 文档摘要 搜索引擎给出的结果是一个有序的条目列表，每一个条目包含标题、网址和摘 要三个基本的元素，其中的摘要需要从网页正文中生成。一般来讲，从一篇文字中 生成一个恰当的摘要是自然语言理解领域的一个重要课题，人们已经做了多年的工 作并取得了一些成果，但相关的技术用到网络搜索引擎来有两个基本困难，一是网 页的写作通常不规范、文字比较随意，因此从语言理解的角度难以做好；二是复杂 的语言理解算法耗时太多，不适应搜索引擎要高效处理海量网页信息的需求。搜索 引擎在生成摘要时要简单化，基本上可以归纳为静态摘要方式和动态摘要方式。静 态方式，独立于查询，按照某种规则事先在预处理阶段从网页内容提取出一些文字， 例如截取网页正文的开头5 1 2 个字节( 对应2 5 6 个汉字) ，或者将每一个段落的第 一个句子拼起来。这样形成的摘要存放在查询子系统中，一旦相关文档被选中与查 询项匹配，就读出返回给用户。显然，这种方式对查询子系统来说是最轻松的，不 需要做另外的处理工作。但这种方式的一个最大的缺点是摘要和查询无关。一篇网 页有可能是多个不同查询的结果，因为存在多种不同的分词组合，当用户输入某个 查询，他一般是希望摘要中能够突出显示和查询直接对应的文字，希望摘要中出现 和他关心的文字相关的句子。动态摘要在响应查询的时候，根据查询词在文档中的 1 2 五邑大学硕士论文 位置，提取出周围的文字来，在显示时将查询词标亮。这是目前大多数搜索引擎采 用的方式。为了保证查询的效率，需要在预处理阶段分词的时候记住每个关键词在 文档中出现的位置。 2 6 体系结构 在上述工作原理的基础上，作为一个网络应用软件，可以勾画出搜索引擎的体 系结构，如图2 3 所示，其中的大部分模块和前面的原理描述有直接的对应。这里 需要特别讨论的是还没有专门提及的“控制器模块。 网页的搜集，如果只是为了做些简单的实验，可以用最简单的工具完成。但如 果是为了向大规模搜索引擎稳定地提供网页数据，通常需要每天搜集上百万网页， 而且是持续进行，情况则要复杂许多，核心是要综合解决效率、质量和“礼貌 的 问题，这就是“控制器”的作用。 所谓效率，就是如何利用尽量少的资源( 计算机设备、网络带宽、时间) 来完 成预定的网页搜集量。由于网页之间存在的独立性，可以利用多台计算机并发地搜 集网页，即使是用一台计算机来搜集网页，也应该注意系统并发性和c p u 的利用率。 由于从网上抓取一篇网页通常需要秒量级的等待网络通信时间，同时启动多个抓取 进程线程，或者利用操作系统提供的异步通信机制是很有意义的。同时启动抓取进 程的数量取决于硬件条件和搜集软件的设计。 在用若干台计算机形成一个机群的安排下，它们共同分享出口网络带宽，随着 设备量的增加，这个网络带宽( 或者是周围的某个环境带宽) 很快就成为瓶颈。人 们曾经有过分布式搜集的想法，即让多台设备分布在网络上的不同位置，从而克服 上述带宽瓶颈问题。影响搜集效率的另外一个因素是服务器方可能来不及提供所需 的网页。这除了有些w e b 服务器所处的网络条件比较差，或者有太多其他人访问外， 搜索引擎太频繁对它们发出网页请求也是一个重要原因。落实到技术上，就是要有 一个访问策略或者u r l 规划，不要让搜集器启动的抓取进程都集中在少数几个网站 匕。 1 3 五邑大学硕士论文 图2 3 搜索引擎的体系结构 将搜集活动的关注过分集中在几个网站上，或者在- d , 段时间里从一个网站抓 取太多的网页还可能引起其他的严重后果，即所谓“礼貌 问题。一般来讲，网站 的管理人员都很愿意让自己的网页被搜索引擎索引，从而有可能得到更多的访问流 量，但这只是问题的一方面。问题的另一方面是网站绝不希望由于搜索引擎的“密 集 抓取活动阻碍了普通用户通过浏览器的访问，使那些用户得到这个网站访问起 来很困难的印象，从而不再光顾。不加控制的网页抓取，给网站造成的现象有时候 、和制造拒绝服务( d e n i a lo f s e r v i d e ，d o s ) 攻击的黑客造成的现象一样。因此，管理 良好的网站常常会有一个监视器运行，监视是否有来源于单个i p 地址的过分密集的 访问，一旦出现这种情况，要么会通告该i p 地址的拥有者注意行为，或者会干脆 屏蔽来自它的访问，更有甚者，还可能在网上公布该i p 地址作为黑名单。因此， 适当地规划网页的抓取，限制单位时间内对一个网站抓取网页的数量是大规模搜索 引擎必须要认真对待的问题。总之，搜索引擎需要和网站“和睦相处一，它们是相 1 4 五邑大学硕士论文 互依存的。 所谓质量问题，指的是在有限的时间内搜集的有限网页是尽量比较“重要的 网页，或者说不要漏掉那些很重要的网页。如果让重要性和流行度等同起来，即越 多人看过的网页越重要，可以考虑一个网站从主页开始向下，按照链接的深度将网 页组织成一层层的，上层中的网页统计上会比下层的网页重要些，即较靠近主页的 网页通常p a g e r a n k ( 页面排名) 值较高。这样，首先得到尽量多的主页，然后从主页 开始的先宽搜索就应该是一个较好的策略。 网页搜集过程中还有一个基本的问题是要保证每个网页不被重复抓取。由于一 篇网页可能被多篇网页链接，在s p i d e r 爬取过程中就可能多次得到该网页的u r l 。 于是如果不加检查和控制，网页就会被多次抓取。遇到循环链接的情况，还会使爬 取器陷死。解决这个问题的有效方法是使用两个表u n v i s i t e dt a b l e 和v i s i t e dt a b l e 。 前者包含尚未访问的u r l ，后者记录已访问的u r l 。系统首先将要搜集的种子u r l 放入u n v i s i t e dt a b l e ，然后s p i d e r 从其中获取要搜集网页的u r l ，搜集过的网页u r l 放入v i s i t e dt a b l e 中，新解析出的并且不在v i s i t e dt a b l e 中的u r l 加入 u n v i s i t e dt a b l e 。此方法简单明了，适合在单个节点上实现。 2 7本章小结 本章主要介绍了w e b 搜索引擎的工作原理和体系结构。先分析了其工作原理和 基本要求，再详细分析了搜索引擎的功能模块，最后给出了搜索引擎的体系结构， 使读者从总体上了解搜索引擎的工作原理以及各功能模块在整个系统中的作用。 五邑大学硕士论文 第三章n u t c h 分布式搜索引擎的分析 3 1n u t c h 介绍 n u t c h 是一个诞生于2 0 0 3 年用j a v a 语言开发的开源( o p e n s o u r c e ) - f f 联网搜索引 擎，其目标是建立一个开源的、灵活的、易扩充的、世界一流的w e b 搜索引擎。开 源代码的n u t c h 避免了低水平的重复开发，为广大研究人员提供了一个良好的研究 搜索引擎技术、进行更多研究实践的平台。 n u t c h 相对于商用的搜索引擎更加透明，从而更值得大家信赖。现在所有主要 的搜索引擎都采用私有的排序算法，而不会解释为什么一个网页会排在一个特定的 位置。除此之外，有的搜索引擎依照网站所付的费用，而不是根据它们本身的价值 进行排序。与商业搜索引擎不同，n u c t h 没有什么需要隐瞒，也没有动机去扭曲搜索 的结果。n u t c h 将尽自己最大的努力为用户提供最好的搜索结果。由于n u t c h 是开 源代码的，因此任何人都可以查看他的排序算法是如何工作的，因此n u t c h 对学术 搜索和政府类站点的搜索来说，是一个比较好的选择。 本文第四章、第五章的中文分词改进和试验是基于n u t c h0 9 版本，该版本建立 在l u c e n e2 0 0 ( 详见3 2 节) 和h a d o o p0 7 1 ( 详见3 3 节) 的基础之上。n u t c h0 9 利用l u c e n e 进行中文分词、索引和搜