Viterbi algorithm in Python

Viterbi algorithm in Python

by Naomie Mathilde Pont -
Number of replies: 1

Good afternoon,

I was trying to implement the viterbi algorithm in Python or to adapt it from a solution found on the internet. Unfortunately, I don't get the same result as in the correction of the practical session.

Therefore, I was wondering if someone managed to implement the code in python and could kindly share its solution?

Thank you very much for your time :)

In reply to Naomie Mathilde Pont

Re: Viterbi algorithm in Python

by Ali Benabdallah -
Good afternoon,
It should do the job :

import numpy as np
def vitterbi(A, B, I, input):
p = [[0 for _ in range(len(I))] for _ in range(len(input))]
index = {'H' : 0, 'T' : 1}
# Initialization
for state in range(len(I)):
p[0][state] = I[state] * B[state][index[input[0]]]
print(p[0])
# Forward pass
argmaxs = [[0 for _ in range(len(I))] for _ in range(len(input))]
for i in range(1, len(input)):
for state in range(len(I)):
argmax = np.argmax([A[k][state] * p[i-1][k] for k in range(len(I))])
argmaxs[i][state] = argmax
p[i][state] = B[state][index[input[i]]] * A[argmax][state] * p[i-1][argmax]
print(p[i])
print(argmaxs[i])
# Backward pass
res = [np.argmax(p[len(input) - 1])]
for i in range(len(input) - 2, -1, -1):
res.append(argmaxs[i][res[-1]])
res = ''.join([str(k + 1) for k in res])
print(len(res))
return res

A = [[ 0.4, 0.6 ], [0.9, 0.1 ]]
B = [[ 0.49, 0.51 ], [ 0.85, 0.15 ]]
I = [ 0.5, 0.5 ]
input = 'HTTHTTHHTTHTTTHHTHHTTHTTTTHTHHTHTHHTTTH'
vitterbi(A, B, I, input)


Best regards,
Ali