/* ----------------------------------------------------------- *//*                                                             *//*                          ___                                *//*                       |_| | |_/   SPEECH                    *//*                       | | | | \   RECOGNITION               *//*                       =========   SOFTWARE                  */ /*                                                             *//*                                                             *//* ----------------------------------------------------------- *//* developed at:                                               *//*                                                             *//*      Speech Vision and Robotics group                       *//*      Cambridge University Engineering Department            *//*      http://svr-www.eng.cam.ac.uk/                          *//*                                                             *//* author: Gunnar Evermann <ge204@eng.cam.ac.uk>               *//* ----------------------------------------------------------- *//*         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 00040static 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_LMtypedef 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));