（控制理论与控制工程专业论文）基于粒子群优化算法的中文全文检索系统研究与开发.pdf

基于粒子群优化算法的中文全文检索系统 研究与开发 控制理论与控制t 程专业 研究生李胜指导教师拇蜀阳 如何从海量的信息中获取有用的信息，如何从迅速爆炸的信息中及时获取 袋粝燕感，这是捻索技术g 蒋匿娅黪撰藏。全文捡索楚强代信惠硷囊接本麴一 个非常重要的分支，是为解决信息的高效获取问题而癌运而生，它是以电了文 本数据为主要处蝉对象，基于全文索引，使用自然语言避行检索的技术。 存在两种基本的索引蓐结构，即耩于“字袤”麴索引库和基于“词袭”的 索引库；在对中文全文检索的有关按术，尤其是对中文信息处理的基础技术： “中文分词技术”进雩亍了较为漾入的研究后，本文箍塞了一静基于粒子群伉纯 算法( p s o ) 的适用于构建全文索引的分词方案。该分词方案结合了“字表法”和 “词表法”的优点，在溅少信息冗余的前提下褥到准确的检索结粜。 粒子群优化算法白提出阻来，由予它的训簿快速性和算法本身的易实现性， 引起了国际上相关领域众多学者的关注和研究，已在函数优化、神经网络训练、 模糊系统控裁等赣域取褥长足鲍发袋。率支是粒了群算法在求解实际闻瑟； j 应用。受粒r 群算法解决旅行商问题的肩发，本文把中文分词问题转化成了求 鳃最短路径问题，并绘出了葵完整约建模魏隶瓣过程。精选了1 2 8 条具有舆型 交集型歧义字段的切分侧旬作为测试用例，在与r f l 科院计算所汉语词法分析系 统1 c t c l a s 的实验结果对比中表明该分词方案是适合于全文检索系统的分 词方案。 根据本文提出的分词算法，从实际问题出发，把该分词算法应用于实际的 融q ( 霉跫同避簿答) 全文捡索系缓驰没计，艮采露瑟囊对象霸模型驱动麓程 序设计方法，利用 源项目l u c e n e 建立和实现全文本索引库，文中给出了系统 的详细设诗说明。为了高效的剥用检索豹结果，文中还实现了基予字段姻摊序 功能。缩合文中给出的检索结粜的排序算法和分词算法，本文实现了全文检索 纺果的准确性和高敝性。 关键词：全文检索；全文索引；中文分词：粒子群优化算法；系统设计：结粜 鞠 痔。 f 1 四川大学硕t 学位论文 t h er e s e a r c ha n dd e s i g no fc h i n e s ef u l lt e x t i n f o r m a t i o nr e t r i e v a ls y s t e m sb a s e do np s o m a j o r ：c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g g r a u d a t e ：l is h e n ga d vis o r ：r a ns h u y a n g h o wt od e r i v em o s tu s e 允l i n f o r m a t i o nf r o mt h ef l o o do fi n f o r m a t i o n h o wt o g a i nm o s tr e c e n ti n f o r m a t i o ni ni n f o r m a t i o ne x p l o s i o np r o m p t l y , w h i c ha r ea l lt h e c h a l l e n g e st h a tt h er e t r i e v e st e c h n o l o g yf a c e sa tp r e s e n t t h ef u l lt e x tr e t r i e v a l 。b e i n g a sa l le x t r e m e l yi m p o r t a n tb r a n c hi nm o d e mi n f o r m a t i o nr e t r i e v a lt e c h n o l o g y , i sf o r s o l v i n gt h eh i g h l ye f f e c t i v eg a i np r o b l e mo fi n f o r m a t i o na tt h eh i s t o r i cm o m e n t b a s i n go nt h ef u l lt e x ti n d e x ，a d o p t i n gn a t u r a ll a n g u a g et oc a r r yo nt h er e t r i e v a l t e c h n o l o g y , t h em a i np r o c e s s i n go b j e c to ff u l lt e x tr e t r i e v a ls y s t e m si st h ee l e c t r o n i c t e x td a t a t h e r ea f et w ok i n d so fb a s i c i n d i c e s s t o r e h o u s e s s t r u c t u r e s n a m e l y c h a r a c t e r - b a s e dt a b l ei n d e xs t o r e h o u s ea n dw o r d b a s e dt a b l ei n d e xs t o r e h o u s e t o c o n c e r n e d c h i n e s ef u l lt e x tr e t r i e v a lt e c h n o l o g y , i np a r t i c u l a rt oc h i n e s ei n f o r m a t i o n p r o c e s s i n gf o u n d a t i o nt e c h n o l o g y ：c h i n e s es e g m e n t a t i o nt e c h n o l o g y ”，h a v i n g c o n d u c t e dm o r et h o r o u g hr e s e a r c h ，t h i sa r t i c l e p r o p o s e do n ek i n do fp s o b a s e d c h i n e s ew o r ds e g m e n t a t i o np l a nf o rc o n s t r u c t i n gt h ef u l lt e x ti n d e x t h i sk i n do f s e g m e n t a t i o np l a nu n i f i e dt h em e r i te x s i t i n gi nc h a r a c t e rt a b l el a wa n dt h ew o r d t a b l em e t h o d , o b t a i n st h ea c c u r a t er e t r i e v a lr e s u l ti nu n d e rt h er e d u c e di n f o r m a t i o n r e d u n d a n c yp r e m i s e ， s i n c ep s o si n v e n t i o n ，o w i n gt oi t s c o m p u t a t i o nr a p i d i t ya n dt h ea l g o r i t h m i t s e l fe a s yr e a l i z a t i o n ，i tc a u s e sm u l t i t u d i n o u s s c h o l a r sa t t e n t i o na n d 陀s e a r c h i n t e r n a t i o n a l l y i nt h ed o m a i no ff u n c t i o no p t i m i z i n g , n e r v en e t w o r kt r a i n i n g , l 四圳夫掌绶 学豫沦史 f u z z ys y s t e m sc o n t r o la n ds oo n i ta c h i e v e st h ec o n s i d e r a b l ed e v e l o p m e n t t h i s a r t i c l ei st h ep s oa l g o r i t h m sa p p l i c a t i o n 掰t h es o l u t i o no fa c t u a lp r o b l e m i n s p i r e d b yt h ep s 0s o l u t i o n i nt r a v e l e rp r o b l e m ，t h i sa r t i c l et r a i l s f o r m sc h i n e s ew o r d s e g m e n t a t i o nq u e s t i o nt ot h es o l u t i o no f m o s ts h o r t - p a t hq u e s t i o n ，a n dh a sp r o d u c e d i t sm o d e la n dt h es o l u t i o ni nc o m p l e t ep r o c e s s 1 2 8i t e m s w h i c hh a v et h em o d e l o c c u r r i n gt o g e t h e rd i f f e r e n tm e a n i n g sf i e l dt oc u tt h em i n u t ei i l u s t r a t i v es e n t e n c e a c h i e v e m e n t ，a r es e l e c t e dt om e a s u r et h et e s te x a m p l e ，c o n t r a s t i n gw i t hc h i n e s e l e x i c a la n a l y s i ss y s t e m i c t c l a s ，i ti n d i c a t e dt h a tt h i ss e g m e n t a t i o np l a ns u i t si n t h ef u l lt e x tr e t r i e v a ls y s t e m e m b a r k sf r o mt h ea c t u a l p r o b l e m ，s e g m e n t a t i o na l g o r i t h mp r o p o s e di nt h i s a r t i c l ei sa p p l i e di nt h ea c t u a ld e s i g no ff a q ( f r e q u e n c ya s k e dq u e g i o n s f i d lt e x t r e t r i e v a ls y s t e m a d o p t i n go b j e c t - o r i e n t e da n dt h em o d e ld r i v e n p r o g r a m m i n g m e t h o d , i n t r o d u c i n go p e ns o 翻p r o j e c tl a c e n et ob u i l da n dt or e a l i z et h ee n t i r e t e x ti n d e xs t o r e h o u s e ，i nt h ea r t i c l ei th a sp r o d u c e dt h es y s t e md e t a i l e dd e s i g n e x p l a n a t i o n f o rt h eh i g h l ye f f e c t i v e 瞄o fr e t r i e v a lr e s u ki nt h ea r t i c l ei th a sa l s o r e a l i z e dt h ef i e l d b a s e da r r a n g e m e n tf u n c t i o n 1 nt h eu n i o n o f t h er e t r i e v a lr e s u l ts o r t a l g o r i t h ma n dt h ep s o - b a s e ds e g m e n t a t i o na l g o r i t h m ，i nt h i sa r t i c l ei to b t a i n sf u l l t e x tr e t r i e v a lr e s u l ta c c u r a t e l ya n de f f e c t i v e l y k e yw o r d ：f u l lt e x tr e t r i e v a l ；f u l lt e x ti 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 ；p a r t i c l e s s w a r m o p t i m i z e r ；s y s t e md e s i g n ；r e s u l ts o r t 绪论 1 1 研究鸷景 随着互联网羊信息技术的高速发展，在i n t e r n e t 上中文信息的急剧膨胀和 中文电子i 嚣叛耪、中文数宁图书、滚子商务务公翡：i 琵速普及，可镶人们选择驹 信息和联机文本数据库的数量急剧增加，传统的手工检索方式越来越不符合发 袋斡震要。磐何献海量的信息中获取舂雳瓣落患，魏露迅遗腹爆宴乍秘信惫中及 时获取最新信息，这是目前面i | 台i 的挑战。因此需要采用更妻子的技术来充分获取 并幂用这憋信息。 全文检索系统就是为了解决信息的高效获取问题而应运而生，它是以电予 文本数据为主要处理对象，基于全文索引，使用自然语言进行检索的技术。 全文索引不仅可以实现对资料的外部特征的检索，如标题、摘要、附录等， 而且还能根据资料文本的内容进行检索。最初的全文检索是通过在文本中逐个 字符扫摇匹配完戒的，不需要全文索引这样的辅助数据。随赣文本集越来越大， 人们对全文检索的需求越来越多样，这种顺序比较的方法越来越显得效率低下。 久们受到书嚣索引游赢菠掇出了全文索引麓愚想，在索；| 静鏊稿上建立索引露， 从而实现全文检索。从理论上来讲，在中文系统中，索引可以是中个汉字，也 霹以是调，霆茈董王存在嚣耱蓥本赘索；| 瘁绻穆，帮萋予“字表”静索；l 瘁蟊罄 于“词表”的索引库【1 。后者有比前者高得多的查准率和空间利用率，而前者 实蜣蕊单，穆建壹褒方便。本文所拯瑟索g 蓐是基予“溺表”麴。 全文检索的核心是将源文本中的所有基本元素的出现信息建立索引库，与 落文全文检素技术比较，中文全文检索的实现更殿难。这是因为汉谬书蠹语不 像两文那样是分词涟写的，词与词之间没有明显的界限，进入计算机后，仍然 是等距排列的汉字字串序列，全文梭索系统，是在词( 由一个或多个单字组成) 运一平面上进行处理。因此，中文全文检索系统的实顼，必须把中文分词作为 第一道工序。为了建立全文检索的索引，中文自然谣言处理露首先对文本进行 分溺，将汉字串切分为正确的谪串，我们称之为淡语自动分词。 有的学者提出，为了从根本上解决分词问题，应该改变汉语的书写习惯， 网丈学硬t 学位论文 实行按词连写【2 1 【”。从历史上看，汉语原先连标点符号也不使用，可见养成新 的书写习惯足有可能的。不过，这涉及国家的语言文字政策问题，即使能够实 行，改变书写习惯也需要假以时日；而且到目前为止积累的现代汉语书面语 料还足要经过分词处理才能做后续分析的。 1 2 国内外研究现状 1 2 1 全文检索的发展现状 在信息检索领域。全文检索一直是一个比较复杂的问题。与普通数据库检 索设计的结构化查询不同，全文索引不仅耍查询结构化数据，而且还要查询非 结构化数据【4 】。与标引索引比较，全文检索提供了全新的，强大的检索功能， 从多角度、多侧面的综合利用信息资源。一般全文索引的研究内容主要有：全 文索引的模型、索引的空间效率、索引的检索效率、索引的动态效率、索引的 创建效率、索引的语义能力等。新一代的全文检索系统除了全文检索功能外， 还应具备语义匹配、文本挖掘这类对语义理解要求较高的功能，而这些功能的 完成也有赖于：全文索引。 目前主流的全文索引模型有倒排索引( i n v e r t e di n d e x ) 、署名文件1 5 】、位图、 和p a t 数组。此外，有人还提出了一些新的全文索引模型，但就目前来说倒排 索引模型的综合性能较好，且应用最为成熟。目前很多主流的全文检索系统用 自主设计的文件来存储倒排索引，比如“易宝北信”的t r s t 6 1 。当倒排索引文 件的空间开销较大时候，就耍考虑在基本不影响检索效率的前提下，实现倒排 索引的压缩。文献【7 】介绍了全文检索系统中的数据压缩文献【8 】在对倒排文件 中单词的p o s t i n g l i s t s 压缩的基础上，又对其建立索引，进一步提高了效率。 在文本检索中，词表和文档元数据的存储要有良好的设计，以满足一定的 查询性能要求一响应时间( r e s p o n s et i m e ) 和系统吞吐量( t h r o u g h p u t ) 。文献【9 】 就检索效率问题作了详细的论述。 在全文索引构造方面，有静态索引技术1 1 0 1 1 川和动态索引技术。随着全文检 索应用范围的扩大，其动态效率的研究也愈显重要【3 】。在中文系统中，索引 库的结构方面，存在两种基本库结构：基于单汉字的索引库和基于词表的索引 库。由于汉字在书写格式上与西文上的不同，词表法的研究主要集中在中文自 四川上学堙 学位论文 动分词的研究，自然语料统计分析等方面。 1 2 2 汉语自动分词的研究现状 l 、几个早期的自动分词系统 自8 0 年代初中文信息处理领域提出了自动分词以来，一些实用性的分词系 统逐步得以开发，其中几个比较有代表性的自动分词系统在当时产生了较大的 影响。 c d w s 分词系统是我国第一个实用的自动分词系统，由北京航空航天大学 计算机系于1 9 8 3 年设计实现，它采用的自动分词方法为最大匹配法，辅助以词 尾字构词纠错技术。其分词速度为5 1 0 字秒切分精度约为1 6 2 5 。 a b w s 是山西大学计算机系研制的自动分词系统，系统使用“两次扫描联 想回溯”方法，运用了较多的词法、句法等知识。其切分正确率为9 8 6 ( 不包 括非常用、未登录的专用名词1 ，运行速度为4 8 词分钟。 c a s s 是北京航空航天大学于1 9 8 8 年实现的分词系统。它使用正向增字最 大匹配，运用知识库来处理歧义字段。其机械分词速度为2 0 0 字秒以上，知识 库分词速度1 5 0 字秒( 没有完全实现) 。 书面汉语自动分词专家系统是由北京师范大学现代教育研究所于1 9 9 1 前 后研制实现的，它首次将专家系统方法完整地引入到分词技术中。 2 、清华大学s e g 分词系统 此系统提供了带回溯的正向、反向、双向最大匹配法和全切分评价切分算 法。由用户来选择合适的切分算法。其特点是：带修剪的全切分评价算法。经 过封闭试验，在多遍切分之后，全切分评价算法的精度可以达到9 9 左右。 3 、清华大学s e g t a g 系统 此系统着眼于将各种备类的信息进行综合，以便最大限度地利用这些信息 提高切分精度。系统使用有向图来集成各种各样的信息。通过实验，该系统的 切分精度基本上可达到9 9 左右，能够处理未登录词比较密集的文本，切分速 度约为3 0 字，秒。 4 、国家语委文字所应用句法分析技术的汉语自动分词 四大学硕f - 学位论文 此分词模型考虑了句法分析在自动分词系统中的作用。以更好地解决切分 歧义。在切词过程中考虑到了所有的切分可能，并运用汉语句法等信息从各种 切分可能中选择出合理的切分结果。 5 、复旦分词系统 此系统由四个模块构成。一、预处理模块，利用特殊的标记将输入的文本 分割成较短的汉字串，这些标记包括标点符号、数字、字母等非汉字字符，还 包括文本中常见的一些字体、字号等排版信息。二、歧义识别模块，使用正向 晟小匹配和逆向最大匹配对文本进行投向扫描，如果两种扫描结果相同，则认 为切分正确，否则就判别其为歧义字段，需要进行歧义处理：三、歧义字段处 理模块，此模块使用构词规则和词频统计信息来进行排歧。最后。此系统还包 括一个未登录词识别模块，实验过程中，对中文姓氏的自动辨别达到了7 0 的 准确率。系统对文本中的她名和领域号有词汇也进行了一定的识别。 6 、哈工大统计分词系统 此系统能够利用上下文识别大部分生词，解决一部分切分歧义。经测试， 此系统的分词错误率为1 5 ，速度为2 3 6 字秒。 7 、杭州大学改进的m m 分词系统 系统的词典采用一级首字索引结构，词条中包括了“非连续词”( 形如 c 1 * c n ) 。系统精度的实验结果为9 5 0 , ，低于理论值9 9 7 3 ，但高于通常的 m m 、r m m 、d m m 方法。 8 、m i c r o s o f t r e s e a r e h 汉语句法分析器中的自动分词 微软研究院的自然语言研究所在从9 0 年代初开始开发了一个通用型的多 国语言处理平台n l p w i n ，据报道，n l p w i n 的语法分析部分使用的是一种烈 向的c h a r t p a r s i n g ，使用了语法规则并以概率模型作导向，并且将语法和分析器 独立开。实验结果表明，系统可以正确处理8 5 * 0 的歧义切分字段，在p e n t i u m 2 0 0 p c 上的速度约6 0 0 9 0 0 字秒。 9 、北大计算语言所分词系统 系统由北京大学计算语言学研究所研制开发，属于分词和词类标注相结合 的分词系统。系统的分词连同标注的速度在p e n t i u m l 3 3 h z 1 6 m b 内存机器上的 达到了每秒3 千词以上，而在p e n t i u m l l 6 4 m b 内存机器上速度商达每秒5 于词。 l o 、中科院自动化所i c t c l a s 分词系统 4 0 - 4 3 1 网川夫学碰t 学位论文 i c t c l a s 分词系统是中科院计算技术研究所在多年研究基础上开发完成 的，采用h m m 模型，在训练阶段，以人民开报一个月的切分标注好的语料作 为学习资源。系统功能有：中文分词；词性标注；未登陆词识别，其中，分词 正确率就高达9 7 0 0 以上，在2 0 0 2 年的9 7 3 评测中，l c l l a s 获得了第一名的 成绩，受到了国内外研究者和工程技术人员的广泛欢迎。 1 3 研究意义和文章结构 信息的飞速增长，使搜索引擎成为人们查找信息的首选工具，人们经常使 用的g o o g l e 、b a i d u 等搜索引擎的核心技术之一就是全文检索。另外，随着信 息的电子化，如何更好地在单位、家庭、甚至个人的电子数据、文档中实现信 息检索，也是全文检索技术的一个核心应用。 汉语分词是中文信息处理的基础。自动分词是自然语言处理的一项基础性 工作。在自然语言处理中首先要解决自动分词这一瓶颈问题。自动分词在自然 语言处理以及全文检索系统中的重要性，可以从两方面来认识。一方面，“词” 是组成句子的基本单位，要对句子进行分析，首先得对它的基本组成单位一 “词”进行分析，只有在这个基础上，才能谈得上进一步作其他的处理。这是 由“词”在自然语言中的基础地位决定的；另一方面，全文检索的索引是用机 器抽取或喊予“索引词”。“索引词”是指与文献主题和全文内容相符的或密切 相关的词语。所以，中文文本全文索引中离不开“词”这个基本单位。 那么中文分词到底对全文检索育多大的影响呢? 对搜索引擎来说，最重要 的并不是找到所有的结果，因为在上百亿的网页中找到所有结果没有太大的意 义。最重要的是找到用户最感兴趣的结果，并把最相关的结果排在最前面。中 文分词的准确与否，常常直接影晌结果的排序；另一方面，对一个中小型的全 文检索系统来说，常常要求检索的准确度和得到检索结果的信息量并重，这时 就要求在分词结果的准确性和信息量之间进行折中。具体来说对一个中小型 的中文全文检索系统，要根据实际情况，在单汉字的索引库和基于词表的索引 库之问求得一个平衡。 本文在对中文检索技术和p s o 算法进行了详细的研究后，从实际问题出 发，提出了构建索引的p s o 优化分词算法。在检索的准确度和捡索的信息黾之 阴大学艰l f 学位论文 间得到一个平衡。本文的选题背景来源于四川大学网络教育学院f a q 检索项 目，基本目标是建立基于汉语语言模型的f a q 全文检索系统。文章研究的重点 在于基于p s o 优化算法的面向全文索引的中文分词算法，然后在分词的基础 上，利用开源项目l u c e n e 建立和实现全文本索引库，该系统的实现还包括：f a q 电子文档格式的转换，检索结果的排序处理等。本文的讨论主要围绕以上几个 方面展开，取得的主要成果和论文的结构如下； 第2 章：中文全文检索技术。对全文检索技术进行研究，进一步对基于中 文分词和单汉字检索技术进行了研究和比较；对中文自动分词技术进行研究。 第3 章：理论基础。介绍本文使用的中文分词的n g r a m 模型：总体介绍 粒子群优化算法的产生、发展及粒了优化算法的三种形式；阐述p s o 应用于中 文分词的可行性。 第4 蕈：基于粒子群算法的中文分词算法。提出解决中文分词的最小费用 路径模型，并给出求解中文分词最小费用路径模型的粒子群算法，最后给出实 验结果的比较和分析，以及算法的优化。 第5 章：系统设计。在第4 章的算法的基础上，设计实际的f a q 全文检索 系统。 第6 章：总结与展望。对完成的工作进行总结，以及展望今后的工作和研 究方向。 6 网j 人学硕卜学位论文 2 中文全文检索技术 全文检索主要有两方面相互结合的核心技术，一个全文索引的组织，如何 建立全文检索索引库，另一个足提供快速有效的检索机制。对于前者，是要针 对实际应用需要，确定索引库的数据结构和存储方式，以及如何从原始文档中 抽取出全部有用信息，并将这些信息记录到索引库中。对于后者，是在索引库 的基础上，系统要提供快速有效的检索机制以及友好的反馈机制，从而在尽可 能短的时间内查找到符合用户需求的全部文档。 2 1 组织索引技术 最初的全文检索是通过在文本中逐个字符扫描匹配完成的，即扫描每个文 档中字的信息，直到找出所有包含查询关键字的文档，如图2 1 所示【1 2 1 。它不 需要全文索引这样的辅助数据，但是当文本变得相当大，而且人们对全文检索 的需求有多样性要求时，这种顺序比较的效率就很低。 一+ 囡咽 回咽 图21 正排表结构 图2 2 倒排表结构 人们受到图书馆的书目索引的启发提出了全文索引的思想，从书目索引延 伸出来的方法就足现在应用广泛的倒排表索引模型f j 4 j 和标签索引模型，如图 2 2 。 倒排索引是以全文中所有可检索项( 包括字段信息、任意字词) 建立一个或 网川人学坝l 学位论丈 多个索引。索引文件和倒排文件在物理上是分开的，逻辑上也可组合成为倒排 索引文件。在索引中，每条记录包含索引词以及与该词有关逻辑记录号或指针。 倒排文档中还可加入文献中各个词的位置信息，包括逻辑记录号、段号、行号 等。检索时，由索引文件指向倒排文件，倒排文件指向主文件。倒排索引 的形式多样。其基本结构如图2 3 所示。 地j 1 卜对照文件倒排索引文件 图23 倒排文件索引结构 标签索引技术足将每个文档鄙划分成一定数量单词的段，然后按照一定的 算法( 如哈希函数) 将每一段转换成一个位串( a b i ts t r i n g ) 形式的标签( s i g n a t u r e ) ， 用以唯一标识文献。所有标签集合组成一个标签文件，索引文件则由这个标签 文件和一个指向相应的数据文件( d a t a f i l e ) 物理地址的指针数组组成。其索引结 构如图2 4 所示。 标签 围24 标签文件索引结构 数据文件 网川大学被 学位论文 检索时首先以同样的算法将睑索字串转换成相应的位串，将其与标签文件 中的各标签进行位运算，结果为“l ”则被认为命中，然后根据相应的数组指针获 得原文献。这种方法对原文的压缩比率高、查询速度快，但是位运算可能导致 误匹配，而且只能判断某个单词在文献中是否出现，而无法获取其出现的位置、 次数等，且对于容量过大的数据库来说难以确定商效的处理算法【1 1 1 。因此，在 全文索引库的建立过程中，更为普遍采用的还足倒排索引技术。 2 2 全文检索模型 信息检索系统的核心是查找，它需要在大量复杂信息中，是用来描述这一 查找过程的。根据查找相关信息方式的不同，筛选出符合用户需要的信息。检 索模型就可将检索分为布尔模型、向量空间模型、概率模型、模糊逻辑模型等。 布尔逻辑模型 布尔逻辑模型【1 8 】是最简单的检索模型，也是其它检索模型的基础。标准布 尔逻辑模型为二元逻辑，即一系列对应于文件特征的二元变量。这些变量包括 从文件中提取的文本检索诃，有时也包括一些更为复杂的特征，如数据、短语、 私人签名和手工加入的描述子。在布尔模型中有确切的文件特征表达集合，用 户可以根据检索项在文档中的布尔逻辑关系递交查询。匹配函数由布尔逻辑的 基本法则确定，所检索出的文档或者与查询相关，或者与查询无关。查询结果 一般不进行相关性排序。 模糊逻辑模型 为了处理精度和复杂性之间的矛盾，引入了模糊逻辑模型 1 。】，它以逻辑真 值为【0 ，l 】的模糊逻辑为基础的，阱隶属函数概念来描述现象差异的中间过渡。 在查询结果处理过程中引入模糊逻辑运算，将所检索的文件信息和用户的查询 要求进行模糊逻辑比较，按照相关性的优先次序排出查询结果，在布尔检索中 借助模糊逻辑模型能够克服布尔逻辑查询结果的无序性。 向量空间模型 向量空间模型 1 叼是近年来使用较多且效果较好的一种信息检索模型。向量 空间模型是由s a l t o n 及其学生们提出的，并在善名的s m a r t 系统中实现。 向量空间模型将文档看作由相互独立的词条组( t l ，t 2 ，l ) 构成，对于 每一词条t l ，都根据其在文档中的重要程度赋以一定的权值h 7 ，这样文档就映 叩大学颂卜学位论文 射成为以各个词条组成的v 维空问中的一个点。对于所有文档和用户查询都可 映射到此文本向量空问。用户查询和被检索文档两者的相似程度可用向量之间 的夹角来度量。这种表示模型考虑到了文档的内容特征，而且文档之间的相似 程度的度量比较简单，现在有一些w e b 上的检索系统采用了这种检索模型， 并取得了较好的效果。 概率模型 在信息检索中存在不确定性问题，对查询本身来说，它不能唯一地表示信 息需求，对于结果来说，不能判定查询结果的正确与否。对于布尔检索也是如 此因为查询的提交本身就足一种不确定方式。为了解决在布尔检索模型中的不 确定性问题，引入了概率睑索模型。该模型基于概率排队理论：当文件按相关概 率递减原则排列时可以获得最大的检索性能i l ”。 2 3 倒排表的组织 2 3 1 中英文全文检索的区别 在计算机内部，无论汉字、西文和数字都是以字节形式存储。中英文全文 检索实际上都足将一个计算机存储的文本记录与用户信息需求做相似程度的比 较，并把足够相似的文本记录返回的过程。中文全文索引和英文全文检索之间 的区别是如何确定索引单元。在英文系统中，基本的处理单位很自然地就是词 ( w o r d ) ，因为词足最小的语义单位，而且荚文词之间有空格隔开，词的识别处 理非常方便。而中文系统中，字足独立的书写单位，另一方面，由于一个句子 中的词与词之间没有任何分隔标志，加上中文词法灵活，使得中文词的切分处 理非常用难。 从以上分析来看，中文全文检索比英文全文检索网难得多，在实现中文全 文检索时，存在两种基本的倒排表结构，即基于“字表”的倒排表和基于“词 表”的僦排表。 2 3 2 基于中文分词的倒排表 汉字全文检索系统和西文全文检索系统相比，在原理和方法上都有相同之 处。首先在计算机内部无论汉字还是西文都是以字节形式存储，两种技术的 四川人学顾卜学位论文 茅别主要足由于汉语本身造成的。在汉字全文检索中，一个基本问题是把检索 点放在词一级还是单字一级。 单汉字索引法 “字表法”是把源文档中的每一个字的出现位盖信息记录到索引库中，索 引库对每个不同的字符都保存一个字表，记录同一个字在文档中的所有出现位 置。建库时只要扫描所有文档，将读到的每个字符的位置信息加到对应的字表 中即可【2 0 1 。 词表法 “词表切分法”，是根据一定的原则和方法来对文章进行自动切词，然后按 词建库，对用户的检索结果按词汇匹配来进行查询，这种处理方法拥有较高的 查询命中率，但对“切词”技术的要求极高。这种方法要求配备一个词典库，其 实质是预先建立切分词典，以之为依据将文本字串与词典条目逐一比较，匹配 成功则以字串为词索引项，从而以能表达一定意义的词为基本单位建立索引库。 字表法和词表法的比较 “字表法”和“词表法”各有优缺点。“字表法”通用性强，实现和维护相 对容易，但检索时有可能断荜取义，将完全不相干的文档也检索出来，其缺点 主要表现为信息的冗余，当被检索的信息相当大的时候，该冗余完全会造成信 息垃圾。而“词表法”优点是对于大规模应用时，其索引库可以组织得比较小。 检索的处理速度比较快，而且能够根据词义进行概念检索，实现同义词、反义 诃的处理。国内外一般的情报检索系统，对于文本信息，如忙目数据库中的题 目、著者以及摘要等字段，或全文数据库的文献文本，都用词作为标引和检索 的基本单元。词表索引的缺点也是显而易见的。 汉字词表索引的不足 “字表法”面临的难题主要是：如何从汉字文本中抽词，即如何正确的从 字符串中提取出符合人类思维习惯的词单元。 为了解决这个问题，一是进行人工切分，即建立全文数据库时，事先由人 用标志符号将关键词切分开来，需要大量人力，同时加上的标志符号也拉长了 文本的篇幅。 另一种方法足事先编存词典，由计算机自动切分，这叫做中文自动分词技 术，其准确性取决于词典及切分规则的完善程度。词典的局限性如上所述，而 网川人学硬卜学位论文 切分规则也往往很难照顾全面。一些看来可以作为分词标志的虚字，有时可同 某一个或几个汉字组合在一起面成为有实质意义的词。例如“受控核反应”( 物 理) 、“以太网”( 计算机) 、“寻导系统( 兵器) a 2 4 中文自动分词技术 汉语自动分词足中文信息处理领域的一项基础性课题，也是智能化中文信 息处理的关键，是机器翻译、文献标引、智能检索、自然语言理解与处理的基 础。由于汉语自动分词在中文信息自动化处理中具有重要的地位，7 0 年代末以 来，这方面研究备受人们关注，并涌现出一批有应用前景的分词方法。目前， 许多分词方法己得到实现，并在不断完善中。从算法的角度划分，现时的分词 算法主要分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基 于统计的分词方法口”。 2 41 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与 一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹 配成功( 识别出一个词) 。按照扫描方向的不同，串匹配分词方法可以分为正向 匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最丈( 最长) 匹配 和最小( 最短) 匹配；按照足否与词性标注过程相结合，又可以分为单纯分词 方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下： 1 ) 正向最大匹配法( 由左到右的方向) ： 2 ) 逆向最大匹配法( 由右到左的方向) ； 3 ) 最少切分( 使每一句中切出的词数最小) 。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向 最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小 匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正 向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错 误率为1 1 6 9 ，单纯使用逆向最大匹配的错误率为1 2 4 5 。但这种精度还远远不 能满足实际的需要。实际使用的分词系统，都足把机械分词作为一种初分手段， 网j 大学颂l 学位论文 还焉通过利用各种其它的语言信息来进一步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符 串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串 分为较小的串再来进机械分词，从而减少匹配的错误率。另一种方法足将分词 和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注 过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。 对于机械分词方法，可以建立一个一般的模型，在这方面有号业的学术论 文，这里不做详细论述。 2 4 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息 来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下分词子系统可以获得有关词、句子等的句法和语 义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方 法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以 将各种语言信息组织成机器可直接读取的形式，因此目前基了：理解的分词系统 还处在试验阶段。 2 4 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现 的次数越多，就越有可能构成一个词。统计语言模型就是在对特定的语料库进 行统计和学习后，推测出自然语言的规律性川，因此字与字相邻共现的频率或 概率能够较好的反映“由字成词”的可信度。可以对语料中相邻共现的各个字的 组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算诱 个汉字x 、y 的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。 当紧密程度高于某一个阂值时，便可认为此字组可能构成了一个词。这种方法 只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词 法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度 朋川大学硕卜学位论史 高、但并不是词的常用字组，例如“这一、“之一”、“有的”、“我的”、“许多的” 等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要 使用一部基本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计方法 识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度 快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义 的优点。 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分 词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。笔 者了解，海量科技的分词算法就采用“复方分词法”，所谓复方，相当于用中药 中的复方概念，即用不同的药才综合起来去医治疾病，同样，对于中文词的识 别，需要多种算法来处理不同的问题。 分词中的难题 有了成熟的分词算法，是否就能容易的解决中文分词的问题呢? 事实远非 如此。中文是一种十分复杂的语言，让计算机理解中文语言更是闲难。在中文 分词过程中，有两大难题一直没有完全突破。 l 、歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：表面的， 因为“表面”和“面的”都是词，那么这个短语就可以分成“表面的”和“表面的”。 这种称为交叉歧义。像这种交叉歧义十分常见， “化妆和服装”可以分成“化妆 和服装”或者“化妆和服装”。由于没有人的知识去理解，计算机很难知道到 底哪个方案正确。 交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据整 个句子来判断了。例如，在句子“这个门把手坏了”中，“把手”是个词，但在句 子“请把手拿开”中，“把手”就不是一个词：在句子“将军任命了一名中将”中，“中 将”是个词，但在句子“产量三年中将增长两倍”中，“中将”就不再是词。这些词 计算机又如何去识别? 文献1 2 2 1 1 2 3 1 给出了目前歧义字段处理的一些基本方法。 如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一个难题， 是真歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪 个应该不是词。例如：“乒乓球拍卖完了”，可以切分成“乒乓球拍卖完了”、 也可切分成“乒乓球拍卖完了”，如果没有上下文其他的句子，恐怕谁也不 4 四川大学硕卜学位论文 知道“拍卖”在这里算不算一个词。 2 、新词识别 新词，专业术语称为来登录词。也就足那些在字典中都没有收录过，但又 确实能称为词的那些词。最典型的足人名，人可以很容易理解句子。王军虎去 广州了”中，“王军虎”是个词，因为是一个人的名字，但要是让计算机去识别 就困难了。如果把“王军虎”傲为一个词收录到字典中去，全世界有那么多名 字，而且每时每刻都有新增的人名，收录这些人名本身就是一项巨大的工程。 即使这项工作可以完成，还是会存在问题，例如：在句子“王军虎头虎脑的” 中，“王军虎”还能不能算词? 新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略 语等都是很难处理的问题2 4 - 2 们，而且这些又正好是人们经常使用的词，因此对 于搜索引擎来说，分词系统中的新词识别十分重要。目前新词识别准确率已经 成为评价一个分词系统好坏的重要标志之一。 分词准确性对大规模全文检索