Python code for doing k-Best or List Viterbi Decoding of a HMM
viterbi(pi, A, O, observations)
A reference implementation of the Viterbi algorithm, robbed from here:-
exhaustive(pi, A, O, observations)
Exhaustively compute all possibilities for the HMM, robbed from here:- http://people.eng.unimelb.edu.au/tcohn/comp90042/HMM.html
kViterbiParallel(pi, a, b, obs, k)
Parallel List Viterbi Decoder to retain the top k scoring paths at each state at each time t in the time series.
Adapted from the outline in this paper:- ieeexplore.ieee.org/iel1/26/12514/00577040.pdf
kViterbiGraph(pi, a, b, obs, k)
Compute a k length Viterbi list by first converting the HMM into a NetworkX compatible DAG (Directed acyclic graph), converting to negative log-space then using Yen's algorithm to return the shortest paths, see this paper below.
There are also some models for testing, namely the Wikipedia exam[ple and tcohn's example above.