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

中文信息检索引擎中的若干技术吴栋滕育平(南开大学组合数学研究中心核心数学与组合数学教育部重点实验室,天津300071)摘要本文论述了在开发中文信息检索系统中所涉及到的两项关键技术，即中文分词技术和检索技术。对中文分词技术，本文介绍了一种改进的正向最大匹配切分算法，以及为消除歧义引入的校正策略，并在此基础上结合统计方法处理未登录词。针对检索技术，本文综述了几种最常用的检索模型的原理，并对每种模型的优缺点进行了简要分析。最后对给出的分词算法进行了测试，测试表明本文给出的分词算法准确度和效率能够满足实用的要求。关键词信息检索搜索引擎分词技术检索技术1引言随着社会的不断进步，特别是在互联网迅猛发展的今天，人们在不断地接触形形色色的信息，同时也要对这些信息进行过滤，从而提取出对自己真正有用的内容。为了达到这个目的，人们开发出了众多的检索引擎，有针对Web进行搜索的Goolge、百度等，也有针对各行业开发的专题检索系统。目前，国内的每个行业、领域都在飞速发展，这中间产生了大量的中文信息资源，为了能够及时准确的获取最新的信息，中文检索引擎是必然的产物。中文检索引擎与西文检索引擎在实现的机制和原理上大致雷同，但由于汉语本身的特点，必须引入对于中文语言的处理技术，而中文分词技术就是其中很关键的部分。2中文检索引擎的基本原理常见的中文检索引擎主要完成两方面的任务：1．信息的规范化。将搜集来的信息按照一定的方式进行组织管理，使之成为可以高效检索的信息库。2．信息的检索和表达。以索引好的信息库作为信息基础，利用信息库已被索引的特点，实施快速检索，同时根据用户的需求将检索结果进行输出。其中，信息的规范化包括分词和索引（以及资料的搜集和整理）、更新（维护）两部分；信息的检索包括搜索、结果输出两部分。整个信息处理和检索过程如图1所示：搜集整理标题、作者、摘要等正文分词索引词1词2词3位置1位置2位置1查询表达式结果输出搜索词串表达式解析搜索结果搜索输入搜索输出结果排序页面生成信息搜集+信息整理信息存储信息检索人机交互分析查询用户图1中文信息处理和检索过程3中文分词技术3.1汉语的特点词是最小的、能独立活动的、有意义的语言成分。因此，通常的检索引擎都是以每一个独立的词为单位建立索引，在查询时按照检索词出现的位置和频率对文档进行输出。英语文本是小字符集上的已充分分隔开的词串,而汉语文本是大字符集上的连续字串，并且在词与词之间并没有明显的分割标记。故而存在一个对汉语中的词加以识别的问题，即中文检索引擎首先必须对原文进行切分词。如果不切词（按字检索）,可能检索的结果与用户的查询要求会大相径庭，例如当检索德国货币单位马克时,就会把马克思检索出来,而检索华人时会把中华人民共和国检索出来。因而进行切词,可以大大提高检索的准确率。中国的汉字是示意文字，总数有几万个，在由国家标准总局颁布的《信息交换用汉字编码字符集--基本集》（即GB2312-80）中共收录了一级和二级常用汉字共6763个，而在Unicode编码中更是收录多达20902个汉字。据统计，在常用汉语中，90%以上使用的是二字词和三字词，也有使用四字词和五字词。知道这些汉字的特点，对于我们选择合理的切分算法是有益的。3.2一般的分词技术由于书面汉语是字的序列，词与词之间没有间隔标记，使得词的界定往往模糊不清。即使这样，在过去的时间里，人们在汉语的自动分词技术的研究上还是做了很多工作，设计了许多实用、高效的算法。通常的方法主要分为两类[1]：第一类主要基于字典、词库的匹配和词的频度统计，这类方法实用、具体，比较容易实现；第二类方法主要基于句法、语法分析，并结合语义分析，通过对上下文内容所提供信息的分析对词进行定界，这类方法试图让机器具有人类的理解能力，其原理较为晦涩，一般不易实现。常用的切词算法如下：1)最大正向匹配法(MaximumMatchingMethod)通常简称为MM法。其基本思想为：设D为词典，MAX表示D中的最大词长，str为待切分的字串。MM法是每次从str中取长度为MAX的子串与D中的词进行匹配。若成功，则该子串为词，指针后移MAX个汉字后继续匹配，否则子串逐次减一进行匹配。2)逆向最大匹配法(ReverseMaximumMatcingMethod)通常简称为RMM法。RMM法的基本原理与MM法相同，不同的是分词的扫描方向，它是从右至左取子串进行匹配。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245，RMM法在切分的准确率上比MM法有很大提高。3)基于词频的统计方法统计方法一般不依赖于词典，而是将原文中任意前后紧邻的两个字作为一个词进行出现频率的统计，出现的次数越高，成为一个词的可能性也就越大。在频率超过某个预先设定得阈值时，就将其作为一个词进行索引。这种方法能够有效地提取出未登录词。3.3一种改进的MM算法MM法和RMM法的缺点在于对词典的完全性有很强的依赖性，而且无法很好的解决歧义问题，有人提出了双向匹配法，即针对一个字符串，分别从两个方向进行处理，但这种方法只有检错功能，却不能自动进行校正，给出正确结果。由于一个词在不同的文章中出现的次数通常不一样，因此采用统计方法对词的切分准确度并不太高。鉴于以上几种方法的优缺点，人们自然想把这几种方法结合起来，扬长避短。这里，介绍一种改进的MM算法。3.3.1词典存储格式采用分层存储的形式，一共分为3层，形成树型结构，如下所示（每一个字母代表一个字）。A1A3A2A1B1(f,n1)A1C1(t,n3)A1B2(t,n2)AnA1D1(t,n4)F1G2H1G2H1R1T1一层存储所有单字。第二层保存所有的双字词和多字词的前两个字（因为，也许会出现ABC为词，但AB不是词的情况），并对两者做不同标记(t/f)。每一个可成词的单字对应一系列第二层结点，用来存储所有以该字为词首的双字（包括上述两种情况）。并且，在这里，针对每一个双字，需要记录以该双字为词首的所有词的最大长度，实际中，可以保存除去该双字部分的最大长度(记为n)。第三层存储以某一双字为首的所有词。为了减少存储空间，只存储除去该双字以外的部分（如上图所示）。每一层各结点需按某种次序排列，可使用hash、二分查找等方法进行查询。采用这种层次的存储结构，可以很快把查询词的工作缩小到一个很小的范围内，有利于分词效率的提高。3.3.2匹配方法(MM方法)由于词库中的最大词长通常大于所切分出的词长，为了提高切分的效率，不采用逐次减一个字的方法，而是使用正向逐一增长的方法。假设对一个句子C1C2……进行分词处理，算法描述如下：1)两个字（开始时为C1C2），在词典中查询C1C2是否存在2)不存在，则C1为单字词，一次分词结束，返回1。3)存在，判断C1C2是否为词，并从词典中获取该词下层节点汉字的最大长度，设为n4)若n=0，一次分词结束，保存结果。5)否则，i=2，转6)。6)i=i+1，若i=n+3，转8)；否则，转7)。7)再取一个字（此处为Ci），判断第三层中是否有以C3……Ci开始的字(不需要恰好匹配，只要匹配开始的i个字就可以了)。8)若存在，分词结束，返回最近一次能够恰好匹配的C3……Cj(ji)，并与C1C2组合成词。如果是C1C2，则根据C1C2的标记判断是双字词还是分为两个单字词。9)否则，转6)。3.3.3歧义词处理汉语中的歧义结构主要有两种：交集型歧义和组合型歧义。据统计，汉语中的交集型歧义字段约占全部歧义字段的90%。所以，处理好交集歧义字段在很大程度上能保证一定的分词精度。鉴于汉语中多数的词组、短语为偏正结构，中心词在后，而修饰词在前，故而在进行歧义校正时，我们让交集歧义字优先与右边的子段组成词，而其余的字段则尽可能的向左组词。设C1C2……Cn是连续型交叉歧义字段，具体的歧义校正策略如下：A．主导策略1)指针移向Cn，调用分词算法对以Cn为首字的词进行查找。2)若句子中Cn可以和后面的字构成词（设Cn……Cm为构成的最长词），则对Cn进行标记。3)移向Cm，继续对Cm进行处理，方法类似于2)，直到找到没有歧异的词为止。4)不妨设Cm与其后的字不成词，此时让Cn优先与右边的子段组成词，即切分Cn……Cm为一词。5)对Cn之前的部分做最大正向匹配，歧义处理结束。B．辅助策略在汉语中许多字是多义字，由于上下文环境的不同，这些字既可以作为只具语法意义或功能意义的虚词，也可以与其他字组合构成实词，如“的”、“地”、“了”等。统计结果表明，当这些字作为虚词时，通常作为词的尾字出现，而构成实词时，往往出现在词的首位，或中间部位，所以对这些字如果直接采用主导策略，往往会造成切分错误。因此，我们对这些字引入辅助策略。1)在使用主导策略第一步时，判断Cn是否是上述的多义字2)若是，且Cn是某个词的词尾字，同时Cn无法与其后的字构成词，此时将Cn视为虚词，并作为单独一个词进行切分，而对Cn之前的部分做最大正向匹配。3)否则，继续采用主导策略。3.3.4统计方法运用由于词典的不完全性，许多词可能不会在字典中登录，为了处理句子中的未登录词，我们在原有的算法中嵌入词频统计方法，将某些出现频率较高的连续字段作为一个词切分，我们首先对频度设定一个阈值f。设已对C1……Cn进行切分，由切分算法和歧义处理算法得到C1……Ci为一个词，Cj……Cn为一个词，Ci与Cj之间皆为单字词，即C1……Ci和Cj……Cn是相邻最近的两个多字词，则将Ci+1……Cj-1作为一个多字词进行词频统计，在对文章全部切分完毕之后，若Ci+1……Cj-1的出现次数达到f时，则将其看作一个词，否则，将其拆分为单字词。同时，对于相同或相近专业和领域建立起动态词库，将由统计得到的词不断加入词库中，可以实现对词典的动态维护。通过将基于词典的处理方法和基于频率的统计方法结合起来，不仅保证了切分速度快、精度高的优点，而且能够结合上下文，最大限度的识别人名、地名、专业术语等未登录词。4检索技术根据查找相关信息的实现方式不同，常见的信息检索引擎有布尔逻辑模型、模糊逻辑模型、向量空间模型和概率检索模型等几类。4.1布尔逻辑模型布尔逻辑模型是最简单的检索模型，也是其他检索模型的基础。设文本集D=(d1,d2,d3,…,dn),di(i=1,2,…,n)为文本集中某一文档;又设Ti=(ti1,ti2,…,tim)为di的标引词集合,则对于形如Q=W1∧W2∧…∧Wk的检索式,如果W1∈Ti,W2∈Ti,…,Wk∈Ti,则di为查询Q的命中文档,否则di为Q的不命中文档;而对于形如Q=W1∨W2∨…∨Wk的检索式,如果至少存在某个Wj∈Ti(j=1,2,…,k),则di为Q的命中文档,否则di为不命中文档。用户根据所检索关键字在检索结果中的逻辑关系递交查询，查询模块根据布尔逻辑的基本运算法则来给出查询结果。布尔检索模型原理简单易理解，容易在计算机上实现并且具有检索速度快的优点。但是最终给出的查询结果没有相关性排序，不能全面反映用户的需求，功能不如其他的检索模型。4.2模糊逻辑模型模糊逻辑模型以模糊数学作为理论基础，设置单个的检索词w在文档d中的隶属度u，u∈[0,1]，u越大代表w和文档d的相关性越高。用户给出查询要求，查询模块根据模糊逻辑运算给出查询的结果，并能够按照相关度排序。模糊逻辑模型能够克服布尔逻辑模型检索结果的无序性，但是给查询词设置准确的隶属度有一定困难。4.3向量空间模型向量空间模型[4]将文档映射为一个特征向量V(d)=(t1,ω1(d)；…；tn,ωn(d))，其中ti(i=1,2,…,n)为一列互不雷同的词条项，ωi(d)为ti在d中的权值,一般被定义为ti在d中出现频率tfi(d)的函数，即))(()(dtfdii。在信息检索中常用的词条权值计算方法为TF-IDF函数)log()(iinNdtf，其中N为所有文档的数目，ni为含有词条ti的文档数目。TF-IDF公式有很多变种，下面是一个常用的TF-IDF公式：niiiiiinNdtfnNdtfd1