Viterbi algorithm for Hidden Markov Models (HMM) taken from wikipedia

Viterbi.py

#!/usr/bin/python
# http://en.wikipedia.org/wiki/Viterbi_algorithm

'''
Consider two friends, Alice and Bob, who live far apart from each other and who talk together daily over the telephone about what they did that day. Bob is only interested in three activities: walking in the park, shopping, and cleaning his apartment. The choice of what to do is determined exclusively by the weather on a given day. Alice has no definite information about the weather where Bob lives, but she knows general trends. Based on what Bob tells her he did each day, Alice tries to guess what the weather must have been like.
Alice believes that the weather operates as a discrete Markov chain. There are two states, "Rainy" and "Sunny", but she cannot observe them directly, that is, they are hidden from her. On each day, there is a certain chance that Bob will perform one of the following activities, depending on the weather: "walk", "shop", or "clean". Since Bob tells Alice about his activities, those are the observations. The entire system is that of a hidden Markov model (HMM).
Alice knows the general weather trends in the area, and what Bob likes to do on average. In other words, the parameters of the HMM are known.
'''
'''
 start_probability represents Alice's belief about which state the HMM is in when Bob first calls her (all she knows is that it tends to be rainy on average). The particular probability distribution used here is not the equilibrium one, which is (given the transition probabilities) approximately {'Rainy': 0.57, 'Sunny': 0.43}. The transition_probability represents the change of the weather in the underlying Markov chain. In this example, there is only a 30% chance that tomorrow will be sunny if today is rainy. The emission_probability represents how likely Bob is to perform a certain activity on each day. If it is rainy, there is a 50% chance that he is cleaning his apartment; if it is sunny, there is a 60% chance that he is outside for a walk.
'''
'''
Alice talks to Bob three days in a row and discovers that on the first day he went for a walk, on the second day he went shopping, and on the third day he cleaned his apartment. Alice has a question: what is the most likely sequence of rainy/sunny days that would explain these observations? This is answered by the Viterbi algorithm.
'''
class Viterbi(object):
	def __init__(self):
		None

	@staticmethod
	def print_dptable(V):
		print "    ",
		for i in range(len(V)): print "%7s" % ("%d" % i),
		print

		for y in V[0].keys():
			print "%.5s: " % y,
			for t in range(len(V)):
				print "%.7s" % ("%f" % V[t][y]),
			print

	@staticmethod
	def viterbi(obs, states, start_p, trans_p, emit_p):
		V = [{}]
		path = {}
		for y in states:
			V[0][y] = start_p[y] * emit_p[y][obs[0]]	# Initialize base cases (t == 0)
			path[y] = [y]
		for t in range(1,len(obs)):	# Run Viterbi for t > 0
			V.append({})
			newpath = {}
			for y in states:
				(prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])
				V[t][y] = prob
				newpath[y] = path[state] + [y]
			path = newpath	# Don't need to remember the old paths

		Viterbi.print_dptable(V)
		(prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
		return (prob, path[state])

	@staticmethod
	def example():
		states = ('Rainy', 'Sunny')
		observations = ('walk', 'shop', 'clean')
		start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
		transition_probability = {
			'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
			'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
		}
		emission_probability = {
			'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
			'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
		}
		return Viterbi.viterbi(observations, states, start_probability, transition_probability, emission_probability)

	@staticmethod
	def main():
		print Viterbi.example()

if __name__ == '__main__':
	Viterbi.main()