隐马尔科夫模型Viterbi算法的c++实现

1、#include <iostream> #include <vector> #include <map> #include <string> using namespace std; typedef vector< string > VecStr; typedef map< string, double > MapStrDou; typedef map< string, map< string, double > > MapStrMap; typedef vector< string >

2、 : iterator VecStrI; typedef map< string, double > : iterator MapStrDouI; typedef map< string, map< string, double > > : iterator MapStrMapI; typedef struct DSD double d1; string s; double d2; DSD; typedef map< string, DSD > MapStrDSD; #define RAINY "Rainy" #define

3、SUNNY "Sunny" #define WALK "walk" #define SHOP "shop" #define CLEAN "clean" DSD forward_viterbi(VecStr& obs, VecStr& states, MapStrDou& start_p, MapStrMap& trans_p, MapStrMap& emit_p); int main(void) VecStr states; VecStr observations; MapS

4、trDou start_probability; MapStrMap transition_probability; MapStrMap emission_probability; states.push_back(RAINY); states.push_back(SUNNY); observations.push_back(WALK); observations.push_back(SHOP); observations.push_back(CLEAN); start_probabilityRAINY = 0.6; start_probabilitySUNNY = 0.4; MapStrDo

5、u t1; t1RAINY = 0.7; t1SUNNY = 0.3; MapStrDou t2; t2RAINY = 0.4; t2SUNNY = 0.6; transition_probabilityRAINY = t1; transition_probabilitySUNNY = t2; MapStrDou e1; e1WALK = 0.1; e1SHOP = 0.4; e1CLEAN = 0.5; MapStrDou e2; e2WALK = 0.6; e2SHOP = 0.3; e2CLEAN = 0.1; emission_probabilityRAINY = e1; emissi

6、on_probabilitySUNNY = e2; DSD ret = forward_viterbi(observations, states, start_probability, transition_probability, emission_probability); cout << ret.d1 <<endl; cout << ret.s << endl; cout << ret.d2 << endl; return 0; DSD forward_viterbi(VecStr& obs, VecStr&

7、amp; states, MapStrDou& start_p, MapStrMap& trans_p, MapStrMap& emit_p) MapStrDSD T; VecStrI VS_i, VS_j, VS_k; DSD DSD_tmp; for(VS_i = states.begin(); VS_i != states.end(); VS_i+) DSD_tmp.d1 = start_p*VS_i; DSD_tmp.s = *VS_i; DSD_tmp.d2 = start_p*VS_i; T*VS_i = DSD_tmp; for(VS_i = obs.be

8、gin(); VS_i != obs.end(); VS_i+) MapStrDSD U; for(VS_j = states.begin(); VS_j != states.end(); VS_j+) double total = 0.0; string argmax = "" double valmax = 0.0; double prob = 1.0; string v_path = "" double v_prob = 1.0; for(VS_k = states.begin(); VS_k != states.end(); VS_k+) DSD

9、 objs = T*VS_k; prob = objs.d1; v_path = objs.s; v_prob = objs.d2; double p = (emit_p*VS_k)*VS_i * (trans_p*VS_k)*VS_j; prob *= p; v_prob *= p; total += prob; if(v_prob > valmax) argmax = v_path + "," + *VS_j; valmax = v_prob; /* test */ cout << "obs = " << *VS_i &

10、lt;< endl; cout << "tnext_state = " << *VS_j << endl; cout << "ttstate = " << *VS_k << endl; cout << "tttp = " << p << " = " << (emit_p*VS_k)*VS_i << " * " << (trans_p*VS_k)*V

11、S_j << endl; cout << "tttprob, v_path, v_prob = " << prob << ", " << v_path << ", " << v_prob << "" << endl; cout << "ttttotal, argmax, valmax = " << total << ", " <

12、< argmax << ", " << valmax << "" << endl; /* end of test */ DSD_tmp.d1 = total; DSD_tmp.s = argmax; DSD_tmp.d2 = valmax; U*VS_j = DSD_tmp; T = U; double total = 0.0; string argmax = "" double valmax = 0.0; double prob = 1.0; string v_path = &q

13、uot;" double v_prob = 1.0; for(VS_i = states.begin(); VS_i != states.end(); VS_i+) DSD objs = T*VS_i; prob = objs.d1; v_path = objs.s; v_prob = objs.d2; total += prob; if(v_prob > valmax) argmax = v_path; valmax = v_prob; DSD_tmp.d1 = total; DSD_tmp.s = argmax; DSD_tmp.d2 = valmax; return DS

14、D_tmp; #include <iostream>#include <vector>#include <map>#include <string>using namespace std;typedef vector< string > VecStr;typedef map< string, double > MapStrDou;typedef map< string, map< string, double > > MapStrMap;typedef vector< string >

15、: iterator VecStrI;typedef map< string, double > : iterator MapStrDouI;typedef map< string, map< string, double > > : iterator MapStrMapI;typedef struct DSDdouble d1;string s;double d2;DSD;typedef map< string, DSD > MapStrDSD;#define RAINY "Rainy"#define SUNNY "

16、;Sunny"#define WALK "walk"#define SHOP "shop"#define CLEAN "clean"DSD forward_viterbi(VecStr& obs,VecStr& states,MapStrDou& start_p,MapStrMap& trans_p,MapStrMap& emit_p);int main(void)VecStr states;VecStr observations;MapStrDou start_probability

