hnet.c

Hidden Markov Toolkit (HTK) 3.2.1 HTK is a toolkit for use in research into automatic speech recogn

      /* Clear hash table */
      GetSubLat(NULL,NULL); 
      /* Set all chain fields to NULL */
      lat->chain=NULL; 
      SubLatList(lat,NULL,1);
      /* Set chain fields to make linked list */
      lat->chain=lat; 
      list=SubLatList(lat,lat,1);
      /* Disconnect loop */
      list->chain=NULL;
      /* Copy last to first Lattices to ensure lat is first thing on stack */
      *fLat=*lat; lat=fLat;
   }
   return(lat);
}

/* ----------------------- ExpandLattice -------------------------- */

static DictEntry specialNull;

/* ExpandedLatticeSize: Calculate the size of the new lattice */
static void ExpandedLatticeSize(Lattice *lat, int *nNodes,int *nArcs)
{
   int i; 
   NodeId thisNode;

   for (i=0; i<lat->nn; i++) {
      thisNode = lat->lnodes+i;
      if (thisNode->word == lat->voc->subLatWord && thisNode->sublat != NULL) {
         if (thisNode->tag != NULL) {
            *nNodes += 1;  
            *nArcs  += 1;
            if (sublatmarkers) {
               *nNodes += 1;  
               *nArcs  += 1;
            }
         }
         ExpandedLatticeSize(thisNode->sublat->lat,nNodes,nArcs);   
      }
   }
   *nNodes += lat->nn;  
   *nArcs  += lat->na;
}

/* CopyLattice: copy lattice from lat to newlat starting at offsets         */
/*              *newNodes and *newArcs - ignore NULL id words if ignoreNull */
void CopyLattice(Lattice *lat, Lattice *newlat, 
                 int *newNodes, int *newArcs, Boolean ignoreNull)
{
   int i,j;
   LNode *oldNode,*newNode;
   LArc *oldArc,*newArc;

   for (i=0,j=0; i< lat->nn; i++) {
      oldNode = lat->lnodes+i;
      if ((oldNode->word != &specialNull) || !ignoreNull) {
         newNode = newlat->lnodes+j+*newNodes;
         newNode->word = oldNode->word;
         newNode->tag = NULL;
         if (oldNode->tag != NULL)
            newNode->tag = oldNode->tag;
         newNode->sublat = oldNode->sublat;
         if (oldNode->foll != NULL) {
            newNode->foll=NumbLArc(newlat,
                                   *newArcs+LArcNumb(oldNode->foll,lat));
            for (oldArc=oldNode->foll; oldArc != NARC; oldArc = oldArc->farc) {
               newArc = NumbLArc(newlat,*newArcs+LArcNumb(oldArc,lat));
               newArc->start = newNode;
               newArc->lmlike = oldArc->lmlike;
               newArc->prlike = oldArc->prlike;
            }
         }
         else
            newNode->foll = NULL;
         if (oldNode->pred != NULL) {
            newNode->pred = NumbLArc(newlat,
                                     *newArcs+LArcNumb(oldNode->pred,lat));
            for (oldArc = oldNode->pred; oldArc != NARC; oldArc = oldArc->parc) {
               newArc = NumbLArc(newlat,*newArcs+LArcNumb(oldArc,lat));
               newArc->end = newNode;
               newArc->lmlike = oldArc->lmlike;
               newArc->prlike = oldArc->prlike;
            }
         }
         else
            newNode->pred = NULL;
         j++;
      }
   }
   for (i=0; i< lat->na; i++) {
      oldArc = NumbLArc(lat,i);
      newArc = NumbLArc(newlat,i+*newArcs);
      if (oldArc->farc != NULL)
         newArc->farc = NumbLArc(newlat,*newArcs+LArcNumb(oldArc->farc,lat));
      else
         newArc->farc = NULL;
      if (oldArc->parc != NULL)
         newArc->parc = NumbLArc(newlat,*newArcs+LArcNumb(oldArc->parc,lat));
      else
         newArc->parc = NULL;
   }
   *newNodes += j;
   *newArcs += lat->na;
}

/*  SubLattice: sub latStart/latEnd in place of thisNode in newlat */
void SubLattice(Lattice *newlat,NodeId thisNode, NodeId latStart,NodeId latEnd)
{
   ArcId thisArc;

   for (thisArc = thisNode->foll; thisArc != NULL; thisArc=thisArc->farc)
      thisArc->start = latEnd;
   for (thisArc = thisNode->pred; thisArc != NULL; thisArc=thisArc->parc)
      thisArc->end = latStart;
   latStart->pred = thisNode->pred;
   latEnd->foll = thisNode->foll;
   thisNode->pred = thisNode->foll = NARC;
   thisNode->word = &specialNull;
}


