维特比算法python

维特比算法是一种用于求解隐马尔可夫模型（HMM）中最优路径的算法。下面是一个简单的 Python 实现：

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    path = {}

    # 初始化第一个观测值的概率
    for y in states:
        V[0][y] = start_p[y] * emit_p[y][obs[0]]
        path[y] = [y]

    # 对于每个观测值计算最优路径
    for t in range(1, len(obs)):
        V.append({})
        new_path = {}

        for y in states:
            # 计算当前状态的最优路径概率
            (prob, state) = max((V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states)
            V[t][y] = prob
            new_path[y] = path[state] + [y]

        # 更新路径
        path = new_path

    # 找到最终状态的最优路径
    (prob, state) = max((V[len(obs) - 1][y], y) for y in states)
    return (prob, path[state])

其中，obs 是观测值序列，states 是可能的状态值，start_p 是初始状态概率，trans_p 是状态转移概率，emit_p 是观测值概率。该函数返回最优路径的概率和路径本身。