17、;MapStrMap transition_probability;MapStrMap emission_probability;states.push_back(RAINY);states.push_back(SUNNY);observations.push_back(WALK);observations.push_back(SHOP);observations.push_back(CLEAN);start_probabilityRAINY = 0.6;start_probabilitySUNNY = 0.4;MapStrDou t1;t1RAINY = 0.7;t1SUNNY = 0.3;

18、MapStrDou t2;t2RAINY = 0.4;t2SUNNY = 0.6;transition_probabilityRAINY = t1;transition_probabilitySUNNY = t2;MapStrDou e1;e1WALK = 0.1;e1SHOP = 0.4;e1CLEAN = 0.5;MapStrDou e2;e2WALK = 0.6;e2SHOP = 0.3;e2CLEAN = 0.1;emission_probabilityRAINY = e1;emission_probabilitySUNNY = e2;DSD ret = forward_viterbi

19、(observations,states,start_probability,transition_probability,emission_probability);cout << ret.d1 <<endl;cout << ret.s << endl;cout << ret.d2 << endl;return 0;DSD forward_viterbi(VecStr& obs,VecStr& states,MapStrDou& start_p,MapStrMap& trans_p,Map

20、StrMap& emit_p)MapStrDSD T;VecStrI VS_i, VS_j, VS_k;DSD DSD_tmp;for(VS_i = states.begin(); VS_i != states.end(); VS_i+)DSD_tmp.d1 = start_p*VS_i;DSD_tmp.s = *VS_i;DSD_tmp.d2 = start_p*VS_i;T*VS_i = DSD_tmp;for(VS_i = obs.begin(); VS_i != obs.end(); VS_i+)MapStrDSD U;for(VS_j = states.begin(); VS

21、_j != states.end(); VS_j+)double total = 0.0;string argmax = ""double valmax = 0.0;double prob = 1.0;string v_path = ""double v_prob = 1.0;for(VS_k = states.begin(); VS_k != states.end(); VS_k+)DSD objs = T*VS_k;prob = objs.d1;v_path = objs.s;v_prob = objs.d2;double p = (emit_p*V

22、S_k)*VS_i * (trans_p*VS_k)*VS_j;prob *= p;v_prob *= p;total += prob;if(v_prob > valmax)argmax = v_path + "," + *VS_j;valmax = v_prob;/* test */cout << "obs = " << *VS_i << endl;cout << "tnext_state = " << *VS_j << endl;cout <<

23、; "ttstate = " << *VS_k << endl;cout << "tttp = " << p << " = " << (emit_p*VS_k)*VS_i << " * " << (trans_p*VS_k)*VS_j << endl;cout << "tttprob, v_path, v_prob = " << prob << &quo

24、t;, " << v_path << ", " << v_prob << "" << endl;cout << "ttttotal, argmax, valmax = " << total << ", " << argmax << ", " << valmax << "" << endl;/* end of te

25、st */DSD_tmp.d1 = total;DSD_tmp.s = argmax;DSD_tmp.d2 = valmax;U*VS_j = DSD_tmp;T = U;double total = 0.0;string argmax = ""double valmax = 0.0;double prob = 1.0;string v_path = ""double v_prob = 1.0;for(VS_i = states.begin(); VS_i != states.end(); VS_i+)DSD objs = T*VS_i;prob = o

26、bjs.d1;v_path = objs.s;v_prob = objs.d2;total += prob;if(v_prob > valmax)argmax = v_path;valmax = v_prob;DSD_tmp.d1 = total;DSD_tmp.s = argmax;DSD_tmp.d2 = valmax;return DSD_tmp; -执行结果： obs = walk next_state = Rainy state = Rainy p = 0.07 = 0.1 * 0.7 prob, v_path, v_prob = 0.042, Rainy, 0.042 tot

27、al, argmax, valmax = 0.042, Rainy,Rainy, 0.042obs = walk next_state = Rainy state = Sunny p = 0.24 = 0.6 * 0.4 prob, v_path, v_prob = 0.096, Sunny, 0.096 total, argmax, valmax = 0.138, Sunny,Rainy, 0.096obs = walk next_state = Sunny state = Rainy p = 0.03 = 0.1 * 0.3 prob, v_path, v_prob = 0.018, Ra

28、iny, 0.018 total, argmax, valmax = 0.018, Rainy,Sunny, 0.018obs = walk next_state = Sunny state = Sunny p = 0.36 = 0.6 * 0.6 prob, v_path, v_prob = 0.144, Sunny, 0.144 total, argmax, valmax = 0.162, Sunny,Sunny, 0.144obs = shop next_state = Rainy state = Rainy p = 0.28 = 0.4 * 0.7 prob, v_path, v_pr

29、ob = 0.03864, Sunny,Rainy, 0.02688 total, argmax, valmax = 0.03864, Sunny,Rainy,Rainy, 0.02688obs = shop next_state = Rainy state = Sunny p = 0.12 = 0.3 * 0.4 prob, v_path, v_prob = 0.01944, Sunny,Sunny, 0.01728 total, argmax, valmax = 0.05808, Sunny,Rainy,Rainy, 0.02688obs = shop next_state = Sunny state = Rainy p = 0.12 = 0.4 * 0.3 prob, v_path, v_prob = 0.01656, Sunny,Rainy, 0.01152 total, argmax, valmax = 0.01656, Sunny,Rainy,Sunny, 0.01152obs = shop next_state = Sunny s