Viterbi Solver for homework 3. Sloppy, but it gets the job done.

viterbi.py

def avalanche(sequence, print_all=False):
    states = ['1', '2']

    emissions = {}
    emissions[('1', 'C')] = .1
    emissions[('1', 'C#')] = .1
    emissions[('1', 'D')] = .4
    emissions[('1', 'D#')] = .4

    emissions[('2', 'C')] = .4
    emissions[('2', 'C#')] = .4
    emissions[('2', 'D')] = .1
    emissions[('2', 'D#')] = .1

    trans = {}
    trans[('1', '1')] = .6
    trans[('1', '2')] = .4

    trans[('2', '2')] = .5
    trans[('2', '1')] = .4

    trans[('2', 'end')] = .1
    trans[('1', 'end')] = 0

    trans[('start', '1')] = .5
    trans[('start', '2')] = .5
    
    return viterbi(states, emissions, trans, sequence, print_all)
    
def invasion(sequence, print_all=False):
    states = ['1', '2', '3']

    emissions = {}
    emissions[('1', 'C')] = .1
    emissions[('1', 'C#')] = .1
    emissions[('1', 'D')] = .2
    emissions[('1', 'D#')] = .6

    emissions[('2', 'C')] = .1
    emissions[('2', 'C#')] = .1
    emissions[('2', 'D')] = .7
    emissions[('2', 'D#')] = .1
    
    emissions[('3', 'C')] = .6
    emissions[('3', 'C#')] = .2
    emissions[('3', 'D')] = .1
    emissions[('3', 'D#')] = .1

    trans = {}
    trans[('1', '1')] = .6
    trans[('1', '2')] = .4
    trans[('1', '3')] = 0

    trans[('2', '2')] = .7
    trans[('2', '1')] = 0
    trans[('2', '3')] = .3
    
    trans[('3', '3')] = .6
    trans[('3', '1')] = 0
    trans[('3', '2')] = 0

    trans[('1', 'end')] = 0
    trans[('2', 'end')] = 0
    trans[('3', 'end')] = .4

    trans[('start', '1')] = .5
    trans[('start', '2')] = .5
    trans[('start', '3')] = .5
    
    return viterbi(states, emissions, trans, sequence, print_all)

def viterbi (states, emit, trans, sequence, print_all):
   
    sn = range(1, len(sequence))
    trellis = {}
    parent = {}
    indiv = {}

    #start
    for state in states:
        trellis[(0, state)] = trans[('start', state)] * emit[(state, sequence[0])]
        indiv[(0, 'start', state)] = 1 * trans[('start', state)]
        parent[(0, state)] = 'start'

    #middle
    for x in sn:
        for state in states:
            best_parent, best_score = None, -1
            for prev_state in states:
                score = trellis[(x - 1, prev_state)] * trans[(prev_state, state)]
                indiv[(x, prev_state, state)] = score
                if score > best_score:
                    best_parent, best_score = prev_state, score
            parent[(x, state)] = best_parent
            trellis[(x, state)] = best_score * emit[(state, sequence[x])]
            
    #end
    x_end = len(sequence)
    best_parent, best_score = None, -1
    for prev_state in states:
        score = trellis[(x_end - 1, prev_state)] * trans[(prev_state, 'end')]
        if score > best_score:
            best_parent, best_score = prev_state, score
    parent[(x_end, 'end')] = best_parent
    trellis[(x_end, 'end')] = best_score

    for x in range(0, len(sequence)):
        print "\n", x, ":", sequence[x], ""
        for state in states:
            if print_all:
                ind = {}
                for prev_state in (states if x != 0 else ['start']):
                    ind[prev_state] = indiv[(x, prev_state, state)]
                print state, '(', trellis[(x, state)], ')', " p =", parent[(x, state)], ' indivs = ', ind
            else:
                print state, '(', trellis[(x, state)], ')', " p =", parent[(x, state)]
    print "\n", 'end', ":"
    print 'end', '(', trellis[(x_end, 'end')], ')', " parent =", parent[(x_end, 'end')]

    return trellis[(x_end, 'end')]

sequence1 = ['D#', 'D', 'C#', 'C', 'C#', 'D', 'D#', 'D', 'C#', 'C']

sequence2 = ['D#', 'D#', 'D#', 'D', 'D', 'D', 'C#', 'C', 'C']