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;

}