hparse.c

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

      --(ls->numLinks);
      for (j=i;j<=ls->numLinks;j++) 
         ls->links[j] = ls->links[j+1];
   }
}

/* MergeLinks: adds all links from *from to *to */
static LinkSet*  MergeLinks(LinkSet *from, LinkSet *to)
     /* note: makes a new link set if *to is not large enough */
     /*       returns the merged link set */
{
   int i,j;
   LinkSet *newls;

   for (i=1; i<= from->numLinks; i++)     /* Remove any duplicates from to */
      DeleteLink(from->links[i], to);       
   if (from->numLinks > (to->maxLinks - to->numLinks))
      {
         newls = CreateLinkSet((int) ((from->numLinks+to->numLinks)*LINKEXTENTFACTOR));
         for (i=1; i<=to->numLinks; i++)
            newls->links[i] = to->links[i];
         newls->numLinks = to->numLinks;
         to = newls;
      }   
   for (i=to->numLinks+1, j=1; j<= from->numLinks; i++, j++)
      to->links[i] = from->links[j];
   to->numLinks += from->numLinks;
   return to;
}

/* CanCompact: Determine if a Gluenode should be compacted */
static Boolean CanCompact(Link p)
     /* compact if p either all succs are non-glue 
           or all preds are non-glue
           or only 1 succ and one pred (both glue)
           or no succs or no preds
*/
{
   int i;
   Boolean ok =TRUE;    
   Link predNode,succNode;

   for (i=1; (i <= p->succ->numLinks) && ok ; i++) {
      succNode = p -> succ->links[i];
      ok = (succNode -> modelName != NULL);
   }
   if (!ok) {
      ok = TRUE;    
      for (i=1; (i <= p->pred->numLinks) && ok ; i++) {
         predNode = p -> pred->links[i];
         ok = (predNode -> modelName != NULL);
      }
   }
   if (!ok)
      ok = ((p->succ->numLinks == 1) && (p->pred->numLinks == 1));
   return ok;
}

/* CompactGlueNode: move all the links from/to node *p to its neighbours */
static void CompactGlueNode(Link p)
{
   int i,j;
   Link predNode, succNode;
   Link predNode2, succNode2;
   LinkSet *oldls;

   /* first process the successors of of the predessor nodes to p */
   DeleteLink(p, p->succ);  /* delete self loop if present */
   for (i=1; i<= p->pred->numLinks; i++) {
      predNode = p->pred->links[i];
      if (predNode == p) continue;
      if (predNode->succ->numLinks == 1) { /* only pointed to this node */
         FreeLinkSet(predNode ->succ);
         predNode->succ = p->succ;
         predNode->succ->nUse++;
      } else {
         if (predNode->succ->nUse > 1) { /* the succ is shared */
                                         /* and hasn't been processed yet */
            oldls =  predNode->succ;
            DeleteLink(p, predNode->succ);
            predNode->succ  = MergeLinks(p->succ,predNode->succ);
            predNode->succ->nUse = -(oldls->nUse);   /* mark as processed */
            for (j=1; j<= p->pred->numLinks; j++) {  /* point other shared ls*/
               predNode2 = p ->pred->links[j];       /* to new linkset */
               if (predNode2->succ == oldls)
                  predNode2->succ = predNode->succ;
            }
            if (oldls != predNode->succ)    /* did the linkset change? */
               FreeLinkSet(oldls);
         }
         else if (predNode->succ->nUse == 1) {    /* non-shared link sets */
            DeleteLink(p, predNode->succ);
            predNode->succ  = MergeLinks(p->succ,predNode->succ);
         }
      }
   }
   for (i=1; i<= p->pred->numLinks; i++) {   /* clean up nUse markers */
      predNode = p -> pred->links[i];
      if (predNode->succ->nUse < 0)
         predNode->succ->nUse = -(predNode->succ->nUse);
   }

   /* now do the predecessors of the successor nodes to p */
   DeleteLink(p, p->pred);  /* delete self loop if present */
   for (i=1; i<= p->succ->numLinks; i++) {
      succNode = p -> succ->links[i];
      if (succNode ->pred ->numLinks == 1) { /* only pointed to this node */
         FreeLinkSet(succNode ->pred);
         succNode->pred = p->pred;
         succNode->pred->nUse++;
      }
      else {
         if (succNode->pred->nUse > 1) { /* the pred is shared */
                                         /* and hasn't been processed yet */
            oldls =  succNode->pred;
            DeleteLink(p, succNode->pred);
            succNode->pred  = MergeLinks(p->pred,succNode->pred);
            succNode->pred->nUse = -(oldls->nUse);   /* mark as processed */
            for (j=1; j<= p->succ->numLinks; j++) {  /* point other shared ls*/
               succNode2 = p -> succ->links[j];      /* to new linkset */
               if (succNode2->pred == oldls)
                  succNode2->pred = succNode->pred;
            }
            if (oldls != succNode->pred)    /* did the linkset change? */
               FreeLinkSet(oldls);
         }
         else if (succNode->pred->nUse == 1) {    /* non-shared link sets */
            DeleteLink(p, succNode->pred);
            succNode->pred  = MergeLinks(p->pred,succNode->pred);
         }
      }
   }
   for (i=1; i<= p->succ->numLinks; i++) {   /* clean up nUse markers */
      succNode = p -> succ->links[i];
      if (succNode->pred->nUse < 0)
         succNode->pred->nUse = -(succNode->pred->nUse);
   }
}

