（计算机应用技术专业论文）垂直搜索引擎的研究与实现(2).pdf

j b 京交道太堂亟堂僮j 金塞虫室擅要 中文摘要 摘要：随着i n t e m e t 和w w w 的迅速发展，i n t e m e t 上的资源日趋丰富，为了帮助 人们在浩如烟海的互联网中得到有用的信息，基于i n t e m e t 的各类信息检索服务应 运而生并得到了迅速发展。目前人们在互联网上搜索信息主要是通过g o o g l e ，百 度等通用搜索引擎。这类搜索引擎的功能已十分强大，在般情况下是可以满足 用户的需求的。然而当用户只想查询具体某专业或某行业，或某种主题的相关信 息时，这类搜索引擎就会显得有些力不从心了。垂直搜索引擎的出现，就是专们 为了解决这个问题的。 本文首先论述了垂直搜索的研究意义，接着详细介绍了搜索引擎的体系结构， 并深入探讨了通用搜索引擎的核心技术，包括网页抓取技术，中文分词技术，网 页排名技术等。然后又通过与通用搜索引擎的对比，介绍了构造垂直搜索引擎所 需要的关键技术。 在此基础上，本文提出了构造垂直搜索引擎时最重要的两个模块，即网页搜 集模块和结构化信息抽取模块的架构设计及算法模型。在网页搜集模块中，对垂 直搜索所要着力解决的“主题飘移”现象，提出了通过主题判定，主题预测和网 页排序的手段束防止这种现象，并在各自的模块中提出了相应的算法模型。在结 构化信息提取模块中，构造了一个基于x m l 技术的信息抽取系统的原型。将搜索 模块和信息提取模块进行合理的组合配置，形成了垂直搜索引擎的核心部分，为 创建一个完整的垂直搜索引擎打下了良好的基础。 关键词：垂直搜索引擎；专业爬虫；信息抽取； 分类号：t p 3 9 1 3 a e 哀交道太堂亟堂僮i 金窑缱s 卫坠鲤 a b s t r a c t a b s t r a c t ：w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e ta n d mr e s o u r c e so nt h e i n t e r n e ta r ei n c r e a s i n g l yr i c h 。i no r d e rt o h e l pp e o p l et og e tu s e f u li n f o r m a t i o ni na b r o a da r r a yo fi n t e m e ti n f o r m a t i o n ，t h ev a r i o u si n t e r a c t b a s e di n f o r m a t i o nr e t r i e v a l s e r v i c e sc a m ei n t ob e i n ga n dh a sb e e nd e v e l o p i n gr a p i d l y c u r r e n t l y , p e o p l es e a r c h i n f o r m a t i o no nt h ei n t e r a c tp r i m a r i l yt h r o u g hg o o g l e ，b a i d ua n do t h e rg e n e r a ls e a r c h e n g i n e s t h ef u n c t i o n so ft h e s es e a r c he n g i n e sh a v eav e r ys t r o n g , u n d e rn o r m a l c i r c u m s t a n c e st om e e tt h eu s e r sn e e d s h o w e v e r , w h e nu s e r sj u s tw a n tap r o f e s s i o n a lo r f o ras p e c i f i ci n d u s t r y , o rs o m et h e m er e l a t e di n f o r m a t i o n ，s u c hs e a r c he n g i n e sw i l lb ea l i t t l ei n s u f f i c i e n t t h ee m e r g e n c eo fv e r t i c a ls e a r c he n g i n e si ss p e c i f i c a l l yf o rs o l v i n g t h i sp r o b l e m t h i sp a p e rf i r s td i s c u s s e st h es i g n i f i c a n c eo fv e r t i c a ls e a r c h ，a n dt h e nd e s c r i b e di nd e t a i l t h es e a r c he n g i n ea r c h i t e c t u r e ，a n di n - d e p t hs t u d yo ft h eg e n e r a ls e a r c he l l 【舀n e sc o r e t e c h n o l o g i e s ，i n c l u d i n gs p i d e rt e c h n o l o g y , c h i n e s ew o r ds e g m e n t a t i o nt e c h n o l o g y , w e b s i t er a n k i n gt e c h n o l o g y t h e nw i t ht h eg e n e r a ls e a r c he l l i g i n e sc o n t r a s t ，i n t r o d u c e da v e r t i c a ls e a r c he n g i n es t r u c t u r er e q u i r e dc r i t i c a lt e c h n o l o g i e s o nt h i sb a s i s ，t h i sp a p e rp r e s e n t st w oo ft h em o s ti m p o r t a n tm o d u l e st ob u i l dv e r t i c a l s e a r c he n g i n e s ，n a m e l yt h ew e b p a g ec o l l e c t i o nm o d u l ea n dw e bi n f o r m a t i o ne x t r a c t i o n m o d u l e ，a n di t sf r a m e w o r kd e s i g na n da l g o r i t h mm o d e l i nt h ep a r to fw e b p a g ec o l l e c t i o nm o d u l e s ，d i s c u s st h em e t h o dt op r e v e n tt h e “t h e m e d r i f t p h e n o m e n o nt h a tt h ev e r t i c a ls e a r c he n g i n em a k e se f f o r t st os o l v e ，b ym e a n so f t h e m ej u d g m e n t ，t h e m ef o r e c a s ta n dw e b s i t er a n k i n g , a n dp r o v i d et h ec o r r e s p o n d i n g a l g o r i t h mm o d e li nr e s p e c t i v em o d u l e s i nt h es t r u c t u r eo fi n f o r m a t i o ne x t r a c t i o n m o d u l e ，p r e s e n t sas t r u c t u r eb a s e do nx m lt e c h n o l o g yi n f o r m a t i o ne x t r a c t i o ns y s t e m p r o t o t y p e m a k ep r o p e rp o r t f o l i oa l l o c a t i o n o fs e a r c hm o d u l ea n di n f o r m a t i o n e x t r a c t i o nm o d u l ea n df o r mt h ec o r eo fv e r t i c a ls e a r c he n g i n e s ，w h i c hl a y sag o o d f o u n d a t i o nt oc r e a t eac o m p l e t ev e r t i c a ls e a r c he n g i n e s k e y w o r d s ：v e r t i c a ls e a r c he n g i n e ；t o p i c a lc r a w l e r ；i n f o r m a t i o ne x t r a c t i o n c l a s s n 0 ：t p 3 9 1 3 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 铂宠 签字日期刁年嗍_ 叶日 导师躲锌【缸导师签名：乞书【7 坷 签字日期：d 。0 年瑚2 f 同签字日期：d u v 年钥6 【同 j e 塞变适太堂亟堂僮逾塞独创性直明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 啼乏 签字日期：0年7 ) ，月砌同 致谢 本论文的工作是在我的导师朱卫东副教授的悉心指导下完成的，朱卫东副教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三 年来朱卫东老师对我的关心和指导。 朱卫东副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都 给予了我很大的关心和帮助，在此向朱卫东老师表示衷心的谢意。 朱卫东副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示 衷心的感谢。 在实验室工作及撰写论文期间，刘宇，吴伟等同学对我论文中的理论研究工 作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 韭塞銮望太堂亟堂焦论塞 缓途 1 绪论 1 1 通用搜索引擎概述 1 1 1 搜索引擎定义 所谓搜索引擎，其实就是因特网上一种基于w 1 a r w 的信息检索工具，用来检索 w e b 网站、w e b 网页、新闻组、图片、声音等w e b 文件。它实际上是一个专用的 w e b 服务器，也可以说是互联网上提供信息检索服务的网站。这类网站与一般网站 不同的是，其主要功能是采用人工或自动的方式去搜寻w e b 上的信息，并将网络信 息进行主题分类、建立索引，再把索引的内容存放到索引数据库中，通过查询语 法为用户返回匹配资源，以帮助用户在i n t e m e t 中搜寻所需要的信息。面对浩瀚的 网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所 有的用户都可以从搜索引擎出发到达自己想去的网上任何一个地方。 1 1 2 搜索引擎的分类 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e xd i r e c t o r y ) 和元搜索引擎( m e t a s e a r c he n g i n e ) 。 1 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e ，a l t a v i s t a 、 i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 。它们都是通过从互联网 上提取的各个网站的信息( 以网页文字为主) 而建立的数据库中，检索与用户查 询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，因此他们是 真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己的检 索程序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人”( r o b o t ) 程序，并自建网 页数据库，搜索结果直接从自身的数据库中调用，如上面提到的几家搜索引擎； 另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如l y c o s 弓l 擎。 2 目录索弓 j e 塞銮道去堂亟堂鱼论童 绪论 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅 是按目录分类的网站链接列表而已。它们主要依靠人工维护网站索引。基于目录 的搜索引擎通过人工浏览各站点的信息，按照一定的分类规则或分类体系，对网 站进行分类。一般来说，它们具有结构清晰、错误较少，比较符合人们的阅读习 惯的优点，而缺点是工作人员多、整理周期长，速度慢、人工干预成分多，不能 适应w e b 资源的规模发展，另外如果查找的信息没有对应的分类项，则无法进行搜 索。目录索引中最具代表性的莫过于大名鼎鼎的y a h o o 雅虎。其他著名的还有o p e n d i r e c t o r yp r o j e c t ( d m o z ) 、l o o k s m a r t 等。 3 元搜索引擎( m e t a s e a r c he n g i n e ) 元搜索引擎是一种通过调用其它独立搜索引擎而完成搜索服务的搜索引擎， 是用户同时使用多个独立搜索引擎进行网络搜索的中介。用户只需递交次检索 请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎，并将 所有查询结果集中起来以整体统一的格式呈现到用户面前。元搜索引擎通过综合 利用多个搜索引擎的搜索服务，可以在一定程度上弥补单个搜索引擎的不足，但 是元搜索引擎的出现，并不能使搜索引擎技术得到质的飞跃，它们仅仅只是提供 了搜索结果的重新组织。 著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等( 元搜索引擎列表) ， 中文元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接 按来源引擎排列搜索结果，如d o g p i l e ，有的则按自定的规则将结果重新排列组合， 如v i v i s i m o 。 1 1 3 通用搜索引擎的不足 不管是g o o g l e 还是百度，都是传统意义上的横向的水平搜索引擎，他们面向 的是全球或全国的互联网范围内的搜索。随着互联网的迅猛发展，这种搜索引擎 的逐渐暴露出一下缺点： 1 覆盖率低：基于w e b 的自身特点，大量的数据分布在数以亿计页面的互联网上， 检索起来困难重重。单个搜索引擎的覆盖率一般都低于3 0 ，很难索引所有的w e b 资源。 2 时效性差：互联网信息呈指数增长，大量信息的存活期却在缩短，这导致搜索 引擎的时效性很难保证，返回结果中存在大量无效或过时的链接。 3 易导致迷航：经典的信息检索界认为用户很难简单地用关键字来忠实表达他所 真正需要检索的内容，甚至根本就不知道要找什么东西，即所谓“迷航”。表达的 2 困难将导致检索结果的不理想，而且如何将结果表达成用户容易理解和使用的方 式也是一个难题。 4 结果不准确：一次搜索的结果可能有成千上万条，而在这过于庞大的信息中， 有用信息只是其中的小部分，可谓“冰山一角”，并且常常发生收到和下载的信息 难以消化的情况，即所谓的“认知过载”。 5 过于死板：现有的搜索引擎多采用关键词的机械式匹配。没有对用户的输入进 行语义理解，这种方式的固有缺点是参与匹配的只有字符的外在表现形式，而非 它们所表达的概念。因此，经常出现答非所问、检索不全的结果。 1 2 垂直搜索引擎的研究意义 1 2 1 垂直搜索引擎的定义 所谓垂直搜索引擎( v e r t i c a ls e a r c he n g i n e ) 2 ，是针对某一特定领域、某一 特定人群或某一特定需求提供的有一定价值的信息和相关服务。其特点就是“专、 精、深”，且具有行业色彩。它是与通用搜索引擎截然不同的引擎类型。垂直搜 索引擎专注具体、深入的纵向服务，致力于某一特定领域内信息的全面和内容的 深入，这个领域外的闲杂信息不收录。 1 2 2 垂直搜索引擎的优势 通用搜索引擎的弊端在网络信息的急剧膨胀下突显起来，搜索越来越难控制， 用户需求和市场服务间的巨大反差产生了强大的“搜索噪音”，人们呼唤更有针 对性的搜索引擎，垂直搜索引擎应运而生。垂直搜索引擎的网络蜘蛛只抓取特定 主题的信息，按预先己经定义好的专题有选择地收集网页。由于所收集的学科领 域小，信息量相对较少，更新及时，因而有效地解决了通用搜索引擎的弊端。由 于垂直搜索引擎只涉及一个或几个领域，词汇和用语“一词( 一语) 多意”的可能 性降低，而且可以利用专业词表进行规范和控制，大大提高查全率和查准率。这 种高度目标化、专业化的搜索引擎的优势在于针对性强，对特定范围的网络信息 的覆盖率相对较高，有明确的检索目标定位，有效地弥补了综合性搜索引擎对专 门领域及特定主题信息覆盖率过低的问题。 1 2 3 垂直搜索引擎的研究现状 3 a e 塞銮遣太堂亟差焦i 金塞 绪论 目前在国内外，有关新一代搜索引擎的研究正在成为一个热点，下面介绍一 下具有代表性的系统。 1 s c i r u s 是面向科技文献的一个垂直搜索引擎，它的信息源主要包括网页和期刊 两部分。它首先对网络中所搜索到的结果进行过滤，然后只列出包含有科学信息 的成分，方便了科研人员的使用。 2 b e r k e l e y 的f o c u s e dp r o j e c t 9 系统通过两个程序来指导爬行器，一个是分类器， 用来计算下载文档与预定主题的相关度，另一个程序是净化器，用来确定那些指 向很多相关资源的页面。 3 基于概念搜索的a k s j e e v s 搜索引擎，它将用户提问转化为系统己知的问题，在 对提问进行结构和内容分析之后，或直接给出问题的答案，或引导用户从几个可 选择的问题中进行再选择。用户只需输入简单的疑问句，如等句式就能直接获得 结果。 4 2 搜索引擎技术概述 2 1 搜索引擎的工作原理及体系结构 现代大规模高质量的搜索引擎一般都包括三个模块，即网页信息搜集模块， 预处理模块和查询服务模块。在实际应用中，这三个模块之间的工作其实是相互 独立的。它们的不同工作形成了搜索引擎不同的工作阶段。通常这三个部分都是 分别由人工启动的。 2 1 1 网页信息搜集模块 搜索引擎说到底其实也是一个软件系统。如果说软件系统是工作在某个数据 集合上的程序的话，那搜索引擎这个软件系统所要操作的数据不仅要包括不可预 测的用户查询还需要在数量上动态变化海量的网页内容，并且这些内容不会主动 送到系统来，而是需要定期去抓取。网页信息搜集模块主要就是完成这个任务的。 图2 - 1 网页搜集模块体系结构 f i g 2 - 1 a r c h i t e c t u r eo f p a g ec o l l e c t i o nm o u d l e 通常搜索引擎会派出蜘蛛程序，从一定的u r i 集合开始，通过一定策略对互 联网进行爬取。爬取回来的网页用某种形式存储在服务器上，形成了最初的网页 库。但是，这时候的网页库对于以后的查询来说，实际上是无法使用的。要想为 查询服务提供真正有用的数据，就需要预处理模块对网页的加工和处理。 信息搜集是搜索引擎系统的基础工作。首先就要考虑到抓取的时机，是事先 还是即时。在网络比较畅通的情况下，从网上下载一篇网页大约需要1 秒钟左右， 那么如果在用户查询的时候即时去网上抓来成千上万的网页，一个个分析处理， 和用户的查询匹配，不能够满足搜索引擎的响应时间要求。不仅如此，这样做的 系统效益也不高( 会重复抓取太多的网页) ：面对大量的用户查询，不可能想象每 来一个查询，系统就到网上“搜索”一次。因此大规模搜索引擎服务的基础应该 是一批预先搜集好的网页( 直接或问接) 。在具体搜集过程中，如何抓取一篇篇的网 页，也可以有不同的考虑。一种是所谓的“爬取”：将w 曲上的网页集合看成是一 个有向图，搜集过程从给定起始u r i 叠耗合s 开始，沿着网页中的链接，不停的从s 中移除u r l ，下载相应的网页，解析出网页中的超链接u r l ，看是否已经被访问 过，将未访问过的那些u r l 加入集合s 。整个过程可以形象地想象为一个蜘蛛 ( s p i d e r ) 在蜘蛛网f w e b ) 上爬行( c r a w l ) 。 2 1 2 预处理模块 图2 2 预处理模块体系结构 f i g 2 - 2a r c h i t e c t u r eo fp r e t r e a t m e n tm o u d l e 得到海量的原始网页集会，离面向网络用户的检索服务之间还有相当的距离。 采用“程序= 算法+ 数据结构”的观点来考察服务子系统，一个合适的数据结构是 查询子系统工作的核心和关键。如今最有效的数据结构是“倒排文件”，而预处理 就是从网页集合形成这样的倒排文件过程中的主要问题，它包括四个方面：关键词 的提取、“镜像网页”( 网页的内容完全相同，未加任何修改) 或“转载网页”( 主 题内容基本相同但可能有一些额外的编辑信息等，转载网页也称为“近似镜像网 页”) 的消除、链接分析和网页重要程度的计算： 1 关键词的提取 随便取一篇网页的源文件，可以看到它的情况纷乱繁杂，除了从浏览器中能 够正常看到的文字内容外，还有大量的h t m 哳记。由于m m l 文档产生来源的多 样性，许多网页的内容上比较随意，不仅文字不讲究规范、完整，而且还可能包 6 韭鏖窑通太堂亟堂焦论毫趁蠢j i 鏊拉丕援亟 含许多和主要内容无关的信息( 如广告，导航条，版权说明等) 。这些情况给有效 的信息查询带来了挑战，也带来了一些新的机遇。为了支持后面的信息查询，需 要从网页源文件中提取出能够代表它的内容的一些特征，关键词就是最好的代表。 于是，作为预处理阶段的一个基本任务就是根据一个词典，用一个所谓“切词软 件”，从网页文字中切出e 所含的词语来。这样一篇网页就主要由一组词来近似代 表了，p 。1 “h h j 。一般来讲，有可能得到很多词，同一个词可能在一篇网页 中出现多次。从效果和效率考虑，不应该让所有的词都出现在网页的表示中，要 去掉诸如“的”，“在”等没有内容指示意义的词，称为“停用词”。 2 重复或转载网页的消除 与生俱来的数字化和网络化给网页的复制以及转载和修改再发带来了便利， 因此在w e b 上的信息存在大量的重复现象。当你通过一个u r l 在网上看到一篇网页 的时候，平均还有另外3 个不同的u r l 也给出相同或者基本相似的内容。这种现象 对于广大的网民来说是有f 面意义的，因为有了更多的信息访问机会。但是对于 搜索引擎来说，则主要是负面的，它不仅在搜集网页时要消耗机器时间和网络带 宽资源，而且如果在查询结果中出现，无意义地消耗了计算机显示屏资源，也会 引柬用户的抱怨，因此消除内容重复或主题重复的网页是预处理阶段的一个重要 任务 3 链接分析 从信息检索的角度讲，如果系统面对的仅仅足内容的文字，那么依据的就是 “共同词汇假设”( s h a r e db a go fw o r d s ) ，即内容所包含的关键词集合，最多加上 词频( t e a mf r e q u e n c y 或t f 、仲) 和词在文档集合中出现的文档频率( d o c u m e n t f r e q u e n c y 或d f 、d f ) 之类的统计量。而1 下和d f 这样的频率信息能在一定程度上指 示词语在一篇文档中的相对重要性或者和某些内容的相关性。有了r r r m l 标记后， 情况还可能进一步改善。在同一篇文档中， 和 之间的信息很可能就比在 和 之间的信息更重要，因此利用链接信息的垂直搜索引擎就能够很好 的返回所需的信息。 4 网页重要程度的计算 搜索引擎返给用户的是和用户查询相关的结果列表。列表中条目的顺序是很 重要的。由于面对各种各样的用户，加之查询的自然语言风格，对同样的查询， 返回相同的列表肯定是不能使所有提交这一查询的用户都满意的( 或者都达到最 高的满意度) 。因此搜索引擎就要在实际上追求一种统计意义上的满意。比如对于 网页和文献的不同特点，一些网页主要是大量对外的链接，其本身基本没有一个 明确的主题内容，而另外有些网页则被大量的其他网页链接。从某种意义上讲， 这形成了一种对偶的关系，这种关系使得人们可以在网页上建立一种重要性指标。 7 在网页重要程度的计算中有很多不同的指标，而这些指标有的可以在预处理阶段 计算，有的则要在查询阶段计算，但都是作为在查询服务阶段最终形成结果排序 的部分参数。 2 1 3 查询服务模块 从一个原始网页集合s 开始，预处理过程得到的是对s 的一个子集的元素的某 种内部表示，这种表示构成了查询服务的直接基础。对每个元素来说，这种表示 至少包含如下几个方面： 1 原始网页文档 2 u r 哪标题 3 编号 4 所含的重要关键词的集合( 以及它们在文档中出现的位置信息) 5 其他一些指标( 如重要程度、分类代码等) 而系统关键词总体的集合和文档的编号一起构成了一个倒排文件结构，使得 一旦得到一个关键词输入，系统能迅速给出相关文档编号和集合输出。 用户通过垂直搜索引擎看到的不是一个“集合”，而是一个“列表”，那么如 何从集合生成一个列表是服务子系统的主要工作。从垂直搜索系统功能划分的角 度来看，有时候将倒排文件的生成也作为服务子系统的一部分功能，在这罩为了 方便把它划分到了预处理阶段，也就是说服务予系统是在服务进行的过程中涉及 的相关软件程序，而为这些软件程序事先准备数据的程序都算在预处理子系统中 了。 服务子系统的工作原理可分为三个方面： 1 查询方式和匹配 查询方式指的是系统允许用户提交查询的形式。考虑到各种用户的不同背景 和不同的信息需求，不可能有一种普遍适用的方式。一般认为，对于普通网络用 户来说，最自然的方式就是“要什么就输入什么”。所以匹配的内容就是用户输入 的查询短语。一般情况下用q 表示用户提交的原始查询，例如“网络分布式系统实 验室”。关键词提取后得n q - - n 络，分布式，系统，实验室 。有了这样的q ，它 的每一个元素都对应倒排文件中的一个倒排表，记作l ，它们的交集即为对应查询 的结果文档集合，从而实现了查询和文档的匹配。 2 结果排序 得到了和用户查询相关的文档集合以后，要考虑通过什么样形式的计算机显 示屏呈现给用户。此处的垂直搜索引擎采用的是列表形式。给定一个查询结果集 8 合，r 2 r t ，r 2 r n 所谓列表就是按照某种评价方式确定出r 中元素的一个顺序， 让这些元素以这种顺序呈现出来。r - 和q 的相关性是形成这种顺序的基本因素。有 效地定义相关性本身是很困难的，从原理上讲它不仅和查询词有关，而且还和用 户的背景，以及用户的查询历史有关。不同需求的用户可能输入同一个查询，同 一个用户在不同的时问输入的相同的查询可能是针对不同的信息需求。在早期采 用了传统信息检索方法基于词汇出现频度法，它是根据在一篇文档中包含的查 询( q ) 中的那些词越多，则该文档就排在越前面的思想，虽然很容易实现但是由于 网页编写的自发性、随意性较强，在w e b 上使用该方法有明显的不足，需要有其他 技术的补充。这时需要通过在预处理阶段为每篇网页形成一个独立于查询词( 也 就是和网页内容无关) 的重要性指标，将它和查询过程中形成的相关性指标结合 形成一个最终的排序。 3 文档摘要 垂直搜索引擎同样给出的结果是一个有序的条目列表，每一个条目有三个基 本的元素：标题、网址和摘要。其中的摘要需要从网页j 下文中生成。从一篇文字 中生成一个恰当的摘要是自然语言理解领域的一个重要课题。但是相关技术被用 道网络搜索引擎来有两个基本困难：一是网页的写作通常不规范，文字比较随意， 因此从语言理解的角度难以做好；二是复杂的语言理解算法耗时太多，不适应搜 索引擎要高效处理海量网页信息的需求。搜索引擎生成的摘要比较简便，基本上 可以归纳为两种方式：一是静念方式，即独立于查询，按照某种规划事先在预处 理阶段从网页内容提取出一些文字，如截取网页正文的开头5 1 2 个字节( 对应2 5 6 个汉字) ，或者将每一个段落的第一个句子拼起来等等。这样形成的摘要存放在查 询子系统中，一旦相关文档被选中与查询项匹配，就读出返回给用户。虽然这种 方式对查询子系统来说是最轻松的，不需要做另外的处理工作，但是缺点是摘要 与查询无关。另一种是动态方式，生成“动态摘要”，即在响应查询的时候，根据 查询词在文档中的位置，提取出周围的文字来，在显示时将查询词标亮。垂直搜 索引擎使用的是动态方式。除上的几个方面外，查询服务返回的内容还有一些细 节的支持。例如，对应一个查询往往会有成千上万的结果，返回给用户的内容是 按页组织的，统计表明网络用户一般没有耐心一页页看下去，平均翻页数小于2 ， 所以第一页的内容组织形式非常重要。 2 2 搜索引擎核心技术 2 2 1s p i d e r 技术 9 1 s p i d e r i 作原理 网络蜘蛛b j s p i d e r ，互联网好比是一个蜘蛛网，s p i d e r 就是在网上爬行的蜘蛛。 网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面( 通常是首页) 开 始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻 找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。 如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所 有的网页都抓取下来。 s p i d e r 是搜索引擎的核心模块。s p i d e r 抓取数据的结果直接影响到搜索引擎的 评价指标。关于s p i d e r 的定义，有广义和狭义两种。狭义：利用标准的h t r p 协议 根据超链和w e b 文档检索的方法遍历万维网信息空脚的软件程序。广义：所有能利 用h t r p 协议检索w e b 文档的软件都称之为s p i d e r 。 对于搜索引擎来说，要抓取i n t e r n e t 上所有的网页几乎是不可能的，从目前公 布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十 左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网 页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的问题，如 果按照每个页面的平均大小为2 0 k 计算( 包含图片) ，1 0 0 亿网页的容量是1 0 0 * 2 0 0 0 g 字节，即使能够存储，下载也存在问题( 按照一台机器每秒下载2 0 k 计算，需要3 4 0 台机器不停的下载一年时间，才能把所有网页下载完毕1 。同时，由于数据量太大， 在提供搜索时也会有效率方面的影响。因此，许多搜索引擎的网络蜘蛛只是抓取 那些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。 在抓取网页的时候，网络蜘蛛主要有两种策略：广度优先和深度优先。 ( 1 ) 深度优先搜索策略 深度优先搜索是在开发s p i d e r 的早期使用较多的方法。它的目的是要达到被搜 索结构的叶结点( 即那些不包含任何超链的h t m l 3 乏件) 。在一个h t m l 3 乏件中，当 一个超链接被选择后，被链接的h t m l 文件将执行深度优先搜索，即在搜索其余的 超链接结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着m m l 文件上 的超链接走到不能再深入为止，然后返回到某一个h t m l 文件，再继续选择该 m m 工皮件中的其他超链接。当不再有其他超链接可选择时，说明搜索己经结束。 深度优先搜索的优点是能遍历一个w e b 站点或深层嵌套的文档集合；缺点是由于 w e b 结构相当深，有可能造成一旦进去再也出不来的情况发生。 ( 2 ) 广度搜索优先策略 在广度度优先搜索中，先搜索完一个w e b 页面中所有的超级链接，然后再继续 搜索下一层，直到底层为止。例如，一个h 聊l 文件中有三个超链接，选择其中之 一并处理相应的h t m l 支：件，然后不再选择第一个b t m l x 件中的任何超链接，而 是返回并选择第二个超链接，处理相应的m m l 文件，再返回，选择第三个超链接 并处理相应的h t m l 文件。一旦一层上的所有超链接都己被选择过，就可以开始在 刚才处理过的h 珊l 文件中搜索其余的超链接。这就保证了对浅层的首先处理。当 遇到一个无穷尽的深层分支时，不会导致陷进w w w 中的深层文档出不来的情况发 生。广度优先搜索策略还有一个优点，即它能在两个咖l 文件之问找到最短路径。 但是如果要遍历一个指定的站点或者深层嵌套的h t m l & ：件集，用广度优先搜索策 略则需要花费比较长的时间才能到达深层的h t m l 文件。 搜索引擎建立网页索引，处理的对象是文本文件。对于网络蜘蛛来说，抓取 下来网页包括各种格式，包括h t m l 、图片、d o c 、p d f 、多媒体、动态网页及其 它格式等。这些文件抓取下来后，需要把这些文件中的文本信息提取出来。准确 提取这些文档的信息，一方面对搜索引擎的搜索准确性有重要作用，另一方面对 于网络蜘蛛正确跟踪其占链接有一定影响。对于d o c ，p d f 等文档，这种由专业厂 商提供的软件生成的文档，厂商都会提供相应的文本提取接口。网络蜘蛛只需要 调用这些插件的接口，就可以轻松的提取文档中的文本信息和文件其它相关的信 息。h t m l 等文档不一样，h t m i 有一套自己的语法，通过不同的命令标识符来表 示不同的字体、颜色、位置等版式，提取文本信息时需要把这些标识符都过滤掉。 过滤标识符并非难事，因为这些标识符都有一定的规则，只要按照不同的标识符 取得相应的信息即可。但在识别这些信息的时候，需要同步记录许多版式信息， 例如文字的字体大小、是否是标题、是否是加租显示、是否是页面的关键词等， 这些信息有助于计算单词在网页中的重要程度。同时，对于h t m l 网页来说，除了 标题和正文以外，会有许多广告链接以及公共的频道链接，这些链接和文本正文 一点关系也没有，在提取网页内容的时候，也需要过滤这些无用的链接。例如某 个网站有“产品介绍”频道，因为导航条在网站内每个网页都有，若不过滤导航 条链接，在搜索“产品介绍”的时候，则网站内每个网页都会搜索到，无疑会带 来大量垃圾信息。过滤这些无效链接需要统计大量的网页结构规律，抽取一些共 性，统一过滤；对于一些重要而结果特殊的网站，还需要个别处理。这就需要网 络蜘蛛的设计有一定的扩展性。 2 s p i d e r t 作过程： s p i d e r 程序的工作过程，简单来讲，就是不断发现新的链接，并对该链接对应 的页面分析存储的过程。当一个u r l 被加入到等待队列中时s p i d e r 程序就会开始运 行。只要等待队列中有一个网页或s p i d e r 程序正在处理一个网页，s p a d e r 程序就会 继续它的工作。当等待队列为空并且当前没有处理任何网页，s p i d e r 程序就会停止 它的工作。 s p i d e r 程序是从网上下载w 曲页面再对其进行处理，为了提高效率，很显然要 1 1 采用多线程的方法，几个s p i d e r 线程同时并行工作，访问不同的链接。构造s p i d e r 程序有两种方式。第一种是将它设计为递归程序，第二种是将它编写成非递归的 程序。递归是在一个方法中调用它本身的程序设计技术。当需要重复做同样的基 本仟务或在处理先前任务时可展现将来的任务信息时，递归是相当实用的 递归方法在访问很少的网页时，可以使用。因为当一个递归程序运行时要把 每次递归压入堆栈( 堆栈是个程序结构，每次调用一个方法时，将返回地址存入 其中) 。如果递归程序要运行很多次，堆栈会变得非常大，它可能会耗尽整个堆 栈内存而导致程序中止。递归还有个问题是多线程和递归是不兼容的，因为在这 一过程中每一个线程都是自己的堆栈。当一个方法调用它自身时，它们需要使用 同一个堆栈这就是说递归的s p i d e r 程序不能使用多线程。非递归程序不调用自身， 而是采用队列的方法。队列就是排队，要得到程序的处理就必须在队列中排队等 待。我们在构造s p i d e r 时就采用该方式。使用非递归的方法时，给定s p i d e r 程序一 个要访问的页面，它会将其加入到要访问的站点的队列中去。当s p i d e r 发现新的链 接时，也会将它们加入到该队列中。s p i d e r 程序会顺序处理队列中的每一个网页。 在s p i d e r 程序的构造过程中，有两种方法用于访问队列的管理。一种方法就是基于 内存的队列管理，令一种方法就是基于s o l 的队列。一般情况下，需要以下几种队 列： ( 1 ) 等待队列：在这个队列中，u r l 等待被s p i d e r 程序处理。新发现的u r l 被加入到 该处理队列：当s p i d e r 丌始处理u r l 时，它们被传送到这一队列：当一个u r l 被处 理后它被移送到错误队列或完成队列。 ( 2 ) 错误队列：如果下载某页面时出现错误，它的u r 嘴被加入该队列。该队列 的u r l 不会再移动到其他队列。被列入该队列的u r 啪不再会被s p i d e r 程序处理。 ( 3 ) 完成队列如果页面的下载没有出现任何错误，则该页面将会被加入完成队列。 加入该队列的u r l 不会再移动到其他队列。同一时刻一个u r l 疑能在一个队列中。 其实通俗的讲就是该u r l 处于什么状态，u r l 状态的变化过程就是程序处理u r l 的过程。 2 2 2 中文分词技术 汉语以字为基本的书写单位，而作为能够独立活动的有意义的最小语言成分 的却是词。中文信息处理中一个重要的基础课题就是词的切分，也称中文分词， 与拉丁语系的语言以空格作为词界不同，在汉语中词与词之间没有明显的区分标 记，因而中文分词的意义显得格外重要。众所周知，词在中文信息处理的诸多环 节起着重要的作用，当然也包括了搜索引擎。现有的分词算法可分为三大类：基于 字符串匹配的分词方法、基于统计的分词方法和基于理解的分词方法。机械分词 方法需要分词词典的支持，具有效率高，算法简单的特点，但难以排除机械切分 产生的歧义，准确率较差；基于统计的分词方法根据词的频度来判断成词的概率， 这种方法能有效地识别新词，时空开销大，效率有限；基于理解的分词方法通过 让计算机模拟人对句子的理解，达到识别词的效果，由于语言知识和语言规则过 于复杂，因而这种方法尚处于研究的阶段。 1 基于字符串匹配的分词方法 这种方法又被称为机械分词方法，它是按照一定的策略将待切分的汉字串与 分词词典中的词条进行匹配查询，若在词典中找到某个字符串，则匹配成功，即 识别出个词。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向 匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配； 按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合 的一体化方法。常用的几种机械分词方法如下： ( 1 ) 正向最大匹配法：方向由左到右 ( 2 ) 逆向最大匹配法：方向由右到左 ( 3 ) 最少切分：使每一句中切出的词数最小 还可以将上述各种方法相互组合，例如邹海山等在现有分词技术的基础上， 提出了一种基于词典的j 下向最大匹配和逆向最大匹配相结合的中文分次方案，可 以高效、准确地实现中文文档的主题词条的抽取和词频统计可以将证向最大匹配 方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点， 正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略 高于正向匹配，遇到的歧义现象也较少。还有一种方法是改进扫描方式，称为特 征扫描或标志切分，优先在待分析的字符串中识别和切分出一些带有明显特征的 词，以这些词作为断点，可将原字符串分为几个较短的子串再进行机械分词，从 而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词 类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、 调整，从而极大地提高切分的准确率。 2 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好 的反映为词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的互现信息。定义两个字的互现信息，计算两个汉字) ( y 的相邻共现概 率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个闭值 时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行 统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法 也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如 “这一”、“之一”、“有的”、“我的”、“许多的”等，并