中文分词改进算法

１２４　２０１４，５０（２）　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ￣￣算机工程与应用　

基于改进最大匹配算法的中文分词粗分方法　

周　俊　，郑中华　，张炜　

ＺＨＯＵ　Ｊｕｎ　，ＺＨＥＮＧ　Ｚｈｏｎｇｈｕａ２，ＺＨＡＮＧ　Ｗｅｉ　

１．华中科技大学模具技术国家重点实验室，武汉４３００７４　

２．中国人民大学教育学院，北京１００８７２　

３．安徽博约信息科技有限责任公司，合肥２３００８８　

１．Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂ　ｏｆＭｏｌｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７４，Ｃｈｉｎａ　

２．Ｓｃｈｏｏｌ　ｏｆ　Ｅｄｕｃａｔｉｏｎ，Ｒｅｎｍｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎａ，Ｂｅｉｊｉｎｇ　１　００８７２，Ｃｈｉｎａ　

３．Ａｎｈｕｉ　Ｂｏｒｙｏｕ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ｃｏ．Ｌｔｄ，Ｈｅｆｅｉ　２３００８８，Ｃｈｉｎａ　

ＺＨＯＵ　Ｊｕｎ，ＺＨＥＮＧ　Ｚｈｏｎｇｈｕａ，ＺＨＡＮＧ　Ｗｅｉ．Ｍｅｔｈｏｄ　ｏｆ　Ｃｈｉｎｅｓｅ　ｗｏｒｄｓ　ｒｏｕｇｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｉｍｐｒｏｖｉｎｇ　ｍａｘｉｍｕｍ　ｍａｔｃｈ　ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１４，５０（２）：１２４－１２８．　

Ａｂｓｔｒａｃｔ：Ｃｈｉｎｅｓｅ　ｗｏｒｄｓ　ｒｏｕｇｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ａｎｄ　ａｍｂｉｇｕｉｔｙ　ｒｅｓｏｌｕｔｉｏｎ　ａｒｅ　ｔｗｏ　ｆｕｎｄａｍｅｎｔａｌ　ｐｒｏｃｅｓｓｅｓ　ｏｆ　Ｃｈｉｎｅｓｅ　ｗｏｒｄ　

ｓｅｇｍｅｎｔａｔｉｏｎ．Ｕｎｄｅｒ　ｔｈｅ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｏｆ　ｇｅｎｅｒａｌｉｚｅｄ　ｔｅｒｍ　ａｎｄ　ｉｎｄｕｃｅｄ　ｗｏｒｄ　ｓｅｔ，ａ　ｍｅｔｈｏｄ　ｕｓｅｄ　ｆｏｒ　Ｃｈｉｎｅｓｅ　ｗｏｒｄｓ　ｒｏｕｇｈ　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｆａｔｉｏｎｓ计算机工程与应用　２０１０，４６（３）　１２５　

汉语文本自动分词算法的研究　

何国斌，赵晶璐　

ＨＥ　Ｇｕｏ—ｂｉｎ，ＺＨＡＯ　Ｊｉｎｇ－ｌｕ　

西南大学汁算机与信息科学学院，重庆４００７　１　５　Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ’ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｅｅ，Ｓｏｕｔｈｗｅｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ　４００７　１　５，Ｃｈｉｎａ　

Ｅ－ｍａｉｌ：ｈｇｇ０７１２３＠１６３．ｃｏｍ　

ＨＥ　Ｇｕｏ—ｂｉｎ．ＺＨＡＯ　Ｊｉｎｇ—ｌｕ．Ｒｅｓｅａｒｃｈ　ｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　Ｃｈｉｎｅｓｅ　ｗｏｒｄ　ａｕｔｏｍａｔｉｃ　ｓｅｇｍｅｎｔａｔｉｏｎ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　

Ａｐｐｌｉｃａｔｉｏｎｓ。２０１０．４６（３）：１２５—１２７．　

Ａｂｓｔｒａｃｔ：Ｃｈｉｎｅｓｅ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｍｅｃｈａｎｉｓｍ　ｉｓ　ａｎａｌｙｚｅｄ．Ａｎ　ｉｍｐｒｏｖｅｄ　ｓｔｒｕｃｔｍ’ｅ　ｏｆ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｄｉｃｔｉｏｎａｒｙ　ｉｓ　ｐｒｅｓｅｎｔｅｄ，ａｎｄ　ｉｎ　

ｖｉｅｗ　ｏｆ　ｔｉｍ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｔｈｅ　ｍｅｃｈａｎｉｃａｌ　Ｃｈｉｎｅｓｅ　ｗｏｒｄ　ｓｅｇｍｅｎｔａｔｉｏｎ，ｃｏｍｂｉｎｅｄ　ｗｉｔｈ　ｐｔ’ｏｂａｂｉｌｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ，ａ　Ｃｈｉｎｅｓｅ　Ｗｏｒｄ　

