（计算机软件与理论专业论文）中文信息检索索引模型及相关技术研究.pdf

复口| 大学博l 学位论文 摘要 随着计算机系统性能的提高，互联网络技术的快速普及，以及企业信息化程度的 提高，中文信息资源以极快的速度递增。信息检索就是从庞大的信息资源中找到人们 所需信息的技术。 信息检索( i n f o r m a t i o nr e t r i e v a l ) ，通常指文本信息检索，包括信息的存储、组织、 表现、查询、存取等各个方面，其核心为文本信息的索引和检索。目前，信息检索已 经发展到网络化和智能化的阶段。为了提高检索的准确率以及增强用户体验，对中文 信息检索除了继续研究索引技术外，对索引技术之外的相关技术研究方兴未艾。跟英 语的提取词根( s t e m m i n g ) 技术类似，中文分词技术是处理中文所特有的技术，中文 分词的好与坏直接影响到信息检索的精度。自动分类( 聚类) 在信息组织、导航方面 非常有用，其目的是帮助人们更好的发现、组织、表示信息，提取知识，满足信息检 索的高层次需要，有助于用户快速评价检索结果的相关程度。文本关联规则技术，特 别是对文本频繁项挖掘，能给用户在对信息检索需求转为搜索关键词时提供帮助，从 而给信息检索的人机交互方面增加了友好的一面。 本文以中文信息检索的索引模型为研究对象，也对信息检索其它相关技术进行了 研究，主要包括中文分词、文本关联分析、文本快速分类。提出了后续有序的互关联 后继树索引模型、基于互关联后继树快速准确的中文分词算法、基于模拟退火算法的 快速k n n 分类算法和基于投影和树的频繁项挖掘算法。本文的研究工作和创新内容 包括以下几个方面： 1 互关联后继树索引模型的改进研究 互关联后继树是国内自主提出的优秀信息检索索引模型，它具有创建速度快，空 间和查询效率高等特点，并且可以通过索引生成原文等优点。为了在i n t e m e t 上大规 模应用，在创建和更新文本索引以及全文检索速度等方面能达到实用的要求，本文对 这个索引模型做了进一步的研究，提出了后续有序的互关联后继树索引模型。它的优 点是在进行检索时，对有序的子树进行求交，能快速地检索出结果，从而有效地提高 了信息检索的时间效率。 2 基于互关联后继树的快速和准确中文分词 中文信息检索的查准率跟中文分词的准确率是息息相关的。目前有很多算法的准 确率比较高，但是是以牺牲时间为代价获得的。在i n t e m e t 上应用，分词算法的时间 效率和分词准确率之间是个折衷平衡的关系，在能满足分词速度实用的前提下，尽可 能提高分词的准确率。在提高分词速度方面，本文提出了用互关联后续树作为分词过 程中使用的数据结构。中文分词准确率不高的主要原因是对歧义词和未登录词的划分 不够准确，本文对中文机构名称和地名进行了研究分析，找出它们的特点，提出了一 复旦大学博l 学位论文 种结合规则和机器学习的分词方法，这种方法在对中文机构名称和地名准确划分上很 有效，实验结果也表明这种方法是一种能快速划分中文词语同时准确率又很高的分词 方法。 3 基于模拟退火的快速k n n 算法 在i n t e r n c t 信息检索应用环境上，对文本自动分类，涉及到问题主要有两个，一 是文档分类的类别是变化的，另一个是文档量大。对于第一个问题，由于模板匹配类 算法的特点，如k n n ，它是一种懒惰( 1 a z y ) 算法，将待分类样本与标准模板进行比 较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类，不需要事先确定分类 函数，因此我们选择k n n 分类算法来解决；解决第二个问题，我们先对文档的高维 特征进行排序，然后借用模拟退火算法的思想，在精度稍微下降的情况下，极快地对 文档进行分类。试验表明，基于模拟退火算法的快速k n n 算法有实际应用前景。 4 基于投影和树的文本频繁项挖掘算法 由于文本的频繁项挖掘的时间效率是随着项的增长以指数级别增长，因此对 i n t e m e t 信息检索应用环境下，频繁项挖掘的时间效率更是研究者研究的重点。本文提 出了一种新的数据结构投影和树，在对项进行建树时，可以同时对项进行计数，这 样在挖掘时，可以直接利用统计好的计数，不需要重新计数；另外，在对树进行挖掘 时，以深度优先的方式，对树进行一次深度优先遍历即可，加快了挖掘的时间。实验 表明，基于投影和树的挖掘算法比同类的算法效率要高。 5 为中国电信集团黄页信息技术有限公司实现了一个黄页搜索引擎( 一期) 系统。 利用上述创新技术，我们为中国电信集团黄页信息技术有限公司实现了一个黄页 搜索引擎( 一期) 系统，并取得显著的成效。尽管黄页搜索引擎( 一期) 系统，是一 种针对黄页信息专用的搜索引擎，但从技术本身来说，对于一般搜索引擎，也同样是 有效和实用的。 关键词：信息检索，索引模型，互关联后继树，中文分词，文本分类，频繁项挖掘 中图分类号：g 2 5 2 7 i i 复旦大学博：l 学位论文 a b s t r a c t w i t ht h ei m p r o v m e n to fc o m p u t e rs y s t e mp e r f o r m a n c e ，i n t e m e ts p r e a d i n gb r o a d l ya n d f a s ta n di m p r o v e m e n to fe n t e r p r i s ei n f o r m a t i z a t i o n , c h i n e s ei n f o r m a t i o nr e s o u r c e sa r e a c c u m u l a t i n gv e r yg r e a t l y i n f o r m a t i o nr e t r i e v a li ss u c hak i n do ft e c h n o l o g yo ff i n d i n g w h a tp e o p l en e e df r o mt h em a s s i v ei n f o r m a t i o nr c s o u r e e s i n f o r m a t i o nr e t r i e v a l ，g e n e r a l l yr e f e r e n c e dt ot e x ti n f o r m a t i o nr e t r i e v a l ，c o m p o s e so f s t o r a g e ，o r g a n i z a t i o n , p e r f o r m a n c e ，r e t r i e v a l o fi n f o r m a t i o na n di t sc o l et e c h e n o l yi s i n d e x i n ga n dr e t r i e v i n go ft e x ti n f o r m a t i o n a f t e r s e v e r a l y e a r s r a p i dd e v e l o p m e n t ， i n f o r m a t i o nr e t r i e v a li sn o wi nt h ei n t e l l i g e n ta n dn e t w o r k i n gs t a g e i no r d e rt oi m p r o v e p r e c i s i o na n du s e re x p e r i e n c e ，t h et e c h n o l o g i e sr e l a t e dw i t hi n d e x i n ga r eb e i n gs t u d i e d b r o a d l ye x c e p tf o rt h er e s e a r c ho fi n d e x i n g s i m i l a rt os t e m m i n go fe n g l i s hl a n g u a g e ， s e g m e n t a t i o ni sp e c u l i a ri nd e a l i n gw i t l lc h i n e s el a n g u a g e s e g m e n t a t i o nd e c i d e si ns o m e d e g r e e t h ep r e c i s i o no fr e t r i e v a l a u t ot e x tc l a s s i f i c a t i o ni su s e f u li ni n f o r m a t i o n o r g a n i z a t i o na n dn a v i g a t i o n i t sa i mi st od oh e l pf o ru s e r st ob e t t e rf i n d ，o r g a n i z ea n d r e p r e s e n ti n f o r m a t i o na n dt om e e tt h eh i g h e rd e m a n do f k n o w l e d g ee x t r a c t i o n a n dt h u si t d og o o dt ot h eu s e rq u i c ke v a l u a t i o no f r e t r i e v a lr e s u l t s t e x ta s s o c i a t i o na n a l y s i s ，e s p e c i a l l y f r e q u e n ti t e m s e tm i n i n g , c a nh e l pi nt r a n s f o r m i n gu s e r sr e t r i e v a ld e m a n dt or e t r i e v i n gk e y w o r d , w h i c hi m p r o v e sf r i e n d n e s so f h n m a ni n t e r a c t i o no f i n f o r m a t i o nr e t r i e v a l r e s e a r c ho ni n d e x i n gm o d e lo f i n f o r m a t i o nr e t r i e v a la n di t sr e l a t e dt e c h n o l o g i e s ，i n c l u d i n gc h i n e s e s e g m e n t i o n , f a s tt e x t u a lc l a s s i f i c a t i o n ，a n dt e x t u a la s s o c i a t i o na n a l y s i sa r ed o n ei nt h ep a p e r t h ep a p e r p r o p o s e san o v e li n d e x i n g m o d e lb a s e d0 1 1s o r t e dd u a l i t yi n t e r - r e l e v a n ts u c c e s s i v et r e e ，af a s t s e g e m e n t a t i o na l g o r i t h mb a s e do ni n t e r - r e l e v a n ts u c c e s s i v et r e e ，af a s tk n na l g o f i t h i mb a s e do n s i m u l a t e da n n e a l i n ga n dan o v e le f f i c i e n ta l g o r i t h mf o rm i n i n gf r e q u e n tp a t t e r n s o u rp r i m a r yw o r k sa 球 a sf o l l o w 1r e s e a r c ho ni n d e x i n gm o d e li m p r o v e m e n to f i n t e r - r e l e v a n ts u c c e s s i v ei x e c i n t e r - r e l e v a n ts u c c e s s i v et r e ei sa ne x c e l l e n ti n d e x i n gm o d e lp r o p o s e db yc h i n e s e 埘t h t h em e r i to fq u i c k l yc r e a t i n gi n d e x ，h i 曲s p a c ee f f i c i e n c ya n da b i l i t yo fr e s t o r i n go r i g i n a l t e x tb yi n d e x i no r d e rt om e e tt h ed e m a n do f i n t e r a c ta p p l i c a t i o nd e a l i n gw i t l lm a s s i v ed a t a , t h ep a p e rs t u d i e sf u r t h e ra b o u tt h i si n d e xm o d e la n dp r o p o s e ss o r t e ds u c c e s s i v ei n d e x i n g m o d e lb a s e do ni n t e r - r e l e v a n ts u c c e s s i v et r e ew h i c hc a nr c t l w nt h ee x p e c t e dr e s u l tq u i c k l y a n di m p r o v e st h et i m ee f f i c i e n c yo f r e t r i e v a lb yi n t e r s e c t i o no f s o r t e ds u b t r e e s 2af a s ts e g e m e n t a t i o na l g o r i t h mb a s e do ni n t e r - r e l e v a n ts u c c e s s i v et r e e c h i n e s er e t r i e v a lp r e c i s i o ni sr e l a t e dt oc h i n e s es e g m e n t a t i o nc l o s e l y n o wq u i t eaf e w s e g m e n t a t i o na l g o r i t h m sh a v eg o o dp r e c i s i o na tt h ec o s to fs a c r a f i c i n gt i m e i nt h e e n v i r o n m e n to fi n t e r u e t i ti sac o m p r o m i s eb e t w e e ne 伍c i e n c ya n dp r e c i s i o no f s e g m e n t a t i o na l g o r i t h m s e g m e n t a t i o nt r i e si t sb e s tt oi m p r o v et h ep r e c i s i o no nt h ep r e m i s e t h a ti tc a nm e e tt h es e g m e n t a t i o ne f f i c i e n c y i no r d e rt oi m p r o v et h es p e e do fs e g m e n t a t i o n , 1 1 1 复且大学博十学位论文 t h ep a p e rp r o p o s e san e wa l g o r i t h mw i t l lt h ed a t as t r u c t u r e - - - 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 t h em a i nr e a s o no fl o wp r e c i s i o no fs e g m e n t a t i o nl i e si na m b i g u i t y w o r da n do t h e rw o r d s w h i c ha r en o ti n c l u d e di nt h ed i c t i o n a r ya n dm o s to fw h i c ha r et h en a m e so fo r g a n i z a t i o n a n dp l a c e s t h ep a p e rs t u d i e st h ec h a r a c t e r i s t i co ff l a m e so fo r g a n i z a t i o na n dp l a c e sa n d s l i m st h ef e a t u r e so f t h e m , t h e np r o p o s e san e ws e g m e n t a t i o na l g o r i t h mc o m b i n i n gt h er u l e s a n dm e t h o d so fm a c h i n el e a r n i n g t h ee x p e r i m e n tt e s t i f i e st h a ti ti sa ne x c e l l e n t s e g m e n t a t i o nw i t l lh i g h e rp r e c i s i o na n dt i m ee f f i c i e n c y 3f a s tk n n a l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n g i nt h eh i g hr e s p o n s i v es c e n a r i oo fi n t e r a c t ，t h e r ea l et w oi m p o r t a n ti s s u e sc o n c e r n i n g w i t i lt e x t u a lc l a s s i f i c a t i o n ：o n ei sc h a t i g i n gc a t e g o r i z a t i o na n dt h eo t h e ri sm a s s i v ed a t a t h e f i r s tf a c t o rc a nb es o l v e db ya d o p t i n gt h et e m p l a t em o d e lm a t c h i n ga l g o r i t h m - - kn e a r e s t n e i g h b o r sa l g o r i t h m ；a sf o rt h es e c o n df a c t o r , w ec a ns o r t a l lt h ef e a t u r e so fh i 曲 d e m e n s i o n so ft e x tf e a t u r e s ，t h e nb o r r o wt h ei d e ao fs i m u l a t e da n n e a l i n g ，i nt h et o l e r a n t c i r c u m s t a n c eo fd e c r e a s i n gp r e c i s i o n , t h i sa l g o r i t h mc a nc l a s s i f yt h ed o c u m e n t sq u i c k l y t h ee x p e r i m e n t sw i t l ld i f f e r e n tc h i n e s ed o c u m e n ts e t s s h o wt h a ti th a sag o o dp r a c t i c a l p r o s p e c to f a p p l i c a t i o n 4t e x t u a lf r e q u e n ti t e m s e t sm i n i n ga l g o r i t h mb a s e do np r o j e e t i o ns l i mt r e e s i n c et i m ee f f i c i e n c yi si n c r e a s i n ge x p o n e n t i a l l y 谢t l lt h ei t e mi n c r e a s i n g , i m p r o v i n g t i m ee f f i c i e n c yo fm i n i n gi sak e yf a c t o ri nt h ea r e ao ff r e q u e n ti t e m s e t sm i n i n g an o v e l d a t as t r u c t u r e - - p r o j e c t i o ns l n nt r e ei sp r o p o s e di nt h ep a p e r w h e nc r e a t i n gp r o j e c t i o ns u m t r e e ，w ec a nc o u n ta n ds u mt h ei t e m sa n dt h e nw en e e dn o td oc o u n t i n ga n ds u m m i n gw h e n m i n i n g ；t h i sa l g o r i t h mi sad e p t hf i r s to n e ，a n dt r a v e r s et h et r e ef o ro n c e ，w h i c hi m p r o v e s t i m ee f f i c i e n c y t h ee x p e r i m e n t ss h o wt h a t t h i sa l g o r i t h mc a ng e th i g h e re f f i c i e n c y c o m p a r e dw i t hs i m i l a ra l g o r i t h m s 5c h i n e s ey e l l o w p a g ei n f o r m a t i o nr e t r i e v a ls y s t e m ( p h a s edf o ry e l l o wp a g e i n f o r m a t i o nc o o f c h i n at e l e e o mg r o u p u s i n gt h e a b o v e - m e n t i o n e di n n o v a t i v et e c h n o l o g i e s , w eb u i l day e l l o w p a g e i n f o r m a t i o nr e t r i e v a ls y s t e m a l t h o u g ht h i ss y s t e mi sas p e c i a lo n ed e a l i n gw i t hy e l l o w p a g e i n f o r m a t i o n , t h et e c h n o l o g i e sc a l lb eu s e di na n yr e t r i e v a ls y s t e ma n dt h e ya r ee q u a l l y e f f e c t i v ea n d p r a c t i c a l k e yw o r d s ：i n f o r m a t i o nr e t r i e v a l ，i n d e x i n gm o d e l ，i n t e r - r e l e v a n ts u c c e s s i v e t r e e ，c h i n e s es e g m e n t a t i o n ，t e x t u a lc l a s s i f i c a t i o n ，f r e q u e n ti t e m s e t s m i n i n g i v 复且大学博 学位论文 第八章结束语1 0 6 8 1 本文取得的成果 8 2 进一步的工作 参考文献 1 ( ) 6 10 7 1 ( ) 8 攻读博士学位期问参与的科研项目及主要成果1 1 4 致谢 图1 1 信息检索过程 图表目录 图3 - 1 倒排表模型结构2 7 图3 - 2p a t 树和p a t 数组示意图。 图3 3 互关联后继树 图3 - 4i s t r 创建实例 图3 - 5 后续节点有序 图3 - 6 后续序列示意图 图3 - 7 后继树示意图 3 4 3 5 图3 - 8 后续有序互关联后继树示意图i 3 6 图3 - 9 后续有序互关联后继树示意图2 图3 1 0 程序界面示意图3 9 图3 - 1 1 实验结果图l 图3 1 2 实验结果图2 图4 1 词表索引后继树示意图 图4 - 2 词索引和词信息结构图1 图4 - 3 词索引和词信息结构图2 图5 1 文本分类流程图一 5 3 5 4 5 7 图5 - 2 线性可分情况下的最优分类线。 图5 - 3 用例表示 图5 - 4 倒摊表表示用例 图5 5s a 算法流程图 6 6 6 7 图5 _ 6 北大语料库不同类别的分类查全率和查准率，k 取值为l o 7 3 图5 7 语料库不同类别的分类查全率和查准率，m a r k o v 取值为3 5 7 4 图6 - l 全局f p - t r e e 的构造 图6 - 2 频繁项i 的条件f p - t r e e 8 4 图6 - 3 项i 和项h 的条件f p - t r e e 及生成的频繁项集8 5 1 | 1 复黾大学博t 学位论文 图6 _ 4 p s f i t 树示例 图6 - 5 倒t r i e 树示意图 图6 - 6 挖掘p s f i t 树 图6 - 8m u s h r o o m 数据集 图6 - 9c h e s s 数据集 图6 - 1 0 数据集c o n n e c t - - 内存消耗 图6 _ 11 数据集c h e s s - 内存消耗 图7 - l 部分语义网络图。 8 9 ，9 2 9 7 9 7 9 8 图7 - 2 本体论系统框架图1 0 1 图7 - 4 系统界面一 图7 - 5 前n 查准率测试结果图 表2 - 1 查全率和查准率度量方法的文档集合 表3 - 1 各种索引模型的比较。 表3 - 2 索引模型的查询速度 表3 - 3 查询时间比较8 8 9 兆数据集一 表3 - 4 查询时间比较9 7 兆数据集。 表4 1 划分词时间和准确率对比。 表5 - 1 北大语料库的实验对比结果( c p u 秒、。 表5 - 2s o g o u 语料库的实验对比结果 表6 - l 项i 的条件模式基一 表6 - 2 示例事务库 表6 3 实验数据集 3 9 8 9 9 6 1 v 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：诬日期：2 艘 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 复旦大学博j 学位论文 第一章绪论 随着互联网的大规模普及和企业信息化程度的提高，文本信息的快速积累使公 司、政府和科研机构在信息处理和使用中面临前所未有的挑战在此背景上建立的信 息检索工具给我们查找信息带来了很大的方便，但现在也面i 占着更高检索精度要求以 及用户体验方面的高要求。人们迫切需要研究出方便有效的信息检索工具去从大规模 文本信息资源中提取符合需要的简洁，精炼、可理解的信息和知识，智能信息检索以 及检索相关问题的研究就是为解决这个问题而产生的研究方向。 本章首先阐述本文的研究背景，包括信息检索的基本概念、跟它相关的中文分词， 分类和文本关联的研究现状与已有的成果；然后，介绍本文的研究内容以及组织结构。 1 1 研究背景 随着计算机软硬件及相关技术的飞速发展和计算机网络的快速发展，i n t e r n e t 普 及程度越来越高，标志着我们已经全面进入了信息时代。根据第十八次中国互联网络 发展状况报告，中国截至至1 j 2 0 0 6 年6 月3 0 号，已有网民1 2 ，3 0 0 万人，上网计算机数为 5 4 5 0 万，网站7 8 8 4 0 0 个。据国务院信息化办公室发布的( 2 0 0 5 年中国互联网络信息资 源数量调查报告显示，2 0 0 5 年中文网页总数猛增，截至去年年底达至1 j 2 4 亿个左右， 其中，网页总数约为2 4 0 亿，同期相比增幅为2 6 9 ，网页字节总数约为6 7 ，3 0 0 g b ， 同比增长率达到2 2 8 。我国网上信息量的高速增长，也从侧面反映出我国网络信息资 源的快速增长。另外，每天有数十万的网页更新，数百万的新的网页加入，使得i n t e r a c t 上的信息丰富而又复杂。 如此丰富的i n t e r n e t 信息资源不仅仅是政府、公司、集团获取信息的重要场所，而 且也为个人的学习、生活和工作获取信息的重要来源地。现在人们需要的绝大部分信 息i n t e m e t 都能提供。 面对如此庞大而且急剧膨胀的信息海洋，如何高效地组织和管理这些信息，并快 速、准确、全面地从中搜索到用户所需要的信息是当前信息科学与技术领域面临的一 大挑战。正是在这一背景下，信息检索以及相关技术就很快地发展起来了。从2 0 0 4 开 始到现在，一直被业界评为检索年，2 0 0 4 年美国时代周刊称之为信息检索年，2 0 0 7 年， 我们中国的媒体把它称为手机信息检索年，垂直信息检索年。 信息检索是与数据库技术并行发展多年的领域，其中以文本为对象的文本信息检 索是目前信息检索的最主要的部分，它以非结构或半结构化数据为处理对象，研究大 量文本的信息组织和检索问题。文本信息检索主要发现与用户检索要求( 关键词) 相 关的文本。例如，基于关键词的文本检索是使用相关度计算文本与用户查询问的相关 复旦人学博上学位论文 性并按相关程度高低排序获得的文档。 1 1 1 信息检索的概念 随着计算机系统性能的提高和网络技术的不断进步，i n t e r a c t 得到蓬勃发展，成为 全球最大的信息资源库，网上存取信息渐渐地变为了人们的日常所需。 信息检索王贾郑0 5 ( i n f o r m a t i o nr e t r i e v a l ) 是对信息项进行表示、存储、组织和存 取。本论文研究的是文本信息检索，它是从一定规模的文档库( d o c u m e n tc o l l e c t i o n ) 中找出满足用户提出的查询请求( u s e ri n f o r m a t i o nq u e r y ) 相关的文档子集的技术，包括 信息的存储、组织、表现、查询、存取等各个方面，其目标是检索出与用户查询相关 的文档，尽量减少不相关的文档，核心为文本信息的索引和检索。 信息检索和数据库检索的区别 信息检索的目的是从大量的信息中找到满足用户需求的信息，这与在数据库系统 中检索数据的概念是类似的。在数据库系统中，其数据检索语言的目标就是检索出满 足定义条件的所有对象，定义的条件可以用规范表达式和关系代数表达式来说明，而 数据检索基于的表格式属性条件不能有效地表达文档的信息内容，因而不能有效地支 持信息检索。信息检索的检索对象( 文档集合) 以及用户查询可以是非结构化的而且 具有语义模糊性；而数据检索系统处理的数据则是具有良好定义的结果和语义。 1 1 2 信息检索过程 信息检索的主要对象是文档( d o c u m e n t ) 资源，文本是文档的一种典型形式，文 图卜1 信息检索过程 档的内容形式可以包括文本、图像、视频和音频等多种媒体。用户可以通过自然语言 2 复噩大学博f 二学位论文 或者关键词( k e y w o r d ) 表达检索需求，用户提交的检索需求称为一个查询( q u e r y ) 。 在检索开始以前，必须要先有一个定义好的文本数据库，它的功能为，1 ) 存放 文档内容；2 ) 在该文档上可以进行操作；3 ) 文本模型。文本数据库中存放的信息通 过人工方式或网络爬虫方式采集到的，它可以通过数据管理模块对文档进行索引的建 立。索引是个关键的数据结构，它支持在大量数据中进行快速查找。在索引过程中也 许要用到不同的索引结构，如倒排文档( i n v e r t e df i l e ) 、互关联后继树( 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 ) 等。 在建好索引后，就可以发生检索过程了。用户首先详细说明用户需求，这个过程 是个迭代的过程，用户会不断地对用户需求进行修j 下表达，系统也通过关联提示帮助 用户对表达式进行描述。当用户表达式确定后，系统为用户的需求提供一个系统表达 式。接着通过处理查询获得检出文档( r e t r i e v e dd o c u m e n t ) 。在把文档送出前，将根 据检出文档的类别以及相关度( 1 i k e l i h o o d ) 对检出文档进行排序。随后，用户查看经 过排序的文档集合，查找有用的信息。用户也可以根据明确的兴趣查看文档，形成一 个子集并且开始用户反馈( u s e rf e e d b a c k ) 循环。 1 1 3 信息检索相关性问题 信息检索的实质是用户需求和信息集合之间的匹配比较。用户和信息文档对同一 概念的表述是不会完全一致的，这更导致返回的结果信息也不会完全是用户希望得到 的。在现存的大量检索系统中，它们不是比较用户需求和信息集合的匹配关系，而是 比较它们的转化形式，即信息标识集合与用户需求表达式之间的匹配，很显然，这种 匹配方式与用户需求同信息集合的匹配有很大的差距，这使得检索结果相关性的判断 成为一种必然。 当一个用户有信息检索的需求时，他的信息请求要经过一序列的转换过程：信息客 观需求信息意识言息主观要求信息要求的语言表达。当能用语言表达后，原先模 糊、多变的信息需求得以固定化。在这个转变过程中，用语言表达出来的信息需求和 信息的客观需求是会存在一定程度的不一致。在这个模糊基础上的，需求语言表达用 检索系统使用的语言表达式来进行检索，这也使检索的不确定性进一步增加。要判断 检索结果对用户信息需求的满足程度，就产生了信息检索过程的相关性问题。这种检 索结果同主观信息要求的匹配称之为语义相关一这种语义相关不仅反映了检索结果 同主观信息需求的匹配程度，而且反映了检索词表的质量。检索结果除了要满足这种 主观信息需求，更重要的是要满足用户的决策需要。检索结果同决策需要所决定的客 观信息之间的这种相关称之为语用相关。 从决策所需客观信息到最后信息检索式的形成，经历了语用需求到语义需求再到 形式需求的转移；从检索结果对用户的满足来说，则经历了形式满足到语义满足，再 到语用满足的嬗变。这一往复过程使检索的相关性问题变得非常复杂，但从现行多数 复且大学博学位论文 检索系统来看，目前仅仅能够解决形式相关问题，其他的语义相关与语用相关还没涉 及到，或者说系统都把这些问题留给了用户去处理和完成，这肯定给用户添加了负担， 至少是时间上的负担。对用户来说，如果发现检索结果同实际决策需求相去甚远的话， 只有通过新的需求表达来进行新一次检索。 1 2 研究现状 1 2 。1 信息检索核心技术的研究 人类对已有的信息加以整理，以利于日后进行检索的活动早在4 0 0 0 年前就已经开 始，书的目录就是一个典型的例子。作为一个研究领域，信息检索从2 0 世纪5 0 年代与 科学技术的发展一起经历了不断的发展和变化。在过去的2 0 多年中，信息检索领域已 经得到发展和壮大，并且超越了它标引文本和在某一集合中检索出有用文献的最初目 标。 信息检索的研究包括建模、文档分类和归类、系统构建、用户界面、数据可视化、 信息过滤和查询语言等。下面就对信息检索及相关技术研究现状和取得成果进行一个 简单的回顾。 1 2 1 1 信息检索模型 三个经典模型：布尔模型、向量模型和概率模型 f b y 9 2 1 。在布尔模型中，文档 和查询用标引词来表示，因此，称该模型为集合论( s e tt h e o r e t i c ) 模型，布尔模型简 单，但效果差：在向量模型中，文档和查询用t 维空间的向量来表示，称它为代数 ( a l g e b r a i c ) 模型，该模型能够进行部分匹配，检索结果按相关性大小排列，更符合 用户的需要。向量检索模型是目前普遍使用的检索模型。在概率模型中，用于构建文 档和查询模型的机制是基于概率论的，因而称它为概率( p r o b a b i l i s t e ) 模型，概率模 型按预测概率的大小输出结果，这是它的优势。但这种模型的计算量比较大，而且需 要给出一个初始预测概率值。 在上述三种经典检索技术的基础上，人们为每一种经典模型( 如集合论、代数、 概率模型) 提出了各种改进模式 b y r n 9 9 。以基于集合论的模型来说，有模糊检索模 型和扩展布尔模型；代数模型中有广义向量空间模型、隐含语义索引模型 d d f + 9 0 1 和神经网络模型。隐含语义索引可以看作是向量模型的一种扩展，它利用奇异值分解 技术i g r 7 1 ，压缩文本向量空间，消减文本库中因用词的同义性和多义性引起的语义 模糊，使得检索效果更理想。特别是，这种方法能够发现不包含相同词语的文档之间 的语义关联。由概率模型发展而来的检索模型有b a y e s i a n 网、推理网络模型( i n f e r e n c e n e t w o r km o d e l ) 和信任网络模型( b e l i e f n e t w o r km o d e l ) 。这些模型考虑了文本中不同词 之间的关联，因而更真实地反映了文本特性。当然，这些模型的计算复杂性也高了。 4 复黾大学博i ：学位论文 1 2 1 2 索引模型 到现状为止，已有好多的索引模型提出，其中比较典型有：签名文件( s i g n a t u r e f i l e ) 、倒排文件法、p a t r i e i at r i e 和互关联后继树等。 签名文件法是把称为签名文件的特征向量作为索引，进行快速检索的方法。在本 方法中，每个文档都通过h a s h i 函数及重叠编码( s u p e r i m p o s e dc o d i n g ) 产生一个称为签名 ( s i g n a t u r e ) 的位串。文档的签名结果顺序存入一个单独的文件( 签名文件) a e ，签名文件 比原文件小得多，因此可以提供更快速的搜索。签名文件是指用0 和1 组成的b i t 序列描 述索引项在文本内出现状况的特征向量。为了形成这个特征向量，需要用b i t 串描述作 为索引项的单词特征。 全文索引模型中最常用的是倒排文件( i n v e r t e df i l e ) k n u