hlat.c

隐马尔科夫模型工具箱

/* ----------------------------------------------------------- */
/*                                                             */
/*                          ___                                */
/*                       |_| | |_/   SPEECH                    */
/*                       | | | | \   RECOGNITION               */
/*                       =========   SOFTWARE                  */ 
/*                                                             */
/*                                                             */
/* ----------------------------------------------------------- */
/* developed at:                                               */
/*                                                             */
/*      Speech Vision and Robotics group                       */
/*      Cambridge University Engineering Department            */
/*      http://svr-www.eng.cam.ac.uk/                          */
/*                                                             */
/* author: Gunnar Evermann <[e-mail]>               */
/* ----------------------------------------------------------- */
/*         Copyright:                                          */
/*         2001-2002  Cambridge University                     */
/*                    Engineering Department                   */
/*                                                             */
/*   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: HLat.c:  Lattice Manipulation                   */
/* ----------------------------------------------------------- */

/*#### todo:

     - implement lattice oracle WER calculation
     - allow batch processing?
*/


char *hlat_version = "!HVER!HLat:   3.2 [CUED 09/12/02]";
char *hlat_vc_id = "$Id: HLat.c,v 1.3 2002/12/19 16:37:11 ge204 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 "HUtil.h"
#include "HDict.h"
#include "HNet.h"
#include "HLM.h"
#include "HLat.h"

/* ----------------------------- Trace Flags ------------------------- */

#define T_TOP  00001
#define T_PRUN 00002
#define T_FB   00004
#define T_EXP  00010
#define T_MEM  00020
#define T_TRAN 00040

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

/* --------------------------- Global Flags -------------------------- */

static LabId startWord;         /* word at start of Lattice (!SENT_START) */
static LabId endWord;           /* word at end of Lattice (!SENT_END) */
static LabId startLMWord;       /* word at start in LM (<s>) */
static LabId endLMWord;         /* word at end in LM (</s>) */
static LabId nullWord;          /* null word in Lattices (!NULL) */

static MemHeap slaHeap, slnHeap;/* MHEAPs for use in LatExpand() */

/* --------------------------- Prototypes ---------------------------- */


#ifndef NO_LAT_LM
typedef struct _SubLNode SubLNode;
typedef struct _SubLArc SubLArc;

struct _SubLNode {
   union {
      LMState lmstate;
      LNode *newln;
   } data;
   SubLArc *foll;
   SubLNode *next;
};

struct _SubLArc {
   LogFloat lmprob;
   SubLNode *end;
   LArc *la;
   SubLArc *next;
};
#endif

/* --------------------------- Initialisation ---------------------- */

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

   Register(hlat_version,hlat_vc_id);
   nParm = GetConfig("HLAT", TRUE, cParm, MAXGLOBS);
   if (nParm>0){
      if (GetConfInt(cParm,nParm,"TRACE",&i)) trace = i;
   }

#ifndef NO_LAT_LM
   CreateHeap (&slaHeap, "LatExpand arc heap", MHEAP, sizeof (SubLArc), 1.0, 1000, 128000);
   CreateHeap (&slnHeap, "LatExpand node heap", MHEAP,sizeof (SubLNode), 1.0, 1000, 32000);
#endif
}


/* --------------------------- Lattice processing ------------------- */

/* LatCheck

     check lattice for consistency: single start & end nodes; no cycles.
*/
void LatCheck (Lattice *lat)
{
   int i, nStart, nEnd;
   LNode *ln;
   LNode **topOrder;

   /* check for unique start and end nodes */
   nStart = nEnd = 0;
   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln) {
      if (!ln->pred)
         ++nStart;
      if (!ln->foll)
         ++nEnd;
   }

   if (nStart != 1)
      HError (8622, "HLat: lattice has %d start nodes (should be 1)", nStart);
   if (nEnd != 1)
      HError (8622, "HLat: lattice has %d end nodes (should be 1)", nEnd);

   /* check wheter lat is a DAG ( <=> top order exists). */
   topOrder = (LNode **) New (&gcheap, lat->nn * sizeof(LNode *));
   if (!LatTopSort (lat, topOrder))
      HError (8622, "HLat: lattice contains cylces");

   Dispose (&gcheap, topOrder);
}