/* RemoveGlue: removes all the glue nodes in the network */
static void  RemoveGlue(HPNetwork *network)
     /* note: takes care to retain LinkSet sharing (where possible) */
{
   Link p,q;
   int numGlueLeft=0;
   Boolean removedp;
   Boolean changed=FALSE;
   Boolean removeAll=FALSE;
   int iter = 0;
   
   if (network->entryNode->modelName==NULL) network->entryNode->modelName=enterExitId;
   if (network->exitNode->modelName==NULL) network->exitNode->modelName=enterExitId;
   do {   /* compact nodes until no glue left  */
      if ((numGlueLeft > 0) && (!changed))
         removeAll = TRUE;
      numGlueLeft = 0; 
      changed = FALSE;
      if (trace & T_HPREMGLUE) {
         printf("RemoveGlue Iteration: %d\n",iter);
         PrintHParseNetwork(network);
      }
      p=network->chain; network->chain=NULL; 
      while (p!=NULL) {         /* while there are nodes left to process */
         removedp = FALSE;
         if (p->modelName==NULL) {        /* then its a glue node */
            if ( CanCompact(p) || removeAll ) {
               CompactGlueNode(p);
               q=p; p=p -> chain; FreeNode(q);
               removedp = TRUE; changed = TRUE;
            } 
            else
               numGlueLeft++; 
         } 
         if (!removedp) {     
            /* not changed on this pass so add to head of new chain */
            q = p->chain;
            p->chain = network->chain;
            network->chain = p;
            p = q;
         }
      }
      iter++;
   }
   while (numGlueLeft != 0); 
   if (network->entryNode->modelName==enterExitId) network->entryNode->modelName=NULL;
   if (network->exitNode->modelName==enterExitId) network->exitNode->modelName=NULL;
}

/* DisconNode: Is a node disconnected from the network */
static Boolean DisconNode(Link p)
{
   if (p->succ == NULL || p->pred == NULL)
      return TRUE;
   if (p->succ->numLinks == 0 || p->pred->numLinks == 0)
      return TRUE;
   return FALSE;
}

