/*
**      File:   backward.cpp
**      功能：給定觀察值序列和HMM模型，利用前向后向算法
**            求取其概率
*/

#include "StdAfx.h"
#include <stdio.h>
#include "hmm.h"

/***************************************************************************
** 函數名稱：Backward
** 功能：后向算法估計參數
** 參數：phmm：指向HMM的指針
**       T：觀察值序列的長度
**       O：觀察值序列
**       beta：運算中用到的臨時數組
**       pprob：返回值，所要求的概率
**/
void Backward(HMM *phmm, int T, int *O, double **beta, double *pprob)
{
	int     i, j;   /* 狀態 */
	int     t;      /* 時間下標 */
	double sum;
 
 
	/* 1. 初始化 */
 
	for (i = 1; i <= phmm->N; i++)
		beta[T][i] = 1.0;
 
	/* 2. 遞歸 */
 
	for (t = T - 1; t >= 1; t--) 
	{
		for (i = 1; i <= phmm->N; i++) 
		{
			sum = 0.0;
			for (j = 1; j <= phmm->N; j++)
				sum += phmm->A[i][j] * (phmm->B[j][O[t+1]])*beta[t+1][j];
			beta[t][i] = sum;
 
		}
	}
 
	/* 3. 終止 */
	*pprob = 0.0;
	for (i = 1; i <= phmm->N; i++)
		*pprob += beta[1][i];
}

/***************************************************************************
** 函數名稱：BackwardWithScale
** 功能：后向算法估計參數（帶比例因子修正）
** 參數：phmm：指向HMM的指針
**       T：觀察值序列的長度
**       O：觀察值序列
**       beta：運算中用到的臨時數組
**       scale：比例因子數組
**       pprob：返回值，所要求的概率
**/
void BackwardWithScale(HMM *phmm, int T, int *O, double **beta, 
	double *scale, double *pprob)
{
	int     i, j;   /* 狀態指示 */
	int     t;      /* 時間下標 */
	double sum;
 
 
	/* 1. 初始化 */
	for (i = 1; i <= phmm->N; i++)
		beta[T][i] = 1.0/scale[T]; 
 
	/* 2. 遞歸 */
	for (t = T - 1; t >= 1; t--) 
	{
		for (i = 1; i <= phmm->N; i++) 
		{
			sum = 0.0;
			for (j = 1; j <= phmm->N; j++)
				sum += phmm->A[i][j] * (phmm->B[j][O[t+1]])*beta[t+1][j];
			beta[t][i] = sum/scale[t];
		}
	}
}