基于一种粗切分的最短路径中文分词研究

中文分词是中文自然语言理解和处理的重要环节，也是一个比较复杂和困难的问题。它是自动翻译、文本检索、语音识别、文本校对以及搜索技术中的重要组成部分。分词就是将连续的字符串或序列按照一定的规范重新组合成词序列的过程[1]。本论文定义的分词(text segmentation或者word segmentation)就是对计算机不能直接理解的字符串或者序列按照一定的规则裁分并最终组合成计算机可以理解的词序列的过程。西文的行文中，空格是天然的分界符。因此，对于西文的各种处理比较直观和方便。而中文只有最简单的句与句之间的划界（比如标点符号之类），词与词之间没有明显分界符。例如一个最简单的例子，英语：I call her sister；译文：我叫她姐姐。在西文处理中，计算机可以通过空格和标点符号确定“sister”为一个独立语意单位，独自构成一个词。但是在译文中，由于没有明显标点符号分界，在没有一定规则的前提下，计算机很难理解“姐”和“姐”共同构成一个语意单位。

如引言中所述，中文自然语言的理解和处理远比西文语言复杂得多，主要体现在以下几个方面[1]：

(1)分词的规范问题：词的确切概念难以标准化，词的应用领域不同，使得分词规范难以统一，需要达到的分词效果也有很大区别。

(2)歧义切分：对于特定的句子或字符串可能存在多种切分方法，不同的切分方法具有不同的含义，因此会导致组合型歧义和交集型歧义。

(3)新词识别：汉字系统是一个开放性系统，可能不断有新词产生，最典型的比如：人名、地名以及各类术语，分词系统必须不断更新分词词典。

(4)分词理解的先与后：由于计算机需要靠词的信息来理解文章，因此它只能采用先分词后理解的方法，而分词需要以理解为基础，理解必须先分词。由此产生的逻辑问题决定了不可能有百分之百正确的分词方法。

目前，已经有很多比较成熟的汉语分词技术。邹海山等在现有分词技术的基础上提出了一种基于词典的正向最大匹配和逆向最大匹配相结合的汉语分词方案，可以高效准确的实现中文文档的主题词条抽取和词频统计；应志伟等基于一个实际的文语转换系统，改进最大匹配算法，从实用角度解决多音字的异读问题和中文姓名自动识别问题；欧振猛、余顺争采用基于自动建立词库的最佳匹配方法进行中文分词；韩客松等主要从知识的自动获取出发，介绍了研究中的汉语语言无词典分词模型系统。

中文词语分词采取的主要步骤是：先采取最大匹配、最短路径、概率统计、全切分等方法，得到一个相对较好的粗分结果，然后进行排歧、未登录词识别，最后标注词性。例如：北大计算语言所分词系统采用了统计方法进行词语粗分，北航1983年的CDWS系统则采用了正向或逆向最大匹配方法，而清华大学的SEGTAG系统采用的是全切分方法。在实际的系统中，这三个过程可能相互交叉、反复融合，也可能不存在明显的先后次序。

本论文的叠加算法着重为了减少粗分结果集，同时针对歧义切分中存在的问题，提出基于非负权图最短路径分词算法，本算法高效、快速的解决了交集型歧义以及多切分问题。预处理过程产生的粗切分结果是后续过程的处理对象，粗分结果的准确性与包容性（即必须涵盖正确结果）直接影响系统最终的准确率、召回率。预处理得到的粗分结果一旦不能成功召回正确的结果，后续处理一般很难补救，最终的词语分析结果必然会导致错误，粗分结果的召回率往往是整个词语分析召回率的上限。同时，粗分结果集的大小也决定了后续处理的搜索空间与时间效率，最终会影响整个系统的运行效率。 因此，词语粗分是后续处理的基础和前提，其关键在于如何以尽量高的效率寻找数量少、涵盖最终结果的粗分结果集。

由于正向与逆向最大匹配算法结果集之间难免存在包含与被包含关系，如果把这两种结果直接叠加可能出现切分错误，而且会增加歧义切分现象。例如：输入“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中长度最小的结果集比较完毕。这样就能保证有向图中的顶点唯一，顶点个数最少。

用给定的字符串构造非负权图的方法如下所述：

①对于给定语句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。由上述方法构造的非负