• Written by Eliot Lee (dr.eliot@gmail.com)
• Download the source code here viterbi.zip
  • Screen shot
  • 

/*
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},
   }
*/

#define MAX_OBS 100 // we don't need one hundreds, but feel comfortable
#define N_STATES 2	// we only have two states
#define N_EMITS 3	//

#include <stdio.h> // printf
#include <stdlib.h> // itoa
#include <string.h> // memset
#include <conio.h> // getch

enum {walk, shop, clean}; // emissions
enum {Rainy, Sunny}; // states

double V[MAX_OBS][N_STATES]; // V[t][k] is the probability of the most probable state sequence responsible for the first t+1 observations.
double start_p[N_STATES] = {0.6, 0.4}; // start probability
double trans_p[N_STATES][N_STATES] = {0.7, 0.3, 0.4, 0.6}; // transmisstion probability
double emit_p[N_STATES][N_EMITS] = {0.1, 0.4, 0.5, 0.6, 0.3, 0.1}; // emission probability
int obs[] = {walk, shop, clean}; // orginal observation
//int obs[] = {walk, shop, clean, walk, shop, clean, clean, walk, shop, clean}; // for testing to compare the same result to the output from python version, it worked.
int states[N_STATES] = {Rainy, Sunny};
char path[][MAX_OBS] = {"", ""};
char newpath[][MAX_OBS] = {"", ""};

void viterbi()
{
	int nobs, nstates;
	int t, y, y0;
	double prob, prob_max;
	int state_max;
	char buf[10]; // for hold a integer

	// Initialize
	nobs = sizeof(obs)/sizeof(obs[0]);
	nstates = sizeof(states)/sizeof(states[0]);
	for(y=0; y<nstates; y++)
	{
		V[0][y] = start_p[y] * emit_p[y][obs[0]]; // V[0]k]
		strcat(path[y], itoa(y, buf, 10)); // path inizilize
	}
	
	// Run Viterbi for t > 0
	for(t=1; t<nobs; t++)
	{
		for(y=0; y<nstates; y++) // y0->y
		{
			prob_max = 0;
			state_max = 0;
			for(y0=0; y0<nstates; y0++) // find max prob and state
			{
				prob = V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]];
				if(prob > prob_max) // find max prob
				{
					prob_max = prob;
					state_max = y0; // update the max state number
				}
			}
			// update the maximum values
			V[t][y] = prob_max;
			strcpy(newpath[y], path[state_max]); 
			strcat(newpath[y], itoa(y, buf, 10)); // newpath = max_path + current_state
		}
		// path update
		for(y=0; y<nstates; y++)
			strcpy(path[y], newpath[y]);
	}

	// Done. let's see the result
	prob_max = 0;
	state_max = 0;
	for(y=0; y<nstates; y++)
	{
		if(prob > prob_max)
		{
			prob_max = prob;
			state_max = y;
		}
	}

	printf("Max prb %f, path = %s", V[nobs-1][state_max], path[state_max]);
}

void main()
{
	viterbi();
	getch();
}