Ａｕｔｏｍａｔｉｃ　Ｓｅｇｍｅｎｔａｔｉｏｎ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｄｉｓｃｕｓｓｅｄ．Ｈａｓｈｉｎｇ　ａｎｄ　ｂｉｎａＵ　ｓｅａｒｃｈ　ｉｓ　ｕｓｅｄ　ｔｏ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｍａｔｃｈ．Ｅｘｐｅｒｉｍｅｎｔ　

ｉｎｄｉｃａｔｅｓ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｇｒｅａｔｌｙ　ｉｍｐｒｍ’ｅ　ｔｈｅ　ｓｐｅｅｄ　ｏｆ　Ｃｈｉｎｅｓｅ　ｓｅｇｍｅｎｔａｔｉｏｎ　ａｎｄ　ｐｒｅｃｉｓｉｏｎ，ａｎｄ　ｓｔｒｅｎｇｔｈｅｎ　ｔｈｅ　ｐｒｏｃｅｓｓｉｎｇ　

中文分词相关技术简介

目前对汉语分词方法的研究主要有三个方面：基于规则的分词方法、基于

统计的分词方法和基于理解的分词方法。

基于规则的分词方法

基于规则的分词方法，这种方法又叫做机械分词方法,它是按照一定的策略

将待分析的汉字串与一个"充分大的"机器词典中的词条进行匹配,若在词典中找到某个字符串,则匹配成功(识别出一个词)。常用的方法：最小匹配算法

(Minimum Matching)，正向(逆向)最大匹配法(Maximum Matching)，逐字匹配

算法,神经网络法、联想一回溯法，基于N-最短路径分词算法,以及可以相互组

合，例如,可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配

法等。目前机械式分词占主流地位的是正向最大匹配法和逆向最大匹配法。

◆最小匹配算法

在所有的分词算法中，最早研究的是最小匹配算法(Minimum Matching)，该算法从待比较字符串左边开始比较，先取前两个字符组成的字段与词典中的

词进行比较，如果词典中有该词，则分出此词，继续从第三个字符开始取两个

字符组成的字段进行比较，如果没有匹配到，则取前3个字符串组成的字段进

行比较，依次类推，直到取的字符串的长度等于预先设定的阈值，如果还没有匹配成功，则从待处理字串的第二个字符开始比较，如此循环。

例如，"如果还没有匹配成功"，取出左边两个字组成的字段与词典进行比

较，分出"如果"；再从"还"开始，取"还没"，字典中没有此词，继续取"还没有

"，依次取到字段"还没有匹配"(假设阈值为5)，然后从"没"开始，取"没有"，如此循环直到字符串末尾为止。这种方法的优点是速度快，但是准确率却不是

很高，比如待处理字符串为"中华人民共和国"，此匹配算法分出的结果为：中

华、人民、共和国，因此该方法基本上已经不被采用。

◆最大匹配算法

基于字符串的最大匹配，这种方法现在仍比较常用。最大匹配(Maximum

Matching)分为正向和逆向两种最大匹配，正向匹配的基本思想是：假设词典中

算法分析　壤　。１与应用　问答系统的汉语分词算法研究　

韩如冰’叶得学　（１．兰州商学院陇桥学院信息管理系甘肃兰州７３０１０１；　２．兰州商学院陇桥学院现代教育技术中心甘肃兰州７３０１０１）　摘要：当前自动问答系统被广泛的应用，而中文分词的正确率和分词速率将直接影响到问答系统的最终执行效率，这使得中文分词技术的　研究逐渐深入。本文通过对分词算法的研究，结合目前常见的几种分词算法，对已有的ＦＭＭ算法（最大正向匹配算法撇了改进，得到了正向　递增匹配算法，并通过实验对该改选算法做出了简单评测。　关键词：问答系统分词ＦＭＭ改进　中图分类号：ＴＰ３９１　文献标识码：Ａ　文章编号：１００７—９４１６（２０１２）０５—０１１４－０２　

