中文分词

用过的中文分词有jieba，hanlp，word，grid，standford.nlp。

从分词原理的直接到间接说起。

1. 基于字典的分词 。 字典给出了词和词频。在word中有正向/逆向/双向最大匹配算法。

原则是：颗粒度越大越好；切分结果中非词典词越少越好，单字字典词数越少越好；总体词数越少越好。

缺点是： 无法识别新词和歧义

原理是：从词的前向后依次扫描，依次确定以第n个字开始的最长词（对第n个字开始扫描时，第一次扫描的窗口长度为字典中最长词的长度）。

双向：前向后向各做一次，以上面的原则，选出一个作为结果。

通常：MMSEG ，正向最大匹配为主，多种消除歧义的规则为辅。“匹配算法”是说如何根据词典里保存的词语，对要切分的语句进行匹配（正向？逆向？粒度？）；“消除歧义的规则”是说当一句话可以这样分，也可以那样分的时候，用什么规则来判定使用哪种分法。而重点就是这两项用什么样的计算方法去衡量。

2. grid：三段式机械分词以及基于信息熵的新词发现

原则：出现次数足够多；内部凝固程度高（ABC的凝合程度是min( P(ABC)/P(A)*P(BC)，P(ABC)/P(AB)*P(C))）；自由运用程度（丰富的左邻字集合和右邻字集合，用信息熵来衡量，即左邻字信息熵和右邻字信息熵中的较小值）。

方法：1. 获取候选词（所有长度<n 的词）。2. 计算出现频数、凝固程度和自由程度。3. 各设定一个阈值，提取出所有满足阈值要求的候选词。

3. 基于统计的。

3.1  jieba  DAG算法+HMM新词发现

基于字典构建一个trie树（单词查找树）（是前缀树，一个词语的前面几个字一样，就表示他们具有相同的前缀，就可以使用trie树来存储，具有查找速度快的优势）特点：

第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。

第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。

第三：每个单词的公共前缀作为一个字符节点保存。每个节点的所有子节点包含的字符都不相同

给定一个待分词的句子和trie树，生成有向无环图。 根据给定的词典进行查词典操作, 生成几种可能的句子切分。DAG记录的是句子中某个词的开始位置, 从0到n-1(n为句子的长度), 每个开始位置作为字典的键, value是个list, 其中保存了可能的词语的结束位置(通过查字典得到词, 开始位置+词语的长度得到结束位置)。

HMM 新词发现 ： HMM：输入是一个序列，输出也是一个序列，输出的序列代表了输入序列的隐含意义（分类）。在计算的过程中，需要依赖几个定义好的概率矩阵做计算。在分词中，输入为字的组合（一句话），输出为BMES的组合，代表每个字的隐含状态。

HMM的假设：输出独立性假设和马尔可夫性假设。

3.2 CRF分词

条件随机场则使用一种概率图模型，具有表达长距离依赖性和交叠性特征的能力，能够较好地解决标注(分类)偏置等问题的优点，而且所有特征可以进行全局归一化，能够求得全局的最优解。

关于CRF，现在还不是特别懂，无法组织出准确的语言来表达。觉得不错的资料如下：

https://www.zhihu.com/question/35866596

http://www.jianshu.com/p/55755fc649b1

https://wenku.baidu.com/view/69e8fc1afad6195f312ba620.html

http://www.cnblogs.com/kemaswill/p/3427422.html