/* FixPronProbs

     replace pronunciation probabilities in lattices with values taken from
     the dictionary
*/
void FixPronProbs (Lattice *lat, Vocab *voc)
{
   int i, v;
   LNode *ln;
   Pron pron;
   LArc *la;

   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln) {
      if (ln->word != voc->nullWord) {
         if (ln->v > ln->word->nprons)
            HError (8621, "FixPronprbs: lattice refers to non-existing pron");
         pron = ln->word->pron;
         for (v = 2; v <= ln->v; ++v)
            pron = pron->next;
         if (pron->pnum != ln->v)
            HError (8621, "FixPronprbs: dict pron numbering invalid");
         
         for (la = ln->pred; la; la = la->parc)
            la->prlike = pron->prob;
      }
      else {
         for (la = ln->pred; la; la = la->parc)
            la->prlike = 0.0;
      }
   }
}


/* LatStartNode

     return lattice start node

     ###GE: maybe store this in Lattice structure to save time?
*/
LNode *LatStartNode (Lattice *lat)
{
   int i;
   LNode *ln;

   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln)
      if (!ln->pred)
         return ln;

   HError (8622, "HLat: lattice has no start node");
   return NULL;         /* make compiler happy */
}

/* LatEndNode

     return lattice end node

     ###GE: maybe store this in Lattice structure to save time?
*/
LNode *LatEndNode (Lattice *lat)
{
   int i;
   LNode *ln;

   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln)
      if (!ln->foll)
         return ln;

   HError (8622, "HLat: lattice has no end node");
   return NULL;         /* make compiler happy */
}


/* helper function for LatTopSort()
   number preceeding nodes depth first 
*/
void LatTopSortVisit (LNode *ln, int *time)
{
   LArc *la;

   ln->n = -2;          /* mark node as seen, but not numbered, yet (GRAY in CLR) */
   for (la = ln->pred; la; la = la->parc)
      if (la->start->n == -1)
         LatTopSortVisit (la->start, time);
   
   ++(*time);
   ln->n = *time;
}

/* LatTopSort

     sort lattice nodes in topological order
     returns array of LNode pointers.
     uses depth first traversal (in reverse (pred) direction) 
     based on [CLR:1990], p. 485 
*/
Boolean LatTopSort (Lattice *lat, LNode **topOrder)
{
   int time = -1;       /* new numbering will start at 0 */
   int i;
   LNode *ln;
   LArc *la;
   Boolean isDAG = TRUE;

   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln)
      ln->n = -1;        /* mark node as unseen (WHITE in CLR) */

   LatTopSortVisit (LatEndNode (lat), &time);
   
   /* we should have seen all nodes */
   assert (time+1 == lat->nn); 

   /* check topological order */
   for (i = 0, la = lat->larcs; i < lat->na; ++i, ++la)
      if (!(la->start->n < la->end->n)) {
         isDAG = FALSE;
         HError (-8622, "LatTopSort: Lattice contains cycles"); 
         break;
      }

   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln)
      topOrder[ln->n] = ln;
   
   /*#### GE: reset ln->n values? */
   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln)
      ln->n = i;

   return isDAG;
}

/* LatAttachInfo

     allocate & attach an Info structre for each node
*/
void LatAttachInfo (MemHeap *heap, size_t size, Lattice *lat)
{
   int i;
   LNode *ln;
   
   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln)
      ln->hook = (Ptr) New (heap, size);
}

/* LatDetachInfo

     free Info structre for each node
*/
void LatDetachInfo (MemHeap *heap, Lattice *lat)
{
   int i;
   LNode *ln;
   
   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln)
      Dispose (heap, ln->hook);
}


/* LatForwBackw

     perform forward-backward algorithm on lattice and store scores in
     FBInfo structre
     choice of using sum (LATFB_SUM) or max (LATFB_MAX) of scores
*/
LogDouble LatForwBackw (Lattice *lat, LatFBType type)
{
   int i;
   LNode *ln;
   LArc *la;
   LNode **topOrder;
   LogDouble score;

   /* We assume that the FBinfo structures are already allocated. */
   /* init */
   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln) {
      LNodeFw (ln) = LNodeBw (ln) = LZERO;
   }
   LNodeFw (LatStartNode (lat)) = 0.0;
   LNodeBw (LatEndNode (lat)) = 0.0;

   /* find topological order of nodes */
   topOrder = (LNode **) New (&gcheap, lat->nn * sizeof(LNode *));
   if (!LatTopSort (lat, topOrder))
      HError (8622, "LatForwBackw: cannot calculate forw/backw score on Lattice with cycles"); 
      
   /* the processing in the forward and backward directions are really
      almost the same. if the data structures had been done _slightly_
      nicer this could be done in one loop. The only readable way now 
      would be defining a couple of macros... */

   /* forward direction */
   for (i = 0; i < lat->nn; ++i) {
      ln = topOrder[i];
      for (la = ln->foll; la; la = la->farc) {
         assert (la->start == ln);
         
         score = LNodeFw (ln) + LArcTotLike (lat, la);
         switch (type) {
         case LATFB_SUM:
            LNodeFw (la->end) = LAdd (LNodeFw (la->end), score);
            break;
         case LATFB_MAX:
            if (score > LNodeFw (la->end))
               LNodeFw (la->end) = score;
            break;
         default:
            abort ();
         }
      }
   }

   /* backward direction */
   for (i = lat->nn - 1; i >= 0; --i) {
      ln = topOrder[i];
      for (la = ln->pred; la; la = la->parc) {
         assert (la->end == ln);
         
         score = LNodeBw (ln) + LArcTotLike (lat, la);
         switch (type) {
         case LATFB_SUM:
            LNodeBw (la->start) = LAdd (LNodeBw (la->start), score);
            break;
         case LATFB_MAX:
            if (score > LNodeBw (la->start))
               LNodeBw (la->start) = score;
            break;
         default:
            abort ();
         }
      }
   }

   if (trace & T_FB) {
      printf ("forward prob:  %f\n", LNodeFw (topOrder[lat->nn - 1]));
      printf ("backward prob: %f\n", LNodeBw (topOrder[0]));
   }
   score = LNodeBw (topOrder[0]);
   Dispose (&gcheap, topOrder);

   return score;
}

