（计算机软件与理论专业论文）主题搜索引擎设计与研究.pdf

摘要 摘要 由于w e b 上海量的信息处于不断的变化中，通用搜索引擎己经很难再为用户 提供一个准确并且更新及时的信息搜索服务，其局限性在于它试图索引全部w e b 并且试图服务于所有主题的查询请求。而主题搜索引擎只覆盖与特定主题相关的 w e b 区域，这样它搜索的可以更深，搜索的周期可以更短，因此能满足用户对获 取信息资源快速、准确的性能要求。面向主题的搜索研究正成为越来越热门的课 题。 本文首先对搜索引擎的历史、分类、发展现状及其趋势做了概要介绍；然后 以搜索引擎的体系结构、工作原理为主线在全文展开我们的研究工作。我们分别 对爬虫技术、h t m l 解析技术、分词技术做了详细的分析与研究。对页面链接、 页面分布的特征也做了分析。 本文设计和实现了一个页面主题相关性判定系统。它的系统结构植根于开源 软件n u t c h ，在健壮性与简单易用性上得到了保证。其核心思想是：把关键词加权 和页面进行主题相关性判定。其中运用到了向量空间模型与关键词集技术。 本文还提出了一个较为新颖的概念：关键词和页面间的q 一距离。形象的说 就好象网络信息交互中的“电阻”将关键词所表达的真实意图和与之匹配的页面 生硬的隔离开了或者说拉远了，这个概念在主题搜索领域具有独特的实用价值， 可以有效地提高信息搜索匹配的智能化程度，但是在实现方面还有待进一步的突 破。 本文在面向主题的搜索引擎方面进行了一些有意义的研究和尝试，并为该领 域进一步的研究工作打下了基础。 关键词：主题搜索，向量空间模型，主题判定，关键词集 a b s t r a c t a b s 仃a c t d u et ot h ec u r r e n tl a r g es c a l ea n dd y n a m i co ft h e 冈哪g e n e r a lp u r p o s es e a r c h e n g i n ec a n n ol o n g e rp r o v i d eac o m p r e h e n s i v ea n du p t o - d a t es e a r c hs e r v i c eo ft h e w e b i nc o n t r a s tt og e n e r a lp u r p o s es e a r c he n g i n e , w h i c ha t t e m p tt oi n d e xt h ew h o l e w e b ，t o p i c - s p e c i f i cs e a r c he n g i n e sc a nc o v e rs p e c i a l i z e dt o p i c si nm o r ed e p t ha n d k e e pt h ec r a w lm o r ef r e s h l y t h er e s e a r c ho l lat o p i c - s p e c i f r cs e a r c he n g i n ei sg o i n g t 0b ea p o p u l a r t a s k t h i sp a p e rg i v e sag e n e r a li n t r o d u c eo f t h eh i s t o r y , c l a s s i f i c a t i o n ，d e v e l o p m e n ta n d t h et r e n do ft h es e a r c he n g i i l ea tt h ef i r s t ；t h e nma ：k et h er e s e a r c hw o r kb a s e d0 1 1t h e s y s t e ms t r u c t u r ea n dt h ep r i n c i p l eo fw o r ko fs e a r c he n g i n e t h et e c h n o l o g yo nt h e c r a w l e r , h t m lp a r s e r , a n dc h i n e s ew o r d ss e g m e n t a t i o ni sd i s c u s s e da n da n a l y z e d s e p a r a t e l y a l s og i v e sa n a l y s i so nt h ep a g el i n ka n dt h es p e c i f i co ft h ed i s t r i b u t i o no f t o p i cp a g e s t h er e l a t i v i t yj u d g i n gs y s t e mb e t w e e nt h ep a g ec o n t e n ta n dt h et o p i ci sd e s i g n e d a n di m p l e m e n t e di nt h i sp a p e r f o rs y s t e ms t r u c t u r ei sb a s e do nt h eo p e ns o f t w a r e n u t c h ，t h ec h a r a c t e ro fr o b u s ta n dc o n v e n i e n ti sg o o dm a i n t e n a n c e i nt h i sw o r ki t s o i y f et h i n k i n gi s ：g i v et h ew e i g h to nt h ek e y w o r d s ，a n dm a k et h ej u d g m e n tt h r o u g ht h e r e l a t i v i t y j u d g i n gs y s t e mb e t w e e nt h ep a g ec o n t e n ta n dt h et o p i c v e c t o rs p a c em o d e la n d k c y w o r d sp l a ya ni m p o r t a n tr o l ei nt h e j u d g i n gs y s t e m an o v e lc o n c e p ti sp r o p o s e di nt h i sp a p e r ：t h ef l - - d i s t a n c eb e t w e e nk e y w o r d s a n dp a g e v i v i d l ys p e a k i n gt h ef l - - d i s t a n c e d ot h ej o b l i k ear e s i s t a n c ei nac i r c u i t i ts e p a r a t e so rp u l l sa p a r tt h ew w wi n f o r m a t i o nr e c i p r o c a l ，i no t h e rw o r d st h ef a i t h f u l p u r p o s ee x p r e s s e db yt h ek e y w o r d sc 孤n o tm a t c ht h er e l e v a n tp a g ec o n t e n t t h i s c o n c e p th a sau n i q u ev a l u eo np r a c t i c a lu t i l i t yi nt h et o p i c - s p e c i f i cs e a r c h , i tc 锄 i m p r o v et h ei n t e l l i g e n c eo ni n f o r m a t i o nm a t c he f f e c t i v e l y , b u ti t s t i l ln e e df u r t h e r r e s e a r c hw o r k t h i s p a p e rs h o w ss o n l em e s n i n g f mr e s e a r c ha n da p p r o a c hw o r k , t h ef x l r t h e r r e s e a r c ho nt h i sm e dc a nd e v e l o pb yt h eg r o u n d w o r kw h i c hi sc o m p l e t e d k e y w o r d s ：t o p i c - s p e c i f i cs e a r c h , v s m ，t o p i c j u d g e m e n t ，k e y w o r d ss e t i i i 前言 信息时代带来的信息爆炸，很难想像现在的i n t g a a c t 上到底有多少信息，又有 多少信息正在产生并且上传到这个网络中。仅仅依赖于人类自身生理范围内的检 索能力在互联网中查找信息，我们几乎等同于信息社会中的盲人，无所适从。不 断发展的数据收集、数据结构、数据存储、数据检索以及等等若干技术因素催生 了搜索引擎这个“网络精灵”的出现。 搜索引擎是伴随w w w 网络出现的检索网上信息资源的新工具。实质上是一 种网页网址检索系统，有的提供分类和关键词检索途径，有的仅提供关键词检索 途径。它根据检索规则和从其他信息服务器上得到数据并对数据进行加工处理， 自动建立索引，并通过检索接口为用户提供信息查询服务，能够自动对w w w 资 源建立索引或进行主题分类，并通过查询语法为用户返回匹配资源的系统。搜索 引擎主要是由c r a w l e r 、s p i d e r 、w o r m 、r o b o t 等程序自动在因特网上漫游，不断 搜集各类新网址及网页，形成数以千万甚至上亿条记录的数据库。它是通过采集 标引众多网络站点来提供全局性网络资源控制与检索机制、将全球w w w 网络中 所有信息资源作一完整的集合、整理和分类、方便用户查找所需信息的网络检索 软件。 说来容易，可是搜索引擎其技术细节却如“塘中荷”，远观很美，近其身却 很难难就难在它要面对的是海量的、或者说是无限膨胀中的数据，它要提供的 是高效的、与当前快节奏生活合拍的服务，它依托的又是当前最新的、最前沿的 技术。自然而然，它在发挥其不可替代的信息检索作用的同时，又戴上了一层神 秘的面纱。本文的目的是研究主题搜索引擎技术实现，设计出了页面主题相关性 判定系统。 图目录 图目录 图2 一l 搜索引擎组成结构8 图2 2 专业搜索引擎系统结构1 4 图3 - 1 通用爬虫流程图1 9 图3 - 2 通用爬虫结构2 0 图3 - 3w e b 超链接结构示意图2 l 图3 - 4 主题爬虫结构示意图2 3 图3 - 5 普通爬虫与主题爬虫扩展链接策略比较3 0 图4 1h t m l 解析器的外部结构3 4 图 2h t i 也解析器的内部结构3 5 图p l 文本向量图5 6 图6 - 2 基于n u t c h 的主题搜索引擎系统6 1 图6 3 对网页进行提取6 4 图争4 对文本内容的分析6 6 图6 - 5 搜索界面6 8 图6 6 搜索结果6 9 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：嘲 日期扣d 年i z , 9 驴日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：鲨! 鱼导师签名： 日期：2 口口年，z 月矽日 第一章绪论 1 1 搜索引擎的历史 第一章绪论 互联网的迅猛发展、w e b 信息的增加，用户要在信息海洋里查找信息，就象 大海捞针一样，搜索引擎技术恰好解决了这一难题。目前，搜索引擎技术正成为 计算机工业界和学术界争相研究、开发的对象。搜索引擎( s e a r c he n g i n e ) 随着 w e b 信息的迅速增加，从1 9 9 5 年开始逐渐发展起来的技术。据发表在科学 杂志1 9 9 9 年7 月的文章w e b 信息的可访问性估计，全球网页超过8 亿，有 效数据超过9 t g ，并且仍以每4 个月翻一番的速度增长。( 当您看到这篇文章的时 候已达到1 1 5 亿，由意大利比萨大学a n t o n i og u l l i ( 现任a s kj e e v e s 公司高级产 品经理) 和爱荷华州立大学a l e s s i os i g n o r i n i a l s o 共同完成) 用户要在如此浩瀚的 信息海洋里寻找信息，必然会“大海捞针”无功而返。搜索引擎正是为了解决这 个“迷航”问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现信 息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信 息导航的目的，一般包括信息搜集、信息整理和用户查询三部分。从用户的角度 来看，它就是一个帮助人们进行信息检索的工具。搜索引擎提供的导航服务已经 成为互联网上非常重要的网络服务，搜索引擎站点也被美誉为“网络门户”。搜索 引擎技术因而成为计算机工业界和学术界争相研究、开发的对象。 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 i a n e m t a g e ，p e t e r d e u t s c h ，b i l l w h e e l a n 发明的a r c h i e ( a r c h i e f a q ) 。一个可以用文件 名查找文件的系统，于是便有了a r c h i e 。a r c h i e 是第一个自动索引互联网上匿名 f t p 网站文件的程序，但它还不是真正的搜索引擎。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月【”。当时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 永远改变了搜索引擎的定义o j ：a l t a v i s t a 是第一个支 持自然语言搜索的搜索引擎，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 d e s 、搜索j a v a a p p l e t s 、 电子科技大学硕士学位论文 搜索a c t i v e xo b i t s 。 1 9 9 8 年，g o o g l e 在p a g er a n k 、动态摘要、网页快照、d a i l yr e f t e s h 、多文档 格式支持、地图股票词典寻人等集成搜索、多语言支持、用户界面等功能上的革 新，象a l t a v i s t a 一样，再一次永远改变了搜索引擎的定义。 现阶段，出现a s kj e e v e s ，b a i d u c o m ，g o t o t o m ，m y s i m o n ，d i t o 等内容类 别不同的搜索引擎。 1 2 搜索引擎的概念及其功能、分类 1 2 1 搜索引擎的概念 搜索引擎( s e a r c he n g i n e ) 啪实质是个专用的w w w 服务器，它存有庞大的索 引数据库，收集了全世界成千上百万个w w w 主页的文字信息。为了收集这些信 息，有个自动搜索程序，沿着w w w 的超链接，经常搜索整个w w w 上的主页， 然后为这些主页上的文字建立索引并送回集中管理的索弓i 数据库，索引信息包括 文档的w w w 地址，每个文档单字出现的频率、位置等。 1 2 2 搜索引擎的功能 搜索引擎的第一个功能是收集信息建立索引数据库，并自动跟踪信息源的变 动，不断更新索引记录，定期维护数据库。搜索引擎的第二个功能也是最主要的 功能是提供网络的导航与检索服务。还为用户提供多种信息服务，如：广告、地 图等。 1 2 3 搜索引擎的分类 根据信息覆盖范围及适用用户群分类邮1 综合性搜索引擎：主要以w e b 网页和新闻组为搜索对象，信息覆盖范围广， 适用用户广泛。如：y a h o o ，朋t a s t a ，i n f o s e e k 等。 专用性搜索引擎：w w w 上搜索引擎作为i n t e r n e t 信息搜索工具，在运行着综 合性搜索引擎的同时，还针对特定的用户群推出专用性搜索引擎，可供查找某一 特定领域的信息。如：v e j a n e w s ，l i s z t ，s o f i s e e k 等。 根据组织信息方式分类 目录式分类搜索引擎( 网站级) ：目录式分类搜索引擎( d i r e c t o r y ) 将信息系统加 2 第一章绪论 以归类，利用传统的信息分类方式来组织信息，用户按类查找信息。最有代表性 的为y a h o o 。特点：网页内容丰富，有较高的查准率，但其查全率低，搜索范围较 窄。 全文搜索引擎( 网页级) ：指能够对网站的每个网页中的每个单字进行搜索。 特点是查全率高，查准率低，搜索范围较广，提供的信息多而全，缺乏清晰的层 次结构，查询结果中重复链接较多。典型的为：a l t a v i s t a 。 分类全文搜索引擎：是针对全文搜索引擎和目录式分类搜索引擎的缺点而设 计的，通常是在分类的基础上再进行全文检索。现在大多数搜索引擎都属于此类。 智能搜索引擎：这种搜索引擎具备符合用户实际需要的知识库，搜索时，引 擎根据己有的知识库来理解检索词的意义并以此产生联想，从而找出相关的网站 或网页。同时，智能搜索引擎还具有一定的推理能力，它能够根据知识库的知识， 运用人工智能方法进行推理。这样大大提高查全率和查准率。比较成功的搜索引 擎有：f s a ，e l o i s e 和f a q f i n d e r 。 根据搜索范围分类 独立搜索引擎：独立搜索引擎建有自己的数据库，搜索时通常只是检索自己 的数据库，并根据数据库的内容反馈出相应的查询信息或链接站点。如：y a h o o ， l y c o s ，i n f o s e e k ，a l t a v i s t a 等。 元搜索引擎：元搜索引擎是一种调用其它的独立搜索引擎的引擎。搜索时， 它利用用户的查询词同时去查询若干个其它搜索引擎，作出相关度排序后，将查 询结果显示给用户。其注意力放在改进用户的界面及用不同的方法过滤它从其它 搜索引擎接收到的相关文档，包括消除重复信息。典型的有：m e t a s e a r c h ， m e t a c r a w l e r ，d i g i s e a r c h 等。用户利用这种搜索引擎可以获得更多、更全面的网址。 但缺点是查询时间长。元搜索引擎又可以分为两类：串行处理引擎和并行处理引擎。 所谓串行处理就是依次将查询词传送给几个独立的引擎并进行处理，而并行处理 是指同时将查询词传送给几个独立的引擎并进行搜索。 1 2 4 搜索引擎的发展阶段 面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫 不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。 因此它也成为除了电子邮件以外最多人使用的网上服务。 搜索引擎技术伴随着w w w 的发展是引人注目的。搜索引擎大约经历了三代 3 电子科技大学硕士学位论文 的更新发展： 第一代搜索引擎出现于1 9 9 4 年。这类搜索引擎一般都索引少于1 ，0 0 0 ，0 0 0 个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一股都要等 待1 0 秒甚至更长的时间。在实现技术上也基本沿用较为成熟的取( i n f o r m a t i o n r e t r i e v a l ) 、网络、数据库等技术，相当于利用一些已有技术实现的一个w w w 上 的应用。在1 9 9 4 年3 月到4 月，网络爬虫w o r l d w i d e w e b w o l i t l ：( 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 次查询。 自1 9 9 8 年到现在，出现了个搜索引擎空前繁荣的时期，我们统称这一时期 的搜索引擎为第三代搜索引擎。第三代搜索引擎的发展有如下几个特点： 索引数据库的规模继续增大，一般的商业搜索引擎都保持在几千万甚至上 亿个网页。 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的 垂直门户站点开始使用该技术。 由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的 研究又可以分为两类：一类是对超文本链的分析，在这方面s t a n f o r d 大学的g o o g l e 系统6 1 和i b m 的c l e v e r 系统f - q 作出了很大的贡献：另一类是用户信息的反馈， d i r e c t r i t 系统采用的就是这种方法。 开始使用自动分类技术。n o r t h e r nl i g h t 和i n k t o m i 的d i r e c t o r ye n g i n e 都在 一定程度上使用了该技术。 在2 0 0 3 年搜索引擎大会上，按照o o o g l e 公司总裁l a r r y p a g e 的演讲，g o o g l e 正在用3 , 0 0 0 台运行l i n u x 系统的个人电脑在搜集w e b 上的网页，而且以每天3 0 台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。每台微机运 行多个爬虫程序搜集网页的峰值速度是每秒1 0 0 个网页，平均速度是每秒4 8 5 个 网页，一天可以搜集超过4 ，0 0 0 ，0 0 0 网页。但是，互联网已经有了2 0 亿网页以 及5 ，5 0 0 亿不可见网页( 至今不能被通用搜索引擎检索到) ，并且在以每天千 万页的速度增长。现在搜索引擎代表着交流的一个重要的进步，向我们提供了搜 4 第一章绪论 索增量信息的有效手段。调查发现，对于8 5 的搜索引擎用户来说，他们这样来 使用搜索引擎：顾客用搜索引擎来定位信息以及购买商品，而研究者使用搜索引 擎来了解他们研究领域的最新进展。但是，对于这些用户，现阶段搜索引擎存在 这些缺陷： 搜索引擎的覆盖范围降低：搜索引擎越来越难提供一个涵盏范围广泛的信 息了。最大的搜索引擎如g o o s e ，a l t a v i s t a 等也只可以索引静态网页的- - d 部分， 没有一个搜索引擎可以检索出可预期的总网页数的1 6 。 平衡访问：搜索引擎主要用来检索主流网站。他们也更容易检索本国网站， 而其它地区的网站则非优先考虑( a l t a v i s t a 是一个例外) 。同时，他们更容易检索 商业网站而非教育网站。 检索内容过时：通过一个主搜索引擎来更新或修改所能检索的内容可能要 花几个月。 1 2 5 搜索引擎的发展趋势 搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、人工智 能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理 等多领域的理论和技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用 户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度 关注，目前的研究、开发十分活跃，并出现了很多值得注意的动向。 一、提高信息查询结果的精度和检索的有效性 用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看 结果是否和自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十万、 几百万篇文档，用户不得不在结果中筛选。解决查询结果过多的现象目前出现了 几种方法：一是通过各种方法获得用户没有在查询语句中表达出来的真正用途， 包括使用智能代理跟踪用户检索行为，分析用户模型；使用相关度反馈机制，使 用户告诉哪些搜索引擎文档和自己的需求相关( 及其相关的程度) ，哪些不相关，通 过多次交互逐步求精。二是用文本分类( t e x tc a t e g o r i z a t i o n ) 技术将结果分类，使 用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。三是进行站点 类聚或内容类聚，减少信息的总量。 二、基于智能代理的信息过滤和个性化服务 信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模 5 电子科技大学硕士学位论文 型( 如w e b 知识、信息处理、与用户兴趣相关的信息资源、领域组织结构) 、用户 模型( 如用户背景、兴趣、行为、风格) 知识进行信息搜集、索引、过滤( 包括 兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、对用户有用的信息提交给 用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而提供 个性化的服务。智能代理可以在用户端进行，也可以在服务器端运行。 三、采用分布式体系结构提高系统规模和性能 搜索引擎的实现可以采用集中式体系结构和分布式体系结构，两种方法各有 千秋。但当系统规模到达一定程度( 如网页数达到亿级) 时，必然要采用某种分 布式方法，以提高系统性能。搜索引擎的各个组成部分，除了用户接口之外，都 可以进行分布：搜索器可以在多台机器上相互合作、相互分工进行信息发现，以 提高信息发现和更新速度；索引器可以将索引分布在不同的机器上，以减小索引 对机器的要求，检索器可以在不同的机器上进行文档的并行检索，以提高检索的 速度和性能。 四、重视交叉语言检索的研究和开发 交叉语言信息检索是指用户用母语提交查询，搜索引擎在多种语言的数据库 中进行信息检索，返回能够回答用户问题的所有语言的文档。如果再加上机器翻 译，返回结果可以用母语显示。该技术目前还处于初步研究阶段，主要的困难在 于语言之间在表达方式和语义对应上的不确定性。但对于经济全球化、互联网跨 越国界的今天，无疑具有很重要的意义。 1 3 本文的主要工作和组织 主要研究内容： 在仔细研究当前主题搜索引擎相关文献的基础上，对搜索引擎的重要方法和 系统架构有了全面的认识和理解；结合主题搜索引擎发展现状，抓住页面的主题 相关性判定，对主题搜索的重要性以及如何构建、设计主题页面相关性判定等系 列关键问题展开研究工作。 最后，分析了本系统的不足，提出了改进措施，并对后期工作进行了展望。 论文的结构安排如下： 第一章绪论。介绍了搜索引擎的历史、发展阶段与趋势，并对搜索引擎的 概念、功能、分类傲了简略的介绍。 6 第一章绪论 第二章搜索引擎基本理论。对搜索引擎的基本理论作出了分析；比较分析 了通用搜索引擎与专业搜索引擎在系统结构、各自优劣上的异同。最后引入了面 向主题的搜索引擎研究，对其产生背景和发展现状做了介绍。 第三章主题爬虫相关技术。研究了爬虫的基本理论；对通用爬虫和主题爬 虫分别建立了模型；深入分析了与爬虫相关的技术以及他们的工作流程，削析了 主题爬虫与普通爬虫的在原理和结构上的区别；结合自己设计的系统，分析和讨 论了爬虫与u r l 主题相关性几种常用算法并提出了基于链接分析和文本分析以及 网页分布特征相结合的思想。 第四章h t m l 解析器与分词技术实现。从一个通用h t m l 解析器( j p a r s e ) 入手，分别对h t m l 解析器的组成部分进行了详细的分析；在分词部分，在n u t h 中利用j a v a c c 构造语言分析模块韵设计架构。 第五章w e b 页面链接与分布特性分析研究。介绍了目前几种运用广泛的基 于链接分析的算法；分析了它们的基本原理；对与主题页面相关性判定关系紧密 的主题页面分布特征做出了详细的分析并且指出了可行的解决方法。 第六章主题搜索引擎关键技术设计实现。对系统实现采用的理论技术作出 了分析研究；给出了系统原型的设计实现框架；针对现有的大型通用搜索引擎存 在的闯题，提出了“关键词集和页面间的q 距离”的概念。 第七章总结与展望。对本文作了总结，并就进一步需要研究的问题和研究 方向进行了展望。 7 电子科技大学硕士学位论文 第二章搜索引擎基本理论 2 1 搜索引擎基本结构、工作原理 2 1 1 搜索引擎组成结构 索引器 u 索引数据库 l 检索器 u 用户接口 图2 - 1 搜索引擎组成结构 2 1 2 搜索引擎的工作原理 当今搜索引擎的主流是基于r o b o t 的网页搜索系统，搜索引擎的原理，可以 看作三步：从互联网上抓取网页一建立索引数据库一在索引数据库中搜索排序， 如上图2 - 1 。 搜索引擎位于信息检索系统层次分类的底层，以w e b 信息为处理对象，虽然 各个搜索引擎具体实现不尽相同，但一般包含5 个基本部分：r o b o t 、分析器、索 第二章搜索引擎基本理论 引器、检索器和用户接口。 r o b o t ( s p i d e r c r a w l e r w a n d e r ) 【8 】：采用广度优先( 或者深度优先) 的策略 对w e b 进行遍历并下载文档，系统中维护一个超链接队列( 或者堆栈) ，其中包 括一些起始u r l 。r o b o t 从这些u r l 出发，下载相应的页面，并从中抽取出新的 超链接加入到队列( 或者堆栈) 中。上述过程不断重复直到队列( 或者堆栈) 为 空【9 1 。为了提高效率，搜索引擎中可能会有多个r o b o t 进程同时遍历不同的w e b 子空间，目前，大多数的r o b o t 并不能够访问基于框架的w e b 页面、需要访问权 限的w e b 页面，以及动态生成的w c b 页面。 在i n t e r n e t 中，信息是使用h t m l 语言描述的，不同的h t m l 页面通过其中 所包含的超级链接互相联接，这些超级链接是以u r l ( u n i f o r mr e s o u r c el o c a t o r ) 的方式被表示出来的。依靠这些相互指向的u r l ，i n t e r a c t 中的信息形成了一个巨 大的信息网络。u r l 是网络中信息资源的标准通用地址。在i n t e r a c t 中，人们用 u r l 来定位具体的信息资源。r o b o t 程序从一个起始的u r l 集开始，顺着u r l 中的超链接( h y p e rl i n k ) 在互联网中搜集信息【1 0 l 。这些起始u r l 的选取通常是 一些质量较高、非常流行、含有很多超链接的门户站点，如：新浪、搜狐、雅虎 等站点。一个u r l 对应一个源文件，r o b o t 将其全数抓回以待分析器对其进行处 理。 r o b o t 在进行网页搜集的时候往往遵循一定的协议，对于那些不愿意被访问的 网页会有一定表明，r o b o t 对这样的网页将不会涉足，为此，r o b o t 也被称为网络 中的君子。 分析器：对r o b o t 下载的文档进行分析以用于索弓 文档分析技术一般包 括：分词、过滤和转换等。这些技术往往与具体的语言以及系统的索引模型密切 相关。在分词时，大部分系统从全文中抽取词条，而有些系统仅从文档的某些部 分( 例如t i t l e 、h e a d e r 等) 中抽取。词条的类型也有多种，包括：字、词或者短语 等。分词后通常要使用禁用词表( s t o p 1 i s t ) 来去除出现频率很高的词条，有些系 统还对词条进行单复数转换、词缀去除、同义词转换等工作【1 1 】。 分析程序通过一些特殊算法，从r o b o t 程序抓回的网页源文件中抽取主题词， 并对其赋予不同权值，以表明这些主题词同网页内容的相关程度，以判断网页内 容【1 2 1 。如一个文章的题目往往能够概括文章的核心内容，它必然会被赋予一个较 高的值。 同时，分析程序还将此网页中的超链接提取出来，返回给搜集程序，以便r o b o t 进一步深入搜集信息。 9 电子科技大学硕士学位论文 分析程序的目的是从一个u r l 到相应网页主题词建立一种关联，并通过对主 题词的提取和分析，判断该网页所描述的信息。但是，按照终端用户搜索习惯通 常都是从一个关键词入手查找相应的网页。而在分析器中形成的对应关系恰恰相 反，这个问题将留给索引器来完成。 索引器：将文档表示为一种便于检索的方式存储在索引数据库中p j 。例如， 在矢量空间索引模型中，每个文档d 被表示为一个范化矢量： v ( d ) - 瓴，w 2 ) ；珥，；( d ) ；- ，似) ) ，其中为词条项，嵋 ) 为 在d 中 的权值，索引的质量是w e b 信息检索系统成功的关键因素之一。一个好的索引模 型应该易于实现和维护，检索速度快，空间需求低。搜索引擎普遍借鉴了传统信 息检索中的索引模型，包括：倒排文档、矢量空间模型、概率模型等。 检索器：从索引中找出与用户查询请求相关的文档。首先采用与分析、索 引文档相似的方法来处理用户查询请求。例如，在矢量空间索引模型中，用户查 询，也被表示为一个范化矢量，然后按照某种方法来计算用户查询与索引数据库 中每个文档之间的相关度1 1 4 , t 5 1 。例如，在矢量空间索引模型中，相关度可以表示 为查询矢量与文档矢量之间的夹角余弦。最后，将相关度大于阈值的所有文档按 照相关度递减的顺序排列，并返回给用户 用户接口：为用户提供可视化的查询输入和结果输出界面。在查询输入界 面中，用户按照搜索引擎的查询语法指定待检索词条及各种简单，高级检索条件。 在输出界面中，搜索引肇将检索结果展现为一个线性的文档列表。由于检索结果 中相关文档和不相关文档相互混杂，用户需要逐个浏览以找出所需文档。 2 2 建立搜索引擎的关键技术 信息收集和存储技术阱城1 7 】 网上信息收集和存储一般分为人工和自动两种方式。人工方式采用传统信息 收集、分类、存储、组织和检索的方法。研究人员对网站进行调查筛选、分类、 存储。由专业人员手工建立关键字索引，再将索引信息存入计算机相应的数据库 中自动方式通常是由搜索程序来完成的搜索程序( 如：r o b o t ，s p i d e r ，h a r v e s t 或p u r s u i t 等) 是一种自动运行的软件，其功能是搜索i n t e m e t 上的网站或网页。这 种软件定期在i n t e r n e t 上漫游，通过网页间链接顺序地搜索新的地址，当遇到新的 网页时，就给该页上的某些字或全部字作上索引并把它加到搜索引擎的数据库中， 由此，搜索引擎的数据库得以定期的更新。一般来说，人工方式收集信息的准确 第二章搜索引擎基本理论 性要远优于搜索程序，但其收集信息的效率及其全面性低于搜索程序。信息的存 储则是根据不同的分析结果和要求，针对提取的索引和查询目的而进行的。可以 采用专用的，也可以采用通用的数据库。 信息的预处理 信息的预处理包括信息的格式支持与转换以及信息过滤。目前，i n t e m e t 上的 信息发布格式多种多样，这就要求搜索引擎支持多种文件格式。从实际的情况看， 所有的搜索引擎都支持h t m l 格式，而对于其他文件格式的支持则不同的搜索引 擎有不同的规定，最多的能支持2 0 0 多种文件格式。一般地说，一个企业级的公 用w 西站点起码支持4 0 6 0 种文件格式。同时搜索引擎还应具备信息格式转换功能， 以保证不同的格式的数据均能在网络流通。信息过滤也是搜索引擎的一项重要技 术。在i n t e m e t 上，存在有大量的无用信息，一个好的搜索引擎应当尽量减少垃圾 站点的数量，这是信息过滤要着重解决的问题。 信息索引技术 信息索引就是创建文档信息的特征记录，以使用户能够快速地检索到所需信 息。建立索引主要涉及到以下几个问题： 信息语词切分和语词词法分析。语词是信息表达的最小单位，由于语词切分 中存在切分歧义，切分需要利用各种上下文知识。语词词法分析是指识别出各个 语词的词千，以便根据词干建立信息索引。 进行词性标注及相关的自然语言处理。词性标注是指利用基于规则和统计( 马 尔可夫链) 的数学方法对语词进行标注。基于马尔可夫链随机过程的n 元语法统 计分析在词性标注中能达到较高的精度。可利用多种语法规则识别出重要的短语 结构。自然语言处理是指自然语言识别在信息检索中应用，可以提高信息检索的 精度和相关性。 建立检索项索引。使用倒排文件的方式建立检索项索引，一般包括“检索项”， “检索项所在文件位置信息”以及“检索项权重”。 检索结果预处理技术。搜索引擎的检索结果通常包含大量的文件，用户不可 能一一浏览。搜索引擎一般应按与查询的相关程度对检索结果进行排列，搜索引 擎确定相关性的方法有概率方法、位置方法、摘要方法、分类或聚类方法等。概 率方法根据关键词在文中出现的频率来判断文件的相关性。这种方法对关键词出 现的次数进行统计，关键词出现的次数越多，该文件与查询的相关程度越高。位 置方法根据关键词在文中出现的位置判定文件的相关性。关键词在文中出现的越 早，文件的相关程度越高。摘要方法是指搜索引擎自动的为每个文件生成一份摘 电子科技大学硕士学位论文 要，让用户自己判断结果的相关性，以便用户进行选择。分类或聚类方法是指搜 索引擎采用分类或聚类技术，自动把查询结果归入到不同的类别中。 2 3 搜索引擎的性能指标 我们将w e b 信息的搜索看作一个信息检索问题，即在由w 曲网页组成的文档 集中检索出与用户查询相关的文档。所以我们可以用衡量传统信息检索系统的性 能参数：召回率( r e c a l l ) 和精度( p r e c i s i o n ) 来衡量一个搜索引擎的性斛”】。 召回率是检索出的相关文档数与文档集中所有的相关文档数的比率，衡量的 是检索系统( 搜索引擎) 的查全率；精度是检索出的相关文档数与检索出的文档总数 的比率，衡量的是检索系统( 搜索引擎) 的查准率。对于一个检索系统来讲，召回率 和精度不可能两全其美；召回率高时，精度低；精度高时，召回率低。对于搜索 引擎系统来讲，因为对于一个查询总能返回很多信息，所以召回率一般不成问题； 加之，没有一个搜索引擎系统能够搜集到所有的w e b 网页，召回率很难比较，所 以衡量搜索引擎的性能时，召回率很少使用。目前的搜索引擎系统都非常关心精 度，即是否为用户提供了相关度很高的、高质量的导航信息。 搜索引擎系统的其它衡量指标还有响应时间、支持峰值查询的能力、易用性、 返回结果的有效性( 是否为死链、过时信息) 等等。 影响一个搜索引擎系统的性能有很多因素，最主要的是信息搜集策略和检索 模型，包括索引库的更新频率和策略、文档和查询的表示方法、评价文档和用户 查询相关性的匹配策略、查询结果的排序方法和用户进行相关度反馈的机制。 2 4 通用搜索引擎的不足 现在的搜索引擎中存在的主要问题有： 搜索引擎覆盖范围相对减少：搜索引擎的索引能力正在越来越落后于网络的 快速增长速度。自1 9 9 7 年1 2 月以来，搜索引擎的覆盖面相对于网络上公开的可 检索的内容实际上是减少了。 搜索差异问题t 1 9 】：对同一关键字使用不同的搜索引擎得出的结果差别很大。 有时采用这种搜索引擎得到的结果较为满意，而有时使用另一种搜索引擎则更好 一些。因此可以考虑综合多个搜索引擎的查询结果，以达到更为令人满意的查询 效果。 第二章搜索引擎基本理论 个性化问题【2 0 】：搜索引擎w e b 信息检索系统通常作为一种大型的服务器程序 运行，同时响应多个用户的请求。这些系统不能够根据用户的兴趣需求来定制检 索结果。事实上，不同领域背景、知识结构的用户对检索结果的要求是不一样的。 故应该建立一种适合用户需求的，随用户的兴趣变化而动态调整的智能检索系统。 主动查询问题：搜索引擎的检索工作是用户驱动的，即由用户显式地提出检 索请求，系统给出响应。这是一种较为被动的信息获取方法。是否存在一种主动 协助用户获取信息的机制，将网络中用户需要的信息主动通知给用户。 动态监测问题：由于网络中的信息是动态变化的，用户经常需要了解一些信 息的最新动态。而在现有搜索引擎技术条件下，只有通过再次查询才能获取最新 信息，对用户来说是