一种词法分析与字标注分词结合的方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种词法分析与字标注分词结合的方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：提出了一种新的字位置信息标记，使用该标记可以实现字标注分词和词性分析的一体化。通过设计一套包含了词性信息的字位置信息标记，在训练前对训练语料进行改造，将训练语料转化成用新标记标注的语料，然后根据转化的结果进行训练，并用训练产生的隐马模型(HMM)对待分词字符串进行字标注，最后找出最大概率路径作为分词结果，该分词结果同时也包含了词法分析的结果。该文将隐马模型中的viterbi算法修改成N-viterbi算法，采用N-viterbi算法可以实现查找分词图中的前N条最大概率路径。实验表明，该模型可以较准确的完成分词操作，同时可以产生有一定引导作用的词法分析结果。
关键词：分词；词法分析；字标注；N-viterbi；隐马模型；一体化
中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)08-1814-04
A Method to Do Lexical Analysis while Word-position Tagging
HUANG Xiao-bin, YU Yue-meng
(School of Information Science and Engineering, Xiamen University, Xiamen 361005, China)
Abstract: A new kind of tags for the word-position tagging. word-position tagging and lexical analysis integration can be achieved using the new tags. the new kind of tags contains both the lexical information and the word-position information, before the training process, modify the trainning data using the new tags,then train the word segment model with the modified trainning data,after the trainning finished,use the model to do a word segment process on a sentence,then get the result from the model.the result will be both the word segment result and the lexical analysis result .This article also changed the viberti algorithm of HMM into N-viberti,which can find the top N results of a word segment graphy. Experiments show that through the model,we can get a good word segment result,and a lexical analysis result in the same time, though the accuracy is still relatively low .
Key words: word segmentation; lexical analysis; word-position tagging; N-viterbi; Hidden Markov Model; integration
汉语中词与词之间不存在分隔符,词本身也缺乏明显的形态标记,因此,中文信息处理领域的一项基础性研究课题是如何将汉语的字串分割为合理的词语序列,即汉语分词。它是句法分析、语义分析等深层处理的基础,也是机器翻译、自动问答系统等应用的关键环节[1]。“词”的定义未确定、分词和理解、孰先孰后、歧义切分字段处理以及未登录词识别等仍是中文自动分词的热点和难点问题[2],这些问题的解决是自动分词前进和发展的关键。
传统的分词方法一般不考虑词性对分词结果的影响，而传统的词法分析一般都是在已经存在的分词结果上进行词性标注，并不能改正分词结果中已经存在的错误。目前也有一些词法分析模型可以同时完成分词和词性标注，但是其真正的实现过程中，分词和词法分析仍然是独立的两个过程，只是在选择结果的时候以某正方式抽取出最可能同时满足分词和词法分析的结果或者是以某正方式将两个过程糅合成一个，这种系统的实现难度一般都比较大。虽然这类系统的准确率较高，但是都存在时间复杂度偏高或者模型训练难度大的问题。本文通过设计一套包含了词性信息的字位置信息标记，在训练时对训练语料进行改造，将训练语料的标注信息转化用新标记标注的语料，然后根据转化的结果进行训练，并用训练产生的模型对待分词字符串采用Viterbi算法进行标注，最后找出最大概率路径作为分词结果，该分词结果同时也包含了词法分析的结果。这样的处理方式，不仅训练数据改造程度较小，比较容易实现，而且只要采用了这套标记，只需要对现有的分词系统进行轻微的更改以适应这套标记，无需对分词系统的结构或者核心算法进行调整，通过这样一个简单的修改过程，即可将一个现有的功能单一的分词系统改造成一个可以同时实现分词和词法分析的系统。本文采用隐马尔科夫模型作为分词系统的数据模型来进行试验。
1传统的字位置信息标记
汉语中的每个词语是由一个字或多个字组成的,例如:“天空”、“今天”是两个字组成的词语,“异想天开”是四字词,“天”是单字词。而构成词语的每个汉字在一个特定的词语中都占据着一个确定的构词位置,即词位。本文中的字位置信息标记一共有7种词位:B(词首)、S2(词的第二字并且不是词尾）、S3(词的第三字），S4(词的第四字）O(词的第五字以及词尾之间的字)、E(词尾)和S(单字成词)。。显然同一个汉字在不同的词语中的词位可以不同,例如,汉字“天”在上面的四个词语中的词位依次是:词首B、词尾E、第三字S3、单字词S基于字的词位标注汉语分词就是把分词过程看作每个字的词位标注问题。如果一个汉语字串中每个字的词位都确定了,那么该字串的词语切分也就完成了。例如,要对字串“中华人民共和国成立了”进行分词,只需标注出该字串的词位序列（1）的标 注结果就很容易得到对应的分词结果(2)了。
(1)词位序列：当/S希/B望/S2工/S3程/E救/B助/E的/S百/B万/E儿/B童/E成/B长/E起/B来/E。/S
(2)分词结果:当希望工程救助的百万儿童成长起来。
需要注意的是,由于汉语真实文本中还包含少量的非汉字字符,所以基于字的词位标注汉语分词中所说的字不仅仅指汉字,而且还包括标点符号、西文字母、数字等其他非汉字字符。
2新的字位置信息标记
传统的字位置信息标记中只包含字的位置信息，对于同一个字在所有不同词性的词中出现的情况下，都只保存其位置信息，而不保存词性，因此产生的结果就是分词的结果，而不能从分词结果中去判断一个词的词性。而且由于同一个字在训练语料的不同类型的词中所处的位置不同，训练时传统的字标注分词模型只能将同一个字在不同词性的词中的所处的位置保存到该字的同一个的字位置信息记录中，而同一个字在不同词类的词中所处的位置经常是完全不同的，这样就会对最终的训练结果产生影响。而在字位置信息标记中包含了词性信息之后，就可以对同一个字，根据其所在词的词性不同，分别保存该字的信息。这样不仅可以产生更准确的训练数据，而且采用这种标记进行字标注分词后，由于标记中包含了词性信息，可以从分词结果中还原出词性信息。
对同一个字在不同词性的词中出现的情况，假设有如下语料：
江/nr泽民/nr黑龙江/ns
对于该语料中的“江”字，作为中文人名的姓出现时，一般是单独的一个字，但是作为一个地名出现时，一般是作为词的结尾出现的。当语料中“江”作为姓出现的次数和作为地名出现的次数一致时，经过该语料训练产生的模型中，“江”字的字位置信息如下：
采用传统的字位置信息标记训练产生的结果：
江/S 1江/E 1
采用包含了词性信息的字位置信息标记训练产生的结果：
江/NR_S 1江/NS_E 1
当采用该模型进行分词时，采用传统的字位置标记的字标注分词系统训练对所有碰到的“江”字都采用1:1的概率来标记该字的位置，而采用包含了词性信息的字位置信息标记的系统中，就可以根据“江”所在的上下文环境来进行判断是一个姓或者是一个地名的结尾，这样就可以较为准确的对“江”进行标记。
3 N-viterbi算法
隐马模型中的viterbi算法可以实现从分词图中查找出一条概率最大的分词路径。但是对于大多数采用隐马模型的分词系统，可能将分词的过程分成多个阶段，每个阶段都要求生成概率最大的前N个结果交给后续的处理过程进行处理。对于这样的情况，就无法采用viterbi算法。而不采用viterbi算法，则时间复杂度和空间复杂度都将大大提升，甚至由于分词图太大导致无法获取结果。
针对这样的情况，本文对viterbi算法进行了修改，并将修改后的算法命名为N-viterbi算法。其中的N表示希望从一个分词图中获取的前N个最大概率路径。由于每次获取的路径都是分词图中的当前最大可能概率路径，因此采用N-viterbi算法获取的路径按获取顺序排列，就可以保证这些路径就是当前分词图的前N个最大概率路径。
N-viterbi算法不仅仅能用于分词系统，也适用于所有采用HMM模型，并且需要获得多个可能的隐藏状态序列的环境，通过N-viterbi算法保存多个可能的隐藏状态序列以供后续的处理过程进行选择和处理。3.1 N-viterbi算法实现
for(int i=0;i
//viterbi对分词图进行标记viterbi();
//从分词图中查找结果
findResult();/
/从分词图删除最大概率路径if(!removeUsedPos())/
/分词图中没有其他路径/
/结束查找过程
break;
}
3.2 N-viterbi算法过程
1）采用viterbi算法对分词图进行标记，如果某个节点存在多个可到达的路径，把该节点标记为multip。
2）利用viterbi算法中的反向指针查找出分词图的当前最大概率路径，并将最大概率路径对应的节点记录下来。
3）从最大概率路径的开始节点开始向后查找，找到第一个被标记为multip的节点，删除这个节点的反向指针指向的前一个节点，并清空分词图中的所有标志位和概率值。
4）重复1）到3)的操作
3.3结束条件(满足任意一条即可)
1）计数值i大于N，即已经查找到了前N条最大概率路径
2）在算法步骤3）中找不到可以删除的节点，说明当前路径是分词图中最后一条可以找到的路径
4双向词性筛选
假设一个字符串包含字Ci(0
4.1单向词性判断
分词模型中，在计算词性节点(CiPj）（表示字符i的第j个词性)时，按照以下步骤执行：1）获取字Ci的所有可能词性Pj
2）从分词图中获取Ci的前一个字符Ci-1的可达词性Pk(0
4）结合步骤1）2）3）的结果，计算词性节点（CiPj)可达的概率P(CiPj)
4.2双向词性判断
在步骤3）中，只分析了词性节点(Ci-1Pk)在词性Pj之前的概率，即P(Pj|Ci-1Pk)，把所有词性为Pj的字都统一对待。但是在汉字的实际应用中，有很多字都可能包含同一个词性，但是并不是所有取该词性的字跟在一个词性为Pk的字的后面的概率都是一致的，甚至其中的某些字根本不能跟在词性为Pk的字的后面，因此只从前向后判断词性的做法并不符合真实的汉语环境。本文对分词模型的第3）个步骤进行了修改，修改后的过程如下：
1）获取字Ci的所有可能词性Pj
2）从分词图中获取Ci的前一个字符Ci-1的可达词性Pk(0
3）从矩阵中获取从词性节点(Ci-1Pk)到词性Pj的概率Pf，从反向矩阵中获取词性Pk在词性节点(CiPj)之前的概率Pb,如果Pb
4）结合步骤1) 2) 3)的结果，计算词性节点（CiPj)可达的概率P(CiPj)
加入了反向词性判断后，就可以避免分词结果中包含了某些本来不可能组合在一起的字组合在一起的情况。但是反向词性判断对训练数据的要求更大，由于对分词路径搜索时的要求更严格，也就更可能导致其中某些字无法找到符合要求的路径，从而被当做未登录字处理的情况出现。
5分词系统技术实现
5.1语料库预处理
包括5个处理步骤,分别为去除编号、合并组合词、日期处理。去除的部分都是对训练没有帮助反而可能会加重训练负担的部分。人民日报语料是纯文本文件,文本中每个开头的编号，“19980101-01-001-001”表示这一自然段是1998年1月1日01版001篇文章的001自然段,首先要去掉的就是这个编号;日期处理主要是把如“1999”这样的字段作为一个字符进行标记,而不是4个字符。
本文还将语料库中中文的姓名的姓和名部分拆开，分别采用不同的标记来表示。
5.2语料库改造
本文对组合词采用的是合并操作，而不是将组合词拆分成几个词进行处理，而组合词一般都由多个字组成，因此本文中的字位置标记一共分为7类，这样可以较完整的保存由多个字组成的词的信息。对于语料库中的每个原始的词性标记，都需要生成对应的7个新的标记。
假设语料中有人名：帕瓦罗帝带标记的原始语料中为：帕瓦罗帝/nr替换成新的标记后，语料被改造成：帕/NR_B瓦/NR_S2罗/NR_S3帝/NR_E
5.3学习
在经过改造后的语料上进行训练。本文采用的分词系统是基于隐马尔科夫模型实现的。
5.4分词
5.4.1分字及标准化
由于是字标注分词，因此分词的第一步仍然是将字符串分割成由元素组成的序列，每个元素都是一个字符或者符号，也可以是采用简单的规则合并连续的阿拉伯数字以及英文字符。
5.4.2分句
根据规定的断句规则，对字符串进行句子分割操作，将字符串分割成句子组成的集合。
5.4.3创建分词图
对每个句子都生成一个对应的分词图。分词图中的每一个节点分别代表一个4.1中生成的元素查询初始状态概率字典后获取的每一个可能词性，并记录该节点取该词性的概率以初始化分词图中节点的状态。
5.4.4遍历分词图
采用N-viterbi算法遍历分词图.N-viterbi可以从当前分词图中获取前N条最该概率的分词路径。
5.4.5查找最大概率路径
由于这是本文分词系统的最后一个处理过程，只要求一个最终结果，而不需要提供多条可能的路径供后续处理过程使用，因此只需选择N-viterbi算法的第一个结果作为分词的结果即可。
5.4.6替换标记，生成结果
由于系统采用的是新标记系统，因此在生成结果输出时，还需要对标记的结果进行还原，根据标记的结果完成分词的操作，将字符串分割成词语的序列，还需要根据新标记的结果进行词性标记替换，以保留词法分析的结果。
6实验及结果分析
本次实验采用1998年人民日报语料：
表1
实验一共分为2个部分：
6.1实验一
第一个实验采用训练数据来测试分词的效果，此时不存在未登录字的问题，实验结果如下：
表2
6.2实验二
第二个实验采用测试数据来测试分词的效果，因为训练数据的局限，测试数据中的某些字并不包含在训练语料中，因此无法被系统识别，只要一个句子中出现了这样的一个未登录字，就会对整个句子的分词和词性标注效果产生影响，从而导致结果的错误。实验结果如下：
表3
6.3结果分析
从实验的结果可以看出，采用新的标记系统仍然可以较准确的完成分词的操作，但是词法分析的准确率比较低。实验二的分词和词法分析的准确率都比实验一要低很多，这主要是因为训练语料的数据量较小，对常用字符的覆盖率较低，因此在对实验二的数据进行分词操作时，就出现了很多无法识别的字符，因此降低了实验二的准确率。实验一和实验二的对比说明本系统在提供足够的训练语料的前提下，分词的准确率能达到97.1%，基本满足了实用系统的条件。而且本文的实验系统能够直接对由多个汉字组成的组合词进行识别，更符合实际的应用需求。
在实验一中，采用双向词性筛选后，分词和词性标记的准确率都有明显的提升，而在实验二中，采用双向词性筛选后，分词的准确率提升不明显，而词性标记的准确率反而下降了。这是由于双向词性筛选对训练数据的要求更大。由于双向词性筛选的准确定位要求，只要没有包含在训练数据中的字，都被直接当做未登录字处理。而采用单向词性筛选的系统，由于少了反向筛选限制，对字信息的要求较低，在碰到未登录字时，就有较大的概率识别出未登录字。因此在训练数据不足以包含测试数据的情况下，单向词性筛选反而可以获得更准确的结果。
7结束语
结合了词性信息的字标注分词系统，不仅可以提升分词的准确率，而且在保证分词准确率的基础上，也能完成词法分析操作。
由于本文中只有一个时间复杂度为O(n）（其中n为一个待分词句子中包含的字符个数）的分词图标记操作，所以系统的总体时间复杂度也是O(n)，分词的速度大于大部分的现有分词系统。并且和一般的字标注系统一样，数据字典和矩阵都是以字为单位，记录的数量等于常见的单个字符数量，远远小于以常用词为单位的分词系统，因此分词系统所占的内存也较少。
限于训练语料的大小，实验的系统无法覆盖所有的常见字，即使这样，实验结果的准确率仍然是很高的。至于词法分析结果，目前仍然不太理想，还无法直接作为词法分析的最终结果，仍然有进一步提升的空间。
从实验结果来看，本文的方法是可行的。本文的方法使原本功能单一的分词系统能兼顾到后续的词法分析过程，虽然目前词法分析的结果准确率不高，但是该结果仍然可以用于引导后续的词法分析过程。而且由于字标注分词的特性，并不存在所谓的未登录词，因此对于后续的词法分析中无法识别的词，在分词阶段就给出了比较准确的词性范围。
在以上研究的基础上,还有很多后续工作要做:由于语料库包含的字的层面的信息不够多使其存在无法识别的字，极大的影响了实验的结果。未来可以尝试扩大语料的数量以提升准确率，还可以尝试在其他的数据模型上使用本文提出的字信息标记系统，查找出最合适的数据模型。笔者希望通过不断改进，可以继续提高分词和词法分析的准确率，使其能够在实现分词和词法分析的一体化的同时，也能够达到较高的准确率。最终应用于实际,为中文信息处理服务。
参考文献：
[1]姚敏.汉语自动分词和中文人名识别技术研究[D].杭州:浙江大学,2006.
[2]刘武.基于统计机器学习算法的汉语分词系统的研究[D].北京:北京邮电大学,2006.