传统分词算法总结

1. 最大匹配算法

1.1 正向最大匹配

思想

从左到右尽可能划分出一段连续字符，使得其等于词典中的某个词，然后将这段连续字符提取出来，对余下的部分进行同样的操作。如果第一个字符不是词典中任何一个词的前缀，那么这个字符单独作为一个词。

算法

输入：一个未分词的句子S，一个词典D

输出：一个序列的词

1.2 逆向最大匹配

跟正向最大匹配的唯一不同是从右到左尽可能划分出一段连续字符。

1.3 双向最大匹配

歧义指对于一个句子有多个分词结果。汉语文本中 90.0%左右的句子，FMM 和 BMM 的切分完全重合且正确，9.0%左右的句子 FMM 和 BMM 切分不同，但其中必有一个是正确的(歧义检测成功)，只有不到1.0 %的句子，或者 FMM 和 BMM 的切分虽重合却是错的，或者FMM 和 BMM 切分 不同但两个都不对(歧义检测失败)。^[1]

双向最大匹配指从正向最大匹配和逆向最大匹配法的结果中选择最满足中文分词原则的一个分词结果。详见Ambiguity Resolution in Chinese Word Segmentation和构建中文分词器 - 双向最大匹配法

2. 最短路径分词^[2]

2.1 最短路径分词/最少词语分词

最少词语分词是在所有的切分过程中选择词语数量最少的分词结果，如果出现词语数量相同的情况，就选择词语长度的方差小的那个分词结果。

最少词语分词也叫最短路径分词，因为求最少词语问题可以变成求有向无环图(DAG)的最短路径问题。位置(position)定义为每个字符后面的位置，如果一个句子的字符是从1到n，那么位置就是从0到n，0是第一个字前面的位置，n是最后一个字后面的位置。

0他1说2的3确4实5在6理7

每个位置是DAG中的一个节点，对于节点  ，如果  和  之间构成了词或单个字，就有一条  到  的边。所有边的长度都是1。从节点0到节点7的路径的长度就是分词的词语数量，最短路径的结果就是最少词语的结果。

2.2 全切分

将上述所有可能的路径都当作分词结果返回，就是全切分方法。

2.3 最大概率分词

最大概率分词是最短路径分词的变种，在最短路径中所有边的权重都是1，如果我们把边的权重替换成边对应的词语的概率，把最短路径替换成最大概率路径，分词的算法就变成了最大概率分词了。

词语的概率约等于频数除以所有词的总数，由于求最大概率需要用到概率的连乘，如果把概率替换成对数，连乘就变成了连加。

相比最短路径分词，词典不仅要记载每个词汇，还要记载每个词汇出现的频率。

jieba的基础分词器使用的就是最大概率分词。

2.4 N最短路径分词^[3]

最短路径分词只返回一个结果，全切分返回所有可能的结果，N最短路径分词是两者的折中，返回路径最短的前N个分词结果。相应地，也有N最大概率分词

3. N元语言模型分词^[4]

N元语言模型分词是指选取N元语言模型概率最大的分词序列作为分词结果。设分词序列为  ，N元语言模型分词的返回是：

以二元语言模型为例， 

4. HMM分词^[5]

把分词当做一个序列标注问题，序列单元是字，序列标签有B和E，分别代表非词尾和词尾。那么一个EBEBEEBBEB序列代表的分词结果就是E BE BE E BBE B。

HMM语境下，隐状态是序列标签，观测序列是未分词的句子。分词问题就是解码问题(给定观测序列，求最有可能的状态序列)。

HMM用于另一个序列标注的例子见^[6]

 

参考

1. 汉语自动分词研究评述 http://59.108.48.5/course/mining/12-13spring/%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE/02-01%E6%B1%89%E8%AF%AD%E8%87%AA%E5%8A%A8%E5%88%86%E8%AF%8D%E7%A0%94%E7%A9%B6%E8%AF%84%E8%BF%B0.pdf
2. 汉语分词初探 https://unordered.org/timelines/59cd4b0655001000
3. 基于 一 最短路径方法的中文词语粗分模型 http://jcip.cipsc.org.cn/UserFiles/File/353基于N_最短路径方法的中文词语粗分模型_张华平.pdf
4. 中文分词算法简介 https://lujiaying.github.io/posts/2018/01/Chinese-word-segmentation/
5. 用HMM做中文分词 http://www.52nlp.cn/itenyh版-用hmm做中文分词一：模型准备
6. 隐马尔可夫模型词性标注及其Python实现 https://zhuanlan.zhihu.com/p/48260272

原文链接：https://zhuanlan.zhihu.com/p/92102484