/* RemoveDiscon: remove any nodes (glue or ortherwise) that are */
/*               not properly connected to the network          */
static void RemoveDiscon(HPNetwork *net)
{
   Link p,q;
   Link succNode, predNode;
   Boolean removedp;
   Boolean changed;
   int i;
       
   do {   /* until no changes  */
      changed = FALSE;
      p=net->chain; net->chain=NULL; 
      while (p!=NULL) {        /* while nodes left to process */
         removedp = FALSE;
         if (p != net->entryNode && p != net->exitNode)
            if (DisconNode(p)) { 
               if (p->succ != NULL)
                  for (i=1; i<=p->succ->numLinks; i++) {
                     succNode = p->succ->links[i];
                     DeleteLink(p, succNode->pred);
                  }
               if (p->pred != NULL)
                  for (i=1; i<=p->pred->numLinks; i++) {
                     predNode = p->pred->links[i];
                     DeleteLink(p, predNode->succ);
                  }
               q=p; p=p->chain; FreeNode(q);
               removedp = TRUE; changed = TRUE;
            } 
         if (!removedp) {    /* not changed so add to new chain */   
            q = p->chain;
            p->chain = net->chain;
            net->chain = p;
            p = q;
         }
      }
   }
   while (changed);
}

/* -------------------- Main HParse Call ----------------------------- */

/* CreateHParseNetwork: parse and build a network */
static HPNetwork CreateHParseNetwork(char *fname)
{
   Link hd,tl;
   HPNetwork theNet;
   
   /* Create the memory heaps */
   CreateHeap(&nodeHeap,"HParse Node Heap",MHEAP,sizeof(Node), 
              0.0, NODEBLOCK, NODEBLOCK);
   CreateHeap(&lsHeap,"HParse LinkSet Heap",MHEAP,sizeof(LinkSet), 
              0.0, LSBLOCK,  LSBLOCK);
   CreateHeap(&lsChunkHeap,"HParse Link Chunk Heap",MHEAP, 
              LINKCHUNKSIZE*sizeof(Link),0.0, LSBLOCK,  LSBLOCK);
   CreateHeap(&lsLargeHeap,"HParse Large Links Heap",CHEAP,1,0.0,0,0);
   InitScan(fname);
   PGetSym(); 
   PNetwork(&hd,&tl,TRUE,FALSE);
   fclose(f);
   theNet.entryNode = hd;
   theNet.exitNode = tl;
   theNet.chain = curChain;
   RemoveDiscon(&theNet);
   RemoveGlue(&theNet); 
   ReSizeNodes(&theNet); 
   FreeSubNetDefs();
   if (trace & T_HPMEMSTAT) {
      printf("Memory statistics after generating HParse network:\n");
      PrintAllHeapStats();
   }
   return theNet;
}

/* ----------------- End of HParse Network building  -------------------- */



/* ------------   HParse Network -> Lattice Conversion ------------------- */

static MemHeap nodeInfoHeap;

/* AttachNodeInfos: to each node in theNet */
void AttachNodeInfos(HPNetwork *theNet)
{
   Link p;
   NodeInfo *ni;
   
   p = theNet->chain;
   CreateHeap(&nodeInfoHeap,"HParse Node Info Heap",MHEAP,sizeof(NodeInfo),1.5,500,5000);
   while (p!=NULL) {
      ni = (NodeInfo *) New(&nodeInfoHeap,sizeof(NodeInfo));
      p->user = (Ptr)ni; 
      if ((p->modelName == wdBeginId) && v1Compat)
         ni->nType = wdBegin;
      else if ((p->modelName == wdEndId) && v1Compat)
         ni->nType = wdEnd;
      else if (p->modelName == enterId || p->modelName == exitId)
         ni->nType = nullNode;
      else 
         ni->nType = unknown;
      ni->seen = FALSE;
      ni->history = NULL;
      if (p->succ->nUse > 1) {  /* we will put a NULL node here ... */
         ni = (NodeInfo *) New(&nodeInfoHeap,sizeof(NodeInfo));
         p->succ->user = (Ptr) ni;
         ni->nType  = nullNode;
         ni->seen = FALSE;
         ni->history = NULL;
      }
      p = p->chain;
   }
}


