最近实验室在做一个topicDetection的Demo，用到了中文分词，这几天对中文分词进行了研究，中文分词已经算是一个比较成熟的研究领域了，做的比较好的开源代码有：IKAnalyzer，Paoding，MMSEG4J，FudaoNLP，ICTCLAS（现改名NLPIR）等等。项目要求说是后面会加入更多新的功能，可能会用到词性，所以综合测试了一个源码，最终选用NLPIR，这是一款非常优秀的分词系统，包括：分词，词性标注，关键字提取，发现新词等功能，而且用起来也非常轻便。
中文分词的算法大致可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。而基于字符串匹配的方法中，常用的方法主要有：最大匹配（包括向前、向后以及前后相结合）、最短路径方法（切分出来的词数最少）、全切分方法（列出所有可能的分词结果）、以及最大概率方法（训练一个一元语言模型，通过计算，得到一个概率最大的分词结果）。下面针对各自的优缺点，对比分析如下：
- 最大匹配分词是一种纯粹基于规则的方法，简单有效。在没有大规模预先切分好的熟语料的情况下，是唯一行之有效的方法。但是该方法仅仅是从最大匹配的角度出发，很多问题无法解决，如交叉歧义、组合歧义。最终的准确率不会太高，预处理的粗分过程一旦采用最大匹配方法，后期处理必须做很多补救措施，才能保证最终的分词质量。另外一个不足在于它缺少合理的评分机制，我们就很难再选出一个次优的切分结果。
- 最短路径方法采取的规则是使切分出来的词数最少，符合汉语自身的语言规律。可以取得较好的效果，但是同样不能正确切分许多不完全符合规则的句子。如果最短路径有多条，往往只保留其中一个结果，这对其他同样符合要求的路径时不公平的，也缺乏理论根据。
- 全切分方法列举出所有可能的切分结果，避免在粗分过程中就出现切分错误，将优选排错的任务交给后续过程，有一定合理性。但是，全切分产生的切分结果数随着句子长度的增大而成指数级增大，其中大多数是无效结果，对正确结果的生成没有太大帮助。无论是求取所有切分结果，还是后续过程对大量结果的分析处理都是非常困难而且费时。因此该方法和实际需求还有一定差距，实用性不强。
- 最大概率分词方法[7]的根据是：联合概率（各个词的词频相乘）最大的词串就是最终的切分结果，是一种效果较好的分词方法。最大概率分词方法实质上是一种简单变形的最短路径方法，改进的地方在于它的切分有向图的边长等于词频。
- N-最短路径方法实际上是最短路径方法和全切分的有机结合。该方法的出发点是尽量减少切分出来的词数，这和最短路径分词方法是完全一致的；同时又要尽可能的包含最终结果，这和全切分的思想是共通的。通过这种综合，一方面避免了最短路径分词方法大量舍弃正确结果的可能，另一方面又大大解决了全切分搜索空间过大，运行效率差的弊端。同时我们还可以看到：最短路径方法和全切分方法分别是N-最短路径方法在N=1(而且只能选择唯一的路径)和N=∞时的退化。N-最短路径一元统计方法在N=1(而且只能选择唯一的路径)时就退化为最大概率分词方法。
作为预处理阶段的一种粗分方法，N-最短路径方法的优势还体现在它的包容性，也就是说：该方法通过保留少量大概率的粗分结果，可以最大限度地包容正确结果，粗分结果仅仅是解决粗分阶段能解决的一些问题，而将歧义字段、未登录词等问题，尽量保留给下一阶段专门处理。常用方法共同的弊端就在于保留一个自己认为最优的结果，而这一结果往往会因为歧义或未登录词问题而丢失正确结果。例如，用最大匹配或最短路径方法粗分“结合成分子时”，得到的结果均为“结合/成分/子时”。显然，由于交叉歧义的存在，这两种方法在粗分阶段就抹杀了事实上的交叉歧义，导致最终的错误，而采取2-最短路径方法就完全可以将正确的结果“结合/成/分子/时”成功召回。
N-最短路径方法相对的不足就是粗分结果不唯一，后续过程需要处理多个粗分结果。但是，对于预处理过程来讲，粗分结果的高召回率至关重要。因为低召回率就意味着没有办法再作后续的补救措施。预处理一旦出错，后续处理只能是一错再错，基本上得不到正确的最终结果。而少量的粗分结果对后续过程的运行效率影响不会太大，后续处理可以进一步优选排错，如词性标注、句法分析等。
而本项目所采用的NLPIR分词系统就是采用N-最短路径方法来实现中文词语的粗分。在下篇文章《N-最短路径中文词语粗分算法研究》中，再来着重讨论N-最短路径算法的原理实现。