第28卷第3期 2011年3月 计算机应用与软件

ComputerApplicationsandSoftwareVol 28No.3

Mar.2011

一种改进的中文分词正向最大匹配算法

王瑞雷 栾 静 潘晓花 卢修配

(新疆师范大学计算机科学技术学院 新疆乌鲁木齐830054)

摘 要 正向最大匹配分词FMM(ForwardMaximumMatching)算法存在设定的最大词长初始值固定不变的问题,带来长词丢失

或匹配次数较多的弊端。针对此问题提出了根据中文分词词典中的词条长度动态确定截取待处理文本长度的思想,改进了FMM算法。与此相配合,设计了一种词典结构,使之能够有效地支持改进的算法。改进的算法与一般正向最大匹配算法相比大大减少了匹配次数,分析表明中文分词的速度和效率有了很大提高。关键词 中文分词 分词词典 正向最大匹配算法

ANIMPROVEDFORWARDMAXIMUMMATCHINGALGORITHMFOR

CHINESEWORDSEGMENTATION

WangRuilei LuanJing PanXiaohua LuXiupei

(CollegeofComputerScienceandTechnology,XinjiangNormalUniversity,Urumqi830054,Xinjiang,China)

Abstract Thereisaprobleminforwardmaximummatching(FMM)algorithmthattheinitialvalueofthemaximumword lengthisimovablem,thismightleadtothelongerwordscannotbesegmentedcorrectlyandbematchedrepeatedly.Aimingatthisproblem,thispaper

putsforwardanideaforimprovingFMMalgorithmthatistoassignthemaximumtext lengthtobetreateddynamicallybasedontheword lengthinChinesewordsegmentationwordbank.Tofitthis,inthepaperwedesignawordbankstructuretoenabletheeffectivesupportontheimprovementofFMM.ComparedwithnormalFMM,theimprovedFMMsharplyreducesmatchingtimes.AnalysisinthispapershowsthatthespeedandefficiencyofChineseWordsegmentationalgorithmhavebeenobviouslyimproved.Keywords Chinesewordsegmentation Wordbank Forwardmaximummatchingalgorithm

示(只列出了2-7字词的统计,因8-13字的词所占比例较小

而未列出),词典中总词数是111950条,其中大部分词是二字词、三字词和四字词,而五字、六字、七字词较少,八-十三字词更少。针对这种情况,本文对现有的正向最大匹配算法进行研究和改进,提出了动态确定最大词长的匹配算法。本算法与改进前算法相比节省了时间,提高了效率。

表1 词条字数统计表

词条字数词条个数

273491

318706

417217

51572

6545

7335

0 引 言

中文自动分词是中文信息处理中最为基础、最为重要的问题,是汉语文本自动标注、搜索引擎、机器翻译等工作中的关键步骤。文献[1]指出 信息处理都要求在词这一平面上进行 ,而基于词典的分词算法因效率高而受到人们的密切关注。

迄今为止,有很多关于正向最大匹配算法的研究和改进。例如:文献[2]提出了一种改进的增字最大匹配算法,该算法根据从被处理材料中取长度是1、2、!!、i(i是词典中最长词的长度)的字串与词典匹配来寻找长词,是由短到长、逐字增加进行的。通过检测一个词的后缀是否是另一个词的前缀找交集型歧义。文献[3]提出先寻找长度为i(词典中最长词的长度)的词,再寻找长度为i-1的词,!!,直到整个句子被切分完毕。文献[4]提出根据一个词是否是其它词的前缀来寻找长词并切分和判断是否为组合歧义。

正向最大匹配算法主要弊端是初始词长MaxLen的值固定不变,即分词过程中切分出一个词之前,总是先对MaxLen赋一个固定的初始值。最大词长初始值不变容易导致两个问题:(1)词长过短,长词就会被切错。假设最大词长设为6,而 中华人民共和国 这个词的长度是7,不能切分出这个词。(2)词长过长,效率就比较低,在切分时会浪费一部分时间用于查词典而,如表1所

1 正向最大匹配算法FMM

FMM算法的基本思想是:假设分词词典中最长词条所含的汉字个数是MaxLen,每次从待切分字串S1的开始处截取一个长度为MaxLen的字串W,令W同词典中的词条依次相匹配,如果某个词条与其完全匹配则把W作为一个词从S1中切分出去,然后再从S1的开始处截取另一个长度为MaxLen的字串,重复与词典中词条相匹配的过程,直到待切分字符串为空。如果在词典中找不到与W匹配的词条,就从W的尾部减去一个字,

收稿日期:2010-04-01。新疆师范大学研究生科技创新活动基金(),主研领域,