viterbi.c

Viterbi算法源程序,注释简洁,利于使用

/*
**	函数功能：给定HMM和观察序列，用Viterbi算法（本质上就是动态规划算法）进行搜索，求得最优状态序列。
**	参数：
**	hmm：HMM结构指针，其中，hmm->N指状态个数，hmm->a[i][j]指从状态i转移到状态j的概率，hmm->b[i][k]指状态i输出观察值k的概率，hmm->pi[i]指初始状态为状态i的概率。
**	T：观察值的个数。
**	O：观察序列。
**	p：p[t][i]指在t时刻到达状态i，并输出观察序列O[1]...O[t]的最大概率。
**	psi：psi[t][i]指t时刻状态为i时，t-1时刻的状态。
**	q：求得的最佳状态序列。
**	prob：输出观察序列O的最优状态序列的概率。
*/



void Viterbi(HMM *hmm,int T,int *O,float **p,int **psi,int *q,float *prob)
{
	int i,j,t;
	float w;

	//初始化
	for(i=1;i<=hmm->N;i++)
	{
		p[1][i]=hmm->pi[i]*(hmm->b[i][O[1]]);
		psi[1][i]=0;
	}

	//递归
	for(t=2;t<=T;t++)
	{
		for(j=1;j<=hmm->N;j++)
		{
			p[t][j]=p[t-1][1]*(hmm->a[1][j]);
			psi[t][j]=1;
			for(i=2;i<=hmm->N;i++)
			{
				w=p[t-1][i]*(hmm->a[i][j]);
				if(w>p[t][j])
				{
					p[t][j]=w;
					psi[t][j]=i;
				}
			}
			p[t][j]*=hmm->b[j][O[t]];
		}
	}

	//终止
	*prob=p[T][1];
	q[T]=1;
	for(i=2;i<=N;i++)
	{
		if(p[T][i]>*prob)
		{
			*prob=p[T][i];
			q[T]=i;
		}
	}

	//回溯
	for(t=T-1;t>=1;t--)
		q[t]=psi[t+1][q[t+1]];
}