/* EXPORT->LatFindBest

     find the N-best paths (i.e. lowest sum of LArcTotLike()s) and generate
     Transcription.

     ####GE: currently only N=1 is supported
*/
Transcription *LatFindBest (MemHeap *heap, Lattice *lat, int N)
{
   int i;
   LNode *ln;
   LNode **topOrder;
   LArc *la;
   LogDouble score, ac, lm, pr, tot;
   Word nullWord;
   Pron pron;
   Transcription *trans;
   LabList *ll;
   LLink lab;
   
   if (N != 1)
      HError (8690, "FindBest: only 1-best supported, yet.");

   /* during the search ln->score will hold the score of the best
      path to ln (i.e. lowest score). ln->hook will point to
      the arc leading to the preceeding node in this path */

   /* init fields */
   for (i = 0, ln = lat->lnodes; i < lat->nn; ++i, ++ln) {
      ln->score = LZERO;
      ln->hook = NULL;
   }
   LatStartNode (lat)->score = 0.0;

   /* find topological order of nodes */
   topOrder = (LNode **) New (&gcheap, lat->nn * sizeof(LNode *));
   if (!LatTopSort (lat, topOrder))
      HError (8690, "LatFindBest: cannot find best path in Lattice with cycles");

   assert (topOrder[0] == LatStartNode (lat));

   /* traverse nodes in top order */
   for (i = 0; i < lat->nn; ++i) {
      ln = topOrder[i];
      
      /* for all outgoing arcs: propagate scores forward */
      for (la = ln->foll; la; la = la->farc) {
         assert (la->start == ln);
         score = la->start->score + LArcTotLike (lat, la);
         if (score > la->end->score) {
            la->end->score = score;
            la->end->hook = (Ptr) la;
         }
      }
   }

   /* create traqnscription */
   trans = CreateTranscription (heap);
   ll = CreateLabelList (heap, 0);
   
   nullWord = lat->voc->nullWord;

   ac = lm = pr = tot = 0;
   if (trace & T_TRAN)
      printf ("1best trans (wordPron t ac lm pr tot): ");

   /* backtrack from end node along best path and generate transcription */
   ln = LatEndNode (lat);
   la = (LArc *) ln->hook;
   while (la) {
      LabId outlab;

      if (ln->word != nullWord) {
         for (pron = ln->word->pron; pron; pron = pron->next)
            if (pron->pnum == ln->v) 
               break;
         if (pron)
            outlab = pron->outSym;
         else   /* if we can't find pronvar (e.g. wlist), fall back to word */
            outlab = ln->word->wordName;
         if (outlab) {
            lab = CreateLabel (heap, ll->maxAuxLab);
            lab->labid = outlab;
            lab->start = la->start->time * 1.0e7;
            lab->end = ln->time * 1.0e7;
            lab->score = LArcTotLike (lat, la);
            
            lab->succ = ll->head->succ;
            lab->pred = ll->head;
            lab->succ->pred = lab->pred->succ = lab;
         }
      }

      ac += la->aclike;
      lm += la->lmlike;
      pr += la->prlike;
      tot += LArcTotLike (lat, la);
      if (trace & T_TRAN)
         printf ("(%s%d %.2f %.3f %.3f %.3f %.3f) ", ln->word->wordName->name, ln->v,
                 ln->time, la->aclike, la->lmlike, la->prlike, LArcTotLike (lat, la));