中文信息检索引擎中的若干技术

1、中文信息检检索引擎中中的若干技技术吴栋 滕育平(南开大学学组合数学学研究中心心 核心数学学与组合数数学教育部部重点实验验室, 天天津 30000711)摘要本本文论述了了在开发中中文信息检检索系统中中所涉及到到的两项关关键技术，即即中文分词词技术和检检索技术。对中文分分词技术，本本文介绍了了一种改进进的正向最最大匹配切切分算法，以以及为消除除歧义引入入的校正策策略，并在在此基础上上结合统计计方法处理理未登录词词。针对检检索技术，本本文综述了了几种最常常用的检索索模型的原原理，并对对每种模型型的优缺点点进行了简简要分析。最后对给给出的分词词算法进行行了测试，测测试表明本本文给出的的分词算法法准确

2、度和和效率能够够满足实用用的要求。关键词信信息检索 搜索索引擎 分词技技术检索技术术1 引言随着社会的的不断进步步，特别是是在互联网网迅猛发展展的今天，人人们在不断断地接触形形形色色的的信息，同同时也要对对这些信息息进行过滤滤，从而提提取出对自自己真正有有用的内容容。为了达达到这个目目的，人们们开发出了了众多的检检索引擎，有有针对Weeb进行搜搜索的Gooolgee、百度等等，也有针针对各行业业开发的专专题检索系系统。目前前，国内的的每个行业业、领域都都在飞速发发展，这中中间产生了了大量的中中文信息资资源，为了了能够及时时准确的获获取最新的的信息，中中文检索引引擎是必然然的产物。中文检索索引擎

3、与西西文检索引引擎在实现现的机制和和原理上大大致雷同，但但由于汉语语本身的特特点，必须须引入对于于中文语言言的处理技技术，而中中文分词技技术就是其其中很关键键的部分。2 中文检检索引擎的的基本原理理常见的中文文检索引擎擎主要完成成两方面的的任务：1信息的的规范化。将搜集来来的信息按按照一定的的方式进行行组织管理理，使之成成为可以高高效检索的的信息库。 22信息的的检索和表表达。以索引好好的信息库库作为信息息基础，利利用信息库库已被索引引的特点，实实施快速检检索，同时时根据用户户的需求将将检索结果果进行输出出。其中，信息息的规范化化包括分词词和索引（以以及资料的的搜集和整整理）、更更新（维护护）

4、两部分分；信息的的检索包括括搜索、结结果输出两两部分。整整个信息处处理和检索索过程如图图1所示：3 中文分分词技术3.1 汉汉语的特点点词是最小的的、能独立立活动的、有意义的的语言成分分。因此，通通常的检索索引擎都是是以每一个个独立的词词为单位建建立索引，在在查询时按按照检索词词出现的位位置和频率率对文档进进行输出。英语文本本是小字符符集上的已已充分分隔隔开的词串串,而汉语语文本是大大字符集上上的连续字字串，并且且在词与词词之间并没没有明显的的分割标记记。故而存在在一个对汉汉语中的词词加以识别别的问题，即即中文检索索引擎首先先必须对原原文进行切切分词。如如果不切词词（按字检检索）,可可能检索的

5、的结果与用用户的查询询要求会大大相径庭，例例如当检索索德国货币币单位马马克时,就会把马克思检索出来来,而检索索华人时会把中华人民民共和国检索出来来。因而进行切切词,可以以大大提高高检索的准准确率。中国的汉字字是示意文文字，总数数有几万个个，在由国国家标准总总局颁布的的信息交交换用汉字字编码字符符集-基基本集（即即GB23312-880）中共共收录了一一级和二级级常用汉字字共67663个，而而在Uniicodee编码中更更是收录多多达209902个汉汉字。据统统计，在常常用汉语中中，90%以上使用用的是二字字词和三字字词，也有有使用四字字词和五字字词。知道道这些汉字字的特点，对对于我们选选择合理

