#!/usr/bin/env python -O
# viterbi.py: simple Viterbi decoding, with protections against underflow
# Steven Bedrick <bedricks@ohsu.edu> and Kyle Gorman <gormanky@ohsu.edu>


from bitweight import BitWeight
from numpy import array, int8, ones, zeros


def viterbi(observations, states, transitions, emissions):
    """
    Compute best path (in the form of a state sequence) through an HMM 
    (represented by the tuple of observations, states, the transition 
    matrix (conditional probability of a state given the previous state), 
    and the emission matrix (conditional probability of a token given the 
    hidden state)
    """
    raise NotImplementedError


if __name__ == "__main__":

    states = ['VB', 'TO', 'NN', 'PPSS']
    observations = ['I', 'want', 'to', 'race']

    state_lookup = {1: 'VB', 2: 'TO', 3: 'NN', 4: 'PPSS'}
    emis_lookup = {1: 'I', 2: 'want', 3: 'to', 4: 'race'}

    # note that row 0 of transitions represents the starting transitions
    # (i.e., P("VB" | "start"), etc.)

    transitions = array([[BitWeight(0.19),    BitWeight(0.0043), 
                          BitWeight(0.41),    BitWeight(0.067)  ],
                         [BitWeight(0.0038),  BitWeight(0.035), 
                          BitWeight(0.047),   BitWeight(0.0070)],
                         [BitWeight(0.83),    BitWeight(0.), 
                          BitWeight(0.00047), BitWeight(0.)    ],
                         [BitWeight(0.0040),  BitWeight(0.016),
                          BitWeight(0.087),   BitWeight(0.0045)],
                         [BitWeight(0.23),    BitWeight(0.0079),
                          BitWeight(0.0012),  BitWeight(0.00014)]])

    emissions = array([[BitWeight(0.),   BitWeight(0.0093),
                        BitWeight(0.),   BitWeight(0.00012)],
                       [BitWeight(0.),   BitWeight(0.), 
                        BitWeight(0.99), BitWeight(0.)    ],
                       [BitWeight(0.),   BitWeight(0.000054),
                        BitWeight(0.),   BitWeight(0.00057)],
                       [BitWeight(0.37), BitWeight(0.),
                        BitWeight(0.),   BitWeight(0.)     ]])

    sequence = viterbi(observations, states, transitions, emissions)
    print ' '.join(state_lookup[i] for i in sequence)