/* ExpandLattice: Expand all the subLats in newlat (recursively) */
static void ExpandLattice(Lattice *newlat, int nNodes, int nArcs)
{
   int i;
   NodeId thisNode;
   NodeId latStart,latEnd,node;
   ArcId arc;
   int newNodes, newArcs;
   int len;
   Lattice *subLat;

   for (i=0; i< nNodes; i++) {
      thisNode = newlat->lnodes+i;
      if (thisNode->word == newlat->voc->subLatWord) {
         newNodes = nNodes; newArcs = nArcs;
         subLat = thisNode->sublat->lat;
         CopyLattice(subLat,newlat,&newNodes,&newArcs,FALSE);
         if (thisNode->tag != NULL) {
            latStart = newlat->lnodes + nNodes +
               (FindLatStart(subLat)-subLat->lnodes);
            latEnd = newlat->lnodes + nNodes +
               +(FindLatEnd(subLat)-subLat->lnodes);
           
            if (sublatmarkers) {
               /* add sublat start marker */
               node = newlat->lnodes + newNodes;
               arc = NumbLArc(newlat,newArcs);
               node->word=GetWord(newlat->voc,GetLabId("!NULL", TRUE),TRUE);
               node->tag=SafeCopyString(newlat->heap,subLatStart);
               /* node->word=GetWord(newlat->voc,
                  GetLabId(subLatStart, TRUE),TRUE);
                  if (node->word->pron==NULL)
                  NewPron(newlat->voc,node->word,0,NULL,
                  node->word->wordName,1.0); */

               arc->start = node;
               arc->end = latStart;
               node->foll = arc;
               latStart->pred = node->foll;
               latStart = node;
             
               newNodes++; newArcs++;
             
               /* add sublat end marker */
               node = newlat->lnodes + newNodes;
               arc = NumbLArc(newlat,newArcs);
               node->word=GetWord(newlat->voc,GetLabId("!NULL", TRUE),TRUE);
               len = strlen(subLatEnd) + strlen(thisNode->tag) + 4;
               node->tag=(char *) New(newlat->heap,sizeof(char)*len);
               strcpy(node->tag, subLatEnd);
               strcat(node->tag, "-");
               strcat(node->tag, thisNode->tag);
               /* node->word=GetWord(newlat->voc,
                  GetLabId(subLatEnd, TRUE),TRUE);
                  if (node->word->pron==NULL)
                  NewPron(newlat->voc,node->word,0,NULL,
                  node->word->wordName,1.0);*/
             
               arc->start = latEnd;
               arc->end = node;
               latEnd->foll = arc;
               node->pred = latEnd->foll;
               node->foll = NARC;
               latEnd = node;
             
               newNodes++; newArcs++;
            }
            else {
               /* add a tagged !NULL node holding the sublat name tag */
               node = newlat->lnodes + newNodes;
               arc = NumbLArc(newlat,newArcs);
               arc->start = latEnd;
               arc->end = node;
               latEnd->foll = arc;
               node->foll=NARC;
               node->pred=arc;
               node->word=GetWord(newlat->voc,GetLabId("!NULL", TRUE),TRUE);
               node->tag=SafeCopyString(newlat->heap,thisNode->tag);
               latEnd = node; 
             
               newNodes++; newArcs++;
            }
         }
         else {
            latStart = newlat->lnodes + nNodes +
               (FindLatStart(subLat)-subLat->lnodes);
            latEnd = newlat->lnodes + nNodes +
               +(FindLatEnd(subLat)-subLat->lnodes);
         }
         SubLattice(newlat,thisNode,latStart,latEnd);
         nNodes = newNodes; nArcs = newArcs;
      }
   }
}

/* CountNonNullNodes: count the nodes with a non-NULL word id */
static int CountNonNullNodes(Lattice *lat)
{
   int i,count=0;
   NodeId thisNode;
   
   for (i=0; i< lat->nn; i++) {
      thisNode = lat->lnodes+i;
      if (thisNode->word != &specialNull) 
         count++;
   }
   return count;
}

/* EXPORT->ExpandMultiLevelLattice: Expand multi-level lattice lat  */
/*                                  into a single-level lattice.    */ 
Lattice *ExpandMultiLevelLattice(MemHeap *heap, Lattice *lat, Vocab *voc)
{
   Lattice *newlat;
   Lattice *final;
   int  nArcs, nNodes;
   int newArcs, newNodes;   

   nNodes = nArcs = 0;
   ExpandedLatticeSize(lat,&nNodes,&nArcs);        
   newlat = NewLattice(&gstack,nNodes,nArcs);
   newlat->voc = lat->voc;
   newArcs = newNodes = 0;
   CopyLattice(lat,newlat,&newNodes,&newArcs,FALSE);  /* copy the top level  */
   ExpandLattice(newlat,newNodes,newArcs);        /* expand all sub-lats */
   nNodes = CountNonNullNodes(newlat);
   final = NewILattice(heap,nNodes,nArcs,lat);              
   newArcs = newNodes = 0;
   CopyLattice(newlat,final,&newNodes,&newArcs,TRUE); /* remove NULL id nodes */
   Dispose(&gstack,newlat);

   final->subList=NULL;  /* Actually unnecessary */

   return final;
}


