fork download 
  1. states = ('Healthy', 'Fever')
  2.  
  3. observations = ('normal', 'cold', 'dizzy')
  4.  
  5. start_probability = {'Healthy': 0.6, 'Fever': 0.4}
  6.  
  7. transition_probability = {
  8.    'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
  9.    'Fever' : {'Healthy': 0.4, 'Fever': 0.6},
  10.    }
  11.  
  12. emission_probability = {
  13.    'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
  14.    'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
  15.    }
  16. # Helps visualize the steps of Viterbi.
  17. def print_dptable(V):
  18.     print "    ",
  19.     for i in range(len(V)): print "%7s" % ("%d" % i),
  20.     print
  21.  
  22.     for y in V[0].keys():
  23.         print "%.5s: " % y,
  24.         for t in range(len(V)):
  25.             print "%.7s" % ("%f" % V[t][y]),
  26.         print
  27.  
  28. def viterbi(obs, states, start_p, trans_p, emit_p):
  29.     V = [{}]
  30.     path = {}
  31.  
  32.     # Initialize base cases (t == 0)
  33.     for y in states:
  34.         V[0][y] = start_p[y] * emit_p[y][obs[0]]
  35.         path[y] = [y]
  36.  
  37.     # Run Viterbi for t > 0
  38.     for t in range(1,len(obs)):
  39.         V.append({})
  40.         newpath = {}
  41.  
  42.         for y in states:
  43.             (prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])
  44.             V[t][y] = prob
  45.             newpath[y] = path[state] + [y]
  46.  
  47.         # Don't need to remember the old paths
  48.         path = newpath
  49.  
  50.     print_dptable(V)
  51.     (prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
  52.     return (prob, path[state])
Success #stdin #stdout 0.02s 4672KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/l6G9j
language:
Python (cpython 2.7.16)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!