本文主要是介绍NLP-词性标注+动态规划实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、计算
1.实现目标
2.训练数据
3.计算原理
二、实现
1.训练数据
2.构建参数
3.统计数据
4.维特比算法
①定义数组
②计算第一列分数
③循环计算后面的分数（举例）
④找最优解
一、计算
1.实现目标
给出一句话，输出每个词的词性
2.训练数据
类似于下面的数据，左边是句子中的每个词，右边是对应的词性，其中句号代表一句话结束。
3.计算原理
要求P(词性|句子)，根据贝叶斯定理，求P(句子|词性) * P(词性)即可
词性记作：z1, z2, z3, z4,......（共有N个词性）
句子记作：w1, w2, w3, w4......（共有T个单词）
因此求的是P(w1, w2, w3, w4...... | z1, z2, z3, z4,......) * P(z1, z2, z3, z4,......)
视为条件独立，使用bigram语言模型：
P(w1 | z1) * P(w2 | z2) * ..... * P(z1) * P(z2 | z1) * P(z3 | z2) * ......
取对数，因此最终需要求的是：
二、实现
对于上式，第一部分发射概率记作A，第二部分记作pi，第三部分状态转移概率记作B
1.训练数据
导入，并且把每个单词及对应的词性统计为一个词典，便于通过id就能找到单词及词性。
2.构建参数
根据公式，发射概率A的行和列分别是词性数、单词数；pi只有一行，是词性数；状态转移B的行和列均为词性数。对这三个参数进行初始化：
3.统计数据
计算概率需要首先统计每一个单词，每个标签的出现数量，然后除以总数即可得到概率：
4.维特比算法
假如我们对每一个单词的每一个词性都进行概率计算，那么时间复杂度是指数级的。也就是词性数量的N次方。于是我们通过维特比算法进行计算：
①定义数组
在这里，动态规划的核心是，计算出上一个词的所有词性的分数，选择最高的分数作为基础，计算下一个词的分数，以此类推。因此，需要定义两个数组：
一个存储计算出来的分数（每一列的分数都是基于上一列的最高分进行计算的）：这个数组是最关键的数组，需要确定好里面数据是什么：dp[ i ] [ j ]：第j个词性给到第i个词的时候的最好分数。这个分数是基于前一列的最大值进行计算的。
另一个数组存储分数所对应的位置。
②计算第一列分数
根据上面的公式，第一列分数不涉及状态转移概率。
③循环计算后面的分数（举例）
对于每一个单词，每一个词性，先给一个小的分数，便于更新。
循环计算举例：
计算第二个单词eat
已经有了第一个词dog的数据，对于dog这个词，noun给到dog时，分数是0.6，prep给到dog时，分数是0.1
计算noun：
分数 = 上一行的noun分数 + noun转移到noun的分数 + 根据noun发射单词"eat"的分数
假设是：0.6 + 0.2 + 0.1 = 0.9
分数比原先的-999大，进行更新
对分数的位置进行更新， 此时是第0个noun得到的分数最大，于是在对应位置记录“0”
"noun"计算完毕。
同样的方式计算prep及verb的概率，假设verb得到的最终分数是1.5，比原来的分数大，则更新两个表：
代码如下：
④找最优解
dp数组中，最后一行，是我们最终的全局最优分数。选择最大的分数对应的下标。
这个下标对应到第二个数组的位置，这个位置包含的信息，就是上一列的最大值所在的位置。（见上面的计算方式）
反向循环记录最优索引即可得到最终结果。
这篇关于NLP-词性标注+动态规划实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
