A trial program of the viterbi algorithm with HMM for POS tagging.

viterbi.py

import numpy as np

# data
x = ["Brown", "promises", "free"]
y = ["Noun", "Verb", "Adj"]

# suppose the probabilities
p_x_y = [[0.3, 0.2, 0.5], [0.3, 0.4, 0.1], [0.4, 0.4, 0.4]] # p(x_t, y_t)
p_y_y = [[0.4, 0.7, 0.5], [0.5, 0.1, 0.2], [0.1, 0.2, 0.3]] # p(y_t, y_t-1)

t = [ [ 0.0 for i in xrange(len(y)) ] for j in xrange(len(x)) ]
s = [ [ 0 for i in xrange(len(y)) ] for j in xrange(len(x)) ]

# calculate each node
def t_s(i, j):
    if i == 0:
        return (np.log(p_x_y[i][j]), j)
    t_temp = [ np.log(p_x_y[i][j]) * np.log(p_y_y[j][k]) * t[i - 1][k] for k in xrange(len(y)) ]
    return (np.max(t_temp), np.argmax(t_temp))

for i in xrange(0, len(x)):
    for j in xrange(len(y)):
        t[i][j], s[i][j] = t_s(i, j)

# assign labels
y_max = [ 0 for i in xrange(len(x)) ]
l = len(x) - 1
y_max[l] = np.argmax(t[l])
for i in xrange(l - 1, -1, -1):
    y_max[i] = s[i + 1][y_max[i + 1]]

# result
print x
print [ y[j] for j in y_max ]