viterbi.txt

viterbi搜索算法是一种全局动态规划算法,在本例中,我们用C实现了他的搜索过程.

/*
 *	韦特比算法
 *	int *pInput			检测序列
 *	int iInputLen		序列长度
 *	int *pBestPath		结果最佳序列
 *	double **pRltMatrix	中间结果
 */
double CHmm::Viterbi(int *pInput, int iInputLen, int *pBestPath, double **pRltMatrix, int **plamda)
{

	for(int i=0; i<iInputLen; i++)
	{
		if(pInput[i]>=m_iDimB)
		{
			AfxMessageBox("输入的数据超界");
			return 0.0;
		}
	}

	m_pRltMatrix = pRltMatrix;
	m_plamda = plamda;


	double rlt = 0.0;

	m_pInput = pInput;
	m_iInputLen = iInputLen;


	double *deta;
	deta = new double[m_iDimA];

	for(i=0; i<m_iDimA; i++)
	{
		deta[i] = viterbi_recursion(iInputLen-1, i);
		if(rlt<deta[i])
		{
			rlt=deta[i];
			pBestPath[iInputLen-1] = i+1;
		}
	}

	
	for(i=iInputLen-2; i>=0; i--)
	{
		pBestPath[i] = m_plamda[pBestPath[i+1]-1][i+1];
	}

	delete [] deta;
	return rlt;
}
//韦特比算法 的递推函数
double CHmm::viterbi_recursion(int iIndex, int j)
{
	double rlt= 0;
	double *deta_last;
	deta_last = new double[m_iDimA];

	if(iIndex==1)
	{

		for(int i=0; i<m_iDimA; i++)
		{
			deta_last[i] = m_pPI[i]*m_pB[i][m_pInput[0]];

			//保存中间结果
			m_pRltMatrix[i][0] = deta_last[i];
			
		}
	}
	else
	{
		for(int i=0; i<m_iDimA; i++)
		{
			deta_last[i] = viterbi_recursion(iIndex-1, i);
		}
	}

	double temp;
	for(int i=0; i<m_iDimA; i++)
	{
		temp = deta_last[i]*m_pA[i][j];
		if(rlt<temp)
		{
			rlt=temp;

			//保存最佳路径
			m_plamda[j][iIndex] = i+1;
		}
	}

	rlt *= m_pB[j][m_pInput[iIndex]];

	//保存中间结果
	//m_pRltMatrix[iIndex][j] = rlt;
	m_pRltMatrix[j][iIndex] = rlt;

	delete [] deta_last;
	return rlt;
}