１、引言　自动问答系统（Ａｕｔｏｍａｔｉｃ　Ｑｕｅｓｔｉｏｎ　ａｎｄ　Ａｎｓｗｅｒｉｎｇ　Ｓｙｓｔｅｍ），　简称问答系统（ＱＡ），是信息检索系统的一种高级形式。它最大的特　点就是能准确、简洁的回答用户用自然语言提出的问题。问答系统　一般要解决三个核心技术：问题分析、信息检索和答案抽取，其中问　题分析，提取关键词是信息检索和答案抽取的基础，而这又都必须　以分词为基础。　２、中文分词技术　分词是指通过一定的方法，将构词句子的词进行切分，使之形　成一个能够清晰反映句子本意的词串。不同语言构成句子的方式不　同，实现分词的难易程度也就不同：如英语的词由没有具体含义的　字母构成，且句中的词与词之间都有空格，因此英语的句子就可以　简单的通过空格来实现分词；但汉语的词是由本身就有含义的字构　成，不同的字组合表意不同，且句中没有词的分隔，因而无法像英文　那样简单的进行分词，必须依靠相关算法才能实现。常用的中文分　词算法有：　２．１基于字符串匹配的分词方法　这种算法基于字符串匹配思想，按照系统中分词词典所含　最长词的字数从句中提取词项，并通过与分词词典中的词条进　行匹配来判定所取词项是否为词。若匹配成功，判定为词，按顺　序继续提取；若匹配失败，则对提取词项逐字删减，重新匹配，直　到成功。　我们将从句首开始提取，从词项尾进行逐字删减的方法称为正　向最大匹配分词法（Ｆｏｒｗａｒｄ　Ｍａｘｉｍｕｍ　Ｍａｔｃｈｉｎｇ　Ｍｅｔｈｏｄ，　ＦＭＭ）；将从句尾开始提取，从词项首进行逐字删减的方法称为逆　向最大匹配分词法（Ｂａｃｋｗｏａｒｄ　Ｍａｘｉｍｕｍ　Ｍａｔｃｈｉｎｇ　Ｍｅｔｈｏｄ，　ＢＭＭ）。但此类算法，切分出的词会出现歧义，而且对分词词典中没　有的词不能识别。　２．２基于理解的方法　这种算法基于人理解句子的思想，通过句法、语法分析，结合语　义分析来实现分词，并利用句法，语义信息来判断分词中产生的歧　义。但由于汉语言的复杂性，我们还无法让机器识别所有的语言环　境，因此，这种算法还处在实验阶段，真正实现还有一定的困难。　２．３基于统计的方法　一个字组合在句子中出现的次数越多，它为一个词的可能性就　越大。基于这个思想，可以通过字组合在句子中出现的频率来进行　分词，这种方法不再局限于分词词典，而且，对于分词词典中未包含　的词也能够识别。但在句中，一个词多次出现的情况毕竟有限，单纯　根据出现频率切分词，切分未必准确。　本文通过对这几种算法的综合研究，对ＦＭＭ算法进行了改进，　得到正向递增匹配算法，对目前分词技术中常用的这些算法在分词　处理时存在的缺陷一定程度上进行了优化，提高了分词效率。　３、改进的Ｉ＝ＭＭ算法一正向递增匹配算法　３．１基本思想　通过分析，我们发现，中文中最常见的词为两字词，那么，首次　提取两字词项匹配的成功率一定高于首次提取多字词项的匹配成　功率，从而可以提高分词的效率。因此，我们在改进的ＦＭＭ算法中　规定，首次从句子句首提取两字词项，与分词词典中的词进行匹配，　如果有匹配词条，判定这两字词项为一个词，切分出来，一次分词结　束，再按顺序依次提取两字词项进行匹配，直到分词结束；如果分词　词典中没有匹配词，则在提取的两字词项尾按句子顺序自左向右逐　一加字，反复匹配，直至匹配成功；如果词项字数加至超过分词词典　最大词项字数时，则将该词项的第一个字切分为单字词，再将其后　的两个字提取成新词项，进行新一轮的匹配。　３．２歧义词处理　汉语分词中产生的歧义最常见的为交集型切分歧义。交集型切　分歧义是指对词项Ｃ。Ｃ，Ｃ　，Ｃ　Ｃ，和Ｃ，Ｃ　都可为词所造成的歧义。由　于汉语在组句时多采用修饰词＋中心词的偏正结构，因此，我们规　定，对于交集型切分歧义字段Ｃ　Ｃ，Ｃ　，我们切分Ｃ，Ｃ　为构成句子的　词，而Ｃ　则与其左边的字组合成词项进行匹配。具体的歧义校正策　略如下：　设Ｃ，Ｃ　…Ｃ　是连续交集型切分歧义字段：　（１）指针移向ｃ　，调用分词算法对以Ｃ　为首字的词进行查找。　（２）若句子中Ｃ　可以和后面的字构成词（设Ｃ　…Ｃ　为构成的最　长词），则对Ｃ一进行标记。　（３）移向Ｃ　，继续对Ｃ　进行处理，方法类似于（２），直到找到没有　歧义的词为止。　（４）不妨设Ｃ　与其后的字不成词，此时让Ｃ　优先与右边的子段　组成词，即切分Ｃ　…Ｃ　为一词。　（５）对Ｃ　之前的部分做最大正向匹配，歧义处理结束。　３．３虚词判定　在汉语中如“的”、“地”、“了”等字，既可以作为虚词，也可以与　其他字组合构成实词，所以如果对这些字直接采用主导策略进行分　词，往往会造成切分错误。因此，需要对这类字做专门判断。