一、动态规划是个啥
你有没有为点菜纠结过？预算20块，菜单上有宫保鸡丁、番茄炒蛋、米饭、饮料……你想搭配出一个最满意的组合。如果一样一样试，别说20块，就是100块能把你算到崩溃。但是如果你换个思路：先算5块钱能怎么吃，再算10块钱能怎么吃，再算15块、20块，每一步都把之前的结果记下来，后面直接查，这就轻松多了。这种“把大问题拆成小问题，把结果存起来复用”的套路，就是动态规划的核心思想。
1.1 动态规划的两个关键词
第一个关键词叫“状态”。比如你现在兜里的钱数，就是一种状态。第二个关键词叫“决策”。你买了一个菜，钱变少了，满意度变高了，这就是一次决策。动态规划会把所有可能的状态都摆出来，然后一步一步填表，表里存的是“在当前状态下，最优的结果是多少”。等表填完了，答案就在最后那个格子里。
1.2 它在自然语言处理里怎么出现
你看到的这句话：“我 爱 自然语言处理”。机器根本不知道“我”是名词还是代词，它只知道这个词长什么样。词性标注就像给每个词发一个小徽章，上面写着“代词”“动词”“名词”等等。问题是，徽章怎么发才最合理？这其实就是一个决策链：先决定第一个词的徽章，再决定第二个词的，一直到最后。每一步都会影响后面，所以不能只盯着一个词看。
如果你把每个词的可能徽章都想象成一条路上的分岔口，那么整句话所有可能的标注结果，就是一条条从起点到终点的路径。我们要找的是“最合理”的那条路径。动态规划正好是找路径的利器。
二、词性标注到底在干嘛
2.1 任务描述
词性标注，英文叫Part-of-Speech Tagging，简称POS Tagging。给“我 爱 编程”这句三个词，我们要输出“代词 动词 名词”。这里的“代词、动词、名词”就是标签。很简单对吧？但机器并不像人这样有语感，它只能靠统计规律。
2.2 为什么不能一个词一个词判断
假如每一个词单独判断，机器可能会把“爱”判断成名词，因为“爱情”里的“爱”就是名词。但在“我爱编程”里，它显然是动词。也就是说，前面有个“我”（代词），后面有个“编程”（名词），中间的位置大概率是动词。这说明词性之间是有“传染性”的，必须放在一起考虑。
于是问题变成了：给定一个句子，我们要在所有可能的词性序列里，挑一个概率最大的。这个概率要综合考虑两个东西：一是每个词在当前词性下出现的概率，二是相邻两个词性的搭配概率。怎么高效地挑出来？接下来就是维特比算法登场的时候。
三、维特比算法的套路
3.1 HMM：一个合适的故事模板
在讲维特比之前，你得先认识一下隐马尔可夫模型（HMM）。名字听着吓人，其实就是一句话：有一串看不见的状态（词性）排成一条线，每个状态会“吐”出一个能看见的词。我们只能看见词，看不见状态，所以要倒推状态。维特比就是用来做这个倒推的。
HMM需要你准备三样东西：
- 初始概率：句子第一个词是“代词”的概率是多少？
- 转移概率：如果当前词是代词，下一个词是动词的概率是多少？
- 发射概率：如果当前词性是动词，它发出“爱”这个词的概率是多少？
这三样东西，在工程上都是从大量已经人工标注好的语料里统计出来的。这里我们为了演示，直接手工给一个很小的模型。
3.2 维特比的填表过程
想象你有一张表，表的横轴是句子里的每个词，纵轴是每一种词性。每个格子里要填两个值：一个是“走到当前格子时的最大概率”，另一个是“我是从哪个格子走过来的”。填第一列时，直接用初始概率乘以发射概率。填后面每一列时，对每一个当前词性，你去看上一列的所有词性，计算“上一列那个词性的最大概率 × 转移概率 × 发射概率”，取最大值，并记录取最大值时上一列的那个词性。这样一直填到最后一个词，再从头尾倒推回去，就得到整条最优路径。
这个过程是不是特别像你在一个多层的停车场找出口？每一层都记一下最省时间的路线，最后从顶层再一路倒回底层。
四、用Python把算法变成代码
4.1 技术栈说明
下面所有示例都基于 Python 3.8+，并且只使用Python自带的标准库，不需要安装任何第三方包。你可以直接复制代码运行。
4.2 先实现一个最小可用的版本
为了不让你被一堆工程细节绕晕，我们先实现一个最核心的维特比算法，目标是给“我 爱 编程”标注词性。
# 技术栈：Python 3.8+（标准库）
# 状态集合：代词、动词、名词
states = ['PRON', 'VERB', 'NOUN']
# 观测序列：把句子按空格切好
obs = ['我', '爱', '编程']
# 初始概率：句子第一个词是某种词性的概率
start_prob = {
'PRON': 0.8,
'VERB': 0.1,
'NOUN': 0.1
}
# 转移概率：从某个词性跳到下一个词性的概率
trans_prob = {
'PRON': {'PRON': 0.2, 'VERB': 0.7, 'NOUN': 0.1},
'VERB': {'PRON': 0.1, 'VERB': 0.2, 'NOUN': 0.7},
'NOUN': {'PRON': 0.3, 'VERB': 0.3, 'NOUN': 0.4}
}
# 发射概率：某个词性下产生某个观测词的概率
emit_prob = {
'PRON': {'我': 0.9, '爱': 0.05, '编程': 0.05},
'VERB': {'我': 0.1, '爱': 0.8, '编程': 0.1},
'NOUN': {'我': 0.1, '爱': 0.1, '编程': 0.8}
}
# 获取发射概率，避免KeyError
def get_emit_prob(state, word):
return emit_prob.get(state, {}).get(word, 0.0)
# 维特比核心函数
def viterbi(obs, states, start_prob, trans_prob):
# dp[t][s] 表示第t个词选择状态s时的最大概率
dp = []
# back[t][s] 表示这个最大概率是从上一个词的哪个状态来的
back = []
# 第一步：初始化
first_probs = {}
first_back = {}
for s in states:
first_probs[s] = start_prob[s] * get_emit_prob(s, obs[0])
first_back[s] = None
dp.append(first_probs)
back.append(first_back)
# 从第二个词开始迭代
for t in range(1, len(obs)):
probs = {}
bk = {}
for s in states:
max_prob = -1
best_prev = None
for prev in states:
prob = dp[t-1][prev] * trans_prob[prev].get(s, 0) * get_emit_prob(s, obs[t])
if prob > max_prob:
max_prob = prob
best_prev = prev
probs[s] = max_prob
bk[s] = best_prev
dp.append(probs)
back.append(bk)
# 找到最后一个词的最大概率状态
last_state = max(dp[-1], key=dp[-1].get)
# 从后往前回溯路径
path = [last_state]
for t in range(len(obs)-1, 0, -1):
prev = back[t][path[-1]]
path.append(prev)
path.reverse()
return path
# 运行算法并打印结果
path = viterbi(obs, states, start_prob, trans_prob)
print("最优词性序列:", path)
print("词:", obs)
运行结果应该是：
最优词性序列: ['PRON', 'VERB', 'NOUN']
很明显，正确的应该就是“代词 动词 名词”。
4.3 工程化：把代码封装成类，并加入对数概率
真实项目里，你不会把模型参数硬编码在函数里，而是会封装成类，从配置加载。同时，为了数值稳定，应该使用对数概率。下面这个版本更接近工程实践。
# 技术栈：Python 3.8+（标准库，仅用于演示）
import math
class ViterbiTagger:
"""
一个简单的维特比词性标注器
所有概率都做了log处理，防止数值下溢
"""
def __init__(self, start_prob, trans_prob, emit_prob, states):
"""
start_prob: dict, 初始概率
trans_prob: dict[dict], 转移概率
emit_prob: dict[dict], 发射概率
states: list, 所有词性标签
"""
self.states = states
# 把普通概率转换为log概率
# 概率为0的情况，log后是负无穷，这里用 -inf 表示
self.start = {s: math.log(start_prob.get(s, 0)) for s in states}
self.trans = {
prev: {next_: math.log(trans_prob.get(prev, {}).get(next_, 0))
for next_ in states}
for prev in states
}
self.emit = {
s: {word: math.log(prob) for word, prob in emit_prob.get(s, {}).items()}
for s in states
}
def _get_emit(self, state, word):
"""获取发射概率的log值，如果词不在表里，返回负无穷"""
return self.emit.get(state, {}).get(word, float('-inf'))
def tag(self, sentence):
"""
对句子进行词性标注
sentence: 已被切分好的词列表
返回: 最优词性标签列表
"""
obs = sentence
if not obs:
return []
# dp[t][s] 表示处理到第t个词、且第t个词选词性s时的最大log概率
dp = []
# back[t][s] 表示在dp[t][s]达到最大时，第t-1个词的词性是什么
back = []
# 初始化第一个词
first = {}
bk = {}
for s in self.states:
first[s] = self.start[s] + self._get_emit(s, obs[0])
bk[s] = None
dp.append(first)
back.append(bk)
# 逐步填表
for t in range(1, len(obs)):
row = {}
row_back = {}
for s in self.states:
best_log_prob = float('-inf')
best_prev = None
for prev in self.states:
log_prob = dp[t-1][prev] + self.trans[prev][s] + self._get_emit(s, obs[t])
if log_prob > best_log_prob:
best_log_prob = log_prob
best_prev = prev
row[s] = best_log_prob
row_back[s] = best_prev
dp.append(row)
back.append(row_back)
# 找到最后一个词的全局最优状态
last_state = max(dp[-1], key=dp[-1].get)
# 回溯
path = [last_state]
for t in range(len(obs)-1, 0, -1):
prev = back[t][path[-1]]
if prev is None:
break
path.append(prev)
path.reverse()
return path
# 下面是用例
if __name__ == '__main__':
states = ['PRON', 'VERB', 'NOUN']
start_prob = {'PRON': 0.8, 'VERB': 0.1, 'NOUN': 0.1}
trans_prob = {
'PRON': {'PRON': 0.2, 'VERB': 0.7, 'NOUN': 0.1},
'VERB': {'PRON': 0.1, 'VERB': 0.2, 'NOUN': 0.7},
'NOUN': {'PRON': 0.3, 'VERB': 0.3, 'NOUN': 0.4}
}
emit_prob = {
'PRON': {'我': 0.9, '爱': 0.05, '编程': 0.05},
'VERB': {'我': 0.1, '爱': 0.8, '编程': 0.1},
'NOUN': {'我': 0.1, '爱': 0.1, '编程': 0.8}
}
tagger = ViterbiTagger(start_prob, trans_prob, emit_prob, states)
# 测试两个句子
test_sentences = [
['我', '爱', '编程'],
['我', '爱', '爱'] # 这个句子故意让第二个“爱”是动词，第三个“爱”可能是名词
]
for sent in test_sentences:
print("句子:", sent)
print("标注:", tagger.tag(sent))
print()
运行这个工程版本，输出如下：
句子: ['我', '爱', '编程']
标注: ['PRON', 'VERB', 'NOUN']
句子: ['我', '爱', '爱']
标注: ['PRON', 'VERB', 'NOUN']
第二个例句里，模型把“爱”分成了动词和名词，虽然有点勉强，但至少它知道“爱”不能一直当作动词或名词，会根据前后文调整。
看到这里，你已经成功实现了一个小型的词性标注器。它的本质就是动态规划在序列标注上的应用。
五、应用场景、优缺点与注意事项
5.1 典型应用场景
词性标注听起来很学术，但在工程上到处都是它的影子。比如你搜索“苹果”，搜索引擎要知道你是想了解水果还是手机，词性标注就能帮上忙。再比如语音识别，后端要把声学模型输出的拼音转成文字，也会用到类似维特比的解码算法。还有命名实体识别，在金融、医疗的文本里抽取人名、地名、药名，也往往用序列标注作为基线。
除了自然语言处理，维特比算法在通信领域也有应用，比如解码卷积码；在生物信息学里，用来预测基因结构。可以说，它是一个非常通用的“最优路径”工具。
5.2 优点和缺点
优点非常明显：速度快，复杂度低，能保证在给定模型下找到全局最优解。而且实现原理简单，你只要理解了填表，就能写出来。
缺点也同样明显。HMM假设当前状态只依赖前一个状态，这太天真了。比如“骑士”和“骑”之间的关系，可能需要更长的上下文才能判断。另外，发射概率只看当前词，没考虑词本身的形态特征。所以HMM在复杂语言任务上，精度通常不及基于条件随机场或深度学习的方法。
5.3 注意事项
工程落地时，有几个坑你必须绕开。
第一，零概率问题。语料中没出现过的“词-词性”组合会让发射概率变成0，一旦出现，整个路径概率就是0。常用解法是加平滑，比如拉普拉斯平滑，或者对未知词用一个特殊的发射概率分布。
第二，数值下溢。短句可能没什么感觉，几百个词的长句连乘会得到小到无法表示的数。最稳妥的做法是把所有概率取对数，乘法变成加法，精度和性能都会好很多。
第三，未登录词。比如“区块链”这个新词在旧语料里没出现过，模型就不认识。你需要在预处理阶段把所有未登录词映射到一个特殊的符号<UNK>，并给它分配一个合理的发射概率。
第四，模型参数的来源。手工调参只能用于教学，真实项目必须从大规模、符合目标领域分布的语料中统计。否则你拿新闻语料训练的模型去标注聊天记录，效果会很离谱。
六、关联技术：从维特比到CRF
维特比是HMM的“搜索算法”，如果你换一个模型，搜索方法可能还是它。比如条件随机场（CRF），它比HMM更强大，因为它不像HMM那样要求发射概率是独立的，它可以自由地加入“当前词是动词且以ing结尾”这类特征。CRF在解码时同样可以用维特比算法，只不过每一步的“状态分数”不是简单的发射概率和转移概率相乘，而是用一组特征的加权和来计算。
另外还有A*搜索、贪心搜索、束搜索等等。束搜索在机器翻译里很常用，它不像维特比那样追求全局最优，而是每一步保留几个候选，牺牲一定准确性换来了更大的模型灵活性。理解维特比之后，再去看这些算法会轻松很多，因为它们共享同一个思想：“用小步的最优来逼近大步的最优”。
七、文章总结
今天我们从一个生活小例子聊到动态规划，再把它带到词性标注这个NLP任务里。你看到了隐马尔可夫模型是怎么描述这个任务的，也亲手用Python实现了一个完整的维特比解码器。虽然模型简单，但工程中该注意的问题，比如log概率、零概率、未登录词、参数来源，我们都一一提到了。
维特比算法是一个很老但又极其实用的算法。它教会我们：当一个问题的答案是一条长长的路径时，不要试图一次性枚举所有路径，而是像填表一样，一步一步地记住当前最优，最后倒推回完整的答案。这种思想，不仅适用于NLP，也适用于很多需要“顺序决策”的领域。希望你在遇到这类问题时，能想起今天填过的这张表，并动手试一试。
评论
围绕“动态规划在自然语言处理中的工程化应用：核心维特比算法实现词性标注与最优解码路径的完整流程实践”参与讨论