6、的的切分算法法是有益的的。3.2 一一般的分词词技术由于书面汉汉语是字的的序列，词词与词之间间没有间隔隔标记，使使得词的界界定往往模模糊不清。即使这样样，在过去去的时间里里，人们在在汉语的自自动分词技技术的研究究上还是做做了很多工工作，设计计了许多实实用、高效效的算法。通常的方方法主要分分为两类1：第第一类主要要基于字典典、词库的的匹配和词词的频度统统计，这类类方法实用用、具体，比比较容易实实现；第二二类方法主主要基于句句法、语法法分析，并并结合语义义分析，通通过对上下下文内容所所提供信息息的分析对对词进行定定界，这类类方法试图图让机器具具有人类的的理解能力力，其原理理较为晦涩涩，一般不不易实

7、现。常用的切词词算法如下下：1)最大正正向匹配法法(Maxximumm Mattchinng Meethodd)通常简称为为MM法。其基本思思想为：设设D为词典典，MAXX表示D中中的最大词词长，sttr为待切切分的字串串。MM法法是每次从从str中中取长度为为MAX的的子串与DD中的词进进行匹配。若成功，则则该子串为为词，指针针后移MAAX个汉字字后继续匹匹配，否则则子串逐次次减一进行行匹配。2)逆向最最大匹配法法(Revversee Maxximumm Mattcingg Metthod) 通常简称为为RMM法法。RMMM法的基本本原理与MMM法相同同，不同的的是分词的的扫描方向向，它是从

8、从右至左取取子串进行行匹配。统统计结果表表明，单纯纯使用正向向最大匹配配的错误率率为1/1169，单单纯使用逆逆向最大匹匹配的错误误率为1/245，RRMM法在在切分的准准确率上比比MM法有有很大提高高。3)基于词词频的统计计方法统计方法一一般不依赖赖于词典，而而是将原文文中任意前前后紧邻的的两个字作作为一个词词进行出现现频率的统统计，出现现的次数越越高，成为为一个词的的可能性也也就越大。在频率超超过某个预预先设定得得阈值时，就就将其作为为一个词进进行索引。这种方法法能够有效效地提取出出未登录词词。3.3 一一种改进的的MM算法法MM法和RRMM法的的缺点在于于对词典的的完全性有有很强的依依赖

9、性，而而且无法很很好的解决决歧义问题题，有人提提出了双向向匹配法，即即针对一个个字符串，分分别从两个个方向进行行处理，但但这种方法法只有检错错功能，却却不能自动动进行校正正，给出正正确结果。由于一个个词在不同同的文章中中出现的次次数通常不不一样，因因此采用统统计方法对对词的切分分准确度并并不太高。鉴于以上几几种方法的的优缺点，人人们自然想想把这几种种方法结合合起来，扬扬长避短。这里，介介绍一种改改进的MMM算法。3.3.11 词典存储储格式采用分层存存储的形式式，一共分分为3层，形形成树型结结构，如下下所示（每每一个字母母代表一个个字）。一层存储所所有单字。第二层保保存所有的的双字词和和多字词

10、的的前两个字字（因为，也也许会出现现ABC为为词，但AAB不是词词的情况），并并对两者做做不同标记记(t/ff)。每一一个可成词词的单字对对应一系列列第二层结结点，用来来存储所有有以该字为为词首的双双字（包括括上述两种种情况）。并且，在在这里，针针对每一个个双字，需需要记录以以该双字为为词首的所所有词的最最大长度，实实际中，可可以保存除除去该双字字部分的最最大长度(记为n)。第三层层存储以某某一双字为为首的所有有词。为了了减少存储储空间，只只存储除去去该双字以以外的部分分（如上图图所示）。每一层各各结点需按按某种次序序排列，可可使用haash、二二分查找等等方法进行行查询。采采用这种层层次的存

11、储储结构，可可以很快把把查询词的的工作缩小小到一个很很小的范围围内，有利利于分词效效率的提高高。3.3.22 匹配方法法(MM方方法)由于词库中中的最大词词长通常大大于所切分分出的词长长，为了提提高切分的的效率，不不采用逐次次减一个字字的方法，而而是使用正正向逐一增增长的方法法。假设对一个个句子C11C2进行分分词处理，算算法描述如如下：1) 两个个字（开始始时为C1C2），在词词典中查询询C1C2是否存在在2) 不存存在，则CC1为单字词词，一次分分词结束，返返回1。3) 存在在，判断CC1C2是否为词词，并从词词典中获取取该词下层层节点汉字字的最大长长度，设为为n4) 若nn=0，一一次分

