NLP-最短路径分词
汉语分词（二）
N-最短路径方法
1.非统计粗分模型
2.统计粗分模型
一. 非统计粗分模型：
已知：
①. 没有空格分割的文本串： \[ S = c_1c_2...c_n \] ②. 词库
1 建图:
我们的目标就是想要得到X种对文本串的粗分结果。
由于我们要使用的是求最短路的方法，所以我们需要建图，然后用Dijkstra的改版来求出N类最短路径。这N类最短路径的路径长度要求是严格递增的，而长度相同的那些路径被我们归到了一个类中。所以最终我们得到的路径数X >= N。
我们认为，文本串中的单个字都是词，以他们为边，建图。结点为：\(V_0,V_1...V_n\)\(，其中\)$ V_{k-1}$ 与\(V_{k}\)之间的边为字\(c_k\)。而边得权值有两种方式：一种是简单的我们给他们规定都相同，都是1，这就是非统计粗分模型，而另一种就是根据一些统计等的方法，给他们规定一个有意义的值，被称为是统计粗分模型。
同时，如果文本串中\(c_ic_{i+1}...c_j\)是词库中的词的话，我们就连一条从结点\(V_{i-1}\)到结点\(V_j\)的边，这样就把文本串中所含有的词库里的词也表示到了图上。
举个例子：
文本串：研究生研究生命的起源
词库：研究生 研究 生命 起源
建图： 
如图所示，黑色数字为边的权值，红色数字为节点的编号。
如上图所示，我们就建好了一个图.
2 算法运行示意：
我们为了得出N大类粗分结果，我们采用的方法是给每一个结点即一个路径前驱表，在表里，用N个大模块，从上到下采用路径长度递增来排列，而同一大模块里，包含着那些路径长度相等的各个路径。
这是我们的最初的想法，然而，是否需要与路径对应的结点编号序列全部存在表里呢？显然这个太麻烦了，聪明的小明这时候举手说：以前遇到有关路径的问题，我们都是只需要记住前驱，然后再递归的print。不得不说，小明说的太对了，我们在这里就是这么干的。
前驱中（a，b），a表示是结点a，b表示是编号b，至于具体选择结点a编号b中的哪一个不影响路径长度，只代表了该路径长度下的不同路径而已。
首节点没有前驱节点。
节点1只有一个前驱节点是节点0，这里我们设其对应的前驱编号为0，表示该前去为首节点。
table1：
节点2的前驱节点可以是节点0+编号0：则长度为1，或是节点1+节点1对应的table1中的编号1
table2： 
之后的以此类推
table3： 
table4： 
table5： 
table6： 
table7： 
table8： 
table9： 
table10： 
这样，我们根据写个table就可以递归的找出那些最短的路径，其中一条长为5的最短路径是这样滴： 结点10 -> 结点8（根据8,1，接下来到table8中找编号1对应的分支路径） -> 结点7 -> 结点6 -> 结点3 -> 结点0 划分的词：研究生|研究生|命|的|起源
二.统计粗分模型:
边长都设置成1，当图的结构比较复杂，N选取的不是很小的时候，会出现最终粗分结果数太多的恶劣影响！我们知道，我们之所以想要去粗分，就是为了给下一步的未登录词以及歧义切分打下一个坚实的基础，采取了宁可错杀一千不可放过一个的原则，才会去设置N大类，但是，却把太多可能的切分都给列出来。另外并非每个词的出现几率都是相同的，一些常用，一些不常用这在生活中很常见。
归根结底还是这个边长的问题，对此，提出了统计粗分模型。
为此，在经过了大量的实验之后，经过统计，对于一个词的出现概率我们有了一个比较客观的认知，不妨设它为：P(\(W_i\)),\(W_i\)是一个词。
这时经过了权值变更成词的概率后，我们开始在数学上面推导一下最后我们所期望的训练结果。
我们将N-最短路径法转为求：N个切分出的词集W，使得在已知文本串的情况下，该N个切分的概率值是最大。 进一步推导： \[ P(W|C) = \frac{P(W)P(C|W)}{P(C)} \] P(C )：文本串的概率，这是一个和分词无关的常数.
P(C|W)：将切分合成为原文本串，这个概率为1，就是将切分出来的次重新首尾连接.
所以最后我们要求的那最大的N个P(W|C)对应的W就变成了求N个最大的P(W)对应的W。
由(2)，我们又可以得出：
\(P(W) = \quad \prod_{i=1}^m P(W_i)\)，其中|W| = m
同时，为防止多个概率连乘在计算机中表示为0，转化成对数形式：
\(P^*(W) = -lnP(W) = \sum_{i = 1}^m[-lnP(w_i)]\)
于是乎，我们边长变成了\(-lnP(w_i)\)， 而求最小的N个P(W)也变成了求最小的N个\(P^*(W)\)