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

在自然语言处理领域，分词是文本分析的第一步。想象一下，当你拿到一串连续的中文字符"经常有意见分歧"时，如何让计算机理解哪些字应该组合成词？这就是我们今天要解决的核心问题。不同于传统的字典匹配方法，我们将采用维特比算法——这个源自通信领域的动态规划方法，能够优雅地解决中文分词中的最优路径问题。

1. 动态规划与维特比算法基础

维特比算法的本质是动态规划在序列问题中的应用。它通过逐步构建最优解，避免了暴力搜索带来的计算爆炸问题。让我们用一个简单的例子理解其核心思想：

假设我们要从城市A到城市D，中间经过B和C两个中转站，各段路径的距离如下：

graph = {
    'A': {'B1': 5, 'B2': 3},
    'B1': {'C1': 6, 'C2': 2},
    'B2': {'C1': 1, 'C2': 4},
    'C1': {'D': 3},
    'C2': {'D': 5}
}

传统方法会计算所有路径的组合：

• A→B1→C1→D = 5+6+3 = 14
• A→B1→C2→D = 5+2+5 = 12
• A→B2→C1→D = 3+1+3 = 7
• A→B2→C2→D = 3+4+5 = 12

维特比算法则采用更聪明的方式：

1. 到达B1的最短路径：A→B1 (5)
2. 到达B2的最短路径：A→B2 (3)
3. 到达C1的最短路径：min(5+6, 3+1) = 4 (A→B2→C1)
4. 到达C2的最短路径：min(5+2, 3+4) = 7 (A→B1→C2)
5. 到达D的最短路径：min(4+3, 7+5) = 7 (A→B2→C1→D)

关键优势 ：每步只保留到达当前节点的最短路径，大幅减少计算量。

2. 中文分词的图表示

将中文句子转化为有向无环图(DAG)是应用维特比算法的前提。对于句子"经常有意见分歧"，我们需要：

1. 构建词典：["经常","有","意见","分歧"]

2. 定义节点位置：

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

3. 创建边表示可能的词语：

dag = {
    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, "歧")}
}

其中边的权重采用负对数概率：

• P("经常")=0.08 → -log(0.08)≈2.52
• 不在词典中的单字默认权重20

3. Python实现维特比算法

现在让我们用Python实现完整的维特比分词器：

import math
from collections import OrderedDict

class ViterbiSegmenter:
    def __init__(self, word_dict, word_prob):
        self.word_dict = word_dict
        self.word_prob = word_prob
        # 转换为负对数概率
        self.neg_log_prob = {w: -math.log(p) for w, p in word_prob.items()}
        self.default_cost = 20  # 默认词代价
    
    def build_dag(self, sentence):
        """构建有向无环图"""
        dag = {}
        length = len(sentence)
        # 初始化节点
        for i in range(length + 1):
            dag[i] = {}
        
        # 添加边
        for start in range(length):
            for end in range(start + 1, length + 1):
                word = sentence[start:end]
                if word in self.word_dict:
                    cost = self.neg_log_prob.get(word, self.default_cost)
                    dag[end][start] = (cost, word)
                elif end == start + 1:  # 单字
                    dag[end][start] = (self.default_cost, word)
        return dag
    
    def viterbi(self, dag):
        """维特比算法求解最短路径"""
        f = OrderedDict()  # 保存各节点的最优路径
        f[0] = (0, 0)  # (累计代价, 前驱节点)
        
        # 前向传播计算最优路径
        for node in dag:
            if node == 0:
                continue
            # 找出到当前节点的最优前驱
            min_cost = float('inf')
            best_prev = None
            for prev_node in dag[node]:
                cost, word = dag[node][prev_node]
                total_cost = cost + f[prev_node][0]
                if total_cost < min_cost:
                    min_cost = total_cost
                    best_prev = prev_node
            f[node] = (min_cost, best_prev)
        
        # 回溯找出最优路径
        path = []
        end_node = len(dag) - 1
        while end_node > 0:
            prev_node = f[end_node][1]
            word = dag[end_node][prev_node][1]
            path.append(word)
            end_node = prev_node
        path.reverse()
        
        return path
    
    def segment(self, sentence):
        dag = self.build_dag(sentence)
        return self.viterbi(dag)

# 使用示例
if __name__ == "__main__":
    word_dict = ["经常", "有", "意见", "分歧"]
    word_prob = {
        "经常": 0.08, 
        "有": 0.04, 
        "意见": 0.08, 
        "分歧": 0.04
    }
    segmenter = ViterbiSegmenter(word_dict, word_prob)
    result = segmenter.segment("经常有意见分歧")
    print("分词结果:", "/".join(result))

执行结果：

分词结果: 经常/有/意见/分歧

4. 算法优化与扩展

基础实现虽然能工作，但在实际应用中还需要考虑以下优化：

1. 概率平滑处理

• 添加一元语法和二元语法概率
• 使用回退平滑处理OOV(未登录词)

def get_word_prob(word, prev_word=None):
    # 实现回退平滑
    if prev_word:
        bigram = f"{prev_word} {word}"
        if bigram in bigram_prob:
            return bigram_prob[bigram]
    return unigram_prob.get(word, default_prob)

2. 性能优化技巧

• 使用堆结构加速最小查找
• 实现剪枝策略，提前丢弃低概率路径
• 采用对数空间计算避免浮点下溢

# 剪枝示例
if current_cost > threshold * best_cost:
    continue  # 跳过该路径

3. 多维度特征融合

• 除了词频，加入词性、语义等特征
• 使用机器学习模型预测转移概率

# 特征工程示例
features = {
    "word_freq": log_prob,
    "pos_match": current_pos == next_pos,
    "word_length": len(word)
}

4. 实时分词与增量处理

• 实现流式处理，适用于长文本
• 支持中途修正和交互式分词

实际工程中，优秀的开源分词工具如Jieba、HanLP等都采用了类似的动态规划思想，但加入了更多语言特征和优化策略。

5. 从分词到序列标注

维特比算法的应用不仅限于分词，它还是序列标注任务（如词性标注、命名实体识别）的核心算法。只需将"词"替换为"标签"，同样的框架就能适用：

# 词性标注示例
states = ["NN", "VB", "JJ"]  # 词性标签集
transitions = {
    "NN": {"NN": 0.1, "VB": 0.3, "JJ": 0.6},
    # 其他转移概率...
}
emissions = {
    "NN": {"苹果": 0.8, "吃": 0.1, "红": 0.1},
    # 其他发射概率...
}

def viterbi_pos_tagging(sentence):
    # 实现类似分词的维特比算法
    pass

这种统一框架使得我们可以用相似的代码解决多种NLP问题，这正是动态规划的魅力所在。