12、词结结束，保存存结果。5) 否则则，i=2，转转6)。6 ) ii=i+1，若若i=n+33，转8)；否则，转转7)。7) 再取取一个字（此此处为Cii），判断断第三层中中是否有以以C3Ci开始的字字(不需要要恰好匹配配，只要匹匹配开始的的i个字就就可以了)。8) 若存存在，分词词结束，返返回最近一一次能够恰恰好匹配的的C3Cj(jii)，并与与C1C2组合成词词。如果是是C1C2，则根据据C1C2的标记判判断是双字字词还是分分为两个单单字词。9) 否则则，转6)。3.3.33 歧义词处处理汉语中的歧歧义结构主主要有两种种：交集型型歧义和组组合型歧义义。据统计计，汉语中中的交集型型歧义字段段约

13、占全部部歧义字段段的90%。所以，处处理好交集集歧义字段段在很大程程度上能保保证一定的的分词精度度。鉴于汉汉语中多数数的词组、短语为偏偏正结构，中中心词在后后，而修饰饰词在前，故故而在进行行歧义校正正时，我们们让交集歧歧义字优先先与右边的的子段组成成词，而其其余的字段段则尽可能能的向左组组词。设C1C22Cn是连续型型交叉歧义义字段，具具体的歧义义校正策略略如下：A主导策策略1) 指针针移向Cnn，调用分分词算法对对以Cn为首字的的词进行查查找。2) 若句句子中Cnn可以和后后面的字构构成词（设设CnCm为构成的的最长词），则则对Cn进行标记记。 3) 移向向Cm，继续对对Cm进行处理理，方法

14、类类似于2)，直到找找到没有歧歧异的词为为止。4) 不妨妨设Cm与其后的的字不成词词，此时让让Cn优先与右右边的子段段组成词，即即切分CnnCm为一词。5) 对CCn之前的部部分做最大大正向匹配配，歧义处处理结束。B辅助策策略在汉语中许许多字是多多义字，由由于上下文文环境的不不同，这些些字既可以以作为只具具语法意义义或功能意意义的虚词词，也可以以与其他字字组合构成成实词，如如“的”、“地”、“了”等。统计计结果表明明，当这些些字作为虚虚词时，通通常作为词词的尾字出出现，而构构成实词时时，往往出出现在词的的首位，或或中间部位位，所以对对这些字如如果直接采采用主导策策略，往往往会造成切切分错误。因

15、此，我我们对这些些字引入辅辅助策略。1) 在使使用主导策策略第一步步时，判断断Cn是否是上上述的多义义字2) 若是是，且Cnn是某个词词的词尾字字，同时CCn无法与其其后的字构构成词，此此时将Cnn视为虚词词，并作为为单独一个个词进行切切分，而对对Cn之前的部部分做最大大正向匹配配。3) 否则则，继续采采用主导策策略。3.3.44 统计方法法运用由于词典的的不完全性性，许多词词可能不会会在字典中中登录，为为了处理句句子中的未未登录词，我我们在原有有的算法中中嵌入词频频统计方法法，将某些些出现频率率较高的连连续字段作作为一个词词切分，我我们首先对对频度设定定一个阈值值f。设已对C11Cn进行切分

16、分，由切分分算法和歧歧义处理算算法得到CC1Ci为一个词词，CjCn为一个词词，Ci与Cj之间皆为为单字词，即即C1Ci和CjCn是相邻最最近的两个个多字词，则则将Ci+1Cj-1作为为一个多字字词进行词词频统计，在在对文章全全部切分完完毕之后，若若Ci+1Cj-1的出出现次数达达到f时，则则将其看作作一个词，否否则，将其其拆分为单单字词。同时，对于于相同或相相近专业和和领域建立立起动态词词库，将由由统计得到到的词不断断加入词库库中，可以以实现对词词典的动态态维护。通过将基于于词典的处处理方法和和基于频率率的统计方方法结合起起来，不仅仅保证了切切分速度快快、精度高高的优点，而而且能够结结合上下

