第11章 条件随机场 - 实现维特比算法

import numpy as np

def viterbi_algorithm(transition_matrix, emission_matrix, start_prob, observations):
    num_states = len(start_prob)
    seq_len = len(observations)
    
    viterbi = np.zeros((seq_len, num_states))
    backpointer = np.zeros((seq_len, num_states), dtype=int)
    
    viterbi[0] = start_prob * emission_matrix[:, observations[0]]
    
    for t in range(1, seq_len):
        for s in range(num_states):
            prob = viterbi[t-1] * transition_matrix[:, s] * emission_matrix[s, observations[t]]
            backpointer[t, s] = np.argmax(prob)
            viterbi[t, s] = np.max(prob)
    
    best_path = [np.argmax(viterbi[-1])]
    for t in range(seq_len - 1, 0, -1):
        best_path.insert(0, backpointer[t, best_path[0]])
    
    return best_path, np.max(viterbi[-1])