hrec.c

实现HMM算法

/* ----------------------------------------------------------- */
/*                                                             */
/*                          ___                                */
/*                       |_| | |_/   SPEECH                    */
/*                       | | | | \   RECOGNITION               */
/*                       =========   SOFTWARE                  */ 
/*                                                             */
/*                                                             */
/* ----------------------------------------------------------- */
/*         Copyright: Microsoft Corporation                    */
/*          1995-2000 Redmond, Washington USA                  */
/*                    http://www.microsoft.com                 */
/*                                                             */
/*   Use of this software is governed by a License Agreement   */
/*    ** See the file License for the Conditions of Use  **    */
/*    **     This banner notice must not be removed      **    */
/*                                                             */
/* ----------------------------------------------------------- */
/*         File: HRec.c  Viterbi Recognition Engine Library    */
/* ----------------------------------------------------------- */

char *hrec_version = "!HVER!HRec:   3.3 [CUED 28/04/05]";
char *hrec_vc_id = "$Id: HRec.c,v 1.1.1.1 2005/05/12 10:52:51 jal58 Exp $";

#include "HShell.h"
#include "HMem.h"
#include "HMath.h"
#include "HWave.h"
#include "HAudio.h"
#include "HParm.h"
#include "HLabel.h"
#include "HModel.h"
#include "HDict.h"
#include "HNet.h"
#include "HRec.h"
#include "HUtil.h"
#include "HAdapt.h"

/* Trace levels */

#define T_NGEN 1

/* Checks */

#define SANITY

static int trace=0;
static Boolean forceOutput=FALSE;

const Token null_token={LZERO,0.0,NULL,NULL};

/* Define macros for assessing node type */
#define node_hmm(node) ((node)->type & n_hmm)
#define node_word(node) ((node)->type == n_word)
#define node_tr0(node) ((node)->type & n_tr0)
#define node_wd0(node) ((node)->type & n_wd0)

/* Reduced storage requirements for merged paths */
struct nxtpath
{
   Path *prev;          /* Previous word record */
   LogDouble like;      /* Likelihood at boundary */
   LogFloat lm;         /* LM likelihood of current word */
   
   NxtPath *chain;      /* Next of NBest Paths */
};

/* Extra alignments information for state/model level traceback */
struct align
{
   short state;         /* State level traceback info */
   NetNode *node;       /* Node for which alignment information present */
   Align *prev;         /* Previous align record */

   LogDouble like;      /* Likelihood upon entering state/model end */
   int frame;           /* Frame number upon entering state/model end */
   
   Boolean used;        /* Reference to struct by current inst */
   int usage;           /* Times struct ref'd (by align or path) */

   Align *link;         /* Next align in list */
   Align *knil;         /* Prev align in list */
};

/* NBest token handling is kept private */
typedef struct reltoken
{
   LogFloat like;       /* Relative Likelihood of token */
   LogFloat lm;         /* LM likelihood of token */
   Path *path;          /* Route (word level) through network */
}
RelToken;

/* A tokenset is effectively a state instance */
typedef struct tokenset
{
   short n;                  /* Number of rtok valid (0==1-best, 1>==N-best) */
   RelToken *set;            /* Likelihood sorted array[0..nToks] of rtoks */
   Token tok;                /* Most likely Token in state */
}
TokenSet;

/* Need some null RelTokens */
static const RelToken rmax={0.0,0.0,NULL};    /* First rtok same as tok */
static const RelToken rnull={LZERO,0.0,NULL}; /* Rest can be LZERO */

/* The instances actually store tokens and links etc */
/* Instances are stored in creation/token propagation order to allow */
/* null/word/tee instances to be connected together and still do propagation */
/* in one pass.  Only HMMs need extra tokens, others are 1 state */
struct _NetInst
{
   struct _NetInst *link; /* Doubly linked list of instances, forward */
   struct _NetInst *knil; /* Doubly linked list of instances, backward */

   NetNode *node;       /* Position of instance within network */

   int flags;           /* Flags, active ... */
   TokenSet *state;     /* TokenSet[0..N-2] in state [1..N-1] for hmm */
   TokenSet *exit;      /* TokenSet in exit state */

   LogFloat wdlk;       /* Max likelihood of t=0 path to word end node */
   LogFloat max;        /* Likelihood for pruning of instance */

   Boolean pxd;         /* External propagation done this frame */
   Boolean ooo;         /* Instance potentially out of order */

#ifdef SANITY
   int ipos;
#endif
};

