网络信息检索中堆栈-最大匹配自动分词算法研究

摘要：本文分析了现有分词算法存在的不足，研究了机械分词方法、堆栈技术理论以及最大匹配法自动分词工作流程，在此基础上，构建了堆栈－最大匹配自动分词模型，详细阐述了该模型基本结构和运行流程。最后针对该算法，进行了简单举例分析。

关键词：堆栈；最大匹配法；分词算法

中图分类号：TP393.03 文献标识码：A文章编号：1007-9599 (2011) 08-0000-01

Network Information Retrieval Stack,Maximum Matching Automatic Segmentation Algorithm Study

Zhang Haiying

(Xiangfan University,Xiangfan441053,China)

Abstract:This paper analyses the shortcoming of segmentation algorithm.Designs a new algorithm for Chinese phrase segmentation based on stack.And also introduces the framework of the model,describes the detailed procedures.

Keywords:Stack;Maximum match method;Segmentation algorithm

自动分词问题是搜索引擎的核心问题，本文针对该问题，在对现有的分词算法分析研究的基础上，结合最大匹配分词法（MM法）和堆栈技术理论，提出了堆栈－最大匹配自动分词模型，该分词算法在对文章中的词进行自动切分时，具有良好的效果，实现了对MM分词算法的进一步改进。

一、机械分词方法和堆栈技术理论

机械分词方法的思路是先查词库进行匹配，然后再适当利用部分词法规则进行歧义校正。机械分词法之所以称之为“机械”，是因为它的切分过程是依赖于词库进行。词库中词条的数目、词条的选择直接影响到最后的分词效果。机械分词法加歧义校正属于机械分词法的一种改进，它主要利用词法规则对歧义进行校正，以提高切分精度，事实证明这种改进是有效的，而且这种改进最终导致了知识分词方法的出现。目前属于机械分词领域的分词方法主要有：最大匹配法、高频优先分词法、双向扫描法等。其中最大匹配分词法是机械分词方法的典型代表。

二、堆栈－最大匹配自动分词模型构建

堆栈-最大匹配自动分词技术主要是结合最大匹配分词法和堆栈技术对文章中的词进行自动切分，是对最大匹配法的改进。基于最大匹配自动分词的思想，结合堆栈技术理论，我们可以得出：最大匹配法重视的是字符长度，如果遇到在分词过程中后面字符串出现不可分的情况，能自动弹栈回退，并且重新检索出另一个成功匹配的词作为分词结果，就有可能解决后面字符串不可分的窘境。所以堆栈－最大匹配自动分词模型构建基本设计思想是：

首先按照文章中的标点符号将文章内容切分成语义块，每个语义块就是一个字符串，针对每一个字符串作循环。每次只处理一个汉字，将该汉字假设为词首，并且在词库中检索以该汉字为词首，检索该汉字后的字符匹配。根据检索出来的词作为分词结果的备选项，按长度排列，首先取出长度最长的那个词，即最大匹配，假设这个词就是以该汉字为首的分词结果，加入到这个语义块的分词结果栈中，然后继续该词语位置之后的下一个汉字的处理。在该方法实现的过程中，笔者将语义块中已经分词成功的那部分字符串在压栈的同时，从语义块中去掉。如果分词结果栈中出现分词歧义需要弹栈时，将弹出的结果加在原来语义块字符串的首部。这样就不需要在每得到一个分词结果后计算下一个即将处理的汉字的位置了。

三、堆栈－最大匹配自动分词算法

根据堆栈－最大匹配自动分词方法的基本思想和模型，形成了相应的堆栈最大匹配自动分词算法。堆栈－最大匹配自动分词的核心算法如下：

①在现有的句子中以标点符号为标界，且分成多个语义块block，存为字符串数组；设置另一个字符串数组result，存放单个block的分词结果；设整型数组undone，用来记录不可分的汉字的出现位置。②循环字符串数组，对数组中每个语义块block进行步骤③，直到整个字符串数组被处理完毕。③对单个的语义块每次都是从block的首个汉字开始进行分析，执行下一步；④如果result的总长度与原语义块的长度相等，或者是block的长度为零，说明该语义块分词完毕，执行步骤⑩；当分词过程遇到该汉字时，将该汉字暂时略过；执行步骤③；⑤取singleword=block.SubString（0，1），继续；⑥在词语表中查找以singleword为首词语，存为一个字符串数组temp，作为分词的备选项，继续以下判断；⑦如果temp的长度为零，即if（temp.Length==0），则说明不存在以该字为首的词语；比较该汉字的位置是否在不可分数组undone中有记录，如果有则略过该汉字，执行步骤③；⑧如果temp的长度为1，即if（temp.Length=1），只有一个分词结果备选项，那么该结果就是所要的分词结果，该词语压入分词结果栈中result数组中，执行步骤③；则说明在词语表中从block首部取出；⑨如果temp的长度大于1，即if（temp.Length>1），则说明分词结果备选项中存在多个结果，按照temp数组中的字符串长度的次序由小到大排列，取数组最后一个元素的字符串，在block首部去掉该词，压入分词结果栈result中，执行步骤③。⑩如果不可分数组undone不为空，则对数组中的元素和分词结果中的元素进行人为干预，将新词录入词库，执行下一步；⑪开始下一个语义块的分词，将上一个语义块的分词结果输出，并且将分词结果栈result清空，执行步骤②。

四、自动分词举例

假设在文章的句子中，已经有了切分好的语义块。例如，有一句话“这些学生会员都来了”。词库中已经有以下的词语了：这些、学生、学生会、会员、都、来、了

那么，应用上述的自动分词算法，依次对该句的汉字进行分析，其详细过程如下：①检索“这”，发现“这些”在词库中并且与原文匹配；②检索“学”，发现有两个匹配，分别是“学生”和“学生会”，取字符长度最长的那个匹配项“学生会”；③检索“员”，发现词库中没有以“员都”或“员”这样的词语，因此不存在匹配，于是将先前的栈顶元素弹出，压入第二长的分词备选项“学生”：④检索“都”，这是一个副词，在词库中；⑤同理，“来”和“了”依次被分出来。

实践证明，利用该分词算法进行自动分词，其分词复杂度得以大的改善，该分词算法在对文章中的词进行自动切分时，可以大大降低分词过程中的匹配次数，提高了分词的响应速度，尤其适合大量中文信息的分析与处理。

参考文献：

[1]揭春雨,刘源,梁南元.论汉语自动分词方法[J].中文信息学报,1989,3(1):101-108

[2]孙巍.一种面向中文信息检索的汉语自动分词方法[J].现代图书情报技术,2006,139(7):733-736

[3]吴绍根.汉语自动分词模式自动机构造研究[J].现代图书情报技术,2006,136(5):551-553+565

[作者简介]张海营（1978-），馆员，主要研究方向：网络信息组织与检索，网络信息增值服务。

[基金项目]襄樊学院2009年教研项目《高校数字化教学资源共享平台构建与实践》研究成果，项目编号：JY200950