Viberbi Algorithm

Viterbi.py

import numpy as np

def decode(self, X, pi, A, B, N):
    T = len(X)
    delta = pi * B[:,X[0]]    # P(X, Z | lamda)
    varphi = np.zeros((T, N), dtype=int)
    path = [0] * T
    for i in range(1, T):
        delta = delta.reshape(-1,1)     # Nx1
        tmp = delta * self.A            # NxN
        varphi[i,:] = np.argmax(tmp, axis=0)
        delta = np.max(tmp, axis=0) * B[:,X[i]]
    path[-1] = np.argmax(delta)
    # 回溯最优路径
    for i in range(T-1,0,-1):
        path[i-1] = varphi[i,path[i]]
    return path