Viterbi algorithm in linear time

Question

Hey,

I have a problem where given a Hidden Markov model and the states S I need to find an algorithm that returns the most probable path through the Hidden Markov model for a given sequence X in time O(|S|).

I was thinking of developing a graph where I would have all the different states at different positions in X and run a shortest path algorithm on this graph. However I will have n|S|^2 edges (where n is the number of states in X) and n|S| vertices.

The best algorithm I have found is the acyclic shortest path which runs in time O(|E|+|V|) which is O(|S|^2) in my case. Is there an algorithm I can develop for it to run in time O(|S|)? All I need is the general idea.

Thanks

Answer 1

I think if you want to retrieve the exact most likely sequence you cannot do it in linear time on all instances. However if your symbol space is discrete the average case time complexity may be reduced. Take a look at Ukkonen's optimization for computing edit distances and its generalizations. Also take a look at compression based techniques this is also based on Ukkonen's work.