中分分词难点：
1. 歧义切分
2. 未登录词识别
语言模型
对于一句话s，由词\(w_1,w_2,...,w_n\)组成。长度为n。句子概率可以表示为
\(P(s)=P(w_1,w_2,..,w_n)\)
根据条件概率公式：
\[P(A,B)=p(A|B)\cdot P(B)
\]
\(P(w_1,w_2,..,w_n)=p(w_1) \cdot p(w_2 \vert w_1)\cdot p(w_3\vert w_2,w_1)...p(w_n\vert w_1,w_2,...,w_{n-1})\)
马尔科夫假设：假设任意一个词Wi出现的评率只同它前面的词Wi-1有关
根据马尔科夫假设，有
\(P(s)=P(w_1)\cdot P(w_2\vert w_1)\cdot P(w_3\vert w_2)...P(w_n\vert w_{n-1})\)
这个公式对应bi-gram，假设一个词由前面\(N-1\)词决定，对应的模型被称为N-gram model。
在计算\(p(w_2\vert w_1)=\frac{p(w_2,w_1)}{p(w_1)}\)时，
\((w_2,w_1)\)频数为0是，条件概率为0，不合理
\((w_2,w_1)\)和\(w_1\)频数都为1时，条件概率为1，不合理，所以需要添加平滑策略。
加1平滑：
\[P(w_i)=\frac{Count(w_i)+1}{N + V}
\]
\[P(w_i \vert w_{i-1})=\frac{Count(w_i,w_{i-1})+1}{Count(w_{i-1}) + V}
\]
差值平滑：
\[P_{interp}(w_i\vert w_{i-1})=\lambda_iP(w_i\vert w_{i-1})+(1-\lambda_i)P(w_i)
\]
机械切分
根据语料库，计算词频，简单计算作为词的权重。
- 基于词库构建词图
- 基于语料，统计每条边的条件概率
- 计算所有可能的概率，得到概率最高的路径
对于词图，使用start_node和end node表示，如下表，
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| start node | S | 我 | 喜 | 喜欢 | 欢 | E |
| end node | 1 | 2，3 | 4 | 5 | 5 | 5 |
黑色数字：节点序号
绿色数字：节点权重
红色数字：从节点E到当前节点的最优路径权重。
根据动态规划，从后往前，逐步计算，终止节点到每个节点的最优路径。
比如：我的最优路径path(我)是weight(我)+ max(path(喜欢), path(喜)).
词库构建词图：
1. 找到句子中所有的单词用字典表示。all_words
{0: [0], 4: [4], 1: [1], 2: [2, 3], 3: [3]}
key 表示词头， value表示词尾。
2. 找到start node中node对应的终止节点索引。
对于index 1 我，计算end node idx
sum([all_words[0],all_words[1])=2
2 + 下一idx对应的列表长度 list(range(len(all_words[2])))
最优路径：
{5: (0, 5), 4: (1, 5), 3: (4, 5), 2: (3, 4), 1: (5, 3), 0: (5, 1)} 括号内容为(路径权重，终止节点)
