别再死记硬背了！用Python手把手实现维特比算法，搞定中文分词（附完整代码）

用Python实战维特比算法：从动态规划到中文分词的完整实现

中文分词是自然语言处理的基础环节，而维特比算法则是解决这一问题的经典方法。本文将带你从零开始实现一个基于维特比算法的中文分词器，不仅理解算法原理，更能掌握实际编码技巧。

1. 维特比算法原理与最短路径问题

维特比算法本质上是一种动态规划算法，用于寻找最短路径。想象你站在一个城市的十字路口，需要选择一条到达目的地的最短路线。每个路口都有多条路径可选，而维特比算法能帮你高效地找到最优解。

算法核心思想可以概括为：

• 最优子结构：全局最优路径必然包含局部最优路径
• 重叠子问题：不同路径可能共享相同的子路径
• 递推求解：从起点开始逐步计算到每个节点的最短路径

在中文分词中，我们将文本看作由节点组成的图，每个节点代表一个可能的分词位置。例如句子"经常有意见分歧"可以表示为：

0-经-1-常-2-有-3-意-4-见-5-分-6-歧-7

2. 构建分词有向无环图(DAG)

要实现分词，首先需要构建表示所有可能分词方式的有向无环图。我们使用Python的字典结构来表示这个图：

# 词典和词频概率 word_dict = ["经常","有","意见","意","见","有意见","分歧","分","歧"] prob = {"经常":0.08,"有":0.04,"意见":0.08,"意":0.01,"见":0.005, "有意见":0.002,"分歧":0.04,"分":0.02, "歧":0.005} # 转换为负对数概率 import math prob_ln = {k: -math.log(v) for k,v in prob.items()} print(prob_ln)

输出结果为：

{'经常': 2.5257286443082556, '有': 3.2188758248682006, '意见': 2.5257286443082556, '意': 4.605170185988091, '见': 5.298317366548036, '有意见': 6.214608098422191, '分歧': 3.2188758248682006, '分': 3.912023005428146, '歧': 5.298317366548036}

接下来构建DAG图结构：

# 手工构建DAG图示例 graph = { 0: {0: (0, "")}, 1: {0: (20, "经")}, 2: {0: (2.52, "经常"), 1: (20, "常")}, 3: {2: (3.21, "有")}, 4: {3: (20, "意")}, 5: {2: (6.21, "有意见"), 3: (2.52, "意见"), 4: (5.30, "见")}, 6: {5: (3.9, "分")}, 7: {5: (3.21, "分歧"), 6: (5.29, "歧")} }

3. 实现维特比算法核心逻辑

维特比算法的实现可以分为三个主要步骤：

3.1 初始化数据结构

我们使用OrderedDict来记录每个节点的最优路径信息：

from collections import OrderedDict def viterbi_segment(text, graph): f = OrderedDict() # 保存每个节点的最优路径信息 f[0] = (0, 0) # (最短距离, 前一节点)

3.2 递推计算最优路径

遍历图中的每个节点，计算到该节点的最短路径：

for node in graph: if node == 0: continue # 找出到当前节点的最短路径 min_path = min( (cost + f[prev_node][0], prev_node) for prev_node, (cost, word) in graph[node].items() ) f[node] = min_path

3.3 回溯找出最优分词

从终点开始回溯，找出完整的最优分词路径：

# 回溯找出最优路径 path = [] last_node = len(graph) - 1 while last_node != 0: path.append(last_node) last_node = f[last_node][1] path.append(0) path.reverse() # 提取分词结果 seg_result = [] for i in range(len(path)-1): word = graph[path[i+1]][path[i]][1] seg_result.append(word) return seg_result

4. 完整实现与效果验证

将上述代码整合成完整的分词函数：

def word_segmentation(text): # 词典和概率初始化代码... # 构建DAG图代码... # 维特比算法实现 f = OrderedDict() f[0] = (0, 0) for node in graph: if node == 0: continue min_path = min( (cost + f[prev_node][0], prev_node) for prev_node, (cost, word) in graph[node].items() ) f[node] = min_path # 回溯路径 path = [] last_node = max(graph.keys()) while last_node != 0: path.append(last_node) last_node = f[last_node][1] path.append(0) path.reverse() # 提取分词结果 seg_result = [] for i in range(len(path)-1): word = graph[path[i+1]][path[i]][1] seg_result.append(word) return "/".join(seg_result) + "/"

测试我们的分词器：

text = "经常有意见分歧" print(word_segmentation(text))

输出结果为：

经常/有/意见/分歧/

5. 性能优化与工程实践

在实际应用中，我们还需要考虑以下几个优化点：

5.1 自动构建DAG图

手工构建DAG图不现实，我们需要实现自动构建：

def build_dag(text, word_dict, prob_ln): dag = {} text_length = len(text) for i in range(text_length + 1): dag[i] = {} max_len = min(4, text_length - i + 1) # 最大词长设为4 for j in range(1, max_len + 1): word = text[i:i+j] if word in word_dict: dag[i][i+j] = (prob_ln[word], word) else: # 未登录词处理 dag[i][i+j] = (20, word) # 设置一个较高的默认代价 return dag

5.2 处理未登录词

对于词典中没有的词，可以采用以下策略：

• 使用字符级别的分词
• 结合统计信息估算概率
• 引入新词发现机制

5.3 算法复杂度分析

维特比算法的时间复杂度为O(N×K²)，其中：

• N是句子长度
• K是每个节点的最大前驱节点数

在实际应用中，通过限制最大词长(如4个字符)，可以将K控制在较小范围内，保证算法效率。

6. 与其他分词算法对比

维特比算法在中文分词中表现优异，但也有其局限性：

在实际项目中，可以根据需求选择合适的算法，或者组合多种方法达到更好的效果。

7. 扩展应用与进阶方向

掌握了维特比算法在分词中的应用后，你还可以将其扩展到其他场景：

• 词性标注：在分词基础上标注每个词的词性
• 命名实体识别：识别文本中的人名、地名等实体
• 语音识别：寻找最可能的词序列
• 机器翻译：选择最优的翻译结果

对于想深入研究的开发者，以下几个方向值得探索：

• 结合深度学习模型改进传统算法
• 实现增量式分词处理长文本
• 开发多语言分词系统
• 优化算法在分布式环境下的性能

中文分词看似简单，实则包含许多精妙之处。通过亲手实现维特比算法，不仅能加深对动态规划的理解，还能掌握将数学公式转化为实际代码的能力，这对提升算法工程能力大有裨益。