/* HMMSet information is some precomputed limits plus the precomps */
typedef struct precomp
{
   int id;                  /* Unique identifier for current frame */
   LogFloat outp;           /* State/mixture output likelihood */
}
PreComp;

struct psetinfo
{
   MemHeap heap;            /* Memory for this set of pre-comps */
   HMMSet *hset;            /* HMM Set for recognition */

   int max;                 /* Max states in HMM set */
   Boolean mixShared;
   int nsp;
   PreComp *sPre;           /* Array[1..nsp] State PreComps */
   int nmp;
   PreComp *mPre;           /* Array[1..nmp] Shared mixture PreComps */
   int ntr;
   short ***seIndexes;      /* Array[1..ntr] of seIndexes */
   Token *tBuf;             /* Buffer Array[2..N-1] of tok for StepHMM1 */
   TokenSet *sBuf;          /* Buffer Array[2..N-1] of tokset for StepHMM1_N */

   short stHeapNum;         /* Number of separate state heaps */
   short *stHeapIdx;        /* Array[1..max] of state to heap index */
};

/* Private recognition information PRecInfo. (Not visible outside HRec) */
/* Contains all status/network/allocation/pruning information for a     */
/*  single network.                                                     */
struct precinfo {
   /* Input parameters - Set once and unseen */

   Observation *obs;         /* Current Observation */

   PSetInfo *psi;           /* HMMSet information */
   Network *net;            /* Recognition network */
   int nToks;               /* Maximum tokens to propagate (0==1) */
   Boolean models;          /* Keep track of model history */
   Boolean states;          /* Keep track of state history */

   float scale;             /* LM (Net probs) scale factor */
   LogFloat wordpen;        /* Word insertion penalty */
   float pscale;            /* Pronunciation probs scale factor */
   /* Private global info */


   int frame;               /* Current frame number */
   int id;                  /* Unique observation identifier */
   int prid;                /* Unique pri identifier */

   NetNode *genMaxNode;     /* Most likely node in network */
   NetNode *wordMaxNode;    /* Most likely word end node in network */

   Token genMaxTok;         /* Most likely token */
   Token wordMaxTok;        /* Most likely word end token */

   LogFloat genThresh;      /* Cutoff from global beam */
   LogFloat wordThresh;     /* Cutoff for word end propagation */
   LogFloat nThresh;        /* Cutoff for non-best tokens */

   LogFloat *qsa;           /* Array form performing qsort */
   int qsn;                 /* Sizeof qsa */

   MemHeap instHeap;        /* Inst heap */
   MemHeap *stHeap;         /* Array[0..stHeapNum-1] of heaps for states */
   MemHeap rTokHeap;        /* RelToken heap */
   MemHeap pathHeap;        /* Path heap */
   MemHeap rPthHeap;        /* NxtPath heap */
   MemHeap alignHeap;       /* Align heap */

   int npth;                /* Current number of path records */
   int cpth;                /* Number of path records after last collection */
   Path pYesRef;            /* Head of PathYesRef linked list */
   Path pNoRef;             /* Head of PathNoRef linked list */
   Path pYesTail;           /* Tail of PathYesRef linked list */
   Path pNoTail;            /* Tail of PathNoRef linked list */

   int nalign;              /* Current number of align records */
   int calign;              /* Number of align records after last collection */
   Align aYesRef;           /* Head of AlignYesRef linked list */
   Align aNoRef;            /* Head of AlignNoRef linked list */
   Align aYesTail;          /* Tail of AlignYesRef linked list */
   Align aNoTail;           /* Tail of AlignNoRef linked list */

   int nact;                /* Number of active instances */
   int tact;                /* Cummulative number of active instances */
   NetInst head;            /* Head (oldest) of Inst linked list */
   NetInst tail;            /* Tail (newest) of Inst linked list */
   NetInst *nxtInst;        /* Inst used to select next in step sequence */
#ifdef SANITY
   NetInst *start_inst;     /* Inst that started a move */
   int ipos;                /* Current inst position */

   int pnlen;               /* Number of PathNoRef list */
   int pylen;               /* Number of PathYesRef list */

   int anlen;               /* Number of AlignNoRef list */
   int aylen;               /* Number of AlignYesRef list */
#endif

};

/* Global variable (so we want to get rid of them) */
static PRecInfo *pri;
static AdaptXForm *inXForm;

/* Module Initialisation */
static ConfParam *cParm[MAXGLOBS];      /* config parameters */
static int nParm = 0;