/* LabelInternal: mark wdInternal nodes until reach a non-internal node */
void LabelInternal(Link p)
{
   NodeInfo *ni;
   int i;
   
   ni = (NodeInfo *) p->user;
   if (ni->nType == unknown) {
      ni->nType = wdInternal;
      if (!ni->seen) {
         ni->seen = TRUE;
         for (i=1; i <= p->succ->numLinks; i++)
            LabelInternal(p->succ->links[i]);
      }  
   }
   else if ((ni->nType != wdEnd) && (ni->nType != wdInternal))
      HError(3131,"LabelInternal: incorrect WD_BEGIN/WD_END node connection, node %d is %d",((int)p % 4000) / 4,ni->nType);
}

/* FindNodeTypes: mark each node as wdInternal or wdExternal */
void FindNodeTypes(HPNetwork *theNet)
{
   Link p;
   NodeInfo *ni;
   int i;
   
   if (!v1Compat) {   /* label all nodes as external */
      for (p=theNet->chain; p !=NULL; p=p->chain) {
         ni = (NodeInfo *) p->user;
         if (ni->nType == unknown) ni->nType = wdExternal;
      }
      return;
   }
   for (p=theNet->chain; p != NULL; p=p->chain) {
      if (p->modelName == wdBeginId)
         numWdBegin++;
      if (p->modelName == wdEndId)
         numWdEnd++;
   }
   if (numWdBegin != numWdEnd) 
      HError(3131,"FindNodeTypes: Different num WD_BEGIN (%d) & WD_END nodes (%d)",
             numWdBegin, numWdEnd);
   if (numWdBegin > 0) {
      if (trace > 0) {
         printf("  HParse Net contains %d WD_BEGIN/WD_END pairs\n", numWdBegin);
         fflush(stdout);
      }
      /* label the internal nodes as such */
      for (p=theNet->chain; p !=NULL; p=p->chain)
         if (p->modelName == wdBeginId)
            for (i=1; i <=p->succ->numLinks; i++) 
               LabelInternal(p->succ->links[i]);
      /* reset the seen flags  */
      for (p=theNet->chain; p !=NULL; p=p->chain) {
         ni = (NodeInfo *) p->user;
         ni->seen = FALSE;
      }
      /* check all nodes connected to wdBegin are internal */
      for (p=theNet->chain; p !=NULL; p=p->chain) {
         if (p->modelName == wdBeginId)
            for (i=1; i <=p->succ->numLinks; i++) {
               ni = (NodeInfo *) p->succ->links[i]->user;
               if (ni == NULL || ni->nType != wdInternal)
                  HError(3131,"FindNodeTypes: incorrect WD_BEGIN node connection");
            }
      }
   }        
   /* label all other nodes as external */
   for (p=theNet->chain; p !=NULL; p=p->chain) {
      ni = (NodeInfo *) p->user;
      if (ni->nType == unknown)
         ni->nType = wdExternal;
   }
}

/* AddWordExtern: Add a wdExternal node to the dictionary */
void AddWordExtern(Vocab *voc, Link p)
{
   Word wd;
   LabId outSym;

   wd = GetWord(voc,p->modelName,TRUE);
   outSym = p->extName;
   if (outSym == NULL) outSym = GetLabId("",TRUE);
   NewPron(voc,wd,1,&(p->modelName),outSym,1.0);
}

static LabId phonebuf[MAXPHONES];   /* space to store the current pronunciation */

/* AddWordModel: add a pronunciation to dictionary voc */
void AddWordModel(Vocab *voc, Link p, Link history)
{
   Link h;
   NodeInfo *ni;
   Word wd;
   int nphon = 0;

   wd = GetWord(voc,p->extName,TRUE);
   h = history;
   while (h != NULL) {
      if (nphon