基于词典的分词

顾名思义，基于词典的分词就是要有一个词典，分词的过程就是用词典中的词和句子中的词进行比对，然后选出一个最优的切分结果。
显而易见，基于词典的分词必须要维护一个好的词典，且其无法处理未登录词。

最长匹配分词

最长匹配分词指的是使用贪婪算法，从前往后匹配，匹配到最长的字串作为一个词，这种方法一般称为最大正向匹配。
如果是从后往前匹配，也叫做最大反向匹配。
由于汉语组词的多样性，使用最大匹配算法的错误率非常高，而由于汉语词前缀的共性，最大反向匹配的结果要好于最大正向匹配。

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

最短路径分词是在所有的切分过程中选择词语数量最少的分词结果，如果出现词语数量相同的情况，就选择词语长度的方差小的哪个分词结果，所以最短路径分词，又叫做最少词语分词。
为什么把这种分词叫做最短路径分词呢，因为这种分词算法是图的最短路径算法的应用。
我们有一个句子，我们把每个位置当成一个顶点，如果两个位置之间的字串是一个词，那么这两个顶点之间就存在一条边，如果一个顶点没有边和后面的顶点相连，我们就认为其与随后的一个顶点之间存在边，这样，一个句子就变成了一个有向无环图（DAG），于是求最少词语的问题就变成求DAG的最短路径问题了。

全切分词

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

最大概率分词

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

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

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

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

N-Short路径分词

最短路径分词只返回一个结果，全切分词返回所有可能的结果，N-Short路径分词是取两者的中间状态，返回路径最短的N个分词结果。
N-Short分词可以作为粗分词的结果，相比最短路径分词可以提高召回率，相比全切分词可以减小搜索空间。
当然，也可以使用概率最大路径最为基础模型，这样N-Short路径分词返回的就是概率最大的N个分词结果了。
具体可以参考张华平教授的《基于N-最短路径方法的中文词语粗分模型》

基于上下文的分词

基于上下文的分词不需要维护词典，不过需要一个切分好的语料作为训练集，而且分词速度会远慢于基于词典的分词，不过遇到跟训练集完全不同领域的句子时，由于不能通过添加词典的方式来提高正确率，会导致最终的分词结果很差。
基于上下文的分词，本质上是一个标准问题，首先需要介绍以下分词的标注系统。

BMES标注系统

分词最常用的标准系统就是BMES标注，也就是给一个句子中的每个字一个标注，如果这个字是词的开头就标B（begin），词的结尾标E（end），词的中间就标成M（median），单字词标S（single）。

BP标注

BP标注比BMES标注更简单，如果一个字是词的第一字就标B,否则标P。

BMM1M2ES

如果将BMES标注系统中的中间字的标准更加细分，我们就能得到各种各样的变种标注。

HMM分词

HMM是隐马尔科夫模型的英语简写。HMM模型会记录上一个状态（即BMES）转移到一个状态的概率，和某个状态下出现某个词的概率，以及最初始的概率，最后使用Viterbi算法求出当前句子下最优的标注序列，得到分词结果。
维特比算法是一个动态规划的算法，实质上也是DAG的最短路径问题。
jieba分词中的新词发现模块(finalseg)使用的就是HMM分词

CRF分词

目前最优非深度学习的基于字的标注的分词算法就是CRF分词，最常用的CRF工具就是CRF++。
具体可以参考论文《基于条件随机场的汉语分词系统》.

LSTM分词

最近在学术界很火的分词模型都是基于BiLSTM+CRF的。

如上图所示，LSTM分词器一般由三个层组成，第一层是EmbeddingLayer，把汉字映射成字向量，第二层是FeatureLayer，通过双向LSTM从字向量中提取出位置特征，最后一层是InferenceLayer，CRF的推断层，通过维特比算法从位置特征和转移特征中求出最终的标注序列。

可以参考论文：

• Bidirectional LSTM-CRF Models for Sequence Tagging
• Long Short-Term Memory Neural Networks for Chinese Word Segmentation

LSTM分词的效果非常好，达到甚至超过了CRF的模型，但是缺点非常明显，一个是对未登录词无法通过添加词典的方式改善（基于标注的模型的通病），二个是速度非常慢，在绝大多数生产系统中无法使用。

混合模型

基于词典的模型和LSTM模型对于分词结果各有利弊，那么能不能将他们互相结合，达到结合两者优点的模型呢。
目前已经有人在探索如何将基于词典的模型和LSTM模型相结合，探索出新的分词方法。

DAG-LSTM+CRF

DAG-based Long Short-Term Memory for Neural Word Segmentation

CNN with word-embedding

Convolutional Neural Network with Word Embeddings for Chinese Word Segmentation

欢迎关注我的微信公众号

直觉与逻辑-二维码