17、文文，最大限限度的识别别人名、地地名、专业业术语等未未登录词。4 检索技技术根据查找相相关信息的的实现方式式不同，常常见的信息息检索引擎擎有布尔逻辑辑模型、模模糊逻辑模模型、向量量空间模型型和概率检检索模型等等几类。4.1 布布尔逻辑模模型布尔逻辑模模型是最简简单的检索索模型，也也是其他检检索模型的的基础。设文本集DD=(d11,d2,d3,dn),di(i=11,2,n)为为文本集中中某一文档档;又设TTi=(ti11,ti2,tim)为ddi的标引引词集合,则对于形形如Q=WW1W2Wk的检索式式,如果WW1Ti,W2Ti,WkTi,则di为查询QQ的命中文文档,否则则di为Q的不不命中文

18、档档;而对于于形如Q=W1W2Wk的检索式式,如果至至少存在某某个WjTi(j=11,2,k),则di为Q的命命中文档,否则dii为不命中中文档。用户根据所所检索关键键字在检索索结果中的的逻辑关系系递交查询询，查询模模块根据布布尔逻辑的的基本运算算法则来给给出查询结结果。布尔检索模模型原理简简单易理解解，容易在在计算机上上实现并且且具有检索索速度快的的优点。但但是最终给给出的查询询结果没有有相关性排排序，不能能全面反映映用户的需需求，功能能不如其他他的检索模模型。4.2 模模糊逻辑模模型模糊逻辑模模型以模糊糊数学作为为理论基础础，设置单单个的检索索词w在文文档d中的的隶属度uu，u0,11，u

