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

void Backward(HMM *phmm, int T, int *O, double **beta, double *pprob)
{
   int     i, j;
   int     t;
   double sum;

   for (i = 1; i <= phmm->N; i++)
	beta[T][i] = 1.0;

   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;
	}
    }

    *pprob = 0.0;
    for (i = 1; i <= phmm->N; i++)
	*pprob += beta[1][i];
}

void BackwardWithScale(HMM *phmm, int T, int *O, double **beta, double *scale, double *pprob)
{
    int     i, j;
    int     t;   
    double sum;

    for (i = 1; i <= phmm->N; i++)
	beta[T][i] = 1.0/scale[T];

    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];
	 }
     }
}