自然语言处理|MP最大概率中文分词

课程作业，只完成了最基本的算法，还有不足的地方，例如一些多位数的分词方式等，大家可以适当参考。

 

1.语言模型说明

语言模型为bigram，保存在一个（n*n）的numpy矩阵LM中，训练过程：

•  第一次遍历训练语料构建词表，即保存所有出现过的词
•  第二次遍历训练语料构建二维计数表，bigram[i][j] = count(wi-1,wi)
•  平滑（由于运算量较大，且测试较小所以平滑运算直接在后面的词表构建过程中单独进行）

 

       Laplace平滑仅在计算的二维计数表的每一个位置进行+1操作处理后极大似然估计得到概率：

                                            

       KN平滑处理后某个位置的概率为

                         

其中D=0.75，N1+ 代表大于1的gram数

                                                                 .

 

2.词网络构建说明

词网络使用图的数据结构构成：

因为句子是一个有序的序列，所以认为节点图中的开头是固定的，节点转移方向也是固定的，所以通过指针为其添加了方向性，代码实现时定义了节点类Node存放节点信息：

                                                  

 

3.词网络和最大概率算法的实际使用

考虑到对长句而言其词网络结构可能会很复杂，所以对节点做出几点调整：

1. prev指针仅指向带给当前节点最大概率的节点，即每个节点仅有一个入点，该入点 即为其BAW
2. next指针没有实质性作用，故删除
3. prob属性由二元概率p（wi|wi-1）集合改为累计概率p（wi|wi-1）p(wi-1|wi-2)…p(w1|<s>)

 

主要思想是令每个节点的累计概率最大，当有多个自由节点（next为空，后删除next后存入数组pre）满足node.endpos == w(startpos) 时对其携带的概率进行运算

                                      Node.prob * p(wi|wi-1)

进行比较后取使其最大的节点为当前节点的BAW。如此从最后一个节点“</s>”（实际中使用“\n”代替了’</s>’）向前递归则可以获得累计概率最大的分词结果，下图给出了节点“的”的前向结果（途中虚线表示节点“的”的前向节点通过比对四个自由节点带来的实际最大累计概率产生）：

5.未登陆词处理

       仅当一个startpos=i时不存在候选词时认为该位置存在一个未登录词。由于词表中没有出现过所以其对应的kn平滑计算结果会出错，所以使用词表中的最小概率值代替了未登录词的概率。

 

实现代码：https://github.com/dorren002/NLP-curriculum-design/blob/master/ChiMPSeg/chiMPSeg.py

参考书籍：

【1】宗成庆，统计自然语言处理

【2】Speech and Language Processing