/* ------------------------ Misc Lattice Ops ------------------------- */

/* EXPORT->LatticeFromLabels: Create lattice from label list for alignment */
Lattice *LatticeFromLabels(LabList *ll,LabId bnd,Vocab *voc,MemHeap *heap)
{
   Lattice *lat;
   LNode *ln;
   LArc *la;
   LLink l;
   LabId labid;
   int i,n,N;

   N=CountLabs(ll);  /* total number of symbols */
   n=1;              /* index of first word in list */
   if (bnd!=NULL) N+=2,n--;
   lat=NewLattice(heap,N,N-1);
   lat->voc=voc;
   for (i=1,ln=lat->lnodes;i<=N;i++,ln++,n++) {
      if (bnd!=NULL && (i==1 || i==N)) {
         labid=bnd;
      }
      else {
         l=GetLabN(ll,n);
         labid=l->labid;
      }
      /* Node */
      ln->n=i-1;
      if ((ln->word=GetWord(voc,labid,FALSE))==NULL)
         HError(8220,"LatticeFromLabels: Word %s not defined in dictionary",
                labid->name);
      ln->v=-1;
      ln->time=0.0;
      ln->foll=ln->pred=NULL;
      ln->score=0.0;
      ln->hook=NULL;
      if (i!=1) {
         /* Arc */
         la=NumbLArc(lat,i-2);
         la->start=ln-1;
         la->end=ln;
         la->lmlike=0.0;
         la->prlike=0.0;
         la->farc=la->parc=NULL;
         la->end->pred=la->start->foll=la;
      }
   }
   return(lat);
}


/* EXPORT->NumNodeFoll: return num outgoing arcs from node n */
int NumNodeFoll(NodeId n)
{
   int c = 0;
   ArcId a;
   
   for (a = n->foll; a != NARC; a=a->farc) ++c;
   return c;
}

/* EXPORT->NumNodePred: return num outgoing arcs from node n */
int NumNodePred(NodeId n)
{
   int c = 0;
   ArcId a;
   
   for (a = n->pred; a != NARC; a=a->parc) ++c;
   return c;
}


/* EXPORT->FindLatStart: find and return the lattice start node */
NodeId FindLatStart(Lattice *lat)
{
   int i;
   NodeId ln;

   for(i=0,ln=lat->lnodes;i<lat->nn;i++,ln++)
      if (ln->pred==NARC)
         return ln;
   HError(8252,"FindLatStart: lattice has no start node");
   return(NARC);
}

/* EXPORT->FindLatEnd: find and return the lattice end node */
NodeId FindLatEnd(Lattice *lat)
{
   int i;
   NodeId ln;

   for(i=0,ln=lat->lnodes;i<lat->nn;i++,ln++)
      if (ln->foll==NARC)
         return ln;
   HError(8252,"FindLatEnd: lattice has no end node");
   return(NARC);
}



/* --------------------------- Network Routines ------------------------ */

static void PrintNode(NetNode *node,HMMSet *hset)
{
   printf("Node[%05d] ",(((unsigned) node)/sizeof(NetNode))%100000);
   if (node->type & n_hmm)
      printf("{%s}\n",HMMPhysName(hset,node->info.hmm));
   else if (node->type == n_word && node->info.pron==NULL) {
      printf("NULL");
      if (node->tag != NULL)
         printf(" ... tag=%s\n",node->tag);
      else
         printf("\n");
   }
   else if (node->type == n_word) {
      printf("%s",node->info.pron->word->wordName->name);
      if (node->tag != NULL)
         printf(" ... tag=%s\n",node->tag);
      else
         printf("\n");
   }
   else
      printf("{%d}\n",node->type);
   fflush(stdout);

}

static void PrintLinks(NetLink *links,int nlinks)
{
   int i;

   for (i=0; i<nlinks; i++) {
      printf("    %-2d: -> [%05d] == %7.3f\n",i,
             (((unsigned) links[i].node)/sizeof(NetNode)%100000),
             links[i].like);
      fflush(stdout);
   }
}

static void PrintChain(Network *wnet,HMMSet *hset)
{
   NetNode *thisNode;
   
   thisNode = wnet->chain;
   while (thisNode != NULL) {
      PrintNode(thisNode,hset);
      PrintLinks(thisNode->links,thisNode->nlinks);
      thisNode = thisNode->chain;
   }
}

static Boolean IsWd0Link(NetLink *link)
{
   int i;
   NetNode *nextNode;

   nextNode = link->node;
   if ((nextNode->type&n_nocontext) == n_word)
      return TRUE;
   if (nextNode->type & n_tr0) {
      for (i = 0; i < nextNode->nlinks; i++)