/* EXPORT->InitRec: register module & set configuration parameters */
void InitRec(void)
{
   int i;
   Boolean b;

   Register(hrec_version,hrec_vc_id);
   nParm = GetConfig("HREC", TRUE, cParm, MAXGLOBS);
   if (nParm>0){
      if (GetConfInt(cParm,nParm,"TRACE",&i)) trace = i;
      if (GetConfBool(cParm,nParm,"FORCEOUT",&b)) forceOutput = b;
   }
}


/* Basic token merging step used during propagation.  在传播中使用的基本的token合并步骤*/ 
/* Token in cmp plus extra info from src merged into res. 将cmp中的Token和来自src中的附加信息合并到res中*/
/*  tokens less likely that info.nThresh ignored. 忽略似然度小于info.nThresh的tokens */
static void TokSetMerge(TokenSet *res,Token *cmp,TokenSet *src)
{
   Path *path;
   TokenSet tmp;
   LogFloat diff,like,limit;
   RelToken *cur,*mch,rtoks[MAX_TOKS];
   NetNode *node, *nodes[MAX_TOKS];
   int i,nw,k,null,aux;

#ifdef SANITY
   if (res->n==0) 
      HError(8590,"TokSetMerge: Not doing NBest");
   if ((res->n!=0 && src->n==0) || (res->n==0 && src->n!=0))
      HError(8590,"TokSetMerge: TokenSet size mismatch");
#endif
   /*当cmp->like>=res->tok.like时执行下列操作，从当cmp->like=res->tok.like时也使用新token，确保了执行传播时替换路径，*/
   /*  Do >= to ensure that when equal new token will be used every time in */
   /*   order to ensure that when propagation is redone paths are replaced. */
   if (cmp->like>=res->tok.like) {
      if (cmp->like>pri->nThresh) {
         if (res->tok.like>pri->nThresh) {
            /* Need to exchange res and src需要将res和src进行交换 */

            tmp.tok=res->tok;
            res->tok=*cmp;
            for (k=0;k<res->n;k++) rtoks[k]=res->set[k];
            for (k=0;k<src->n;k++) res->set[k]=src->set[k];
            tmp.n=res->n;
            res->n=src->n;
            tmp.set=rtoks;
         }
         else {
            /* Just need to copy src to res进需要将src复制到res中 */

            res->tok=*cmp;
            for (k=0;k<src->n;k++) res->set[k]=src->set[k];
            res->n=src->n;
            return;
         }
      }
      else
         return;
   }
   else { 
      /* Don't copy src->set just for comparison 不复制src->set，仅为了比较*/

      if (cmp->like > pri->nThresh) {
         tmp.tok=*cmp;
         tmp.set=src->set;
         tmp.n=src->n;
      }
      else
         return;
   }

#ifdef SANITY
   if (tmp.tok.like>res->tok.like)
      HError(8590,"TokSetMerge: Tokens not exchanged");
#endif

   diff=res->tok.like-tmp.tok.like;/*替换后的似然度的差*/
   
   for (i=nw=null=0,cur=res->set;i<res->n;i++,cur++) {
      for (path=cur->path;path!=NULL;path=path->prev)
         if (path->node->info.pron != NULL)
            break;
      if (path==NULL) 
         null=i+1;
      else {
         /* allow for NULL nodes in path 允许路径中有NULL节点*/
         node=path->node;
         node->aux = i+1; 
         nodes[nw++] = node;
      }
   }
   
   limit=pri->nThresh-tmp.tok.like;
   for (i=0,cur=tmp.set;i<tmp.n;i++,cur++) {
      if (cur->like<limit) break;
      
      /* allow for NULL nodes in path */
      for (path=cur->path;path!=NULL;path=path->prev)
         if (path->node->info.pron != NULL)
            break;
      if (path==NULL)
         aux=null, node=NULL;
      else {
         node=path->node;
         aux=node->aux;
      }
      like=cur->like-diff;
      mch=NULL;
      /* Find matching tok/path if one (still)exists */
      if (aux!=0) {
         for (k=aux-1;k<res->n;k++) {
            for (path=res->set[k].path;path!=NULL;path=path->prev)
               if (path->node->info.pron != NULL)
                  break;
            if (path==NULL) {
               /* NULL paths match null paths */
               if (!node || !node->info.pron->word) {
                  mch=res->set+k;
                  break;
               }
            }
            else if (node && node->info.pron->word) {
               /* should compare actual net node, not the pron to avoid 
                  incorrectly merging two distinct paths */
               if (path->node==node) {
                  mch=res->set+k;
                  break;
               }