最短路径算法

1、引言
“词是最小的能够独立活动的有意义的语言成分。”[1], 但汉语是以字为基本的书写单位，词语之间没有明显的区分标记，因此，中文词语分析是中文信息处理的基础与关键。而中文词语分析一般包括3个过程：预处理过程的词语粗切分，切分排歧与未登录词识别、词性标注。目前中文词语分析采取的主要步骤是：先采取最大匹配、最短路径、概率统计方法、全切分等方法，得到一个相对最好的粗分结果，然后进行排歧、未登录词识别，最后标注词性。例如：北大计算语言所分词系统采用了统计方法进行词语粗分[2,3,5]，北航1983年的CDWS系统则采用了正向或逆向最大匹配方法[4,5]，而清华大学的SEGTAG系统采用的是全切分方法[5]。在实际的系统中，这三个过程可能相互交叉、反复融合，也可能不存在明显的先后次序。
预处理过程产生的粗切分结果是后续过程的处理对象，粗分结果的准确性与包容性（即必须涵盖正确结果），直接影响系统最终的准确率、召回率。预处理得到的粗分结果一旦不能成功召回正确的结果，后续处理一般很难补救，最终的词语分析结果必然会导致错误，粗分结果的召回率往往是整个词语分析召回率的上限。同时，粗分结果集的大小也决定了后续处理的搜索空间与时间效率，最终也会影响整个系统的运行效率。因此，词语粗分是后续处理的基础和前提，其关键在于如何以尽量高的效率寻找数量极少、涵盖最终结果的粗分结果集。
我们采取当前常用的粗分方法，对大规模真实语料库的进行测试实验，词语粗切分的召回率均不足93.50%。因此，改进预处理过程中的汉语词语粗分方法，是提高排岐、未登录词识别、词性标注最终效果的基础性措施，也是提高中文词语分析质量的重要途径。
本文提出了一种旨在提高召回率同时兼顾准确率的词语粗分模型——基于N-最短路径方法的中文词语粗分模型。根据我们针对大规模真实语料库的对比测试，粗分结果的召回率有较大提高，模型的运行效率也令人满意，该方法是行之有效的。本文第二节将系统描述非统计模型的基本思想与实现，然后加入词频信息，得到N-最短路径的一元统计模型，最后给出对比实验的结果及分析。
2、基于N-最短路径的非统计粗分模型
粗切分的目标是：快速（粗分结果集尽量少）、高召回率（即可能的涵盖最终结果）。一个很直接的研究思路是：先快速的找出包含正确结果在内的N（N≥1）种粗分结果。然后综合考虑速度和召回率，通过试验，确定N的最佳值，最终得到涵盖最终结果在内的尽量小的粗分结果集。
2.1 基本思想
我们采取的是最短路径的改进方法——N-最短路径方法。其基本思想是：根据词典，找出字串中所有可能的词，构造词语切分有向无环图。每个词对应图中的一条有向边，并赋给相应的边长（权值）。然后针对该切分图，在起点到终点的所有路径中，求出长度值按严格升序排列（任何两个不同位置上的值一定不等，下同）依次为第1， 第2，…，第i，…，第N的路径集合作为相应的粗分结果集。如果两条或两条以上路径长度相等，那么他们的长度并列第i，都要列入粗分结果集，而且不影响其他路径的排列序号，最后的粗分结果集合大小大于或等于N。
2.2 模型求解
设待分字串 S=c1 c2……cn，其中ci（i =1,2,…n）为单个的字， n 为串的长度，n≥1。建立一个节点数为n+1的切分有向无环图G，各节点编号依次为V0，V1，V2，…，Vn。
通过以下两种方法建立G所有可能的词边。
(1) 相邻节点Vk-1, Vk之间建立有向边 ，边的长度值为Lk， 边对应的词默认为ck   (k=1,2,…n)
(2) 若w=ci ci+1……cj 是一个词，则节点Vi-1, Vj之间建立有向边 ，边的长度值为Lw，边对应的词为w   (0这样，待分字串S中包含的所有词与切分有向无环图G中的边一一对应。如图1所示：

在非统计粗分模型中，我们假定所有的词都是对等的，为了计算方便，不妨将词的对应边长的边长均设为1。
设：Path(i,j)为所有从Vi到Vj的路径集合；Length(path) 为路径path的长度，其值等于path中所有边的长度之和；LS为G中所有从V0到Vn路径的长度集合；NLS为V0到Vn的N-最短路径长度集合；NSP为V0到Vn的N-最短路径集合；而RS是最终的N-最短路径粗分结果集. 则有：
LS={len| len=Length (path), path∈Path(0,n)}
NLS的定义： NLSÍLS, | NLS |=min(|LS|,N); " a∈LS-NLS , b∈NLS → a < b
NSP={path| path∈Path(0,n), Length(path)∈NLS }
RS={w1w2…wm| wi是path 的第i条边对应的词， i=1,2, … , m , 其中path∈NSP }。
RS是NSP对应的分词结果，即我们所求的粗分结果集。因此，N-最短路径方法词语粗切问题转化为：如何求解有向无环图G的集合NSP。
2.3 N-最短路径求解与复杂度分析
求解有向无环图G的集合NSP，可以采取贪心方法 [6]。我们使用的算法是基于Dijkstra[3]的一种简单扩展。改进的地方在于：每个节点处记录N个最短路径值，并记录相应路径上当前节点的前驱。如果同一长度对应多条路径，必须同时记录这些路径上当前节点的前驱。最后通过回溯即可求出NSP。
我们以“他说的确实在理”为例, 给出了3-最短路径的求解过程。如图2所示。