目录
零、jieba中文分词库逻辑结构图
一、规则字典方法
1、最大长度匹配
思路简单，就是从前到后或者从后到前，依次找出最长的单词。如果找不到单词，就输出单个字。Trie树，即字典树，又称单词查找树或键树，是一种哈系树的变种，常被搜索引擎系统用于文本词频统计。这种数据结构能够帮我们更好地理解最大长度匹配法。
以大学生活动中心为例，分词结果如上图所示，正反向分词结果一致。然而，该方法的规则过于简单，就是贪心地寻找最长的单词，因此分词效果一般。以“北京大学生活动中心”为例，正向的分词结果就不好。
2、基于概率语言模型和动态规划的分词
（1）整体思路
该方法将分词转化为一个求最大概率的问题。输入是中文字符串C=c1,c2,...,cn，输出是词串S=w1,w2,...,wn。我们的目标是：给定C时，找到一种分词策略S，使得S的后验概率P(S|C)最大，根据贝叶斯公式展开：
其中，P(C|S) = P(S) = 1。因此，最终对于不同的S，只需要比较P(S)的大小。举例如下：
（2）P(S)的计算：概率语言模型
一元语言模型假设句子中各个单词是彼此独立的，因此一种分词策略出现的概率是每个词出现概率的乘积；二元语言模型假设句子中各个单词出现的概率依赖于上一个单词是什么；以此类推。
因此，我们可以提前用大语料库计算得出不同单词出现的概率或者条件概率，应用P(S)的计算中。
此外，在真实计算中，需要计算log(P(S))而不是P(S)，一是因为log函数时单调递增函数，不会改变不同P(S)的大小关系；二是因为，加法运算要比乘法运算快；最后也是最重要的，如果直接计算P(S)，概率值的连乘很可能出现栈溢出。
（3）找到所有可能的分词策略
对于句子中的每一个字，要依次向前遍历所有字，找到所有以该字结尾的单词并记录，其中该字本身也作为一个单词。以“南京市长江大桥中”的市为例，可以找到{{南京市}，{市}}。
利用该结果，我们可以生成下面的DAG词图，jieba中文分词就是利用该词图完成的。
（4）计算所有策略的P(S)（作业3）
这里找策略，计算P(S)需要用到维特比动态规划算法，我们先简单介绍一下维特比算法。维特比算法用于解决多步骤，每个步骤多选择的路径规划问题。以下图为例，计算S到E的最短路径。
首先，从前向后地对每一个步骤的每一种选择，计算当前选择的最短路径，并记录最短路径对应的前一节点。例如，对于B1，最短路径是S-A2-B1，前一结点是A2。依次计算从A到C的结点。接着，从后向前回溯最短路径的结点。例如C中路径最短的是C2，那么根据其记录的上一节点，依次进行回溯，就可以找到最短路径。复杂度就是边的个数。
对于我们的分词问题而言，句子中的每个字就是一个步骤，而刚才找到的以该字为结尾的单词的集合，就是不同的选择，如下图所示。
每一个字就是每一个步骤，每一个步骤有不同的选择。从前到后计算每一个步骤的每一个选择的最大对数联合概率，这里我们采用二元语言模型，并记录最大对数联合概率对应的对数概率值和前一个结点。最后，从后向前回溯每一个最大对数概率对应的结点。
二、基于统计机器学习的方法
1、隐马尔科夫模型
（1）模型结构
隐马尔科夫模型是一个双序列模型，结构如下图所示。
上面蓝色的序列为隐藏序列，下面橙色的序列为观测序列，我们需要通过观测序列，根据联合概率最大化的思路，去求出隐藏序列。注意，基于概率语言和动态规划的分词方法是最大化P(S)，而这里我们要最大化P(S,O)。
其中，观测序列O就是句子中的每一个字，而隐藏序列中每个结点都有四个状态BMES，分别代表B单词开头、单词中间、单词结尾和独立词。
（2）模型参数
模型有以下参数：
①状态：就是BMES标注法的四种状态。jieba分词中的状态则是BMES和词性相结合的256种状态，例如（B，n）代表以单词词首且为名词的字。
②观测：就是每一个字。
③初始概率：一个字作为一句话中第一个字的概率。
④状态转移概率：不同状态转化的概率，例如从(B,n)转化为(M,v)的概率。
⑤发射概率：从隐藏序列生成观测序列的概率，例如(B,n)生成“南”字的概率。
（3）P(S,O)的计算
以上三个概率的参数都需要从大语料库中进行统计。有了模型结构和参数，给出联合概率P(S,O)的计算公式如下：
找到使得联合概率最大的BMES隐藏序列，就完成了分词。
（4）viterbi动态规划算法求得隐藏序列状态（作业2）
此时隐藏序列各个步骤的选择有4个词位置状态B、M、E、S或者位置状态与词性的结合(B，n)、(S，v)等256个状态。依照viterbi算法的思路，以“广州塔”为例，假设只有位置的四种状态，分词步骤如下：
对于“广”字，计算对数的P(B,"广”)、P(M,"广”)、P(E,"广”)、P(S,"广”)，而由于第一个只可能是B或者S，所以P(M,"广”)=P(E,"广”)=0。对于“洲”字，分别计算对数联合概率最大的P(B,"洲”)、P(M,"洲”)、P(E,"洲”)、P(S,"洲”)，并分别记录下最大对数联合概率，以及对应的前一个隐藏结点状态。对于塔字同理。最后，找打最大的对数联合概率P(状态,“塔”)，并依次从后向前回溯记录的前一个结点。