（计算机软件与理论专业论文）搜索引擎关键技术研究与实现.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均己在论文中作了明确的声明 并表示了谢意。 作者签名：华 日期：叁丝幽 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：耋毕导师签名：二墨噬日期：二壅蚴 摘要 搜索引擎技术的核心是全文检索，而全文索引的显著特点就是提供对非结构 化海量数据的管理和快速查询。全文索引创建的空间效率( 包括最终索引空间和 创建过程中需要的辅助空间) 和索引建好后的查询速度是全文索引研究领域的两 大热点。 随着信息时代的数据，特别是非结构化数据的爆增，人类从中获取信息的需 求也越来越大，从全文中获得信息，是一个传统的关系型数据库系统( r d b m s ) 解决起来比较低效的问题。结合全文检索技术的搜索引擎技术应运而生，它的优 势在于专门为了解决全文数据而设计的高效的存储结构和高速的查询速度以及 多种的查询接口。在发展中，搜索引擎的目标是能像传统的数据库一样提供方便 有效的功能。因此，搜索引擎是该技术的方向和最终目标。本文从搜索引擎的工 作原理及其实现技术进行分析，从中可以了解限制搜索引擎性能改善用户体验的 因素到底有哪些。由于互关联后继树作为一种优秀的全文模型在全文检索领域发 挥着越来越重要的作用，所以本文虽然着力于搜索引擎的核心技术与应用的研究， 但互关联后继树全文模型贯穿始终几乎渗透在所有关键技术之内。互关联后继树 全文模型与搜索引擎技术的相互贯穿与结合，使其在搜索领域发展出属于自己的 一套技术与理论，中国电信黄页信息检索系统的开发，使得互关联后继树全文模 型走出纯理论框架范畴，在实际应用环境中发挥其重要的作用。 关键字：搜索引擎，全文检索，互关联后继树 中图法分类号t p 3 1 l a b s t r a c t t h ec o r eo fs e a r c he n g i n et e c h n o l o g yi sf u l l t e x tr e t r i e v a l t h em o s t p r o m i n e n tc h a r a c t e ro ff u l l t e x ti n d e xi sa no f f e r i n gt ot h em a n a g e m e n t o ft h em a s s i v ed a t aw i t hf a s ts e a r c h t h es p a t i a le f f i c i e n c yi nc r e a ti n g f u l l t e x ti n d e xa n dt h eq u e r y i n gs p e e da f t e rt h ei n d e xc r e a t e dh a v eb e e n t h et w oh o tt o p i c si nt h ea r e ao ff u l l - t e x ti n d e xr e s e a r c h a st h ei n f o r m a t i o ne r a st a k i n gf a s tp a c ef o r w a r d ，h u m a nb e i n gn o w i sf a c i n gt h ee x p l o s i v ed a t ac o v e r i n ge v e r ya s p e c to fr o u t i n e1i f e m o s t o ft h e ma r en o tw e l s t r u c t u r e d s ot h et r a d i t i o n a lr e l a t i o n a ld bt h e o r yi s n o ts u i t a b l ef o rd e a li n gw i t ht h e m t h u sc o m e st h ec o n c e p to fs e a r c he n g i n e ， w h i c hi so r i g i n a l yat e r mo fi n f o r m a t i o nr e t r i e v a la r e a n o w a d a y sa st h e s e a r c he n g i n et e c h n o l o g yi se v o l v i n gt o w a r d sd a t a b a s ea r e a ，m o r ea n dm o r e f u n c t i o n a l i t i e sa r eb e i n ga d d e di n t ot h ei m p l e m e n t a t i o no fas e a r c he n g i n e s y s t e m b a s e do nt h ea n a l y s i so ft h ep r i n c i p l ea n dt e c h n o l o g yo ft h es e a r c h e n g i n e ，t h i sp a p e ra n a l y s e st h el i m i t a t i o na n dc o n s t r a i n to np e r f o r m a n c e o ft h es e a r c he n g i n ea n du s e re x p e r i e n c ei no r d e rt of i n do u tw h a tk i n d o ft h i n g sa r et h em a j o ra s p e c t st oi m p r o v ep e r f o r m a n c ee f f i c i e n t l y a s b e i n ga ne x c e l l e n tf u l l 一i n d e xm o d e la n dp l a y i n gm o r ea n dm o r ei m p o r t a n t r o l ei nf u l l 一t e x tr e t r i e v a l ，w h i c hi so r i g i n a l l yat e r mo fi n f o r m a t i o n r e t r i e v a la r e a , i r s t ( i n t e r r e l e v a n ts u c c e s s i v et r e e ) i sr e l e v a n tw i t ha l l i m p o r t a n tt e c h n o l o g ya n dt h e o r yi nt h ep a p e rd e s p i t er e s e a r c ha n d d e v e l o p m e n tc o r et e c h n o l o g yo ft h es e a r c he n g i n ei st h em a j o rp o i n to f t h ep a p e r c o m b i n e di r s ts e a r c hm o d e lw i t hc o r et e c h n o l o g yo ft h es e a r c h e n g i n e ，w ec o n c l u d eat h e o r ya n dt e c h n o l o g yf r a m e w o r ko nf u l 卜t e x t r e t r i e v a ld o m a i n w h a t sm o r ei m p o r ti st h er e s e a r c ha n dd e v e l o p m e n to f c h i n a - t e l e c o my e l l o wp a g es e a r c he n g i n es y s t e mm a k ei r s tf u l l 一i n d e xm o d e l o u to ft h ee x p e r i m e n tp e r i o dt os h o wi t si m p o r t a n c ei nt h er e a lw o r l d k e y w o r d ：s e a r c he n g i n e ， f u l 卜t e x tr e t r i e v a l ， i r s t ( i n t e r r e l e v a n t s u c c e s s i v et r e e ) 中图法分类号t p 3 1 1 6 1 1 研究背景 第一章绪论 搜索引擎是一种依靠技术取胜的产品。搜索引擎的各个组成部分，包括页面 搜集器、索引器、检索器等，都是搜索引擎产品提供商进行比拼的着力点。 近几年，搜索引擎的商业化取得了巨大的成功。如著名搜索引擎公司g o o g l e 、 y a h o o 百度等纷纷成功上市，引发了众多公司涉足于该领域，带动了人力、资本 的大量投入，连软件巨人m i c r o s o f t 公司也禁不住诱惑积极打造自己的搜索引 擎。但是，从性能上来说，目前的搜索引擎还不尽如人意，搜索返回的结果往往 与用户的检索要求相去甚远，有效性还不是很高。 于是如何提高搜索引擎的可检索信息量；用户检索速度；检索结果的有效性 等都成为了搜索引擎领域炙手可热的研究方向，本文也是向着这样的方向进行了 诸多的研究是应用。 1 2 研究现状 1 2 1 信息检索 搜索引擎的基础是信息检索，而信息检索中全文检索技术的出现，导致了信 息检索领域的一场革命。比起传统的标引检索来，全文检索技术提供了全新的、 强大的检索功能是发现信息、分析和过滤信息、信息代理、信息安全控制等主要 应用技术的基础。以全文检索为核心技术的搜索引擎已经成为网络时代的主流技 术之一。在全文检索研究领域中，基于概念、超文本信息检索最为活跃，并己取 得了突破性进展。 基于概念的信息检索是指通过对文献中的原文信息进行语义上的自然语言 处理，析取各种概念信息，并由此形成一个知识库。然后，根据对用户提问的理 解，检索知识库中的相关信息，以提供直接的回答。概念信息检索有以下几个特 性： 具有分析和理解自然语言的能力：可以对输入的原文根据其概念内容进行组 织和安排，以析取相关的概念信息和范畴知识。然后，通过记忆机制将它们存储 到知识库中，以备检索用。 记忆机制能够自动补充与更新：具有用自然语言回答用户提问的能力。 概念信息检索技术的上述特性，使系统的查全率和查准率都得到提高。w e b 7 上的e x c i t e 搜索引擎就是采用概念信息检索理论设计的数据库，在e x c i t e 搜索 引擎输入检索词“e l d e r l yp e o p l ef i n a n c i a lc o n c e r n s ”，系统可将含有 “e c o n o m i cs t a t u so fr e t i r e dp e o p l e ”和“t h ef i n a n c i a lc o n c e r n so fs e n i o r c i t i z e n s ”等与检索词概念一致的信息作为返回结果，可见系统自动将“e l d e r l y p e o p l e ”与“r e t i r e dp e o p l e ”和“s e n i o rc i t i z e n s ”，”f i n a n c i a lc o n c e r n s ” 与“e c o n o m i cs t a t u s ”进行了概念匹配。 由于基于概念的信息检索技术具备了智能检索的一些特性，其系统分析和理 解原文内容及用户提问信息的能力较强，因此，备受检索用户的青睐。 超文本信息检索技术是以超文本网络为基础的文献检索技术。超文本信息组 织的特点是正文信息以节点而不是以字符串作为信息的基本单元，节点间通过链 进行连接。在检索文献时，其检索技术应能满足节点问的多种链接关系可以动态 地选择性激发，根据思维联想或新信息的需要，通过链从一个节点到另一个节点。 i n t e r n e t 上的搜索引擎代表了超文本信息检索技术的发展水平，网上建立和运 行的多个基于超文本信息的全文检索系统如：y a h o o ! 、l y c o s 、i n f o s e e k 等著名 引擎，不仅检索速度快，还普遍实现了自动分类、自动摘要、自动索引等功能， 使w e b 信息得到有效的组织，极大地方便了用户对i n t e r n e t 信息的查找和利用。 目前国外对全文数据库的研究方兴未艾，已有一些较成熟的商用产品出现。 由于中西文问的巨大差异，简单地移植改造国外成果的方法是行不通的，而且可 能是市场竞争和商业机密的缘故，我们甚至发现国外企业界的产品水平超过学术 界的论文水平。因此在我们国内进行面向中文文本的全文数据库的研究非常必 要，它在目前的重要性可以与汉字编码技术和汉字排版技术在几年i j i 的重要性相 媲美。 1 2 2 全文检索的研究内容 作为一种特殊的数据库系统，全文数据库要完成的工作仍然是传统数据库的 两大功能：存储和检索，具体而言就是文本数据的存储和任意字符串的检索。后 一项功能就是与本技术手册密切相关的全文检索。 数据库系统的两大功能中，检索更具有核心的地位，可以认为全文数据库研 究的重点是全文检索，而全文检索的关键又是全文索引。一般全文索引的研究内 容主要有：l 索引的空间效率；2 索引的检索效率；3 索引的创建效率。而更加 实用的全文索引还应该增加两项研究内容：1 索引的动态效率；2 索引的语义能 力。 8 1 3 论文的组织 本文从搜索引擎的工作原理及其实现技术进行分析，从中可以了解限制搜索 引擎性能改善用户体验的因素到底有哪些。由于互关联后继树作为一种优秀的全 文模型，在全文检索领域发挥着重要的作用。所以本文虽然着力于搜索引擎的核 心技术与应用的研究，但互关联后继树全文模型贯穿始终几乎渗透在所有的关键 技术之内 论文的内容结构如下：第一章和第二章概述了搜索引擎的发展与现状并简单 介绍了搜索引擎的基本实现原理；第三章概述了基于互关联后继树搜索引擎的基 础知识：第四章详细论述了基于互关联后继树模型搜索引擎的核心技术与其创新 点；第五章则从实际应用角度出发，详细阐述了基于互关联后继树模型搜索引擎 在中国电信黄页信息检索系统中的应用，并附上大量的应用环境测试数据来展示 该模型下搜索引擎的种种优势；第六章中对现有模型提出了相当实用的改进意 见，以便更好的发挥基于互关联后继树模型搜索引擎的优势和作用；在最后的结 束语中，对相关工作进行了总结和展望 9 第二章搜索引擎相关知识介绍 2 1 引言 搜索引擎( s e a r c he n g i n e s ) 是对互联网上的信息资源进行搜集整理，然后 供你查询的系统。它包括信息搜集、信息整理和用户查询三部分。 搜索引擎是一个为你提供信息“检索”服务的网站，它使用某些程序把因特 网上的所有信息归类以帮助人们在茫茫网海中搜寻到所需要的信息。 早期的搜索引擎是把因特网中的资源服务器的地址收集起来，由其提供的资 源的类型不同而分成不同的目录，再一层层地进行分类。人们要找自己想要的信 息可按他们的分类一层层进入，就能最后到达目的地，找到自己想要的信息。这 其实是最原始的方式，只适用于因特网信息并不多的时候。随着因特网信息按几 何式增长，出现了真正意义上的搜索引擎，这些搜索引擎知道网站上每一页的开 始，随后搜索因特网上的所有超级链接，把代表超级链接的所有词汇放入一个数 据库。这就是现在搜索引擎的原型。 随着y a h o o ! 的出现，搜索引擎的发展也进入了黄金时代，相比以前其性能更 加优越。现在的搜索引擎已经不只是单纯的搜索网页的信息了，它们已经变得更 加综合化，完美化了。以搜索引擎权威y a h o o ! 为例，从1 9 9 5 年3 月由美籍华裔 杨致远等人创办y a h o o ! 开始，到现在，他们从一个单一的搜索引擎发展到现在 有电子商务、新闻信息服务、个人免费电子信箱服务等多种网络服务，充分说明 了搜索引擎的发展从单一到综合的过程。 然而由于搜索引擎的工作方式和因特网的快速发展，使其搜索的结果让人越 来越不满意。例如，搜索“电脑”这个词汇，就可能有数百万页的结果。这是由 于搜索引擎通过对网站的相关性来优化搜索结果，这种相关性又是由关键字在网 站的位置、网站的名称、标签等公式来决定的。这就是使搜索引擎搜索结果多 而杂的原因。而搜索引擎中的数据库因为因特网的发展变化也必然包含了死链 接。 2 2 搜索引擎核心技术介绍 搜索引擎并不真正搜索互联网，它搜索的实际上是预先整理好的网页索引数 据库。真正意义上的搜索引擎，通常指的是收集了因特网上几千万到几十亿个网 页并对网页中的每一个词( 即关键词) 进行索引，建立索引数据库的全文搜索引 擎。当用户查找某个关键词的时候，所有在页面内容中包含了该关键词的网页都 l o 将作为搜索结果被搜出来。在经过复杂的算法进行排序后，这些结果将按照与搜 索关键词的相关度高低，依次排列。 现在的搜索引擎已普遍使用超链分析技术，除了分析索引网页本身的内容， 还分析索引所有指向该网页的链接的u r l 、a n c h o r t e x t 、甚至链接周围的文字。 所以，有时候，即使某个网页a 中并没有某个词比如“恶魔撒旦”，但如果有别 的网页b 用链接“恶魔撒旦”指向这个网页a ，那么用户搜索“恶魔撒旦”时也 能找到网页a 。而且，如果有越多网页( c 、d 、e 、f ) 用名为“恶魔撒旦” 的链接指向这个网页a ，或者给出这个链接的源网页( b 、c 、d 、e 、f ) 越 优秀，那么网页a 在用户搜索“恶魔撒旦”时也会被认为更相关，排序也会越靠 前。 搜索引擎的原理，可以看做三步：从互联网上抓取网页一建立索引数据库一 在索引数据库中搜索排序。 从互联网上抓取网页 利用能够从互联网上自动收集网页的s p i d e r 系统程序，自动访问互联网， 并沿着任何网页中的所有u r l 爬到其它网页，重复这过程，并把爬过的所有网页 收集回来。 建立索引数据库 由分析索引系统程序对收集回来的网页进行分析，提取相关网页信息( 包括 网页所在u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大 小、与其它网页的链接关系等) ，根据一定的相关度算法进行大量复杂计算，得 到每一个网页针对页面内容中及超链中每一个关键词的相关度( 或重要性) ，然 后用这些相关信息建立网页索引数据库。 在索引数据库中搜索排序 当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合该 关键词的所有相关网页。因为所有相关网页针对该关键词的相关度早已算好，所 以只需按照现成的相关度数值排序，相关度越高，排名越靠前。 最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返 回给用户。 搜索引擎的s p i d e r 一般要定期重新访问所有网页( 各搜索引擎的周期不同， 可能是几天、几周或几月，也可能对不同重要性的网页有不同的更新频率) ，更 新网页索引数据库，以反映出网页内容的更新情况，增加新的网页信息，去除死 链接，并根据网页内容和链接关系的变化重新排序。这样，网页的具体内容和变 化情况就会反映到用户查询的结果中。互联网虽然只有一个，但各搜索引擎的能 力和偏好不同，所以抓取的网页各不相同，排序算法也各不相同。大型搜索引擎 的数据库储存了互联网上几亿至几十亿的网页索引，数据量达到几千g 甚至几万 g 。但即使最大的搜索引擎建立超过二十亿网页的索引数据库，也只能占到互联 网上普通网页的不到3 0 ，不同搜索引擎之间的网页数据重叠率一般在7 0 以下。 我们使用不同搜索引擎的重要原因，就是因为它们能分别搜索到不同的内容。而 互联网上有更大量的内容，是搜索引擎无法抓取索引的，也是我们无法用搜索引 擎搜索到的。心里应该有这个概念：搜索引擎只能搜到它网页索引数据库里储存 的内容。你也应该有这个概念：如果搜索引擎的网页索引数据库里应该有而你没 有搜出来，那是你的能力问题，学习搜索技巧可以大幅度提高你的搜索能力。 2 3 主流搜索引擎介绍 目前市场上的搜索引擎已经是名目繁多让人眼花缭乱了，但占据主导地位的 搜索引擎依然是屈指可数。在这里我们列举以下5 个： g o o g l e 一业界霸主的地位无人能及，是目前世界最大的搜索引擎。 百度一中国本土搜索引擎“老大”，随着在美国纳斯达克的上市，未来发展 空间巨大。 搜狗一第三代互动式中文搜索引擎。 雅虎一雅虎公司基于全球领先的y s t 技术，在中国推出的搜索门户，整合了 原来一搜搜索引擎。 中国搜索一其搜索引擎技术被国内众多知名门户网站所采用，同时也是中 国搜索联盟的发起组织之一。 搜索引擎；首页满意度搜索结果满意度自定个性化界面语言 义搜索结主页 i果条数i 6 0 0 9 l e i - k - t - a 2- k 支持 支持4 多语言界面 百度支持不支持多语言界面 雅虎不支持支持多语言界面 搜狗， 支持不支持中文界面 中国搜索 l- k a - 不支持不支持中文界面 提示：最高为。 表2 - 1 主流搜索引擎页面比较 总体来说，五位“选手”在外貌方面的比试，g o o g l e 、百度和雅虎略胜一筹， 其他的在伯仲之间。 一- 。”。一q 。一”1一一”- 搜索引擎搜索结果搜索时间有效结果条数综合评价l o o o g l e 百度 雅虎 搜狗 中国搜索 4 。1 1 0 。0 0 0 条0 0 4 秒 5 ，9 5 0 ，0 0 0 条0 0 0 1 秒 6 ，2 0 0 ，0 0 0 条0 0 2 秒 2 ，7 1 6 ，1 8 7 条0 0 0 7 秒 2 ，4 5 0 ，0 0 0 条0 0 0 3 秒 9 条 1 0 条 9 条 6 条 8 条 提示：最高为 表2 - 2 主流搜索引擎搜索结果比较 搜索关键字是”超级女生”的时候，从搜索结果上来看，雅虎是最多的，以 6 ，2 0 0 ，0 0 0 条高居榜首；从搜索速度上来看，百度的搜索速度最快，其搜索准确 率也是最高的。 搜索引擎地图载入速两点距离；地图缩放公交换乘、驾车 支持城市4 综合评价 度：测量l路线 6 0 0 9 l e ，一般：不支持支持不支持 主要城市|； 百度，快支持支持支持主要城市i 搜狗慢2支持支持支持主要城市l 中国搜索快；支持 支持 支持大部分城市； 注：雅虎不提供地图搜索功能表 表2 3 主流搜索引擎图片搜索比较 图片搜索作为一种搜索引擎最常见的应用之一，通过以上使用不同的关键词 的综合对比，百度表现不俗，还支持新闻图片搜索：g o o g l e 、雅虎在单个和多个 关键词搜索前后表现不够稳定；而中国搜索表现的则中规中矩。因为图片搜索可 能不是搜狗的优势项目，整体表现的不够理想。 综合多方面因素，百度在表现都比较出色，堪称“全能搜索引擎”。而老牌 搜索引擎g o o g l e 的表现前后迥异，强大的网页搜索功能，并不能掩盖他在中文 图片、本地搜索方面的薄弱。虽然面对百度、g o o g l e 这样“重量级”的“选手”， 网页搜索让搜狗寒碜了一次。但是搜狗在音乐搜索和地图搜索方面表现出了超强 的实力。而雅虎同样有这样的经历，在其他项目并不占优的情况下，雅虎的图片 搜索帮他挽回了不少面子。而中国搜索的表现算是中规中矩了，没有明显的亮点， 也没有明显的弱点。 第三章互关联后继树搜索引擎概要 3 1 互关联后继树模型概要 互关联后继树( i n t e rr e l e v a n ts u c c e s s i v et r e e s ) 模型是在2 邻接矩阵模 型的研究中发展出来的一种新模型，模型提出时为二元模型。为了解二元i r s t 模型，我们先给出一个实例，结合此实例给出下列定义。 实例：设有文本库为字符串abcdab dbc 口 其中字符“口”为文本库的结尾符，a ，b ，e ，d 芑，我们可得到如下二 元互关联后继树表达式、互关联后继树、精简互关联后继表达式和精简互关联后 继树( 图3 卜图3 6 参照定义7 ，定义1 1 和定义1 2 ) 。 a ( b ( e ) ，b ( d ) ) ，b ( e ( d ) ，d ( b ) ，c ( 口) ) ，e ( d ( a ) ，口) ，d ( a ( b ) ，b ( c ) ) ( 对原文中每个字符考察其后的两个字符得到的二元后继表达式，两层括号：) 图3 - 1 二元互关联后继表达式 ( 下图则是二元互关联后继树的表现图：) 图3 2 二元互关联后继树 a ( b ( 1 ) ，b ( 2 ) ) ，b ( c ( 1 ) ，d ( 2 ) ，c ( 2 ) ) ，c ( d ( 1 ) ，口) ， d ( a ( 2 ) ，b ( 3 ) ) ( 用序号代替符号得到二元精简后继表达式：) 图3 3 二元精简互关联后继表达式 图3 4 二元精简互关联后继树表现图，叶子括号中的数字为位置信息 注意：精简互关联后继树中叶子的标记和后继分枝的序正好一致，称为该叶 渤哭勘釜葛 只m 苍 子的后继信息。 ( 树枝按字典排序后，把相同字符合并得到优化的后继表达式：) a ( b ( 1 ) ，b ( 3 ) ) ，b ( c ( 1 ，2 ) ，d ( 3 ) ) ，c ( d ( 1 ) ，口) ，d ( a ( 2 ) ，b ( 2 ) ) 图3 - 5 优化后的二元精简互关联后继表达式 哭： 苍。劲迨圆 图3 6 优化后的二元精简互关联后继树表现，叶子括号中的数字为位置信息 定义l ：是数目有限的字母表，全文数据库中用到的字母均属于，记作 i i = m ，即字母表字母数目为m ，上例中= a ，b ，c ，d ，口 ，i l = 5 。 定义2 ：对任意a1 ，a2 ，字符串d1a2 中，l 称为a2 的前驱，d2 称为nl 的后继 定义3 ：对于任意字符串1q2 ai an ，i 芑，i = l ，2 ，n ，i 指 明字符ni 在字符串中的位置，dlq2 an 构成一个全文数据库，上例中全文 数据库就是abadab db 口。 定义4 ：在全文数据库中若di l ，i 2 ，f li n 为相同的字符，不妨记作 b ，则b ，则所有b 和它的后继构成一个一元后继表达式b ( ni 1 + 1 ，a i 2 + 1 di n + 1 ) ，其中b 为根结点，oi 1 + 1 ，ai 2 + 1 ，ai n + l 为后继结点。 上例中第二、第五、第七个字符均为b ，它和它的后继构成一元后继表达式b ( c ，d ， 口) 。 定义5 ：在全文数据库中，若ai ldi 1 + 1 ，qi 2 qi 2 + 1 qi m di m + l 是相同 的二连字符，不妨记作ab ，其中q ，e ，则所有ab 和它的后继构成 一个二元后继表达式，记作d ( b ( di 1 + 2 ，qi 2 + 2 ai m + 2 ) ) ，其中ab 为根 结点。oi 1 + 2 ，i 2 + 2 di m + 2 为后继结点。例如上例中a b 出现两次，后面跟 的分别是c 和d ，则有二元后继表达式a ( b ( c ，d ) ) 。 依此类推，可定义n 元后继表达式，n = 3 ，4 定义6 ：对任意一元后继表达式，q ( i 1 ，ai 2 ai m ) 中任一子结点n i r ，1 r m ，若存在i r ( j l ，qj k ，f li n ) ，且nqi r aj k 正 文q1a2 dn ，贝0 称d ( ai 1 ，ai ( r 一1 ) ，oi r ( aj k ) ，i ( r + 1 ) ，ai m ) ， 为d ( oi 1 ，di 2 ，ai r ，i m ) 关于qi r 的二元互关联后继表达式。 定义7 ：令o ，且f l 0 1 一n ，对所有的后继表达式中所有后继子结 点进行后继关联，得到的关联后继表达式的全体称为互关联后继表达式，见图 3 一l 。由关联后继表达式生成的互关联后继树是一个相互关联的树林，见图3 2 。 氇 |” 定义8 ：若aiqi + l q1 ”dn ，则ai i + l 。性质：若ai di + l ，ai + l ai + 2 ，则i ai + 2 。 定义9 ：若后继表达式( di 1 ，ai m ) 中ai l ai m 满足ai 1 qi 2 ( ai m ，则称n ( ai l ，ni m ) 为有序后继表达式，上例中是有序后继表达式 和有序后继树。 定义1 0 ：映射f 是后继表达式关于根结点至子结点的标记，如果f 满足： f ( d ( qi l ，ai 2 i m ) ) = a ( 1 ，2 ，m ) ，映射f 是一种保序映 射。 定义1 1 ：互关联有序后继表达式经过保序f 映射后得到的互关联后继表达式 称精简的互关联后继表达式，见图3 3 。由精简的互关联后继表达式得到的树林 是精简的互关联后继树，见图3 - 4 。精简互关联后继树中叶子的标记称为该叶子 的后继信息。 定义1 2 ：优化的t r s t 模型，在普通i r s t 模型精简后的基础上，对后继树 的叶子进行字典排序，合并同样字符的叶子节点，对同一个字符的叶子进行保序 映射，其表达式和表现见图3 - 5 和图3 6 。 性质： 任意字符串可按c o 进行关联分解，任意文本数据库均可表达成互关联后继 表达式。q1 an 口= ala2 a3 0 0q2a3 a4 an 一2c in 一1an o oan 一1 n 口o oan - lan 口o oan 口 显而易见，分解完后可以依此构造互关联后继树与互关联后继表达式。 二元互关联后继树是一种相互关联的树林。树根是文本中所有可能出现的字 符，利用一个数组，下标可方便地表达所有可能的后继树的根位置。查询时则从 目标字符串的首字符出发，如本节实例中： 查询单字符比如a ，从图3 - 6 中看出a 为根的树只有两个分枝，有两个解； 查询双字符串比如a b ，从根结点为a 的后继树中遍历所有叶结点为b 的分 枝，由于有两个分枝，所以有两个解： 查询多字符串比如b c d ，从根为b 的后继树出发，b 的后继分枝中只有一个 分枝为c ，所以最多有一个解。根据c 的关联后继为d ，我们立即得到b c d 有一 个解。 具体应用中，互关联后继树模型有分段式存储和文章式存储两种方法。由于 实际中数据库中数据主要是分成多文档存放，因此二元互关联后继树的应用系统 也是基于多文档的系统。即索引单元中存放文档号，输出的结果也是基于文档的 匹配。系统的实现，包括创建索引库，查询等过程实现参见参考文献 1 2 1 3 t 4 。 1 6 相比于前面几种索引模型，由于互关联后继树模型的查询最大复杂性为目标 字符串第一个字符为根的后继分技数，其后的步骤中复杂性渐减，因此时间性能 是非常好的；而在使用了精简和优化技术后，其空间性能也得到提升的。另外， 该模型还能方便地实现多种查询功能和原文生成。 3 2 搜索引擎与互关联后继树的结合 存 图3 7 搜索引擎各个组成部分的关系 图3 7 描述了一般搜索引擎的系统架构，其中包括页面搜集器、索引器、检 索器、索引文件等部分。 索器接口 器接口 互关联后继树切词l存取更新接口 互关联百珏橱授素t i 买蔟屠珏橱更薪t 1 羁两事霸丽 互关联后继树索引模型 图3 8 互关联后继树与搜索引擎核心部件关系 图3 8 结识了搜索引擎中的核心部件与互关联后继树全文模型的密切关系，互关 联后继树作为一种优秀的全文模型几乎渗透在搜索引擎所有的关键技术中。 1 7 曰卣 第四章互关联后继树搜索引擎核心技术 4 1 词索引核心技术 词表索引创建算法：c r e a t e w o r d t a b l e i n d e x ( t ，& i s t r e e ) 功能：创建词表的二元后继有序的互关联后继树索引 输入：词表全文t ( 由词w 1w 2 w n 以及词之间的分隔符号”组成) 符集合，其中w i 木 输出：二元后继有序的互关联后继树i s t r e e 步骤： 初始化：清空双字符频率数组f r e q i 1 i 1 ， 后继编号数组p o s 1 i 】 i 门 s t e p l ：a = r e a d f r o m t e x t ( t ) ： b = r e a d f r o m t e x t ( t ) ： 顺序读取t 中的相邻字符到a ，b s t e p 2 ：f r e q a b + + ：统计双字字频 a = b ： b = r e a d f r o m t e x t ( t ) ： s t e p 3 ：i f ( b = = ) b 是词的分割符号 j u m p s e p a r a t o r ( t ) ：跳过分隔符号 i f ( b = = e n d o f f i l e ( t ) ) 转到s t e p 4 e l s e 转到s t e p 2 s t e p 4 ：f o r ( a = m i n ( z ) ：a 1 i ：a = n e x t ( a ，) ) f o r ( b = m i n ( ) ：b 3 时 s t e p 2 ：a 2 在a 1 中的后继区间为 p s t a r t c u r r ，p e n d c u r r a l a 2 其对应的后继 序列为 a l a 2 a 3 在a 2 中的后继区间为 p s t a r t c u r r ，p e n d c u r r a 2 a 3 求出 l = a l a 2n p s t a r t c u r r ，p e n d c u r r a 2 a 3 s t e p 3 ：i f ( i = = m ) 没有后继序列 w o r d = n u l l ： 转到s t e p 5 ) e 1 s e i f ( i ii = = 1 ) 取出x i i f ( x 是一个词尾结束标志) w o r d = a l a 2 oo a i + 2 e l s e w o r d = n u l l 转到s t e p 5 e 1 s e i f ( i 1 i 一1 对应该后继区间的后继序列为 i 一1 求出 i = i 一1n p s t a r t c u r r ，p e n d c u r r a i + l a i + 2 转到s t e p 3 s t e p 5 ：算法结束 2 l 使用基于后继区间的互关联后继树搜索思想来处理切分词是本算法的最大 特色所在。本算法是在基于后继区间的互关联后继树搜索基础上，加入了切分词 相关的一些特殊处理，算法的时间复杂度和空间复杂度与基于后继区间的互关联 后继树搜索完全相同。在前述章节和参考文献 1 1 中已经对基于后继区间的互关 联后继树搜索算法的性能进行了具体的分析，这里就不详细叙述了。要说明的是， 虽然该算法输出是一个切分词w o r d ，但本质上是对一个长度为s i z e o f ( w o r d ) 的 字符串进行搜索。基于后继区间的互关联后继树搜索即便是对长字符串和大文 本库索引，其搜索效率也是非常高的( 详见前述章节和参考文献 1 1 ) 。对于这种 长度只有s i z e o f ( w o r d ) 的词表索引，每个切分词花费的实际时间都是在微秒级 别的。 词索引创建算法：c r e a t e w o r d i n f o i n d e x ( w o r d t a b l e i n d e x ，s t r i n g s t r e a m ) 功能：创建词索引 输入：切词所需的词表索引，需要创建词索引的字符流a l a 2 a n 输出：创建到磁盘上的词索引 步骤： 初始化：w o r d i n f o p o s 和p w o r d i n f o q u e 为磁盘上索引文件的起始位置，i = l s t e p l ：w o r d i n f o w o r d = c u t w o r d f r o m s t r i n g ( a i a i + l a n ) ： 获得切分的词 s t e p 2 ：i f ( w o r d i n f o w o r di _ n u l l ) 将词信息写入索引文件中偏移量为w o r d i n f o p o s 的位置处 w r i t e ( w o r d i n f o p o s ，w o r d i n f o ) ： 链接词w o r d 的单链表队列 * p w o r d i n f o o u e w o r d i n f o n u m n e x t = w o r d i n f o p o s ： w o r d 链表队列中下一个词的位置 p w o r d i n f o q u e w o r d l n f o n u m = w o r d i n f o p o s ： p w o r d i n f o p o s + + ； e 1 s e i + - 一个字符长度：切词失败，则偏移一个位置 s t e p 3 ：i + _ s t r l e n ( w o r