PandA-2024.02
viterbi.c
Go to the documentation of this file.
1 #include "viterbi.h"
2 
3 int viterbi( tok_t obs[N_OBS], prob_t init[N_STATES], prob_t transition[N_STATES*N_STATES], prob_t emission[N_STATES*N_TOKENS], state_t path[N_OBS] )
4 {
5  prob_t llike[N_OBS][N_STATES];
6  step_t t;
7  state_t prev, curr;
8  prob_t min_p, p;
9  state_t min_s, s;
10  // All probabilities are in -log space. (i.e.: P(x) => -log(P(x)) )
11 
12  // Initialize with first observation and initial probabilities
13  L_init: for( s=0; s<N_STATES; s++ ) {
14  llike[0][s] = init[s] + emission[s*N_TOKENS+obs[0]];
15  }
16 
17  // Iteratively compute the probabilities over time
18  L_timestep: for( t=1; t<N_OBS; t++ ) {
19  L_curr_state: for( curr=0; curr<N_STATES; curr++ ) {
20  // Compute likelihood HMM is in current state and where it came from.
21  prev = 0;
22  min_p = llike[t-1][prev] +
23  transition[prev*N_STATES+curr] +
24  emission[curr*N_TOKENS+obs[t]];
25  L_prev_state: for( prev=1; prev<N_STATES; prev++ ) {
26  p = llike[t-1][prev] +
27  transition[prev*N_STATES+curr] +
28  emission[curr*N_TOKENS+obs[t]];
29  if( p<min_p ) {
30  min_p = p;
31  }
32  }
33  llike[t][curr] = min_p;
34  }
35  }
36 
37  // Identify end state
38  min_s = 0;
39  min_p = llike[N_OBS-1][min_s];
40  L_end: for( s=1; s<N_STATES; s++ ) {
41  p = llike[N_OBS-1][s];
42  if( p<min_p ) {
43  min_p = p;
44  min_s = s;
45  }
46  }
47  path[N_OBS-1] = min_s;
48 
49  // Backtrack to recover full path
50  L_backtrack: for( t=N_OBS-2; t>=0; t-- ) {
51  min_s = 0;
52  min_p = llike[t][min_s] + transition[min_s*N_STATES+path[t+1]];
53  L_state: for( s=1; s<N_STATES; s++ ) {
54  p = llike[t][s] + transition[s*N_STATES+path[t+1]];
55  if( p<min_p ) {
56  min_p = p;
57  min_s = s;
58  }
59  }
60  path[t] = min_s;
61  }
62 
63  return 0;
64 }
65 
uint8_t tok_t
Definition: viterbi.h:13
TYPE prob_t
Definition: viterbi.h:14
int32_t step_t
Definition: viterbi.h:16
void init(int bucket[BUCKETSIZE])
Definition: sort.c:42
int viterbi(tok_t obs[N_OBS], prob_t init[N_STATES], prob_t transition[N_STATES *N_STATES], prob_t emission[N_STATES *N_TOKENS], state_t path[N_OBS])
Definition: viterbi.c:3
#define N_OBS
Definition: viterbi.h:22
uint8_t state_t
Definition: viterbi.h:15
#define N_STATES
Definition: viterbi.h:21
#define N_TOKENS
Definition: viterbi.h:23

Generated on Mon Feb 12 2024 13:02:50 for PandA-2024.02 by doxygen 1.8.13