Wednesday, January 21, 2009

Viterbi Algorithm in C++ and using STL

To practice my C++ and STL skills, I implemented the Viterbi algorithm example from the Wikipedia page: http://en.wikipedia.org/wiki/Viterbi_algorithm. The original algorithm was implemented in Python. I reimplemented the example in C++ and I used STL (mainly vector and map classes).  This code is in public-domain. So, use it as you want. 

The complete solution for MS Visual C++ 2008 can be found at http://filip.jurcicek.googlepages.com/ViterbiSTL.rar

// ViterbiSTL.cpp : is an C++ and STL implementatiton of the Wikipedia example
// Wikipedia: http://en.wikipedia.org/wiki/Viterbi_algorithm#A_concrete_example
// It as accurate implementation as it was possible

#include "stdafx.h"

#include "string"
#include "vector"
#include "map"
#include "iostream"

using namespace std;

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

vector states;
vector observations;
map start_probability;
map> transition_probability;
map> emission_probability;

class Tracking {
public:
  double prob;
  vector v_path;
  double v_prob;

  Tracking() {
    prob = 0.0;
    v_prob = 0.0;
  }

  Tracking(double p, vector & v_pth, double v_p) {
    prob = p;
    v_path = v_pth;
    v_prob = v_p;
  }
};

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void init_variables(void) {
  states.push_back("Rainy");
states.push_back("Sunny");

  observations.push_back("walk");
  observations.push_back("shop");
  observations.push_back("clean");

  start_probability["Rainy"] = 0.6;
  start_probability["Sunny"] = 0.4;

  transition_probability["Rainy"]["Rainy"] = 0.7;
  transition_probability["Rainy"]["Sunny"] = 0.3;
  transition_probability["Sunny"]["Rainy"] = 0.4;
  transition_probability["Sunny"]["Sunny"] = 0.6;

  emission_probability["Rainy"]["walk"] = 0.1;
  emission_probability["Rainy"]["shop"] = 0.4;
  emission_probability["Rainy"]["clean"] = 0.5;
  emission_probability["Sunny"]["walk"] = 0.6;
  emission_probability["Sunny"]["shop"] = 0.3;
  emission_probability["Sunny"]["clean"] = 0.1;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void print_variables(void) {
  // print states
  cout << "States:" <<>
  for(vector::iterator i=states.begin();i!=states.end();i++) {
    cout << "S: " << (*i) <<>
  }
  // print observations
  cout << "Observations:" <<>
  for(vector::iterator i=observations.begin();i!=observations.end();i++) {
    cout << "O: " << (*i) <<>
  }

  // print start probabilities
  cout << "Start probabilities:" <<>
  for(map::iterator i=start_probability.begin();i!=start_probability.end();i++) {
    cout << "S: " << (*i).first << " P: " << (*i).second <<>
  }

  // print transition_probability
  cout << "Transition probabilities:" <<>
  for(map>::iterator i=transition_probability.begin();i!=transition_probability.end();i++) {
    for(map::iterator j=(*i).second.begin();j!=(*i).second.end();j++) {
      cout << "FS: " << (*i).first << " TS: " << (*j).first << " P: " << (*j).second <<>
    }
  }

  // print emission probabilities
  cout << "Emission probabilities:" <<>
  for(int i=0; i
    for(int j=0; j
      cout << "FS: " <<>
        " P: " <<>
    }
  }
}

//this method compute total probability for observation, most likely viterbi path 
//and probability of such path
void forward_viterbi(vector obs, vector states, map start_p, 
                     map> trans_p, 
                     map> emit_p) {
  map T;

  for(vector::iterator state=states.begin(); state!=states.end();state++) {
    vector v_pth;
    v_pth.push_back(*state);

    T[*state] = Tracking(start_p[*state], v_pth, start_p[*state]);
  }

  for(vector::iterator output=obs.begin(); output!=obs.end();output++) {
    map U;

    for(vector::iterator next_state=states.begin(); next_state!=states.end(); next_state++) {
      Tracking next_tracker;

      for(vector::iterator source_state=states.begin(); source_state!=states.end(); source_state++) {
        Tracking source_tracker = T[*source_state];

        double p = emit_p[*source_state][*output]*trans_p[*source_state][*next_state];
        source_tracker.prob *= p;
        source_tracker.v_prob *= p;

        next_tracker.prob += source_tracker.prob;

        if(source_tracker.v_prob > next_tracker.v_prob) {
          next_tracker.v_path = source_tracker.v_path;
          next_tracker.v_path.push_back(*next_state);
          next_tracker.v_prob = source_tracker.v_prob;
        }
      }

      U[*next_state] = next_tracker;
    }

    T = U;
  }

  // apply sum/max to the final states
  Tracking final_tracker;

  for(vector::iterator state=states.begin(); state!=states.end(); state++) {
    Tracking tracker = T[*state];

    final_tracker.prob += tracker.prob;

    if(tracker.v_prob > final_tracker.v_prob) {
      final_tracker.v_path = tracker.v_path;
      final_tracker.v_prob = tracker.v_prob;
    }
  }

  cout << "Total probability of the observation sequence: " <<>
  cout << "Probability of the Viterbi path: " <<>
  cout << "The Viterbi path: " <<>
  for(vector::iterator state=final_tracker.v_path.begin(); state!=final_tracker.v_path.end(); state++) {
    cout << "VState: " << *state <<>
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
  cout << "Viterbi STL example" <<>
  
  init_variables();
  print_variables();

  forward_viterbi(observations, 
                  states, 
                  start_probability, 
                  transition_probability, 
                  emission_probability);

cout << "End" <<>

  string end;
  cin >> end;

  return 0;
}

Post a Comment