（计算机软件与理论专业论文）搜索引擎设计分析与结果聚类改进.pdf

摘要 摘要 搜索引擎是获取信息的有效工具，设计与实现搜索引擎是一项庞大的工程， 要运用较多专业技术知识。本文力图通过实例分析，介绍搜索引擎的设计、实现、 搜索结果聚类及其它与搜索引擎紧密相关的知识。 文中指出了搜索引擎在提取摘要信息上存在的不足：仅选取关键词临近区域 的语词并不具语义特征，为此提出了以文本的语义特征词来替换摘要信息。文中 同时对语义特征词的提取进行了理论分析，并实现了部分功能。 本文利用后缀数组来提取文档的语义特征词，因此对后缀数组的结构作了详 细的阐述，提出以完全子串来表示文档的语义特征。文中实现了后缀数组的构造， 左、右完全子串及完全子串的提取。 本文还对搜索引擎的聚类过程、以及常用的聚类算法进行了比较，并对基于 奇异值分解的文本聚类算法一l i n g o 作了详细分析。修改了n u t c h 的体系结构以实 现搜索结果的聚类。最后以我校内网作为爬行目标，给出了实验结果及其评价。 关键词：搜索引擎，特征词提取，文本聚类，l u c e n e ，n u t c h a b s t r a c t a b s t r a c t a l o n gw i t ht h er a p i dg r o w t ho fi n f o r m a t i o no nw e b i t se a s yt oo b t a i nb u th a r dt o g e tu s e f u li n f o r m a t i o n s e a r c he n g i n e ，i ns o m ed e g r e e ，a c c e l e r a t et h es p e e do f i n f o r m a t i o nr e t r i e v a l , b u tt h ec o m m o ns e a r c he n g i n e 啪n o ts a t i s f yo n e sn e e di ns o m e s p e c i a lf i e l d s f o rt h i s ，d e s i g na n dd e v e l o ps p e c i a ls e a r c he n g i n ei sn e c e s s a r y b u tt h e s p e c i a ld o m a i nk n o w l e d g eo fd e s i g ns e a r c he n g i n em a k e si td i f f i c u l ti ni m p l e m e n t d e s i g na n dd e v e l o p m e n to fs e a r c he n g i n ea n di t si n t e r r e l a t e dt e c h n o l o g y , s u c ha ss e a r c h r e s u l tc l u s t e r , a l la r ee x p a t i a t e do ni nt h i st h e s i s t h et w om a i np a r t so fi r ：i n d e x i n ga n ds e a r c h i n ga r ed i s c u s s e df i r s t l y , b a s e do n t h eo p e ns o u r c ep r o j e c tl u c e n e ，i n c l u d i n gt h ei n d e xf i l ef o r m a t , i n d e xf i l eb u i l d i n g , s e a r c hp r o c e s s t h e na n a l y s i st h ew o r ks y s t e ma n d c o m p o s i t i o no fs e a r c he u g i u e , a n d t h ei n t e r r e l a t e dt e c h n o l o g ys u c ha st h es p i d e r t h ew e b p a g ep a r s e r , t h el i n ka n a l y s i s ，t h e i n d e xb u i l d i n g ，t h ef o r m a to fi n d e xf i l e ，s e a r c hp r o c e s sa n dt h ed a t as t r u c t u r ef o r s p e e d i n gt h es e a r c h s e c o n d l y , t h ef a u l to ft h ec o m m o ns e a r c he n g i n e ss n i p p e t si sp o i n t e do u t ：o n l yt h e p h r a s e sb yt h ek e y w o r d , i tc a nn o td e s c r i p tt h es e m a n t i cc h a r a c t e ro ft h et e x t t of e t c h u pi t , s e m a n t i cf e a t u r ee x t r a c t o ri sa d v a n c e d a n da f t e rt h a t , i st h ei m p l e m e n t t oe x t r a c tt h ef e a t u r ew o r d s , t h es u f f i xa r r a yi sa p p l i e d s ot h et h e o r i e so fs u f f i x a r r a ya r ei n t r o d u c e d , a n dt h e np o i n to u tt h a tc o m p l e t es o b s t r i n g 啪d e s c r i p tt h et e x t s f e a t u r e s t h e nd e v e l o pt h em o d u l eo fc o n s t r u c t i n gt h e s u f f i xa r r a y , f o r mt h el e f t c o m p l e t es u b s t r i n g , r i g h tc o m p l e t es u b s t r i n ga n dt h ec o m p l e t es u b s t r i n g c l u s t e rs e a r c hr e s u l ti st h ee f f e c t i v ew a yt oe n h a n c et h es e a r c he n g i n ef u n c t i o n t h ed u s t e rp r o c e s sa n dt h ec l u s t e rm e t h o d sd i f f e r e n c ea r ed i s c u s s e d t h e na n a l y s i st h e c l u s t e rm e t h o db a s e do ns i n g u l a rv a l u ed e c o m p o s i t i o na n dm o d i f i e st h ef r a m e w o r ko f c o m m o ns e a r c he n g i n et oi m p r o v et h ec l u s t e rf u n c t i o n a tl a s t ，t h ee x p e r i m e n t a t i o ni s s h o w n k e yw o r d s ：s e a r c he n g i n e , f e a t u r ee x t r a c t ，t e x tc l u s t e r , l u c e n e ，n u t c h 刖舌 i n t e r n e t 自1 9 6 9 年诞生以来不断成长，其内容不断丰富，整个网络逐渐堆积成 一个前所未有的超大型信息库【l - 3 1 。然而伴随互联网爆炸性的发展( 具中国互联网信 息中心q 统计：截至2 0 0 6 年6 月3 0 日，网民数量达1 2 3 0 0 万人；上网计 算机数达5 , 4 5 0 万台；w e b 站点数达7 8 8 ，4 0 0 + t 4 b ，普通网络用户想找到所需的资 料简直如同大海捞针，以至于出现了”信息丰富，知识贫乏”的奇怪现象。搜索引擎 正是为了解决这个”迷航”问题而出现的技术。 搜索引擎( s e a r c he n g i n e 简称s e ) 是一个信息处理系统，它以一定的策略在互 联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检 索服务，起到信息导航的目的【4 】。 搜索引擎经历了近2 0 年的发展，已形成了较多实用型的商品，国外有g o o g l e 、 v i v i s i m o 等，国内有b a i d u 、搜狐搜狗、新浪爱问等。然而搜索引擎仍存在较大的 发展空间，比如传统的准、全、新、快这四个基本问题还有待进一步的提高；而 基于语义理解而不仅仅是基于关键词串匹配的查询还不能有效解决。因而搜索引 擎被誉为未来w e b 应用的主流( 也有人认为未来的信息技术发展起主导作用的是搜 索技术的发展1 ，为此各个国家先后投入了大量的研究工作。 搜索引擎的基本原理虽然简单，但具体实仍存在较多的技巧及技术上的难题。 a p a c h e 公司推出的著名开源全文检索工具包l u c e n e 及开源搜索工具n u t c h 的出现 为设计搜索引擎提供了一个范本，本文所做的研究工作正是建立在该项目基础之 上。 文中首先详细分析了l u c e n e 及h u t c h 的体系结构，设计思想及代码实现。内 容涵盖了索引文件、索引建立、搜索过程、网络蜘蛛、网页分析、链接分析，也 分析了搜索相关的较为重要的数据结构如优先对列，后缀树及后缀数组等。 同时文中还指出当前通用搜索引擎在提取摘要信息上的缺陷，提出相应的解 决方法。文章最后讨论了搜索结果聚类的问题，并给出了实验结果。 通过该文的介绍，能够更深刻理解搜索引擎的原理、架构设计、细节实现等， 并能更好的把握搜索引擎未来的发展趋势，以改进目前搜索引擎的不足，设计面 向特定领域的搜索引擎。 图目录 图1 - 1 图1 2 图1 - 3 图2 1 图2 2 图2 - 3 图“ 图2 - 5 图2 - 6 图2 7 图3 - 1 图3 2 图3 3 图3 - 4 图3 - 5 图3 - 6 图3 - 7 图3 8 图3 - 9 图3 1 0 图3 1 1 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图4 _ 1 搜索引擎的系统结构图 图目录 搜索引擎系统流程图。 文档预处理过程。 l a c e n e 的系统结构及源码组织结构 l u c e n e 的主要数据流图 l a c e n e 索引文件结p “6 关系图 l u c e n e 索引文件的组成 索引建立的序列图 l a c e n e 搜索过程序列图 1 6 1 7 ，3 1 3 4 3 8 n u t c h 包的依赖关系图3 9 n u t c h 的工作流程图 n u t c h 索引的目录结构 p l e g i n 的类图。 e x t e n s i o n p o i n t 的类图4 3 e x t e n s i o n 的类图 m a p r e d u c e 的运行原理图。 由字母a b e 所组成的t r i e 树 4 4 4 6 4 9 “ik n o wy o uk n o wik n o w 的后缀树。 后缀连接 快速定位子串a l l a n 的过程图5 2 查找b a n a n a 的最长重复子串a r i a 示意图 注入u r l s 地址的序列图 生成f e t c i d i s t 的序列图。5 5 n u t c h 的连接分析关系图5 7 具有语义聚类效果的搜索引擎结构图 表目录 表2 1 表2 2 表2 - 3 表2 4 表2 - 5 表2 - 6 表2 7 表2 8 表2 - 9 表2 - 1 0 表2 1 1 表2 - 1 2 表2 - 1 3 表2 1 4 表2 - 1 5 表2 - 1 6 表2 - 1 7 表2 - 1 8 表2 - 1 9 表2 - 2 0 表2 - 2 1 表2 - 2 2 表2 2 3 袭4 1 表4 2 表4 - 3 表 词项文档序列 表目录 预处理后的词项文档序列 排序后的词项文档序列 合并关键词后的词项文档序列 词项文档序列与文档间的关系。 倒排索弓 s e g m e n t s 文件格式 d e l e t a b l e 文件格式 1 4 1 4 1 4 1 5 1 5 c o m p o u n d 文件格式 f i e l di n f o 文件格式 f i e l d b i t s 各位的含义 域数据域文件格式 词项信息文件格式 t e r m i n f o 文件格式。 t e r m 文件格式 词项信息索引文件格式 词项频数文件格式 词项向量文档文件格式 词项向量域文件格式 被删除文件的格式 任务的优先权及执行顺序 l u c e n e 的常用查询方式 后缀树组及其l c p 例子 右完全子串数组示例 完全子串示例 2 3 2 3 2 4 2 5 2 6 2 6 2 8 2 9 常用聚类方法及其分类 i x 6 3 6 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：垡链主日期：肿媚易日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名 日期：加多年厂2 ，目驴日 第一章绪论 第一章绪论 搜索引擎是获取信息及解决信息“迷航”问题的有效手段，它涉及到基本的 信息处理、存储、检索以及数据挖掘、机器学习、知识发现等可视化过程，也涵 盖了语音技术、自然语言处理、多媒体技术、语义互联网络等前沿学科知识f 1 3 1 。 本章在充分回顾搜索引擎发展历程的基础上，指出了课题研究的意义、国内外研 究的现状及内容，搜索引擎的工作原理以及本论文的章节安排。 1 1 问题的提出 1 1 1 搜索引擎发展历史 1 1 1 1 萌芽期 1 9 9 0 年，加拿大麦吉尔大学( u n i v e r s i t yo fm c g i l l ) 计算机学院的学生a l a n e m t a g e 等人开发出a r c h i e ( 第一个自动索引互联网上匿名f r p 网站文件的程序) 。 当时，万维网( w o r l dw i d ew g 瞬还没有出现，人们通过f 1 曙来共享交流资源。a r c h i e 能定期搜集并分析f r p 服务器上的文件名信息，提供查找分布在各个f i t 主机中 的文件。用户必须输入精确的文件名进行搜索，a r c h i e 告诉用户哪个f f p 服务器 能下载该文件。虽然a t c h i e 搜集的信息资源不是网页( h t m l ) 文件，但和搜索引辈 的基本工作方式是一样的：自动搜集信息资源、建立索引、提供检索服务。所以， a r c h i e 被公认为现代搜索引擎的鼻祖【1 翔。 1 1 1 2 第一代搜索引擎一目录式搜索引擎 1 9 9 4 年4 月，斯坦福大学( s t a n f o r du n i v e r s i t y ) 的两名博士生，美籍华人j e r r y y a n g ( * 历致远) 和d a v i df i l o 共同创办了y a h o o 。随着访问量和收录链按数的增长， y a h o o 目录开始支持简单的数据库搜索。因为y a h o o 的数据是手工输入的，所以不 能真正被归为搜索引擎，事实上只是一个可搜索的目录。y a h o o 也被称为第一代搜 索引擎的代表1 3 , 5 , 6 。 1 1 1 3 第二代搜索引擎一机器人搜索引擎 1 9 9 3 年m a t t h e wg r a y 开发了w o r l dw i d ew e bw a n d e r e r ，这是第一个利用 电子科技大学硕士学位论文 h t m l 网页之间的链接关系来检测万维网规模的“机器人( r o b o t ) ”程序。开始，它 仅仅用来统计互联网上的服务器数量，后来也能够捕获网址m r l ) 。 1 9 9 4 年初，华盛顿大学( u n i v e r s i t yo fw a s h i n g t o n ) 的学生b r i a np i n k e r t o n 开始 了他的小项目w e b c r a w l e r 。1 9 9 4 年4 月，w e b c r a w l e r 正式亮相时仅包含来自6 0 0 0 个服务器的内容。w e b c r a w l e r 是第一个支持全文搜索的搜索引擎。在它之前，用 户只能通过u r l 和摘要搜索，摘要一般来自人工评论或程序自动提取正文的前1 0 0 个字。 1 9 9 4 年7 月，卡内基梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ) 的m i c h a e lm a u l d i n 将j o h nl e a v i t t 的s p i d e r 程序接入到其索引程序中，创建了l y c o s 。除了相关性排 序外，l y c o s 还提供了前缀匹配和字符相近限制，l y c o s 第一个在搜索结果中使用 了网页自动摘要，而最大的优势还是它远胜过其它搜索引擎的数据量。 1 9 9 4 年底，i n f o s e e k 正式亮相。其友善的界面，大量的附加功能，使之和l v c o s 一样成为搜索引擎的重要代表。 1 9 9 5 年，出现了元搜索引擎( a m e t as e a r c he n g i n er o u n d u p ) 。用户只需提交一 次搜索请求，由元搜索引擎负责转换处理，提交给多个预先选定的独立搜索引擎， 并将各个独立的搜索引擎返回的所有查询结果集中起来处理，再把处理结果返回 给用户。第一个元搜索引擎是w a s h i n g t o n 大学硕士生e r i es e l b e r g 和o r e ne t z i o n i 发明的m e t a e r a w l e r 。 1 9 9 5 年1 2 月，d e c 正式发布a l t a v i s t a 。a l t a v m 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 aa p p l e t s 、搜索a c t i v e xo b j e e t s 。 a l t a v k s t a 也声称是第一个支持用户自己向网页索引库提交或删除u r l 的搜索引 擎，并能在2 4 小时内上线。a l t a v i s t a 最出色的新功能之一是能搜索有链接指向 u r l 盼所有弼站。1 9 9 7 年，a l t a v m t a 发布了一个图形演示系统l i v e t o p i e s ，帮助 用户从成千上万的搜索结果中找到想要的信息。 1 9 9 8 年1 0 月之前，o o o g i e 只是斯坦福大学( s t a n f o r du n i v e r s i t y ) 的一个小项目 b a c k r u b 。1 9 9 5 年博士生t a r r yp a g e 开始学习搜索引擎设计，于1 9 9 7 年9 月注册 了g o o g l e t o m 的域名，1 9 9 7 年底，在s e r g e yb r i n 和s c o t th a s s a n 、a l a ns t e r e m b e r g 的共同参与下，b a c h r u b 开始提供d e m o 。1 9 9 9 年2 月，c , o o g i e 完成了从a l p h a 版到b e t a 版的蜕变。g o o g l e 以网页级别( p a g e r a n k ) 为基础，判断网页的重要性，使 得搜索结果的相关性大大增强。2 0 0 6 年4 月，o o o g i e 宣布其中文名称“谷歌”，这 2 第一章绪论 是c , o o g l e 第一个在非英语国家起的名字。g o o g l e 也被称为第二代搜索引擎的代表。 2 0 0 0 年1 月，两位北大校友，超链分析专利发明人、前i n f o s e e k 资深工程师 李彦宏与好友徐勇( 如州伯克利分校博士后) 在北京中关树创立了百度( b a i d u ) 公司。 2 0 0 1 年8 月发布b a i d u c o l n 搜索引擎b e t a 版，2 0 0 1 年1 0 月正式发布的b a i d u 搜 索引擎，专注于中文搜索【1 ，3 ，5 问。 1 1 1 4 第三代搜索引擎智能化搜索引擎 2 0 0 4 年8 月，门户网站搜狐正式推出全新独立域名的专业搜索网站“搜 狗”( w w w s o g o u c o r n ) ，并声称该搜索引擎是全球首家第三代中文交互式互动搜索引 擎，同时指出第三代搜索引擎具有以下特点【3 】。 1 互动式搜索：在用户查询和搜索引擎返回结果的人机交互过程中，搜索引 擎根据用户的查询内容，智能展开多组相关的主题，帮助用户快速找到相关搜索 结果。 2 分类导航；针对部分查询结果项，扩展到类似或相关网站。 3 查询精确相关：先进的分词引擎，并利用搜狐4 0 0 0 万用户名优化分词引 擎的人名识别。在查询结果中，剔出了页面中仅在链接文字上包含查询词的网页 数据量，收录2 亿中文网页，超过6 0 0 9 l e 收录量。 4 更新速度快：每天更新最重要的网站和新闻。 1 1 2 研究现状 目前搜索引擎在诸多方面发生着深刻的变化，对搜索引擎的评价不在仅仅看 数据库大小、更新频率、检索速度、对多语言的支持这几个基本特性，而是力争 在数据收集、数据存储、智能切词、数据组织等方面的突破。国际国内对搜索引 擎的风险投资主要集中在垂直搜索、非w w w 信息( f 1 田、桌面等类信息的检索) 搜索、多媒体搜索等项目，目前搜索引擎的主要技术发展方向如下： 1 通过智能化、人机交互等方法提高信息查询和检索的精度、有效性、相关 度。 2 基于智能代理和人工自然语言处理的信息过滤和个性化服务。 3 采用p 2 p 等分布式体系结构提高系统规模和性能。 4 重视交叉语言的研究和开发。 比如微软亚洲研究院的互联网搜索与数据挖掘组正在从事以下领域的研究工 作：文本与数据挖掘、网页信息抽取、结构化数据记录抽取、新的搜索排序算法、 3 电子科技大学硕士学位论文 深层互联网搜索与数据挖掘、大规模文本分类与聚类、互联网建模、大规模链接 分析与图分析、网络社区搜索与数据挖掘、对象级互联网搜索、移动搜索以及多 媒体搜索等。并致力于将数据挖掘、机器学习与知识发现技术和信息分析、组织、 检索与可视化过程的结合。微软也在进行包括类似g o o s e 风格的硬盘搜索或者数 据分类技术等旧。 g o o g l e 搜索技术开发主要在两个层面着重突破：一方面从一维到三维，众所 周知，目前使用的搜索都是一维的，而现实世界是以三维形式存在，如何通过关 键词获得平面文字、时间以及空间信息组成的三维信息将成为未来搜索技术发展 的重要目标。另一方面，g o o g l e 推出了其著名的六度空间理论，提出了自己的c c c 发展战略c o m m n i t y ( 社区) 、c o m m u n i c a t i o n ( j $ 信) 、c o l l a b o r a t e ( 作) ，根据六度 空间理论，将把现有的人一信息查找模式推进到人信息人互动搜索架构，让信 息数据结构更叫智能化，架构化m1 5 1 。 1 1 3 搜索引擎的发展趋势 随着w w w 信息的急剧增加，目前的搜索引擎存在界面不够友好、响应时间 长、死链接过多、结果中重复信息及不相关信息过多等问题，难以满足人们的各 种信息需求，搜索引擎将向智能化、个性化、精确化、专业化、交叉语言检索、 多媒体检索等适应不同用户需求的方向发展【1 , 3 矧。 1 智能化的搜索引擎：它是未来搜索引擎的发展方向，被称作是”第三代搜索 引擎”，主要体现在两方面：一是对搜索请求的理解，二是对网页内容的分析。它 利用智能代理技术对用户的查询计划、意图、兴趣方向进行推理，自动进行信息 搜集过滤，自动地把用户感兴趣的、对用户有用的信息提交给用户。这其中也包 含了服务多元化、个性化，结果精确化，交叉语言检索等方面的功能。 2 重视查询结果的精度，提高检索的有效性：解决查询结果过多的现象目前 有以下几种方法：幻构建基于内容的搜索引擎。基于内容的搜索不是根据字形， 而是试图理解用户的请求，同时根据文档的内容选出符合用户要求的文档。即通 过各种方法获得用户没有在查询语句中表达出来的而对用户有用的文档，实现自 然语言的智能查询功能。当前比较成熟的解决方案是依靠语义网络、汉语分词、 句法分析、处理同义词等信息处理技术。b 1 将用户提问转化为系统已知的问题， 然后对已知问题进行解答，以求降低对自然语言理解技术的依赖性。曲用正文分 类技术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣 4 第一章绪论 的类别。d ) 进行站点聚类或内容聚类，减少信息的总量。c ) 让用户对返回结果进 行选择，进行二次查询。 3 实现交叉语言的检索：搜索引擎对多种语言的数据库进行交叉语言信息检 索，返回能够回答用户问题的所有语言的文档。配上机器翻译，就可使返回结果 以用户熟悉的语言显示。该技术目前还处于初步研究阶段，其难点在于语言之间 在表达方式和语义对应上的不确定性。 4 提供对自然语言检索的支持：为了提高搜索引擎对用户检索提问的理解， 就必须有一个好的检索提问语言，为了克服关键词检索和目录查询的缺点，现在 已经出现了自然语言智能答询。如g o o g l e 有专用于回答问题的g o o g l ea n s w e r ， 微软有a n s w e r b o t 等。用户可以输入简单的疑问旬，比如”h o wc a nk i l lv i r u so f c o m p u t e r ? ”。搜索引擎在对提问进行结构和内容的分析之后，或直接给出提问的答 案，或引导用户从几个可选择的问题中进行再选择。自然语言的优势在于，一是 使网络交流更加人性化，二是使查询变得更加方便、直接、有效。比如上面的例 子中，如果用关键词查询，多半人会用”v i r u s ”这个词来检索，结果中必然会包括各 类病毒的介绍、病毒是怎样产生的等等许多无效信息，而用”h o wc a nk i l lv i r u so f c o m p u t e r ? ”，搜索引擎会将怎样杀病毒的信息提供给用户，提高了检索效率。 5 多媒体搜索引擎：网络资源丰富多彩，具有很多类型的信息，用户需要的 信息也不完全是网页的形式，从用户的角度来看，必然要求搜索引擎能够覆盖更 多的网络资源。现在有很多搜索引擎已经提供了网页、新闻、图片、音乐等资源 搜索，当然范围还可以更广，再如可以搜索新闻组、软件、f f p 、f l a s h 、论文等等。 6 专业化搜索引擎：是为了专门收录某一行业、菜一学科、某一主题和某一 地区的信息而建立，非常实用，如有商务查询、企业查询、人名查询、电子邮件 地址查询和招聘信息查询等等。这种专业化的搜索引擎是将来的方向之一。 7 桌面型搜索引擎：这类引擎实际上是一个软件，下载安装后放在电脑桌面 上，用户不用频繁打开浏览器，而只要通过它就能完全实现搜索过程，更甚者它 可以同时搜索本地、局域网和互联网上的信息。它完全越过传统的搜索模式，越 过浏览器，真正实现让搜索无处不在。 此外还有一些其它值得注意的发展技术，如元搜索引擎，移动代理，语音检 索技术等。 5 电子科技大学硕士学位论文 1 2 搜索引擎原理 1 2 1 搜索引擎的工作原理 搜索引擎在解决海量信息的检索中发挥着越来越重要的作用，它定期( 比如一 个月) 从w e b 上抓取网页信息，并以一定的方式建立索引数据库，以此来方便人们 查找所需要的信息。传统搜索引擎( 第二代搜索引擎) 的结构可以分为收集器 ( s p i d e r ) 、索引器( h d e x c r ) 、搜索器( s e a r c h e r ) 三大部分，如图1 - 1 所示f 4 1 川： 州拇 图1 - 1 搜索引擎的系统结构图 它的工作过程如下： 1 收集器从互联网上抓取网页：利用能够从互联网上自动收集网页的网络蜘 蛛程序，自动访问互联网，并沿着网页中的u r l 信息再抓取其它的网页。重复这 个过程( 理论上是可以爬行完所有w e b 网页的) ，并把抓取下来的网页信息收集到某 个临时文件中 2 建立索引数据库：由索引器程序对收集回来的网页进行分析，提取其中的 信息( 包括网页所在u r l 、编码类型、页面内容包含的关键词、关键词位置、生成 时间、大小、与其它网页的链接关系等) 。根据一定的相关度算法进行相关度的计 算，得到网页中的关键词的相关度( 或重要性) ，然后用这些信息建立网页索引数据 库。 3 用户提交查询需求：通过用户界面接口，提交相应的查询需求。目前大多 是通过关键词进行查询的，搜索器需要先对这些输入的关键词进行解析，然后再 执行查询操作。 4 对搜索结果进行排序处理：网页中的关键词在索引库中都建立倒排记录。 6 第一章绪论 查询时，首先找到相应的关键词，然后提取该关键词的相关信息，根据相关度值 进行排序。相关度越高，排名越靠前。 5 搜索结果的显示：页面生成系统将搜索结果的链接地址和页面内容摘要等 内容组织起来返回给用户。 搜索引擎的详细处理流程可以用图1 2 来表示。 图1 - 2 搜索引擎系统流程图 “网络蜘蛛”从互联网上抓取网页，把网页送入“网页数据库”，从网页中“提取 i 瓜i 芦，把u r l 送入“u l u 数据库”，“蜘蛛控制”得到网页的u r l ，控制“网络蜘蛛” 继续抓取其它网页，反复循环直到把所有的网页抓取完毕。系统从“网页数据库” 中提取文本信息，送入“文本索引”模块建立索引，形成“索引数据库”。同时进行“链 接信息提取”，把链接信息( 包括锚文本、链接本身等信息) 送入“链接数据库”，为“网 页评级”提供依据。“用户”通过提交查询请求给“查询服务器”，服务器在“索引数据 库”中进行相关网页的查找，同时“网页评级”把查询请求和链接信息结合起来对搜 索结果进行相关度的评价，通过“查询服务器”按照相关度进行排序，并提取关键词 的内容摘要，组织最后的页面返回给“用户”。 7 电子科技大学硕士学位论文 1 2 2 搜索引擎采用的主要技术 1j 2 2 1 网络蜘蛛 网络蜘蛛即w 曲s p i d e r ，网络蜘蛛是通过网页的链接地址来寻找网页的i 跗0 1 ， 从网站某一个页面( 通常是首页) 开始，读取网页的内容，找到在网页中的其它链接 地址，然后通过这些链接地址寻找下一个网页，一直循环下去，直到把这个网站 所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可 以用这个原理把互联网上所有的网页都抓取下来【1 6 1 7 1 。 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先。广度 优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个 链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方式，因为这个 方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网络蜘蛛会从起 始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始 页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。 1 。2 2 2 信息获取模型 信息获取模型给出了文档的标识、查询的标识以及查询与文档的匹配过程。 目前大多数获取模型依赖于布尔模型，面在实验室用得最多的是向量空间模型， 其他信息获取模型还有概率论模型、神经网络模型、聚类模型、基于规则的模型、 模糊模型和语义模型等【1 7 1 。 1 2 2 3 文档预处理 文档预处理的过程可以用图1 - 3 来表示，大致可以分为以下几个步裂8 ，9 捌。 等。 图1 - 3 文档预处理过程 1 文本的语法分析，处理文本中的数字、连接符、标点符号和字符的大小写 2 无用词汇的删除，过滤掉那些对于信息获取过程来说区分能力度低的词汇。 3 词干提取，去除词缀( 前缀和后缀) ，这样可以允许获取的文档包含一些查 8 第一章绪论 询关键词的变换形式。 4 索引词项词干的选择，在选择的时候通常按照单词的习惯用法，实际上名 词往往要比形容词、副词和动词包含更多的语义。 5 构造词项的分类结构，例如词典或者结构提取，利用它可以进行查询的扩 展。 一在中文信息的获取过程中，还要利用中文分词技术对文本进行预处理。 1 2 2 4 文件索引与索引压缩 当文本信息库的容量很大时，如果要快速有效获取这种文本，那么就需要使 用某种特定的索引技术。一种简单而常用的文本索引结构是倒排文件。该种文件 结构适用于简单的单词匹配方式。 倒排文件通常由以下几个部分组成： 1 一个包含信息库中的文本中的所有不同单词( 也叫做词汇表) 的向量 2 对于词汇表中的每个单词，有一张包含这个单词的所有文档佣文档号来标 示1 组成的列表。每个列表中的文档根据文档号的大小升序排列。查询执行的时间 与访问索引所需要的时间密切相关。 倒排文件的构造过程可以表述为： 把所有已知的单词都存放在一棵树结构中。在构造倒排索引的时候，对于每 个读入的单词，首先在该树中查找，如果没有找到，就在该树种加入一个空的词 汇出现情况列表；否则将该词汇的新位置加入到树中对应词汇出现情况列表的末 尾。在对要加入的文本中的每个单词都处理完以后，该树被写入到磁盘。在实际 操作中，索引一般被分成两个文件存放。第一个文件顺序存放词汇出现情况列表， 第二个文件以字典序存放树中的词汇，还为每个词汇存放一个指向第一个文件中 该单词对应的词汇出现情况列表的指针。 文本压缩是指用较少的位或字节来标示文本，这样将可以显著地减少计算机 中存储文本的空间大小。有两种文本压缩的方法：统计方法和字典方法。 1 2 2 5 排序技术 搜索引擎体系结构中每一部份的实现都较复杂，每个搜索引擎的具体实现也 不尽相同。这其中最能体现搜索引擎设计思想的就是网页排序系统，因为面对常 常是数以十万计的返回结果，用户一般只会去点击排在前一百位的搜索结果。因 此搜索引擎最关注的不是如何返回尽可能多的结果，而是尽可能的将最有可能与 9 电子科技大学硕士学位论文 用户搜索请求相关的链接放在前一百位。常用的网页排序算法有p a g e r a n k 算法、 h i t s 算法、a r c 算法、域值算法、s a l s a 算法、b f s 算法、p h l t s 算法、贝叶斯 算法、r e p u t a t i o n 算法等。 1 2 2 6 搜索技术 倒排文件的搜索算法一般分成以下三步： 1 词汇查找，将查询串中的单词和模式分割成独立的部分，短语和近似查询 串被分割成单个词汇。 2 查找词汇出现情况：获取与查询串中所有词汇相关的出现情况列表。 3 词汇出现情况的操作：主要是通过对上一步中获取的词汇出现情况的操作 实现短语查询、近似查询和布尔查询。 1 3 搜索引擎系统的性能评价 早在1 9 6 6 年c l e v e r d o n 就给出了信息系统的六个主要评价指标，常常被用来 衡量搜索引擎的系统性能，它的详细表述如下【l q ： 1 信息的覆盖率，即该系统包含信息的范围、数量： 2 系统响应时间，即查询请求与结果返回之间的平均时间； 3 结果输出方式，即结果是以仔么样的格式输出的； 4 用户获取搜索结果所需付出的努力； 5 召回率，是指检索出的相关文档数和文档库中所有的相关文档数的比率， 衡量的是检索系统( 搜索引擎) 的查全率； 6 精度，是检索出的相关文档数与检索出的文档总数的比率，衡量的是信息 获取系统的查准率。 其中指标1 到4 是比较容易得到的，而指标5 和6 反映了信息获取系统的效 力，也就是衡量信息系统获取相关文档同时阻止不相关文档的能力。一般说来信 息获取系统的效力越高，其满足用户需要的能力也就越高。 1 。4 课题的研究意义 本文是在对开源全文检索包l u c e n e 及开源搜索工具n u t c h 的充分分析的基础 上形成的，使初涉搜索引擎领域专业的技术人士能更好地理解搜索引擎的原理、 第一章绪论 架构设计、细节实现等。同时文中对搜索引擎自c h 结构的更改、搜索结果的聚 类处理、在搜索引擎性能提高等方面的解决方法具有一定的理论及实践指导价值。 1 5 本论文所做的主要工作 本论文的主要工作如下： 1 分析了文本检索的两大主要部分：索引建立及搜索过程。并以开源项目 l u c e n e 为背景，详细阐述了他们的实现过程，包括索引文件格式、索引建立、搜 索过程以及为提高索引建立速度与搜索性能而采用的一些常用数据结构。 2 详细分析了搜索引擎的工作原理及组成结构，并通过开源项目n u t c h ，介 绍搜索引擎的设计与实现：包括网络蜘蛛、网页解析、链接分析、索引建立、搜 索过程以及为提高索引与搜索的性能而采用的常用数据结构。 3 指出了目前搜索引擎的摘要在信息提取上存在的不足，为此提出了以文本 的语义特征词来替换摘要信息。论文中还对语义特征词的提取进行了理论上的分 析，并实现了其中的部分功能。 4 文中对后缀树的结构进行了详细的阐述，提出用完全予串来表示文本的语 义特征。并且实现了后缀数组的构造，左、右完全子串及完全子串的提取。 5 对搜索引擎的聚类过程、以及常用的聚类算法进行了比较，并对一种较常 用的基于奇异值分解的文本聚类算法i a n g o 作了详细的剖析。 6 为提高搜索结果聚类的速度及聚类的精度。文中对开源搜索引擎n u t c h 的 体系结构作了相应的更改，包括页面的预处理、文档语义内容的提取、索引及搜 索结构的修改等。最后以我校内网作为爬行目标，给出了实验结果。 1 6 本论文的章节安排 第二章以开源文本检索包l u c e n e 为例，详细阐述了文本检索的设计与实现， 为后文搜索引擎的分析打下基础。该章的重点是索引与搜索的建立，其中包括以 下内容：l u c e n e 系统结构简介、索引文件的格式、索引的建立及搜索处理过程。 同时对一种用于按权值检索的有效数据结构l 优先队列作了阐述。 第三章以开源检索工具n u t c h 为例，详细阐述了搜索引擎的工作流程，包括： 搜索引擎n u t c h 的结构、n u t c h 的可扩展架构一柏件体系以及n u t c h 的分步式文件 处理结构h a d o o p ，文章中还对用于文本检索的有效结构后缀树及后缀数组作了阐 1 1 电子科技大学硕士学位论文 述。本章的重点在n u t c h 的工作流程。 第四章对n u t c h 的结构作了必要修改，以便于更加准确的表示摘要信息及提 高结果聚类性能。包括文本的表示，特征词的提取，n u t c h 结构的更改以及文档聚 类。 文章的最后对全文的结构作了总结并对本项目的设计存在的不足及将来的工 作进行了分析。 第二章索引与搜索 2 1 索引概述 第二章索引与搜索 第一章中已对搜索引擎采用的倒排文件进作了说明，这里以一个简单的实例 详细分析这一过程是怎样进行的，以便于后文的分析。 假设有两个文档： d o c l ：id i de n a c tj u l i u sc a e s a r1w a sk i l l e di ft h ec a p i t o l ；b r u t u sk i l l e dm c d o c 2 ：s ol e ti tb ew i t hc