摘 要 本论文在分析现有的分词算法并比较各种算法优缺点的基础上，提出了将正向匹配算法与逆向匹配算法所得到的结果集进行叠加，生成粗分结果集的新观点，再对生成的粗分结果集构造非负权有向图，然后应用最短路径算法求解有向图。本文提出的叠加算法着重考虑粗分结果的准确性、包容性以及粗分结果的长度。经过实验验证，该算法有效提高了汉语切分的准确性以及切分速度，同时部分解决了交集型歧义切分问题。
1 引言
中文分词是中文自然语言理解和处理的重要环节，也是一个比较复杂和困难的问题。它是自动翻译、文本检索、语音识别、文本校对以及搜索技术中的重要组成部分。分词就是将连续的字符串或序列按照一定的规范重新组合成词序列的过程[1]。本论文定义的分词(text segmentation或者word segmentation)就是对计算机不能直接理解的字符串或者序列按照一定的规则裁分并最终组合成计算机可以理解的词序列的过程。西文的行文中，空格是天然的分界符。因此，对于西文的各种处理比较直观和方便。而中文只有最简单的句与句之间的划界（比如标点符号之类），词与词之间没有明显分界符。例如一个最简单的例子，英语：I call her sister；译文：我叫她姐姐。在西文处理中，计算机可以通过空格和标点符号确定“sister”为一个独立语意单位，独自构成一个词。但是在译文中，由于没有明显标点符号分界，在没有一定规则的前提下，计算机很难理解“姐”和“姐”共同构成一个语意单位。
2 中文分词技术概述
2.1 中文分词技术中存在的难题
如引言中所述，中文自然语言的理解和处理远比西文语言复杂得多，主要体现在以下几个方面[1]：
(1)分词的规范问题：词的确切概念难以标准化，词的应用领域不同，使得分词规范难以统一，需要达到的分词效果也有很大区别。
(2)歧义切分：对于特定的句子或字符串可能存在多种切分方法，不同的切分方法具有不同的含义，因此会导致组合型歧义和交集型歧义。
(3)新词识别：汉字系统是一个开放性系统，可能不断有新词产生，最典型的比如：人名、地名以及各类术语，分词系统必须不断更新分词词典。
(4)分词理解的先与后：由于计算机需要靠词的信息来理解文章，因此它只能采用先分词后理解的方法，而分词需要以理解为基础，理解必须先分词。由此产生的逻辑问题决定了不可能有百分之百正确的分词方法。
2.2 中文分词技术发展现状
目前，已经有很多比较成熟的汉语分词技术。邹海山等在现有分词技术的基础上提出了一种基于词典的正向最大匹配和逆向最大匹配相结合的汉语分词方案，可以高效准确的实现中文文档的主题词条抽取和词频统计；应志伟等基于一个实际的文语转换系统，改进最大匹配算法，从实用角度解决多音字的异读问题和中文姓名自动识别问题；欧振猛、余顺争采用基于自动建立词库的最佳匹配方法进行中文分词；韩客松等主要从知识的自动获取出发，介绍了研究中的汉语语言无词典分词模型系统。
2.3 中文分词算法综述
中文词语分词采取的主要步骤是：先采取最大匹配、最短路径、概率统计、全切分等方法，得到一个相对较好的粗分结果，然后进行排歧、未登录词识别，最后标注词性。例如：北大计算语言所分词系统采用了统计方法进行词语粗分，北航1983年的CDWS系统则采用了正向或逆向最大匹配方法，而清华大学的SEGTAG系统采用的是全切分方法。在实际的系统中，这三个过程可能相互交叉、反复融合，也可能不存在明显的先后次序。
3 粗切分的最短路径中文分词
本论文的叠加算法着重为了减少粗分结果集，同时针对歧义切分中存在的问题，提出基于非负权图最短路径分词算法，本算法高效、快速的解决了交集型歧义以及多切分问题。预处理过程产生的粗切分结果是后续过程的处理对象，粗分结果的准确性与包容性（即必须涵盖正确结果）直接影响系统最终的准确率、召回率。预处理得到的粗分结果一旦不能成功召回正确的结果，后续处理一般很难补救，最终的词语分析结果必然会导致错误，粗分结果的召回率往往是整个词语分析召回率的上限。同时，粗分结果集的大小也决定了后续处理的搜索空间与时间效率，最终会影响整个系统的运行效率。 因此，词语粗分是后续处理的基础和前提，其关键在于如何以尽量高的效率寻找数量少、涵盖最终结果的粗分结果集。
3.1 叠加算法描述
由于正向与逆向最大匹配算法结果集之间难免存在包含与被包含关系，如果把这两种结果直接叠加可能出现切分错误，而且会增加歧义切分现象。例如：输入“ABCDEFGHIJK LMN”，其中每一个字母代表一个字。采用正向匹配算法的切分结果为：AB/CD/EF/GH/I/JKL/MN；采用逆向匹配算法的切分结果为：ABC/DE/F/GH/IJ/KLM/N。如果按照常规方法叠加，可能在有向图的顶点中同时存在AB与ABC，这样构成的有向图会严重影响整个切分效率和准确性。
本文采用的叠加方法避免了上述情况的发生，如下描述：正向切分按照切分结果顺序排列Lz，逆向切分按照切分结果倒序排列Lr。对于Lz与Lr，从某一个切分词Wi（i=0，1，2，…，n,其中n=min{length（Lz），length （Lr）}）开始比较，保留词W应该是两者中长度最大的。根据保留词从Lz和Lr中取得下一个比较词的开始字符，重复上述过程直到Lz与Lr中长度最小的结果集比较完毕。这样就能保证有向图中的顶点唯一，顶点个数最少。
3.2 构造非负权图
用给定的字符串构造非负权图的方法如下所述：
①对于给定语句S（从构成来看由许多单字组成，而表达的意义是由多个语义单位构成）；
②根据提供的统一分词词典，按照正向最大匹配算法找出字符串中所有可能的语意对象或者词，求得构词集Vd={vd1,vd2,…,vdn}；
③如同②，按照反向最大匹配算法找出字符串中所有可能的语意对象或者词；求得构词集Vr={vr1,vr2,…,vrn}；
④对②与③的构词集Vd与Vr按照本论文算法进行叠加运算，连同语句中所有的单字集Vs取得无负权图所有构词集V={v1,v2,…,vn}，边权值定义为wij=1(i,j=1,2,…,n)；
⑤在相邻节点Nk-1，Nk之间建立有向边Nk-1,Nk，边的长度值为Lk，边对应的词默认为vk(k=1,2,…,n)；
⑥若w=vivi+1…vj是一个在V中的词，则在节点Ni-1，Nj之间建立有向边Ni-1,Nj，边的长度为Lw，边对应的词为w(0ij≤n)。
在本论文中，边的长度Lk(k=1,2,…,n)统一赋值为1。由上述方法构造的非负
权图如图1所示。
3.3 求解非负权图的算法描述[1]
假设P(i,j)是顶点集N中ni到nj的路径集合(i,j=0,2,…,n)，L(p)是某两点间路径长度，其值等于p中所有边的长度之和。LS是G中所有n0到nn路径的长度集合，LS={len|len=L(p),p∈P(1,n)}。NLS为n0到nn的N-最短路径长度集合，，|NLS|=min(|LS|)； ，b∈NLS←ab。NSP为n0到nn的N-最短路径集合，NSP={p| p∈P(1,n),L(p)∈NLS}。而RS是最终的N-最短路径结果集，RS={w1w2…wm|wi是p的第i个顶点对应的词，i=1,2,…,m，其中p∈NSP}。RS是NSP对应的分词结果，即为所求的结果集。这样，N-最短路径方法转化为：如何求解无负权有向图G的集合NSP。在每一个节点处记录下最短路径值，并记录相应路径上当前节点的前驱。如果同一长度对应多条路径，必须同时记录这些路径上当前节点的前驱，最后通过回溯即可求出NSP。
以上求解算法借鉴了文献[1]最短路径匹配算法的求解模式。而本文所提出的算法与文献[1]有明显不同，在最短路径匹配算法中根据分词词典找出所有可能的词，直接构造有向无环图G，每一个词对应图中的一条有向边。本论文是根据叠加算法求解的构词集以及语句中所有单字作为图中边对应的词。
4 实验验证
整个算法实验过程中，正向与逆向所用数据字典是segmenter程序提供的一个基本词典，共有词量195580条。经过对含有汉字串：“我是中国人民的儿子”与“我是一个深深爱着祖国和人民的好儿子”进行实验，以及一个大小为6kb的文本文件进行实验，结果
对于汉字串1：正向正大匹配算法结果集{我，是，中国人民，的，儿子}；逆向最大匹配算法结果集{我，是中国，人民的，儿子}。
叠加算法求得结果集{我，是中国，人民的，儿子}。
最终构造的有向图，如图2。
求得最终结果：我/是中国/人民的/儿子。
程序运行结果如图3。
采用同样方法对汉字串2和文本文件(6kb)进行实验，验证结果如表1所示。
图3 汉字串1实验结果
表1 实验结果对比表
测试对象
本算法实验时间(ms)
文献[1]最短路径算法实验时间(ms)
汉字串1
15
17
汉字串2
23
26
文本文件(6kb)
148
156
5 结论
本论文提出的对正向与逆向匹配算法所得到的结果集进行叠加的算法，高效、快速的解决了交集型歧义以及多切分问题。在一定程度上减小了算法的时间复杂度，但是空间复杂度没有太大变化，在今后的学习中我会向这方面努力。
参考文献
[1] 朱巧明，李培峰．中文信息处理技术教程［Ｍ］．北京：清华大学出版社，2005：183-184
严蔚敏，吴伟民．数据结构[M]．北京：清华大学出版社，1997：187-188
《现代数学手册》编纂委员会．现代数学手册(计算机数学卷)．湖北：华中科技大学出版社，2001.2：450
冯书晓，徐 新．国内中文分词技术研究新进展［Ｊ］．情报杂志．2002 (11)：29
李大农，董 慧．汉语分词有向图的快速生成算法［Ｊ］．情报杂志．2004.2：36-37
刘群，张华平等译．自然语言理解［Ｍ］．北京：电子工业出版社，2005.1：153-178
张华平，刘群．基于N-最短路径方法的中文词语粗分模型［Ｊ］．中文信息学报 No1.16 No. 5：2
