viterbi.cpp

NLP中viterby算法的实现,对语料进行处理

/*
**   File：Viterbi.cpp
**   功能：给定HMM和观察序列，求最可能的状态
*/

#include "StdAfx.h"
#include <math.h>
#include "vector.h"
//#include "hmm.h"

using namespace std;
//#define VITHUGE  100000000000.0

/**************************************************************************
** 函数名称：Viterbi
** 功能：Viterbi算法
** 参数：phmm：HMM结构指针
**       T：观察值的个数
**       O：观察序列
**       delta，psi为中间变量
**       q：求得的最佳状态序列
**       pprob：概率
**/
//  A 
void main()
{   
	double **A,**B;
	int 	i, j;	   /* 状态下标 */
	int   	t;	      /* 时间下标 */	
	int     T,N;      //时间和序列长度
	vector<double>  start;       //hmm中的pi 初始状态
	int     *q;       //最后记录的是最佳状态序列
	vector<int>  object;  //状态序列
	int  	maxvalind;    // 最佳状态序号
	double  beststate;    //最后回溯用 记录最佳状态序列
	double	maxval, val;
	double  **delta;
	int     **psi;
	/* 1. 初始化  */
	
	for (i = 1; i <= N; i++) 
	{
		delta[1][i] = start[i] * B[i][object[1]];  //delta符号
		psi[1][i] = 0;  
	}	

	/* 2. 递归 */
	
	for (t = 2; t <= T; t++) 
	{
		for (j = 1; j <= N; j++) 
		{
			maxval = 0.0;
			maxvalind = 1;	
			for (i = 1; i <= N; i++) 
			{
				val = delta[t-1][i]*A[i][j];
				if (val > maxval) {
					maxval = val;	
					maxvalind = i;	
				}
			}	
			delta[t][j] = maxval*B[j][object[t]];
			psi[t][j] = maxvalind;  //  记录argmax(delta*A)
		}
	}
	/* 3. 终止 */

    beststate = 0.0;
	q[T] = 1;
	for (i = 1; i <= N; i++)   //找到最佳的序列
	{
		if (delta[T][i] > beststate) 
		{
			beststate = delta[T][i];	
			q[T] = i;
		}
	}  	
	/* 4. Path (state sequence) backtracking */
	for (t = T - 1; t >= 1; t--)
		q[t] = psi[t+1][q[t+1]];
	//q[t]最后存储的是最佳的观测序列
}