19、越越大代表ww和文档dd的相关性性越高。用用户给出查查询要求，查查询模块根根据模糊逻逻辑运算给给出查询的的结果，并并能够按照照相关度排排序。模糊逻辑模模型能够克克服布尔逻逻辑模型检检索结果的的无序性，但但是给查询询词设置准准确的隶属属度有一定定困难。4.3 向向量空间模模型向量空间模模型4将文档映映射为一个个特征向量量V(d)=(t11,1(d)；tn, n(d)，其中tti(i=1,22, ,n)为一列互互不雷同的的词条项，i(d)为ti在d中的权值, 一般被定义为ti在d中出现频率tfi(d)的函数，即。在信息检索中常用的词条权值计算方法为 TF-IDF 函数，其中N为所有文档的数目，ni

20、为含有词条ti的文档数目。TF-IDF公式有很多变种，下面是一个常用的TF-IDF公式：根据TF-IDF公公式，文档档集中包含含某一词条条的文档越越多，说明明它区分文文档类别属属性的能力力越低，其其权值越小小；另一方方面，某一一文档中某某一词条出出现的频率率越高，说说明它区分分文档内容容属性的能能力越强，其其权值越大大。两文档之间间的相似度度可以用其其对应的向向量之间的的夹角余弦弦来表示，即即文档dii，dj的相似度度可以表示示为进行查询的的过程中，先先将查询条条件Q进行行向量化，主主要依据布布尔模型:当ti在查查询条件QQ中时，将将对应的第第i坐标置置为1，否否则置为00，即从而文档dd与查

21、询QQ的相似度度为 根据文档之之间的相似似度，结合合机器学习习的一些算算法如神经经网络算法法，K-近近邻算法和和贝叶斯分分类算法等等，可以将将文档集分分类划分为为一些小的的文档子集集。在查询过程程中，可以以计算出每每个文档与与查询的相相似度，进进而可以根根据相似度度的大小，将将查询的结结果进行排排序。向量空间模模型可以实实现文档的的自动分类类和对查询询结果的相相似度排序序，能够有有效提高检检索效率；它的缺点点是相似度度的计算量量大，当有有新文档加加入时，则则必须重新新计算词的的权值。4.4 概概率检索模模型概率检索模模型是在布布尔逻辑模模型的基础础上为解决决检索中存存在的一些些不确定性性而引入

22、的。概率检检索模型有有多种形式式，常见的的为第二概概率检索模模型,首先先设定标引引词的概率率值，一般般是对检索索作业重复复若干次,每一次检检索用户对对检出文档档进行相关关性判断。再利用这这种反馈信信息,根据据每个词在在相关文档档集合和无无关文档集集合的分布布情况来计计算它们的的相关概率率,将词的的权值设计计为:其中P,PP分别表示示某词在相相关文档集集和无关文文档集中出出现的概率率。某一文文档的权值值则是它所所含的标引引词权值之之和,于是是,文档dd与用户查查询Q相关关概率可定定义为:其中pw和和pw分别为ww在相关文文档和无关关文档中的的概率。上上式中右边边和式是对对所有出现现在文档dd和查

23、询QQ中的词ww求和，即即wdQ.概率模型有有严格的数数学理论基基础，采用用了相关反反馈原理克克服不确定定性推理的的缺点，它它的缺点是是参数估计计的难度比比较大，文文件和查询询的表达也也比较困难难。以上介绍了了几种传统统的检索模模型，随着着检索技术术的不断发发展，新的的检索技术术也不断涌涌现，出现现了诸如并并行信息检检索系统、演绎信息息检索系统统、基于超超文本技术术的信息检检索系统、分布式检检索系统和和智能检索索系统等5。这这些新的技技术代表了了检索技术术的发展方方向。5 实验结结果我们对设计计的切分算算法作了程程序上的实实现，采用用的语料库库来自由北北京大学计计算语言学学研究所和和富士通研研

24、究开发中中心有限公公司共同制制作的PFFR人民日日报标注语语料库（版版本1.00）。CPU内存操作系统开发环境P4 11.5G256MWin20000VC+66.0本文在以下下环境中实实现了切分分算法：切分结果：文件大小汉字（个）用时（秒）切分准确率率3.55 MB18394414 483.5544 91577%统计结果：统计词数（个个）人名（个）地名（个）其它有意义义的词（个个）有效率19966229032351855%结果分析：我们的词典典总共收录录了1300152个个词，基本本上覆盖了了常用词汇汇。切分结结果表明采采用一个比比较完全的的词典，再再配合以快快速的切分分算法和适适当的校正正策

25、略，从从而使得无无论是切分分效率还是是切分正确确率，都是是令人满意意的。根据据词频统计计出的结果果中，也有有很大一部部分是有意意义的词汇汇，说明用用统计方法法处理未登登录词包括括人名和地地名也是有有效的。最最后，我们们还将经过过统计得到到的有意义义的词加入入词典进行行再次切分分，得到的的准确率为为92.334%，比比原结果提提高了0.77%，可可见在原有有的切分算算法上再辅辅助以统计计方法，可可以有效提提高切分的的准确度。 6 结束语语要开发高性性能的中文文检索引擎擎，快速、可靠的中中文分词算算法和准确确、高效的的检索技术术是至关重重要的，针针对不同领领域和需求求，需要采采取不同的的策略和方方

26、法，本文文仅起抛砖砖引玉的作作用。随着着科学技术术的发展，人人们必然需需要针对性性更强的中中文检索引引擎，因此此，专业化化、 深层层次的中文文检索引擎擎将是今后后的发展方方向。参考文献献1严威威, 赵政政. 开发发中文搜索索引擎汉语语处理的关关键技术. 计算算机工程 Voll .255, Noo.61, 19999, ppp5-66.2姚天天顺, 朱朱靖波等. 自然语语言理解（第第2版）. 北京：清华大学学出版社, 20002.3Toom M. Mittchelll. 机机器学习. 曾华军军, 张银银奎等译.北京：机械工业业出版社，22003.4G.Saltton, A.Woong, C.S.

27、Yangg. Onn thee speecifiicatiion oof teerm vvaluees inn auttomattic iindexxing. Jouurnall of Docuumenttatioon, 11973 , 299(4):351372.5贾同同兴. 人人工智能与与情报检索索.北京：北京图书书馆出版社社, 19997.77.Some Techhniquues for IInforrmatiion SSearcch Ennginees foor ChhinesseWU DoongTENGG Yu-pingg(Centter ffor CCombiinatooricss

28、, Laaboraatoryy of Puree Matthemaaticss andd Commbinaatoriics, Nankkai Univversiity, Tiannjin 3000071, P.R. Chiina)Abstrract. Two kkey ttechnniquees inn thee devveloppmentt of Chinnese Infoormattion Retrrievaal Syystemm aree disscusssed iin thhis ppaperr, i.e., Chinnese wordd seggmenttatioon annd seearchh tecchniqque. For Chinnese