基于词典的中文分词算法研究.pdf

总第233期计算机与数字工程Vo1．37No．3
2009年第3期Computer&DigitalEngineering68

基于词典的中文分词算法研究

周程远朱敏杨云
(华东师范大学计算中心上海200062)

摘要中文分词是计算机自动处理文本的基础。通过比较常用的机械分词算法的优缺点，提出了分层逐字二分算
法，综合了TRIE树和逐字二分分词的特点，以求通过较小的开销来实现较快的匹配速度。实验结果表明，该算法在综合性
能上有显著提高。
关键词中文分词计算机应用中文信息处理
中图分类号TP391．1

ResearchonChineseWordSegmentation
AlgorithmBasedontheDictionary

ZhouChengyuanZhuMinYangYun

(Dept．ofComputerCenter，EastChinaNormalUniversity，Shanghai200062)

AbstractChinesewordsegmentationisthebaseforChineseinformationprocessing．Bycomparisoncommonlythe

advantagesanddisadvantagesofthemachinerywordsegmentationalgorithm，thenaliedverbatimbinaryalgorithmhas

beenpresented，whichintegratedTRIEtreesandverbatimbinarysearch'scharacteristics，trytotakethesmalleroverhead

toachievefastermatchspeed．Theresultsshowthatthealgorithminthecomprehensiveperformancehasmadesignificant

increase．

KeywordsChinesewordsegmentation，computerapplication，Chineseinformationprocessing

ClassNumberTP39】．1

典的分词方法和基于频度统计的分词方法。具体应
l引言
用时的不同算法则是二者不同程度的组合。基于词
由于汉语的书写习惯，汉语句子中词与词之间典的分词方法是以汉语词典为基础对中文语句通过
的标志是隐含的，英文的单词与单词之间有空格，匹配进行切分，这种方法主要包括三种基本算法：正
所以不存在分词问题。而中文的每一句中词与词向最大匹配法、逆向最大匹配法、全切分法。
之间是没有空格的，因而必须采用某种技术将其分很多分词系统较注重分词的准确率，而忽视了
开。中文文本分词算法从2O世纪8O年代以来就速度。在实时性要求比较高的场合下要求分析算

一直是一个研究热点，由于中文语言的复杂性使之法对输入句子做出迅速的反应，所以分词算法的效

一直处于发展阶段。中文分词是中文信息处理的率在实时性应用系统中的地位非常重要。
基础与关键，从实际应用上来说，中文分词又是实本文列举了一些比较常用的基于词典的机械
现计算机人工智能、智能搜索、人机对话、中文翻译分词算法，并且对几种中文分词处理的电子字典结
以及web信息处理等核心应用的关键技术。构和相应的查找算法作了性能比较。最后提出了

自动分词的基本算法主要分为两大类：基于词一种改进算法一分层逐字二分算法来提高分词系

收稿日期：2008年11月2日，修回日期：2008年11月19日
作者简介：周程远，男，硕士研究生，研究方向：现代软件技术。朱敏，女，高级工程师，研究方向：现代软件技术、模式
识别、图像处理。杨云，女，工程师，研究方向：WEB应用技术。
第37卷(2009)第3期计算机与数字工程69

统的效率。引表很容易确定指定词在词典正文中的可能位置
范围，进而在词典正文中通过整词二分进行定位。
2基于词典的机械分词的方法
2．1正向最大匹配分词
正向最大匹配分词是基于词典的分词系统。
所谓最大匹配，就是要求每一句的分词结果中的词
汇总量最少。
正向最大匹配分词又分为增字和减字匹配法。
增字匹配法需要一种特殊的词典结构支持，能够达
到较高的分词效率。
图2基于整词二分的分词词典结构
减字法的流程为：首先读人一句句子，取出标
3．3基于TRIE索引树的分词词典机制【2]
点符号，这样句子就被分成相应的若干段，然后对
TRIE索引树是一种以树的多重链表形式表
每一段进行词典的匹配，如果没有匹配成功就从段
示的键树。基于TRIE索引树的分词词典机制由
末尾减去一个字，再进行匹配，重复上述过程，直到
首字散列表和TRIE索引树结点两部分组成。
匹配成功某一个