第卷第期燕山大学学报
年月
引言
词是最小的能够独立活动的有意义的语言成
分，中文词与词之间没有明显的分割标志。中文信
息处理的诸多重要领域如信息检索和信息摘录、文
本分类和自动文摘、汉字的侦错与纠错、词语的计
量分析、自然语言理解等都要求在词这一层面上进
行，因此，中文自动分词是中文信息处理的基础
与关键。
中文分词的基本算法主要分为大类：）基
于词典的分词方法，这是一种机械分词方法，该
方法依据一个词典和一个基本的切分原则，即“长
词优先”原则来进行分词；）基于统计的分词方
法，该方法首先切分出与词典匹配的所有可能
的词，这种切分方法称为“全切分”，运用统计语
言模型和决策算法决定最优的切分结果；）基于
理解的分词方法，该方法又称为基于人工智能
的分词方法，其基本思想就是在分词的同时进行句
法、语义分析，利用句法信息和语义信息来处理歧
义现象。
基于统计的分词方法，前期的工作量非常大，
对常用词的识别精度差；基于理解的分词方法，理
论上是最理想的分词方法，但是由于中文自然语言
复杂灵活，知识表示困难，该方法还处于起步阶
段；而基于词典的分词方法具有结构简单、易于实
现、开发周期短等优点，因此，目前中文分词方法
采用最多的是基于词典的分词方法。
文献介绍了种典型的词典结构：整词
二分，索引树，逐字二分；陈桂林等在文献
中提出了一种高效的电子词表的数据结构；文
献中提出了基于双字哈希机制的词典结构等
等。不论是哪种基于词典的分词方法，词典的查询
速度是决定分词算法效率的直接因素，对系统效率
有重要的影响，可见建立高效快速的分词词典机制
势在必行。因此，本文根据汉语成词特点，在结
合索引树优点的基础上提出一种新的词典机
制，采用分治策略进行分词。采用该策略的分词算
法在保持现有分词精度的前提下，减少比较次数，
具有更好的分词效率。最后在理论和实验两方面给
予了分析和证明，进一步诠释了该算法的准确性和
有效性。
词典设计
汉语成词特点
汉语的词是一个开放的集合，其数量可以认为
文章编号：1007-791X(2009)05-0444-06
一种应用分治策略的中文分词方法
赵春红，高希龙，王柠，赵威，刘国华
（燕山大学信息科学与工程学院，河北秦皇岛；河北建材职业技术学院，河北秦皇岛；
齐齐哈尔大学计算机系，黑龙江齐齐哈尔）
摘要：自动分词是中文信息处理的关键步骤。由于具有结构简单、易于实现和开发周期短等优点，基于词典
的分词方法被广泛应用。结合中文多字词数量少，使用频度低的特点，设计实现了一种新的词典机制，在此基
础上，把分治策略引入到分词中，提出了一种新的分词算法，幷对该算法进行了理论分析和实验验证。
关键词：中文分词；词典机制；分治策略
中图分类号：TP391.1文献标识码：A
收稿日期：基金项目：国家自然科学基金资助项目（）；国家“十一五”科技支撑计划资助项目（）；
河北省自然科学基金资助项目（）
作者简介：赵春红（），女，河北沧州人，硕士研究生，主要研究方向为数据库、信息安全；通讯作者：刘国华（），
男，黑龙江齐齐哈尔人，教授，博士生导师，主要研究方向为数据库安全、模式匹配、系统仿真，：。
第期赵春红等一种应用分治策略的中文分词方法
是接近无穷的，并且随着时代的发展，很多新词汇
不断涌现，致使任何一部词典都很难囊括所有的
词。根据文献的统计结果（如表所示），发
现：二字词最多，且出现频率最高；三字和四字以
上的的词相对较少，且出现频率较低。
表数词频统计表
词条字数
词条数
出现频率
字串成词状态标记
在分词的过程中，通过观察词中字串的成词状
态，可以对字串进行如下种方式的标记：）是
词，独立成词且不能构成更长词的前缀，用标
记；）是词，并能构成更长词的前缀，用标记；
）不是词，只能构成词的前缀，用标记。如果
仅用是否为词的二态标记，则无法一次区分一个词
是单独成词还是构成词的前缀。首字只需二态标
记，单独成词用标记，构成更长词的前缀用标
记。
词典结构
词典中的词由首字哈希表、二字表、三字表及
剩余字表张表分别存储，剩余字表只存储词第三
字以后的剩余字。词典机制如图所示。
图词典机制
）首字哈希表。词首字可以通过一次哈希运
算得到该字在首字哈希表中的位置，其计算公式如
下：
，
式中，表示该汉字在首字哈希表中的偏移量；
、分别为汉字内码的高字节和低字节。首字哈
希表的一个单元包括项内容：
①（个字节）：记录首字；
②（个字节）：首字成词状态与词
第字在二字表中第次出现的位置的乘积；
③（个字节）：以该首字为前缀的词中
第字不相同的词条数目。
）二字表。二字表的一个单元包括项内容：
①（个字节）：记录词的第字；
②（个字节）：前字成词状态与词
第字在三字表中第次出现的位置的乘积；
③（个字节）：以对应前两字为前缀的
词中第字不相同的词条数目。
）三字表。三字表的一个单元包括项内容：
①（个字节）：记录词的第字；
②（个字节）：前字成词状态与
剩余字在剩余字表中第次出现的位置的乘积；
③（个字节）：以对应前字为前缀的
词条数目。
）剩余字表。剩余字表的一个单元包括项
内容：
①（个字节）：记录词第字以后
的剩余字（：剩余字的字数）；
②（个字节）：对应前个字相同
的词第次在剩余字表中出现的位置；
③（个字节）：对应前个字相同的词
条数目；
④（个字节）：是否还有以该剩余字为前
缀的剩余字。
分词算法
分治策略
分治顾名思义就是“分而治之”的意思，它是
一种在实际中应用最多的有效算法之一，其基本思
想是将问题划分成个规模较小而结构与原问题相
首字哈希表啊阿中鼾
哈班国足睡声
大风话科人银
陆民解放军民寿行学家民银行寿保险剩余字表
三字表
二字表
燕山大学学报
似的子问题：递归地解决这些子问题，子问题
往往很简单，可以直接求解，然后再合并其结果，
就得到原问题的解。
分治法求解一般分为个步骤：）分解。
将原问题分解成一系列子问题；）解决。递归地
求解各子问题。若子问题足够小，则直接求解；）
合并。将各子问题的结果合并成原问题的解。
用分治策略求解的问题很多，如二分检索、归
并分类等。分词成功的标志是在词典中将词查找出
来，将查找完整词的问题转化为按顺序查找该词中
字的问题。由于词典中的词除第个字外其他字都
按内码升序排列，待切词的第个字及其后的字的
查找都可以转换为二分检索，再将查找各个字的结
果合并起来，得到查找该词是否成功的结果。
分词算法
将词中字串的成词状态与词中下一字在对应
字表中的位置结合起来，既可以通过该值快速找到
下一字的位置，也可以判断首字到该字是否是词，
简化了分词算法。例如待分字串的前两字在词典中
已经查到，但在三字表中没有找到第字，这时判
断第字的值，若值为正，前
两字是词，将词切分出来，若值为负，前
两字不是词，直接把待分字串的首字作为单字词切
分出来，而不需要其他的重复操作，从而可以提高
分词效率。分词算法的具体描述如下：
输入：汉字串
输出：有分割标识的词串′
）指针指向待分汉字串首字，；获得汉字
串的汉字数；
）（）如果，将切分出来添加到′，在后加分割
标识“”，转）；否则指针处取，利用式计算的哈希
值，在首字哈希表中的对应位置找到，如果的为
，单独成词不为任何词前缀，则将从中切分出来添加到
′，在′后加分割标识“”，，转）；否则取
出和，转）；
）在二字表中的和范围之间二
分查找，找到且为，单独成词不为任何词
前缀，则将从中切分出来添加到′，在′后加分割标识
“”，，转）；否则取出和，
转）；没有找到，则将从中切分出来添加到′，在′后
加分割标识“”，，转）；
）在三字表中的（是的绝对值）和
范围之间二分查找，找到且
为，单独成词不为任何词前缀，则将从中切分
出来添加到′，在′后加分割标识“”，，
转）；否则取出和，转）；没有找到，若
的，是词，则将从中切分出来添加到′，
在′后加分割标识“”，，转）；否则将
从中切分出来添加到′，在′后加分割标识“”，
，转）；
）在剩余字表中的（是的绝对
值）和范围之间查找剩余字，剩余字匹
配成功，则将（为匹配成功的剩余字的汉字数）从
中切分出来添加到′，在′后加分割标识“”，
，转）；剩余字匹配不成功，若的
，是词，则将从中切分出来添加到′，在′
后加分割标识“”，，转）；否则若的
，是词，则将从中切分出来添加到′，在
′后加分割标识“”，，转）；否则将从
中切分出来添加到′，在′后加分割标识“”，
，转）；
）结束分词程序，输出。
算法流程举例
待切分的汉字串是“中国人民解放军和平解放
北平”，取得首字“中”的机内码，根据式计
算其在首字哈希表中的位置，得到“中”字的索引
结构，不等于，在二字表中的
和之间二分查找“国”，
找到“国”且“国”的不等于，在三字
表中的和之间二分
查找“人”，找到“人”且“人”的不
等于，在剩余词表中的和
二分查找剩余字的第个字是“民”的剩
余字，取出对应单元中的和，这
样找到以“中国人民”为前缀的词在剩余字表中的
首位置和以“中国人民”为前缀的词条数目；剩余
字“民”的前缀标志为，取出下一个剩余字“民
解放军”与汉字串中对应长度的“民解放军”比
较，匹配成功且没有以“民解放军”为前缀的剩余
字，返回剩余字长，则切出词长为的“中国人
民解放军”，其它部分进行类似的切分。
词典性能分析
理想情况
）词典空间。理想情况，首字相同的词中，
凡三字词以二字词为前缀，四字词以三字词为前
缀，多字词四字词为前缀，根据表中的统计数
据，词典空间（）计算如下：
首字首字索引表：
第期赵春红等一种应用分治策略的中文分词方法
；
二字表：
；
三字表：
；
剩余字表：
；
整个词典约占内存：
。
由于三字词的第二字，多字词的的第二、三字
可能单独出现，字典实际占用的空间要比理论计算
值略高。
）时间复杂度。一般认为，时间复杂度，是
衡量分词算法优劣的一个非常重要的标准。在其他
条件相同的情况下，如果时间复杂度越低，则说明
这种分词算法的性能越好，分词速度越快。计算分
词方法的复杂度时，一般选择匹配比较次数作为衡
量的基本单位。分词方法的时间复杂度，确切指的
乃是这种分词方法平均每切分出一个词所需要的
比较次数。
根据表中的统计数据，词条首字个数近似认
为，切分各长度词条的平均比较次数如表
所示。
表想情况下各长度词条平均比较次数
词条字数词条数该词条下的平均词条数平均比较次数
根据文献的方法，理想情况下每切分一
词条所需要的平均比较次数：
。
最坏情况
）词典空间。最坏情况，首字相同的词均不
为词长更长的词的前缀，词典空间（）计算
如下：
首字首字索引表：
；
二字表：
；
三字表：
；
剩余字表：
；
整个词典约占内存：
。
由于三字词的第二字，多字词的的第二、三字
大部分可能重复出现，字典实际占用的空间要比理
论计算值少很多。
）时间复杂度。表中词条数累计为
条，每个首字下二字及二字以上的平均词条数为
条，以下计算相同。最
坏情况下，切分各长度词条的平均比较次数如表
所示。
最坏情况下每切分一词条所需要的平均比较
次数：
燕山大学学报
。
表最坏情况下各长度词条评均比较次数
词条字数词条数该词条下的平均词条数平均比较次数
性能比较
吴远胜提出了单扫描分词方法，该方法的时
间复杂度为。陈桂林等提出了一种改进的快速
分词算法，该算法采用了一种新的中文电子词表
数据结构，支持首字和标准的二分查找，在
快速查找两字词的基础上，利用近邻匹配方法来查
找多字词，时间复杂度为。李振星等提出了全
二分最大匹配快速分词算法，该算法采用首字
和完全二分查找，时间复杂度为。张海
营等提出一种新的分词词典，通过为分词词典建
立首字表和词索引表两级索引，使得该分词
词典支持全二分最大匹配分词算法，但在计算时间
复杂度时，错将计算成
，计算出来的错误时间复杂度为
，按文中统计数据计算的正确值应为。采
用全二分最大匹配算法时，词典中的每个词在词索
引表和词典正文中要各存储一遍，词索引表的数据
结构复杂，使得词典空间非常大，维护困难。
本文算法最坏情况的时间复杂度为优于
上述文献中的值，通过对词中字串进行三态标记，
使得本文设计的词典机制结构简单、维护方便、空
间复杂度小，分词效率高。
准确性分析及实验
准确性分析
词典中的词可以分为两类：一类词包括长度小
于等于的词和普通的多字词；二类词指长度大于
且前个字与该词前个字相同的词条数大
于等于的词。由于预先不设定最大词长，所以正
确切分二类词是一个难点。
本文算法不仅可以正确切分所有的一类词，而
且通过“长词优先”原则和剩余字的标识能
快速准确地切分二类词。如“中国人民解放军”就
属于二类词，它的前缀“中国人民”也是一个词。
节的例子中，当剩余字表中的“民”与待分汉
字串中的“民”完全匹配时，算法没有立即把“中
国人民”作为一个词切分出来，而是将下一个剩余
字“民解放军”与待分字串中的“民解放军”比
较，这是因为“民”字的为，表示还有以
“民”为前缀的剩余字。比较结果完全匹配，且“民
解放军”的为，没有以该剩余字为前缀的
剩余字了，此时才将“中国人民解放军”作为一个
词切分出来。该算法不会将长词切断，充分体现了
“长词优先”的原则。
实验结果
评价中文分词算法的性能参数主要有个：准
确率、分全率、召回率。
准确率算法所分得的正确的词的个数分得的所有词的个数；
分全率算法所分得的词的个数原文应有的词的个数；
召回率算法最初分得的词的个数全部正确切分时词的个数。
采用维普全文数据库中的六类文本作为测试
集，实验结果如表所示。
表分词效果
数据规模准确率分全率召回率
计算机
体育
经济
政治
艺术
文学
结束语
本文分析了汉语构词特点，根据汉语二字词、
三字词、四字词数量多出现频率高的特点，设计了
第期赵春红等一种应用分治策略的中文分词方法
一种新的词典机制，提出了新的分词算法，理论分
析证明了该词典机制比其它词典机制具有更好的
分词效率，并通过实验验证了该分词算法的准确性
与有效性。
参考文献
黄昌宁中文信息处理中的分词问题语言文字应用
孙茂松左正平黄昌宁汉语自动分词词典机制的实验研究
中文信息学报
吴胜远一种汉语分词方法计算机研究与发展
陈桂林王永成韩客松等一种改进的快速分词算法
计算机研究与发展
李振星徐泽平唐卫清等全二分最大匹配快速分词算法
计算机工程与应用
李庆虎陈玉健孙家广一种中文分词词典新机制——双字
哈希机制中文信息学报
张海营全二分快速自动分词算法构建现代图书情报技
术
王晓龙关毅计算机自然语言处理北京清华大学出
版社
孙茂松黄昌宁邹嘉彦等利用汉字二元语法关系解决汉语
自动分词中的交集型歧义计算机研究与发展
李家福张亚非一种基于概率模型的分词系统系统仿
真学报
费洪晓康松林朱小娟谢文彪基于词频统计的中文分词
的研究计算机工程与应用
翟凤文赫枫龄左万利字典与统计相结合的中文分词方法
小型微型计算机系统
徐辉何克抗孙波书面汉语自动分词专家系统的实现
中文信息学报
姚天顺张桂平吴映明基于规则的汉语自动分词系统
中文信息学报
揭春雨刘源梁南元论汉语自动分词方法中文信息
学报
算法导论高等教育出版社
AChinesesegmentionmethodbyapplyingdivide-and-conquerstrategy
Abstrac:
Keywords:
|
|
