在上篇文章中对比了中文词语粗分的几个算法，提到N-最短路径算法在中文词语粗分中的优势，下面在这篇文章中就着重研究N-最短路径算法的原理。

首先我们要知道，N-最短路径算法中的N指的是什么？

_N指的是从源点到终点的前N条最短路径长度的若干条路径，这里有个地方要注意的是N指的是前N条最短路径长度。_例如：求2-最短路径，从源点到终点的最短路径长度为5，次短路径长度为6，但是包含最短路径长度的不一定就只有一条路径，譬如可能有两条路径A，B都是路径长度为5，又有三条路径C，D，E的长度为6，那么求2-最短路径即求A，B，C，D，E这五条路径。这个问题清楚之后，我们就开始下面的问题。

在了解N-最短路径之前，首先，我们来看看1-最短路径算法。顾名思义，1-最短路径即求的是最短路径，下面我们来看看1-最短路径是如何实现的：

一、数据表示

我们用如下的有向图来举例说明，各权重已标明：

（图一）

根据有向图可以建立如下所示的二维表：

（图二）

二维表内取值即为权重。

最近实验室在做一个topicDetection的Demo，用到了中文分词，这几天对中文分词进行了研究，中文分词已经算是一个比较成熟的研究领域了，做的比较好的开源代码有：IKAnalyzer，Paoding，MMSEG4J，FudaoNLP，ICTCLAS（现改名NLPIR）等等。项目要求说是后面会加入更多新的功能，可能会用到词性，所以综合测试了一个源码，最终选用NLPIR，这是一款非常优秀的分词系统，包括：分词，词性标注，关键字提取，发现新词等功能，而且用起来也非常轻便。

中文分词的算法大致可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。而基于字符串匹配的方法中，常用的方法主要有：最大匹配（包括向前、向后以及前后相结合）、最短路径方法（切分出来的词数最少）、全切分方法（列出所有可能的分词结果）、以及最大概率方法（训练一个一元语言模型，通过计算，得到一个概率最大的分词结果）。下面针对各自的优缺点，对比分析如下：

1. 最大匹配分词是一种纯粹基于规则的方法，简单有效。在没有大规模预先切分好的熟语料的情况下，是唯一行之有效的方法。但是该方法仅仅是从最大匹配的角度出发，很多问题无法解决，如交叉歧义、组合歧义。最终的准确率不会太高，预处理的粗分过程一旦采用最大匹配方法，后期处理必须做很多补救措施，才能保证最终的分词质量。另外一个不足在于它缺少合理的评分机制，我们就很难再选出一个次优的切分结果。
   Read more »