Assignment

Write a function viterbi that takes five arguments: i) an output sequence $$x$$, ii) an alphabet $$\Sigma$$, iii) a sequence of states $$S$$, iv) a transition probability matrix $$T$$ and v) an emission probability matrix $$E$$ of an HMM ($$\Sigma$$, $$S$$, $$T$$, $$E$$). The function must return a path that maximizes the (unconditional) probability $$P(x, \pi)$$ over all possible paths $$\pi$$.

Example

>>> viterbi('xyxzzxyxyy', 'xyz', 'AB', [[0.641, 0.359], [0.729, 0.271]], [[0.117, 0.691, 0.192], [0.097, 0.42, 0.483]])
'AAABBAAAAA'
>>> viterbi('zzzxyyyzzyxyzxzzzxxxxxyxzzyxyyyyxyzyyxzxzzzzxzxxyyzyzzxyyyyxzyxxxzyyyzxzyyzxxxxzxzxyxxxzxzyxxyyzzxzz', 'xyz', 'AB', [[0.426, 0.574], [0.327, 0.673]], [[0.469, 0.511, 0.02], [0.606, 0.14, 0.254]])
'BBBBAAABBABABBBBBBBBBBABBBABAAAABABAABBBBBBBBBBBAABABBBAAAABBABBBBAAABBBAABBBBBBBBBABBBBBBABBAABBBBB'