（计算机科学与技术专业论文）基于互关联后继树模型的词索引方法研究.pdf

摘要 随着i n t e m e t 的快速发展，人们越来越希望能够在庞大的网页库中快速准确地找到 自己想要的信息，全文检索技术应运而生。它对文档的全部文本数据都建立索引并提供 检索，目自订己逐渐成为w e b 信息检索的主流技术。索引建库策略和索引模型是全文检 索技术的核心内容，如何将两者合理结合以提高全文检索系统的性能具有重要的研究意 义。 介绍了全文检索技术的知识体系，对现有的索引建库策略进行了研究和比较，选择 了基于词表的建库策略作为研究内容。通过对词索引方法中的中文自动分词技术的研 究，选择了基于p a t r i c i a 树词典结构的分词方法，可以很方便的增加新词条，并且采 用f 向加字匹配法进行分词操作，提高了切分的效率。 分析了主流的索引模型及其优缺点，在现有的索引模型中，互关联后继树模型具有 较快的创建和查询速度、查询方式多样化等优点，因此深入研究了该模型的结构以及算 法。目前对该模型的研究中，大都使用字索引方法，普遍存在检索精度低、索引膨胀比 高等问题，因此将基于分词的建库策略应用在以互关联后继树模型为索引模型的伞文检 索系统中，对全文本分词后建立互关联后继树索引，既能保证较高的查准率，又能降低 索引的膨胀比。另外将分词词典的树结构与互关联后继树索引文件进行关联，在检索过 程中对查询字符串分词时可以直接查找索引文件，大大提高了检索的效率。 最后，通过实验对这种新型的索引方法进行验证与分析，实验结果表明，该方法提 高了查准率，并有效降低了索引的膨胀比。 关键词：全文检索，互关联后继树模型，词索引，中文分词 t h er e s e a r c ho f “白r di n d e xm e t h o db a s e do ni 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 sm o d e l c h e nj u n t a n g ( c o m p e e rs i c e n c ea n dt e c h n o l o g y ) d i r e c t e db ys e n i o re n g i n e e rz h a n gw e n d o n g 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 t ，p e o p l ei n c r e a s i n g l yw a n tt of i n dt h ei n f o r m a t i o n t h e yw a n tf r o mw e bp a g e sq u i c k l ya n da c c u r a t e l y , t h u sf u l l - t e x tr e t r i e v a lt e c h n o l o g ye m e r g e d t h et e c h n o l o g yo fb u i l d i n gi n d e xa n dp r o v i d i n gr e t r i e v a lf o rt h ef u l lt e x to ft h ed o c u m e n th a s g r a d u a l l yb e c o m et h em a i n s t r e a mo fw e bi n f o r m a t i o nr e t r i e v a l i n d e xc o n s t r u c t i o ns t r a t e g i e s a n di n d e x i n gm o d e la r et h ec o r eo ff u l l t e x tr e t r i e v a lt e c h n o l o g y h o wt oc o m b i n et h e mf o r i m p r o v i n gt h ep e r f o r m a n c eo f f u l l t e x tr e t r i e v a ls y s t e mi so fg r e a ts i g n i f i c a n c e t h ek n o w l e d g es y s t e mo ff u l l t e x tr e t r i e v a lt e c h n o l o g yi si n t r o d u c e d t h e nt h ee x i s t i n g i n d e xc o n s t r u c t i o ns t r a t e g i e sa r es t u d i e da n dc o m p a r e d ，b yw h i c ht h ei n d e xc o n s t r u c t i o n s t r a t e g yb a s e do nv o c a b u l a r ya st h ec o n t e n to fr e s e a r c hi sc h o o s e n c h i n e s ea u t o m a t i cw o r d s e g m e n t a t i o nt e c h n o l o g yi nw o r d b a s e di n d e xm e t h o di sd e e p l ys t u d i e d a i mt os o l v et h e d i f f i c u l t yo fu p d a t i n gt h ed i c t i o n a r ya n ds l o ws e a r c h i n gs p e e d ，a ni m p r o v e dp a t r i c i at r e e d i c t i o n a r ys t r u c t u r ei sp r o p o s e d i tc a ne a s i l ya d dn e we n t r i e s ，a n du s ef o r w a r dm i n i m u m m a t c h i n gm e t h o dt oc u tw o r d s ，w h i c hi m p r o v e st h ee f f i c i e n c yo fs e g m e n t a t i o n t h ep o p u l a ri n d e xm o d e l sa n dt h e i ra d v a n t a g e sa n dd i s a d v a n t a g e sa r ea n a l y z e d a m o n g t h ee x i s t i n gi n d e xm o d e l s ，t h ei 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 ) m o d e lh a saf a s t e rs p e e d t oc r e a t ea n dq u e r y , q u e r yf o r m s ，e t c ，s ot h es t r u c t u r ea n da l g o r i t h m so ft h em o d e la r ed e e p l y s t u d i e d t h ep r e s e n ts t u d yo ft h i sm o d e lm o s t l yu s e st h ew o r di n d e x i n gm e t h o d ，w h i c hh a sl o w r e t r i e v a la c c u r a c ya n dr e l a t i v e l yh i g h e ri n f l a t i o np r o b l e m s s ow ea p p l i c a t et h ew o r d b a s e d s t r a t e g yo fb u i l d i n gd a t a b a s e 、加t ht h ef u l l - t e x ts e a r c hs y s t e mw h i c hu s e si r s tm o d e la si t s i n d e xm o d e l w eb u i l dt h ei r s tm o d e la f t e rt h ef u l lt e x th a sb e e nc u ti n t ov o c a b u l a r y s ，w h i c h h a sh i g hp r e c i s i o na n dc a nr e d u c et h ee x p a n s i o nr a t i oo ft h ei n d e x t h e nt h et r e es t r u c t u r eo f w o r dd i c t i o n a r ya n di r s ti n d e xf i l e sa r ea s s o c i a t e d ，w h e ns e g m e n tt h eq u e r ys t r i n gi nt h e r e t r i e v a lp r o c e s s ，i n d e xf i l e sc a nb el o o k e du pd i r e c t l y ，w h i c hg r e a t l yi m p r o v e st h er e t r i e v a l e f f i c i e n c y f i n a l l y , t h en e wm e t h o do fi n d e xi s v e r i f i e da n da n a l y z e db ye x p e r i m e n t 。t h e e x p e r i m e n t a lr e s u l ts h o w st h a tt h i sm e t h o d c a r li m p r o v et h ep r e c i s i o na n de f f e c t i v e l yr e d u c e t h ee x p a n s i o nr a t i oo fi n d e x k e yw o r d s ：f u l l t e x tr e t r i e v a l ，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 sm o d e l ，w o r d s - b a s e d i n d e x ，c h i n e s ew o r ds e g m e n t a t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：隘j 丝些日期：沙p 年歹月夕，) 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：随：工塾垒 指导教师签名： 毖交煎， 日期：知f 口年多月? 雷日 日期：加，p 年厂月歹) 日 中国石油大学( 华东) 硕上学位论文 1 1 课题背景与意义 第一章绪论 随着互联网的迅速发展，网络上的信息量急剧增长，据c n n i c ( 中国互联网络信息 中心) 统计，自2 0 0 3 年开始，我国的网页规模基本上逐年保持翻番增长，截止2 0 0 9 年网 页数量已经达到了3 3 6 亿个。网页作为网络信息的主要载体，其内容丰富而又复杂，如 何在庞大而又急剧膨胀的网页库中快速准确地搜索到用户所需要的信息是当前信息检 索领域面临的一大挑战。在这种背景下，全文检索技术成为目前w e b 领域的一个研究热 点。 全文检索技术就是以全文本信息为主要的检索对象，允许用户通过布尔逻辑或自然 语言的方式查询文本内容的技术。它的核心内容主要在于索引策略的选择和索引模型 的构建。中文检索技术存在两种建索引库策略，即基于字表的建库策略【2 】和基于词表的 建库策略【3 】，基于单字的建库策略构建索引库方便直观，实用性好，不会漏检，在前几 年很受追捧，但是庞大的索引库以及无用信息的检出使得这种方法越来越不适应日新月 异的w e b 环境；基于分词的建库策略实现起来比较困难，因为词与词之间在文本中没 有明显的分界，以词作为索引项需要借助于分词等技术，在精度和效率方面都还达不到 英文分词的效果，于是中文自动分词技术【4 】成为了近几年中文检索技术的研究热点。 索引模型是一个关键的数据结构，它提供了数据的快速存取，并能够加快查询处理 任务的速度。主要有以下几种索引模型：签名文件模型( s i g n a t u r ef i l e s ) 【5 】、倒排文档模 型( i n v e r t e df i l e ) 6 1 、后缀树模型 7 1 、互关联后继树模型( 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 s ) 8 】 等。很多人对众多知名搜索引擎所使用的倒排文档模型进行了深入的研究，因为这种模 型结构简单，对单词的查询速度快：却很少有人关注互关联后继树模型，作为一种较新 的索引模型，它具有较快的创建和查询速度，查询功能也比较多样化。目前对这种模型 的研究仅限于基于单字的建库策略，并未摆脱这种建库策略的落后性。 本文旨在对基于互关联后继树索引模型的词索引方法进行研究，将中文自动分词技 术与互关联后继树索引模型相结合，充分发挥两者的优点，提高索引创建和检索的效率、 查准率【9 】并降低索引的膨胀比【1 0 1 。 第一章绪论 1 2 国内外研究现状 国外的全文检索技术诞生时间比较早，发展也比较成熟，目前已经在门户网站、数 字图书馆和搜索引擎等许多领域有了广泛的应用，其中搜索引擎是全文检索技术比较主 要的一个应用，如我们常用的g o o g l e 等搜索引擎，已经成为我们获取网络信息的必备工 具。另外也出现了一些较成熟的商业产品，如：1 9 7 2 年丌始提供搜索服务的美国d i a l o g 国际联机检索系统、美国系统发展公司( s y s t e md e v e l o p m e n tc o m p a n y ，简称s d c ) 的 o r b i t 系统、i b m 的l o t u sn o t e s 群件工作组系统等；几大数据库厂商也对其数据库产品 提供了全文索引的功能，如：o r a c l e 数据库中的o r a c l e t e x t 组件、s q l s e r v e r 数据库中7 o 版本以后出现的全文检索功能，以及d b 2 数据库的t e x te x t e n d e r 。国外的全文检索技术 都是基于词索引方法的，因为计算机是适合英文环境的，而英文又以单词为基本语言元 素，只要对单词建立索引，就可以提供全文检索服务。 国外全文检索技术在发展的过程中出现了几种在不同时期比较流行的索引模型。 a b o o k s t e i n i 等提出了将位图索引应用在中等规模的信息检索系统中，可以很方便地通 过词语在逻辑上的不同组合检索文本片段，但是位图索引包括后来的签名文件都是采用 类似二进制的编码形式，检索模式比较单一，难以实现功能的扩展。w b c r o f t | 眩l 等提 出了一种t i l e 树型的后缀树索引结构，对文本从头到尾建立所有后缀，能够实现前缀检 索等t r i e 检索模式，不足之处在于索引的空问占用太多。m a n b e r l l 3 1 等提出了后缀数组的 概念，即按照词典顺序排列并存储后缀树的叶结点指针的数组，由于可以使用二元检索， 因此执行检索操作所花费的时间大大缩短了，不足之处在于后缀数组和原文本最好都存 储在主存中，不适应大型文本索引的构造。a l i s t a i rm o f f a t m l 等提出了一种基于倒排文档 的自索引，通过为每一个倒排表插入少量的辅助消息的方式，在小幅度增长索引存储空 间的情况下提高了布尔检索的时间效率，不足之处在于这种索引模型由于将倒排索引分 成了许多小块，导致访问硬盘的时间丌销超过了压缩所提高的时间效率。目自订比较流行 的模型主要是倒排文档模型，虽然也有对签名文件模型和后缀树模型的研究，最终都因 为索引空间占用过大或索引创建时间过长而逐渐淡出人们的视野。 国内的全文检索技术的研究起步较晚，始于1 9 7 8 年左右，但发展速度比较快。首先 着手研究的是数字图书馆方面，如1 9 9 9 年中国国家图书馆开始的启动“中国数字图书馆 工程”，结合汉字处理的特点开发适合中文检索的全文数据库。提供中文信息检索的全 2 中国石油大学( 华东) 硕士学位论文 文检索系统也开始出现，如百度、北京大学开发的北大“天网 搜索引擎以及华南理工 大学开发的w w w 服务器的中英文全文检索系统等。 国内的全文检索系统在发展过程中，根据建库策略的不同使用的索引模型也不尽相 同。曹元大2 1 等实现了一个基于字表法的中文w e b 文档全文检索系统，索引模型使用的 是倒排文档模型，该系统的优点是不需要构造分词词典，不会发生漏检，另外由于系统 中采用了压缩算法对文本编号和字在文本中的位置信息进行了压缩，减少了索引的膨胀 比；缺点是采取字表法建库会检出大量与检索请求无关的文档，另外倒排表模型中需要 存储每个字在文本中的位置信息，即使采用了压缩算法，仍然会占用大量的存储空间， 而且解压缩过程会降低_ 定的检索速度。刘学文【l5 j 等提出了一种倒排文件与后缀树相结 合的后继数组模型，即将文本的排列和后缀数组的排列保存在一个文件中，减少文本位 置的存储，在创建和检索索引时无需频繁的读取这两个排列，提高了空间效率和时间效 率，不足之处是将多种索引机制的结合往往增加了实现的复杂度，而且面对大规模数据 的时候性能并不佳。 总的来说，目前国内全文检索技术在索引建库策略方面的研究主要集中在自然语言 处理、人工智能等领域，在索引模型方面的研究主要集中在新型索引结构开发、索引压 缩及分布式存储等领域。 1 3 论文研究内容 论文的主要研究内容如下： ( 1 ) 全文检索技术 全文检索技术是一个综合的知识体系，包括建索引库的策略、索引模型的选择、检 索模型的选择等多方面的内容，如何将其中的各个模块有机的组合在一起以发挥更好的 性能是本文的主要研究内容，其中涉及到各个模块在整个系统中发挥什么样的作用，模 块与模块之间是如何相互关联的等等。 ( 2 ) 中文分词方法 中文自动分词方法是基于词表的建库策略的核心内容，有的方法利用分词词典通过 匹配的方式进行分词，有的方法利用数学上的统计学原理对大规模的语料库进行计算来 判断是否成词，如何选择一个合适的分词方法是本文的一个研究内容。 第一章绪论 ( 3 ) 互关联后继树索引模型 互关联后继树模型是一种新型的针对中文检索提出的索引模型，为什么这种索引结 构有较好的时间性能及空间性能，如何对其改进以提高它的性能是本文的一个研究内 容。 ( 4 ) 基于互关联后继树模型的词索引方法 如何将互关联后继树模型与基于分词的索引策略进行结合，结合的过程中有哪些关 键问题需要注意，是本文的重要研究内容。 1 4 论文组织结构 论文共分六章，具体结构如下： 第一章“绪论 ，阐述了本课题的研究背景与意义、国内外研究现状，并介绍了论 文的主要研究内容，最后给出论文的组织结构。 第二章“全文检索技术综述”，介绍了全文检索技术的知识体系，然后分别对体系 结构中的关键模块进行了阐述。 第三章“中文自动分词方法的选择”，介绍了目前主流的中文自动分词方法，并进 行了比较，经过分析与研究选择了基于词典的中文自动分词方法。 第四章“互关联后继树索引模型改进 ，介绍了互关联后继树索引模型的相关定义 及操作，分析了几种该模型的扩展模型，对互关联后继树模型进行了改进。 第五章“基于互关联后继树模型的词索引方法实现的关键技术”，对本文提出的基 于互关联后继树模型的词索引方法的架构设计进行了介绍，并重点讨论了其中的各个模 块在实现时的关键技术。 第六章“实验验证与分析”，对索引的创建效率、膨胀比及检索效率等指标进行了 实验验证，实验结果表明，这种新型的词索引方法有良好的综合性能。 “总结”，对全文进行了总结，说明了论文已完成的工作、论文的创新之处、以及 下一步的工作打算。 4 中国石油大学( 华东) 硕士学位论文 第二章全文检索技术综述 2 1 全文检索技术的知识体系 全文检索技术是一个知识体系，涉及到多个模块和流程，检索信息的过程可以用一 个一般的软件体系来表示，如图2 1 。 图2 - 1 检索信息的过程 f i 9 2 - 1 t h ep r o c e s so fi n f o r m a t i o nr e t r i e v a l 在这个体系中我们可以看到，全文检索技术主要是由文本操作模块、索引模块和检 索模块组成的。 文本操作模块的主要任务是对源文档库中的文本进行预处理【l6 1 ，将文本处理成索引 项的集合，本文所研究的中文自动分词技术就是属于这一模块。文本操作模块还负责对 用户的输入语句进行处理，形成计算机可以识别的查询语言。 索引模块的主要任务是对预处理后的文本中索引项进行标引从而形成索引文件。影 响索引模块效率的主要是索引模型，包括索引的数据结构以及对该结构的操作。 检索模块的主要任务是对用户的查询操作进行处理，通过相应的查询方式从索引文 件中找出和用户的查询相关的文本呈现给用户。检索模块的实现与索引模块有着密切的 关系，对于不同的索引模型，所采用的检索模型和检索方法也是不一样的。 第二章伞义榆索技术综述 2 2 全文检索技术的建库策略 在中文检索系统中，索引的语言单元可以分为字和词两种，由此出现了两种不同的 建索引库策略：基于字表的建库策略和基于词表的建库策略。以下将对两种策略进行简 单介绍，分析它们在中文全文检索中的优缺点，为本文选择建库策略提供理论依据。 2 2 1 基于字表的建库策略 基于字表的建库策略，是指将源文档中的每个汉字均作为标引的基本单元，为每个 不同的字都建立一个字表，字表中记录了该字在不同文档中的所有出现位置，在检索时 对查询字符串中的单字所检索到的记录进行逻辑乘运算从而获得最终的结果集。 基于字表建库的优点主要有： ( 1 ) 字表规模小。基于字表的建库方法是为单个汉字建立位置索引，目前人们币常 使用的汉字数量在六、七千左右，字表集合非常小。 ( 2 ) 标引时间短。这一点和英文自动标引技术相似，汉字是构成中文语言的最小单 位，因此使用基于字表的建库方法，可以很简单的分割出索引项，节省了大量的标引时 间。 ( 3 ) 查全率高9 1 。基于字表的建库方法是对文档中的全部字符建立索引，检索时不 会出现漏检情况。 ( 4 ) 跟得上检索的时新性需求。随着时代的发展，网络上的新词语越来越多，基于 词表的建库策略要维护跟得上时代的词典会面临很多挑战，但是基于字表的建库策略不 存在这个问题，不管是多么生多么新的词，都一样能够检索出来。 基于字表建库的缺点主要有： ( 1 ) 检索结果太粗糙，失去了词与词之间的联系，导致检索的结果可能和用户的查 询要求相差较大，检索出的无用信息比较多，一般的解决方法都是借助于后控词表f 】 对检索词进行处理来提高查准率。 ( 2 ) 当用户提交关键词查询后，要将词细分为单字到索引中进行匹配，结果集的产 生要经过多次求交运算，在索引中的查询次数较多，导致检索速度比较慢，这对于用户 的检索体验来说是一个不小的缺陷。 ( 3 ) 需要为文本中的每个汉字建立位置索引，尽管字表的规模不大，但是由于字作 为索引项在文本中数目巨大，导致索引文件占用的存储空间很大，索引的膨胀比随着原 始文档规模的增大也有较快的增加，过高的膨胀比造成检索时对磁盘的读写次数增多， 6 中国石油大学( 华东) 硕士学位论文 降低了检索效率。 2 2 2 基于词表的建库策略 基于词表的建库策略就是要以能表达一定语言意义的词为索引单元建立索引库。这 种建库思想一般需要对源文档进行分词操作，也就是将源文档中的字符集合分解为词的 集合，检索的时候同样需要对检索字符串分词，然后对每个词在索引文件中查找记录， 求交后最后得到检索结果集。 基于词表建库的优点主要有： ( 1 ) 检索速度快。基于词表的建库方法检索时把查询语句分解成若干个单词的组合， 比基于字表的建库方法检索项数目要少，可以大大减少集合求交集的次数，尤其是查询 串较长时，对检索速度的提高很明显。 ( 2 ) 查准率较高。借助于分词词典和一定的分词规则，基于词表建库时可以有效的 减少歧义词索引项的产生，最终将会提高检索的准确率。 基于词表建库的缺点主要有： ( 1 ) 随着时代的发展网络上的新词越来越多，要构造一个足够大的分词词典成为一 项比较艰巨的任务。如果新词不能及时添加到词典中去，或者不能通过别的方式被识别 出来，则会导致检索系统查全率的下降，用户在搜索比较流行的一些新词或短语时将无 法得到想要的结果。 ( 2 ) 不管是哪种分词方法，分词规则都没有一个权威精确的标准，分词的准确性难 以达到令人满意的效果，总是会有一些词切分不出来或者被切分成更小的粒别，导致检 索不到，因此查全率不高一直是中文自动分词方法为人诟病的问题。 ( 3 ) 常规的词典只包含数量有限的常用词，当面对一些专业词汇、人名地名等词汇 时，词典便无能为力了，由于这些词汇的数量相当巨大，词典不可能完全收录，所以用 户在检索这些词汇时往往也很难检索得到。 2 2 3 本文选择的建库策略 本文所研究的互关联后继树索引模型是一种优秀的索引模型，在第四章会详细介 绍，目前采用这种模型进行全文检索技术研究的大都采用基于字表建库的策略，一方面 是可以通过索引生成原文，不需要保存原始文档，从而达到节省存储空间的效果。另一 方面因为检索时不需要对检索串进行处理，可以直接查询任意长度的检索串，不需要进 行分词等比较麻烦的操作。 第二章全文检索技术综述 但是基于互关联后继树模型的字索引方法有几个比较明显的缺点： ( 1 ) 由于需要额外的空间来存储字的后继，当源文本库增大到上g 字节的时候，这 种方法方法在索引创建和检索方面的时间性能都会有较大的下降。 ( 2 ) 将字的索引信息从内存写入硬盘中的索引文件时需要多次的内外存读写操作， 而硬盘的读写速度远低于内存的读写速度，这使得索引创建的速度又下降了很多，检索 也存在同样的问题。如果无法解决或缓和这一问题，基于互关联后继树模型的全文检索 技术可能就无法适用于信息飞速增长的网络环境，也失去了模型本身的优势。 因此针对字索引方法存在的问题，本文选择基于词表的建库策略，在切词准确性较 高的情况下，具有较好的查全率和查准率，检索效率比较高，并且生成的索引库的规模 相对较小，具有较低的索引膨胀比。 2 3 全文检索技术的索引模型 建立一种有效的索引模型，能够加快信息检索的速度，对于全文信息检索来说有着 重要的意义。考察全文索引模型性能的主要指标有：索引的生成时间、查询时间、膨胀 比和更新效率等【l 引。膨胀比就是指索引建立后，全文检索系统中所有数据( 原文本库+ 索引文件) 所占的存储空间与索引建立前文本库所占的存储空间之比。下面将介绍全文 检索技术发展的过程中出现的主流的索引模型。 2 3 1 签名文件模型 ( 1 ) 构造：签名文件模型是基于散列变换的面向单词的索引结构，在签名文件索引 中，每个文本被分配了固定宽度为w 位的签名，或者叫位串。它使用了哈希函数来将单 词映射到b 位编码中，每个单词都是被哈希计算多次来确定其签名的位数。如果两个或 多个不同的单词发生了( 这是不可避免的) 被设置为相同位的情况，则无法采取任何补 救措旋。 ( 2 ) 检索操作：如果要检测一个查询串是否在给定的文档中出现，首先要将此查询 串转换为签名w ，并与文本的签名b i 进行比较，即执行( w & b i _ w ) 操作。如果文本的 签名从某一位开始每位都和查询串的签名一一对应的话，那么这个文本就是潜在的匹配 文本。每一个这样的文本必须再和查询串核对一下，以确定它是否是一个错误的匹配。 ( 3 ) 优缺点：签名文件模型以在索引上顺序检索为代价，空间的开销较低；检索的 复杂度虽然是线性的，但是常数很低，所以复杂度总体来说不算高；缺点是由于散列函 中困石油夫学( 华东) 硕1 ：9 位论义 数的使用，使签名档的查询结果具有一定的不确定性。为了排除误匹配，必须扫描结果 文档来检查索引项是否真j 下出现。可以通过加大文本的签名宽度b 来降低误匹配率，但 这样会导致索引空间的膨胀。另外进行误匹配检查在一定程度上增加了查询的丌销。 2 3 2 倒排文档模型 ( 1 ) 构造：倒排文档是一种面向单词的标引机制，其结构由两种元素组成：词汇表 和事件表，词汇表是文本中所包含的所有不同单词的集合1 1 9 】。词汇表中的每一个单词在 文本中出现的所有位置都存储在一个列表中，所有这些列表的集合就称为“事件表”， 这些位置可以表示单词和字符。如果表示单词，比如第i 个位置表示的是第i 个单词， 则单词的位置可以简化短语和相邻查询；如果表示字符，比如第i 个位置表示第i 个字 符，则字符的位置有利于对匹配文本的位霄进行直接存取。 理论上，为一个n 个字符的文本建立倒排索引需要花费的时间复杂度为o ( n ) 。目自订 的词汇表大都采用t i l e 树数据结构，文本中的每个单词都在t r i e 树中进行存储和检索， 每个单词在文本中的位置则存储在它们的事件表中。建立索引时如果在t i l e 树中没有找 到某个单词，则在该t r i e 树中添加一个空的事件表；如果在t i l e 树中找到了这个单词， 则在其事件表的术尾添加这个新位置。处理完这个文本后，便将t i l e 树和事件表一起写 入磁盘。实际情况一般是将索引文件分为两个文档，一个用来连续存储事件表，另一个 则按照词典顺序存储词汇表，词汇表中的每个单词都有一个指向它在事件表中的记录的 指针。 ( 2 ) 检索操作：倒排索引的检索过程遵循以下三个基本步骤： 第一步是词汇表检索：将用户查询语句中的单词和模式分离出来，并在对每个单词 在词汇表中进行检索； 第二步是事件表检索：对于找到的词汇，通过指针到事件表列表中找出该单词出现 过的文本及位置； 第三步是事件表操作：对各个单词检出的事件表记录进行处理，以实现相邻查询或 布尔运算等。 如上所述，在倒排索引上进行检索总是先从词汇表丌始，一般都是将词汇表作为一 个独立的文档调入到主存中。对查询字符串中的每个索引项单独在词汇表中进行检索， 然后得到它的事件表，然后对各个索引项的事件表进行求交集操作，从而得出最终的结 果集，结果集不为空表示检索到包含该查询串的文本，结果集为空则表示在源文档库中 9 第- 二章令文检索技术综述 没有包含该查询串的文本。对单个单词进行检索时，可以使用多种数据结构以加快检索 速度，如使用散列技术、t i l e 树技术或b 树技术。如果将单词简单的以词典编写的顺序 存储，则可节省大量的空间并提高性能，因为可以对词典采用二分法检索，检索丌销为 o ( 1 0 9 n ) 。 ( 3 ) 优缺点：倒排索引模型的思想比较简单，建立索引的过程也比较快。检索单个 的词时可以直接得出它所在的文档，速度非常快；但是如果要查询短语或句子时，事件 表的求交操作要花费大量的时间。另一个缺点是当源文档库中的文档发生变化时，维护 和更新它们的索引文件工作量很大，因为发生变化的文本中的词汇在事件表中的记录也 发生了变化，需要对文本重新建立倒排文档索引。 2 3 3 后缀树模型 ( 1 ) 构造：后缀树模型1 2 0 1 是存储了文本的每一个半无限字符串的二叉查找t i l e 树结 构，将文本看成是一个长字符串，文本中的每个位置都被认为是文本的一个后缀，即一 个从当前位置到文本结尾的字符串，又叫半无限字符串。半无限字符串用来存储子串信 息非常有效，长度为n 的字符串所具有的子串的个数是n ( n + 1 ) 2 ，其中最长的长度为n ， 存储这些子串所需的空间将达到o ( n 3 ) ，但如果用半无限字符串柬代替子串则只需要 o ( n 2 ) 的存储空膪j ，对于前缀查询柬说，半无限字符串能够实现和子串一样的功能，因此 半无限字符串是子串的一种更好的表现形式。 比如对于文本“h e l l o t h i sd o c u m e n ti ss i m p l e ”来说，其半无限字符串及相应编码 如表2 1 所示： 表2 - 1 半无限字符串 t a b l e 2 1t h es e m i i n f i n i t es t r i n g h e l l ot h i sd o c u m e n ti ss i m p l e t h i sd o c u m e n ti ss i m p l e d o c u m e n ti ss i m p l e i ss i m p l e s i m p l e 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 1l o l 0 0 1 0 1 1 1 0 0 1 1 其对应的后缀树如图2 - 2 所示： 1 0 中图打油人学( 华东) 硕 ：学位论文 图2 - 2 后缀树 f i 9 2 2 t h es u f f i xt r e e 在上树中，由于文本的半无限字符串是从第2 位开始不一样的，所以p a t 树的根节 点就是所有串的第二位，然后对字符串逐位比较，出现不一致则分成两个分支，叶子结 点罩存储的就是每一个半无限字符串。这样的p a t 树结构需要存储的半无限字符串的空 间是o ( n 2 ) ，还是比较大，通过对指针的有效利用，可以将其降低到0 ( n ) ，如图2 - 3 所 示： 图2 3 改进的后缀树 f i 9 2 3 t h em o d i f i e ds u f f i xt r e e 这样后缀树彳4 真正算是一个索引结构了，共需要的存储空间为o ( n ) ，p a t 树索引 o ( n ) ，叶子指针o ( n ) ，最终的存储空问是线性的。 中文的后缀树结构与英文的有些不同，汉字之间紧密的靠在一起，一般都是在句子 级别上对中文文本建立半无限字符串。由于汉语的单词一定是文本的子串，所以文本中 所有的单词一定能在中文后缀树上找到，这也是后缀树结构在中文自动分词技术中的一 第二章伞文十令索技术综述 个重要应用。经常会发生这样的情况，同一文本罩的不同句子存在相同的子串，这样的 话在建树的时候就只是存储了一遍，造成了信息的丢失，为了解决这个问题，在中文后 缀树结构中加入了频率统计的思想，结点的结构变成了图2 4 所示： 左 图2 - 4 结点的结构 f i 9 2 - 4 t h es t r u c t u r eo fn o d e 对结点的结构进行改进后，虽然增大了结点占用的空问，但是后缀树还是一个o ( n ) 的结构，而且在内存空间已经足够大的情况下，由结点结构的改动带来的所需存储空i 、日j 增大的问题便不是什么大问题了。 ( 2 ) 检索操作：后缀树可以实现对文本的快速检索，检索的过程就是在后缀树中从 根结点丌始对查询串在树中遍历的过程，当查询串比较结束了，到达后缀树的某一结点 时，可以分为下面两种情况来讨论： 如果这个结点是叶子结点，就判断查询串是不是叶子结点所指向的半无限字符串的 前缀，如果是则查询串在文本中出现的次数就是叶子结点中存储的频率；不是则该查询 串在文本中不存在。 如果该结点是内部结点，就判断查询串是不是该结点的子树中任何一个叶子结点所 指向的半无限字符串的前缀。如果是则该子树中所有叶子结点中存储的频率之和就是查 询串的出现次数；不是则该查询串在文本中不存在。 ( 3 ) 优缺点：在后缀树上进行查找的时间复杂度和树的深度有关，树的构造又取决 于不同比特位上0 和1 的分布，因此后缀树的查找特性比较像二叉查找树，最坏的情况 是单支树结构，时间复杂度为o ( n 1 ) ，最好的情况是平衡二叉树结构，时间复杂度为 o ( 1 0 9 ( n ) ) 。后缀树比较适合于子串匹配，经常被用于新词发现、关键词提取等领域。缺 点是后缀树模型的空间开销比较大，创建索引的速度也比较慢，另外检索的过程比较依 赖子源文本。 1 2 中国石油人学( 华东) 硕 ：学位论义 2 4 全文检索技术的检索模型 信息检索的目标就是在给出的文档集合中找出与用户查询最相关的文档，通过采用 不同的排序算法对检索出的文档进行简单的相关性排序可以实现这一目标。信息检索系 统大都会给检索出的文档分配一个权值用来排序，排序算法假设文档之间有相关性，对 相关性的不同假设便形成了不同的信息检索模型。 信息检索模型可以定义成一个四元组m = ( d ，q ，f , r ( q i ，d i ) ) ，其中d 是经过标引后的文 档集合，q 是用户查询的检索词集合，f 是用来构建文档表示、用户查询以及它们之间 关系的模型，r ( q i ，d j ) 则是排序函数，这个函数的值是一个与查询q i q 和文档表示d j d 有关的实数。这样就在文档之间根据查询q j 定义了一个表示相关性的顺序。经典的信 息检索模型有以下三种：靠尔模型、向量模型和概率模型。 2 4 1 布尔模型 布尔模型2 1 1 是基于集合论和句尔代数而产生的，文档和查询都是用标引词的集合来 表示的，基于该模型的用户查询被表示成语义确定的布尔表达式。检索时，系统将表达 式与文档进行逻辑上的匹配，能够匹配到的文档就是结果文档。 布尔模型假定标引词在文档中只有出现和不出现两种情况，如果为文档中的标引词 定义一个权值来描述它与文档的相关程度，则标引词的权值都是二值数据，即要么相关 要么不相关。用k i 表示标引词，d j 表示文档，w i j 0 ，1 就是k i 的权值，一个查询q 是 由连接词a n d 、o r 和n o t 连接起来的多个标引词组成的，实质上，q 就是一个布尔表达 式。 布尔模型的优点在于结构比较简单，形式简明，在早期的许多商业文档数掘库系统 中得到应用。 稚尔模型的缺点在于：检索策略是基于二值判定的，文档的相关情况只有两种：相 关和不相关，没有能够用于区分相关级别的系数，也就是说没有对检索出的文档进行相 关性排序；另外准确的匹配会导致检索出的文档数目过多或者过少，这样就难以提高检 索的性能。实际上布尔检索是一个数值检索模型而不是信息检索模型，尽管命尔表达式 能够反映出语义上的信息，但通常很难成功地将用户的查询需求转换成布尔表达式。 针对布尔模型的不足之处，人们提出一种想法：给标引词加权来提高检索效果，从 而导致了向量模型的出现。 1 3 第二章令义检索技术综述 在向量模型中，文档和查询中的标引词的权值w i j 是正的非二值数，用w i ，q 表示查 询标引词的权值，则查询向量可以表示为：q = ( w l q ，w 2 q ，w t ，q ) ，其中t 是系统中标引词 的数目。文档d j 的向量可以表示为d j = ( w i j ，w 2 j ，w u ) 。通过计算向量d j 和q 之间央角 s i m 护编2 蒜= l ( 2 - 1 ) 其中川和i q l 是文档向量和查询向量的模。s i m ( q ，d j ) 的值介于0 和1 之问，根据这个值对 矿，2砥freq,7 ( 2 - 2 ) 磷：logn(2-3) 尼 w = 氏i d j l ( 2 - 4 ) 其中n 表示文档总数，n i 表示包含标引词k i 的文档数目，f r e q i j 表示k i 在文档也中出现 1 4 中困白油人学( 华东) 硕i ：学位论文 的次数。则f ；j 为文档d j 中标引词k i 的标准化频率，i 觚是标引词k i 的逆文档频率，w i j 为文档d j 中标引词k i 的权值。 向量模型的优点在于：标引词加权改进了检索的效果：即使文档与查询只有 部分匹配，文档也可能被检索出来，而不是必须严格的完全匹配；查询向量的权值 可以由用户指定，而且通过查询扩展和相关反馈，其产生的排序结果可以得到改善。 向量模型的缺点在于：文档与查询的相似度的计算量比较大，当文档集中有新文档 加入时，必须重新计算标引词的权值。 2 4 3 概率模型 在概率模型【2 3 1 中，文档和查询模型的构建都是基于概率论的。其基本的思想是：对 于给定的用户查询，存在一个文档集合，该集合只包含与查询完全相关的文档而不包含 其他不相关的文档，我们把这个集合称为理想结果集，那么构造查询的过程就可以看作 是描述理想结果集属性的过程。 概率模型基于以下假设：给定文档d j 和用户查询q ，概率模型试图估算出用户找到 所需的与文档a j 相关文档的概率，并且认为这个相关概率仅依赖于文档d j 和查询q 的表 示方式。 根据假设，对于查询q ，概率模型为每篇文档d j 赋值为p ( d j 和q 相关) e ( d j 和q 不相 关) ，以此作为d j 与q 的相关系数。根据相关系数排序可以使出现判断错误的概率降到 很低的水平。下面用公式来描述一下文档d j 与查询q 的相似度的计算方法： 州川= 黜 ( 2 - 5 ) 其中，r 表示已