0 引言
　　
　　中文信息处理的特有问题就是如何将汉语的字串分割为合理的词语序列。中文分词是句法分析等深层中文信息处理的基础,也是机器翻译、信息检索和信息抽取等智能化信息处理的关键所在[1,2]。而中文分词的主要困难在于切分歧义消解和未登录词语的识别,这也是世界上最令计算机感到棘手的语言现象之一[3~5]。中文分词方法中机械分词法主要包括正向最大匹配法(maximum matching method ,MM)、逆向最大匹配法(reverse direction maximum matching method ,RMM)和最少切分法。目前机械式分词占主流地位的是正向最大匹配法和逆向最大匹配法,这两种方法是利用一个分词词表进行模式匹配来切分,不依赖词法、句法和语义知识,切分速度快、简洁、易于实现,在各种中文信息处理上得到了广泛的应用;缺点是对于歧义字段无法有效地识别和切分。统计结果表明,单纯使用正向最大匹配的错误率为1/169;单纯使用逆向最大匹配的错误率为1/245[6],但这种精度还不能满足智能信息处理以及人机交互的要求,对词义消歧(word sense disambiguation,WSD)是计算语言学和自然语言处理领域一个重要的研究课题,也是近些年来该领域的热点研究问题之一[7]。本文在正向最大匹配法的基础上,提出二次回溯中文分词方法(简称二次回溯法),该方法对歧义字段能有效地识别和切分,大大提高分词的召回率和查准率。
　　
　　1 相关概念
　　
　　歧义字段分为交集型歧义字段和多义型歧义字段两类,为行文方便,结合文献[3,5,8]给出如下定义:
　　定义1 令T1为词库,T2为字库,
　　W=a1NA1ADaib1NA1ADbkc1NA1ADcj
　　W1=a1NA1ADaib1NA1ADbk
　　W2=b1NA1ADbkc1NA1ADcj
　　Wa=a1NA1ADai,Wc=c1NA1ADcj
　　其中:W,W1,W2,Wa,Wc∈T1以及ai′,bk′,cj′∈T2(i′∈[1,i],j′∈[1,j],k′∈[1,k]),则称字串W为由词W1和词W2形成的交集型歧义字段,n=i+j+k为歧义字段的长度, 字串b1NA1ADbk为交段,k为交段的长度,歧义字段中交段的个数称为链长。
　　例如,为人民工作。其中“为人”“人民”“民工”“工作”均是词,交段长度均为1,链长为3。
　　定义2 令T1为词库,
　　W=a1NA1ADaib1NA1ADbk
　　W1=a1NA1ADai,W2=b1NA1ADbk
　　其中:W,W1,W2∈T1以及ai′,bk′∈T2(i′∈[1,i],k′∈[1,k]),而且存在语境〈α,β〉和〈λ,μ〉,使得αa1NA1ADaib1NA1ADbkβ中a1NA1ADaib1NA1ADbk为词W,λa1NA1ADaib1NA1ADbkμ中a1NA1ADaib1NA1ADbk为词序列W1W2,则称W为多义型歧义字段。
　　例如:a)这个门把手坏了;b)请把手拿开。
　　例1,“把手”为多义型歧义字段,a)中“把手”不应该切分,b)中“把手”应该切分为“把”和“手”两个独立的词。
　　交集型歧义字段占全部歧义切分字段的85%以上[9],所以要提高中文分词质量最关键的是提高对交集型歧义字段的识别率和切分准确性。
　　定义3 文本中相邻两个标点符号(含段首不可见符号)之间字串序列称为元句子。
　　
　　2 二次回溯法设计
　　
　　2.1 二次回溯法总体过程
　　二次回溯中文分词算法,主要由如下几步组成:
　　a)将文本转换成细粒度文本,即元句子;
　　b)正向最大匹配;
　　c)正向次大匹配(第一次回溯匹配);
　　d)尾单字与后继单字结合成二字检测;
　　 　　e)循环步骤b)~d)至元句子切分结束;
　　f)对元句子切分后的字串进行碎片检查(第二次回溯匹配);
　　g)继续下一个元句子进行切分,循环步骤b)~f)直至文本切分结束。
　　2.2 第一次回溯切分算法描述
　　首先将待切文本中所有诸如:“,”“;”“!”等标点符号用标签隔开,如用“/,/”“/;/”“/!/”分别替换“,”“;”“!”。这样文本就被“/”分隔成一个个标点符号或者无标点符号的字串,这个字串称为元句子(定义3)。“/”符号之间的标点符号无须切分;针对长度小于等于2的元句子独立成词,无须切分。对文本的切分只要依次完成对文本中长度大于2的元句子的切分即可,以下过程就针对单一的元句子来进行切分。
　　若分词词表中最长的词由n个字组成,在待切元句子str中按自左向右截取长度为n的字串str1,使之与词表中的词条依次匹配(如果元句子Str长度小于等于n,则取整个元句子来匹配):
　　1)如果词表中存在str1,再取str1的前n-1个字串str2=str1.Substring(0,n-1)与词表中的词条依次匹配:
　　a)如果词表中不存在str2,则将str1从待切文本中切分出去,str=str.substring(n),继续在剩下待切元句子中自左向右截取长度为n的字串与词表中的词条依次匹配。
　　b)如果词表中存在str2,则取Str1最右端的字与待切元句子中的第n+1个字组合str3= str.substring(n-1,2), Str3与词表中的词条依次匹配:
　　(a)如果不存在str3这样的词,则将str1从待切元句子中切分出去,str=str.Substring(n),继续在剩下待切元句子中自左向右截取长度为n的字串与词表中的词条依次匹配。
　　(b)如果存在str3这样的词,则将str2从待切元句子中切分出去,str=str.Substring(n-1),继续在剩下待切元句子中自左向右截取长度为n的字串与词表中的词条依次匹配。
　　2)如果词表中不存在str1,就从该字串最右端部删去一个字,用n- 2 的字串去词表中匹配,直至匹配成功。
　　上述一次回溯分词算法的流程如图1所示。
　　在《人民网》选择若干篇文章用MM法和一次回溯法切分,选择其中不同部分切分,如表1所示。
　　表1 两种切分效果对比
　　MM法一次回溯法
　　有关/责任人/员有关/责任/人员
　　一万下/游群众一万/下游/群众
　　将他/们/救出去将/他们/救出去
　　最紧/迫/的/任务最/紧迫/的/任务
　　要得/到/批准要/得到/批准
　　情况/会/更糟/糕情况/会/更/糟糕
　　2.3 第二次回溯切分算法描述
　　对于链长大于1的字串,一次回溯切分后可能会产生以单字组成的切分碎片,如“研究生产生活”被切分成“/研究/生/产/生活/”,“生产”是一个词,被切分成两个单字。
　　再进行一次回溯碎片检查,算法描述如下:
　　在对每个元句子切分过程中设置一个整型变量,不妨设为tag,初始值为0,在对该句子切分过程中一旦对str2切分,则tag增1,在二次回溯法步骤e)切分元句子结束后检测tag。如果tag值小于2,则对该句子切分结束;否则用如下二次回溯算法来检查元句子切分后的含有切分符号“/”的字串:
　　a)在元句子中进行逆向截取,截取长度为5,如果该字符串不满足“/单字1/单字2/”结构,则按照步长为1向左平移进行截取,截取字符串长度仍然是5,再进行检测,直到检测符合上述结构或元句子被截取完为止。
　　b)如果该字符串满足“/单字1/单字2/”结构,则检测单字1和单字2组合是否是词。如果是词则合并该切分,即在元句子中用“/单字1单字2/”替换“/单字1/单字2/”;如果不是词,则继续向左平移截取,直至元句子被截取完。
　　例:“/研究/生/产/生活/” 中“/生/产/”满足“/单字1/单字2/”结构,且“生产”是词,则将这两字合并,即用“/生产/”替换“/生/产/”。
　　
　　3 二次回溯中文分词算法分析
　　
　　3.1 与正向最大匹配法(MM法)异同
　　1)相同点 都是属于机械分词,都是基于对词典中词条的匹配结果来切分。
　　2)不同点 如表2所示。
　　表2 两种算法对比
　　比较项二次回溯法MM法
　　标点预分割分割不分割
　　切分方向整体正向+局部回溯正向
　　词条优先规则长词+次长词协调切分长词优先切分
　　其他句尾匹配+碎片检查无
　　3.2 算法设计分析
　　MM法的长词优先规则大部分情况下能很好地切分,但对于包含有歧义字段的文本往往作出了错误的切分,如“原北京市长王岐山”, 其中有词“原”“北京”“北京市”“市长”“王岐山”(属于未登录词的名字提取,本文不作讨论)和“北京市长”构成交集型歧义字段,交集词为“市”,交段长为1。用MM法切分结果是:“原/北京市/长/王岐山/”,这是错误的切分,因此仅仅依靠长词优先规则无法对歧义字段很好也切分。
　　二次回溯中文分词方法则利用长词、次长词,二字词句尾匹配谐调切分,主要从如下方面考虑:
　　a)文献[10]中对大量真实语料进行统计,共统计了132 411词条,词条的长度分布以及出现频率如表3所示。
　　由表3可知:二字词词条总数的65891/132411=49.76%,占所有词条数接近一半之多; 单字词和二字词出现频率之和为96.4%。
　　MM法采用的长词优先规则并没有考虑到词长分布规律和词频统计情况,从而导致MM法的分词精度不够。而二次回溯中文分词方法则综合考虑最大词长、次大词长、二字词句尾匹配协调切分,更符合真实文本中词条的分布情况。
　　b)文献[11]中以含有约77000词条的词库作为切分词序对510万从网上随机下载的新闻语料进行加工,对交集型歧义字段在大量真实语料中的切分结果进行统计,如表4所示。
　　由表4可知:链长为1的词也只占歧义字段总数的53.05%,MM法对链长为1的歧义字段切分较好,超过1的一般都切分失败,而二次回溯中文分词方法对于多链长的歧义字段都能较好地识别和切分。
　　3.3 训练评测
　　在中新网、人民网等随机抽取27篇28541字的真实语料,用二次回溯法和MM法对其中所有交集型歧义字段进行封闭式测试,结果如表5所示。
　　表5 训练结果
　　两种方法对比词数
　　MM法失败,二次回溯法成功204
　　MM法成功,二次回溯法失败25
　　均切分错误33
　　由表5数据可知:二次回溯法相对于MM法的召回率为86.08%,查准率为89.08%;交集型歧义字段切分上,二次回溯法将MM法切分错误率降低了75.53%,即错误率降低了3/4以上;由于单纯使用正向最大匹配的错误率为1/169[6],以及交集型歧义字段占全部歧义切分字段的85%以上[9],二次回溯法的切分错误率为1/466以下,切分错误率远低于MM法和RMM法。
　　
　　4 结束语
　　
　　算法复杂度方面,二次回溯法整个过程没有对上下文语义、词性进行分析,仅仅利用词表进行词条匹配,因此属于机械分词,算法比MM法复杂,但仍然比较简单且易于实现;切分精度方面,能对交集型歧义字段有效地识别和切分,大大提高了对歧义字段的召回率和查准率。二次回溯法对多义型歧义字段不能有效发现,这同时也是机械分词的一个难点。今后的工作尝试将二次回溯法结合文献[12]所提出基于词频统计并具有过滤功能的关键词自动抽取和词条添加的方法,来进一步提高分词的召回率和查准率。
　　
　　参考文献:
　　[1]刘群,张华平,俞鸿魁,等. 基于层叠隐马模型的汉语词法分析[J]. 计算机研究与发展,2004,41(8):1421-1429.
　　[2]赵伟,戴新宇,尹存燕,等.一种规则与统计相结合的汉语分词方法[J].计算机应用研究,2004,21(3):23-25.
　　[3]罗智勇,宋柔. 现代汉语通用分词系统中歧义切分的实用技术[J].计算机研究与发展,2006,43(6):1122-1128.
　　[4]孙茂松,肖明,邹嘉彦.基于无指导学习策略的无词表条件下的汉语自动分词[J].计算机学报,2004,27(6):736-742.
　　[5]谭琼,史忠植. 分词中的歧义处理[J].计算机工程与应用,2002,38(11):125-127.
　　[6]翟凤文,赫枫龄,左万利. 字典与统计相结合的中文分词方法[J]. 小型微型计算机系统,2006, 27(9):1766-1771.
　　[7]卢志茂,刘挺,李生. 统计词义消歧的研究进展[J].电子学报,2006,34(2):333-343.
　　[8]谈文蓉,杨宪泽,谈进,等.MIS智能接口中汉语分词系统的设计与应用[J].计算机科学,2006,33(7):204-206.
　　[9]孙茂松,黄昌宁,邹嘉彦.利用汉字二元语法关系解决汉语自动分词中的交集型歧义[J]. 计算机研究与发展,1997,34(5):332-339.
　　[10]揭春雨,刘源,梁南元.论汉语自动分词方法[J].中文信息学报,1989,3(1):1-8.
　　[11]闫引堂,周晓强.交集型歧义字段切分方法研究[J].情报学报,2000,19(6):637-642.
　　[12]肖红,许少华,李欣.具有三级索引词库结构的中文分词方法研究[J].计算机应用研究,2006,23(8):49-51.