hparse.c

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

      TailMerge(p, b);
      (trilist+total)->m = loopEndId;
      (trilist+total)->l = NULL;
      tle = trilist+total; ie = total;
      total++;
   }
   asucc=a->succ;
   if (ie != total-1) {  /* need to swap around */
      SwapSN(trilist+total-1,tle);
      SwapNodeNames(asucc->links[ie+1], asucc->links[total]);
      if (ib == total-1) {
         ib = ie; tlb = trilist+ib;
      }
   }
   if (ib != total-2) {  /* need to swap around */
      SwapSN(trilist+total-2,tlb);
      SwapNodeNames(asucc->links[ib+1], asucc->links[total-1]);
   }
   (trilist+total-2)->l = GetLabId("",TRUE);
   (trilist+total-1)->r = GetLabId("",TRUE);
   return total;
}

/* DoesMatch: returns true if name s is equal to snet or is a
              member of subnet snet */
static int DoesMatch(LabId s, LabId snet)
{
   HPNetwork *subnet;
   Link *p;
   LinkSet *asucc;
   int i;

   if (snet == NULL) return TRUE;            /* No context match required */
   if ((subnet = (HPNetwork *) snet->aux) == NULL) 
      return s == snet;            /* No subnet so use simple match */
   else {
      asucc = subnet->entryNode->succ; p = asucc->links+1;
      for (i=1;i<=asucc->numLinks;i++,p++)
         if (s == (*p)->modelName) return TRUE;
      return FALSE;
   }
}

static void CreateJMat(void)
{
   int i,j;
   unsigned char *p;
   int jmatsize;   
 
   jmatsize = jmRows*sizeof(unsigned char *);
   CreateHeap(&jMatHeap,"HParse JMat Heap",MSTAK,1,0.0,jmatsize,jmatsize);
   jmat = (JoinMatrix) New(&jMatHeap,jmRows*sizeof(unsigned char *));
   for (i=0; i<jmRows; i++){
      p = (unsigned char *) New(&jMatHeap,jmCols);
      for (j=0;j<jmCols;j++) p[j] = 0;
      jmat[i] = p;
   }
}

static void ClearJMat(void)
{
   int i,j;
   
   for (i=0; i<jmRows; i++)
      for (j=0; j< jmCols; j++)
         jmat[i][j] = 0;
}

static void FreeJMat(void)
{
   int i;
   
   for (i=jmRows-1; i>=0; i--) 
      Dispose(&jMatHeap,jmat[i]);
   Dispose(&jMatHeap,jmat);
}

/* SameLinks: Check to see if a1 and a2 have the same succs or preds */
static Boolean SameLinks(int a1, int a2)
     /* note: succs or preds checked depending on contents of jmat */
{
   Boolean same = TRUE;
   int j;
   unsigned char *p, *q;
   
   p=jmat[a1]; q=jmat[a2];
   for (j=0; same && j<jmCols; j++)
      if (*p++ != *q++) same = FALSE;
   return same;
}

static Boolean IsJoined(int a, int b)
{
   return (jmat[a][b/8] & (1 <<(b&7))) != 0;
}

static int NumJSuccs(int a)
{
   unsigned char x, *p;
   int j, count =0;

   p = jmat[a];
   for (j=0; j<jmCols; j++)
      for (x=*p++; x!=0; x>>=1)
         if (x&1) ++count;
   return count;
}

static int NumJPreds(int a)
{
   unsigned char x, *p;
   int j, count=0;

   p = jmat[a];
   for (j=0; j<jmCols; j++)
      for (x=*p++; x!=0; x>>=1)
         if (x&1) ++count;
   return count;
}

/* FillSuccJM: find joins with succs as rows of jmat */
static void FillSuccJM(int numElements, SplitName *trilist)
{
   SplitName *tli,*tlj;
   int i,j;
   
   for (i=0;i<numElements-2;i++){ 
      tli = trilist+i;
      for (j=0;j<numElements-2;j++){
         tlj = trilist+j;
         if (DoesMatch(tlj->m,tli->r) && DoesMatch(tli->m,tlj->l))
            jmat[i][j/8] |= 1 <<(j&7);
      }
   }
   /* do the succs that point from TLOOP_BEGIN */
   i = numElements-2;  
   for (j=0,tlj=trilist;j<numElements-2;j++,tlj++)
      if (DoesMatch(tlj->m,(trilist+i)->r))
         jmat[i][j/8] |= 1 << (j&7);
   /* do the succs that point to TLOOP_END */
   j = numElements-1;  
   for (i=0,tli=trilist;i<numElements-2;i++,tli++)
      if (DoesMatch(tli->m,(trilist+j)->l))
         jmat[i][j/8] |= 1 << (j&7);
}

/* FillPredJM: find joins with preds as rows of jmat */
static void FillPredJM(int numElements, SplitName *trilist)
{
   SplitName *tli,*tlj;
   int i,j;

   for (i=0;i<numElements-2;i++){   
      tli = trilist+i;
      for (j=0;j<numElements-2;j++){
         tlj = trilist+j;
         if (DoesMatch(tli->m,tlj->r) && DoesMatch(tlj->m,tli->l))
            jmat[i][j/8] |= 1 <<(j&7);
      }
   }
   /* do the preds that point from TLOOP_END */
   i = numElements-1;  
   for (j=0,tlj=trilist;j<numElements-2;j++,tlj++)
      if (DoesMatch(tlj->m,(trilist+i)->l))
         jmat[i][j/8] |= 1 << (j&7);
   /* do the preds that point to TLOOP_BEGIN */
   j = numElements-2;  
   for (i=0,tli=trilist;i<numElements-2;i++,tli++)
      if (DoesMatch(tli->m,(trilist+j)->r))
         jmat[i][j/8] |= 1 << (j&7);
} 
 
/* MakeTriSubNets: Make up sub net for each variable defn in triloop */
/*                 Make the node user field point to  network        */
static void MakeTriSubNets(LinkSet *asucc, int numElements, 
                           SplitName *trilist)
{
   HPNetwork *proto, *thisNet;
   int i;
   Link thisL,p;
   int numSubNets = 0;

   for (i=0; i<numElements; i++)   
      if ((HPNetwork *) (trilist[i].m)->aux != NULL)
         numSubNets++;
   CreateHeap(&subNetStoreHeap,"HParse SubNetStore Heap",MHEAP,sizeof(HPNetwork),0.0,
              numSubNets,numSubNets);
   if (numSubNets > 0)
      for (i=0; i<numElements; i++) {   
         thisL = asucc->links[i+1];
         proto = (HPNetwork *) (trilist[i].m)->aux;
         if (proto!=NULL) {        /* clone the def */
            thisNet = (HPNetwork *) New(&subNetStoreHeap,sizeof(HPNetwork));
            *thisNet = CloneNetwork(*proto);
            thisL->user = (void*) thisNet;
            p = thisNet->chain;
            while(p->chain!=NULL)p=p->chain;
            p->chain=curChain; curChain = thisNet->chain;
            thisL->modelName = NULL; /* turn into glue */
            /* thisL->extName = NULL; turn into glue */
         }
         else
            thisL->user = NULL;
      }
}

static void MakeSuccLinks(int numElements, LinkSet *asucc)
{
   int i,j,k,n;
   Link thisL, p;
   LinkSet *ls;

   for (i=0; i<numElements; i++) {    
      if (i == numElements-1) {
         asucc->links[i+1]->succ->numLinks = 0; /* clear succs for TLOOP_END */
         continue;                              /* & don't make any new ones */
      }
      p = NULL;
      thisL = asucc->links[i+1];
      for (j=0; j<i; j++)            /* look to see if same set of */
         if (SameLinks(i,j)) {       /* succs already created */
            p = asucc->links[j+1];
            break;
         }
      if (p!=NULL) {                 /* use previous link set */
         ls = (p->user != NULL) ? ((HPNetwork *) p->user)->exitNode->succ 
            : p->succ ;
         FreeLinkSet(thisL->succ); thisL->succ = NULL;
         if (thisL->user != NULL) { /* node has sub-net attached */
            FreeLinkSet(((HPNetwork *)thisL->user)->exitNode->succ); 
            ((HPNetwork *)thisL->user)->exitNode->succ = ls;
         }
         else 
            thisL->succ = ls;
         ++(ls->nUse);
      } else {                      
         FreeLinkSet(thisL->succ);  /* free the old one */
         thisL->succ = NULL;
         n = NumJSuccs(i);         /* and create a new one */
         ls = CreateLinkSet(n);
         for (j=0,k=0; j<jmRows; j++)                
            if (IsJoined(i,j)) {
               if (asucc->links[j+1]->user != NULL)
                  ls->links[++k] = 
                     ((HPNetwork *)asucc->links[j+1]->user)->entryNode;
               else
                  ls->links[++k] = asucc->links[j+1];
            }
         ls->numLinks = k;
         if (thisL->user != NULL) { /* node has sub-net attached */
            FreeLinkSet(((HPNetwork *)thisL->user)->exitNode->succ); 
            ((HPNetwork *)thisL->user)->exitNode->succ = ls;
         }
         else
            thisL->succ = ls; 
      }
   }
}

static void MakePredLinks(int numElements, LinkSet *asucc)
{
   int i,j,k,n;
   Link thisL, p;
   LinkSet *ls;

   for (i=0; i<numElements; i++) {    
      if (i == numElements-2) {
         asucc->links[i+1]->pred->numLinks = 0; /* clear preds for TLOOP_BEGIN */
         continue;                              /* & don't make new preds      */
      }
      p = NULL;
      thisL = asucc->links[i+1];
      for (j=0; j<i; j++)            /* look to see if same set of */
         if (SameLinks(i,j)) {       /* preds already created */
            p = asucc->links[j+1];
            break;
         }
      if (p!=NULL) {                 /* use previous link set */
         ls = (p->user != NULL) ? ((HPNetwork *)p->user)->entryNode->pred 
            : p->pred ;
         FreeLinkSet(thisL->pred); thisL->pred = NULL;
         if (thisL->user != NULL) {    /* node has sub-net attached */
            FreeLinkSet(((HPNetwork *)thisL->user)->entryNode->pred); 
            ((HPNetwork *)thisL->user)->entryNode->pred = ls;
         }
         else 
            thisL->pred = ls;
         ++(ls->nUse);
      } else {                      
         FreeLinkSet(thisL->pred);   /* free old one */
         thisL->pred = NULL;
         n = NumJPreds(i);          /* and create new one */
         ls = CreateLinkSet(n);
         for (j=0,k=0 ; j<jmRows; j++) 
            if (IsJoined(i,j)) {
               if (asucc->links[j+1]->user != NULL)
                  ls->links[++k] = 
                     ((HPNetwork *)asucc->links[j+1]->user)->exitNode;
               else
                  ls->links[++k] = asucc->links[j+1];
            }
         ls->numLinks = k;
         if (thisL->user != NULL) {  /* node has sub-net attached */
            FreeLinkSet(((HPNetwork *)thisL->user)->entryNode->pred);
            ((HPNetwork *)thisL->user)->entryNode->pred = ls;
         }
         else
            thisL->pred = ls;
      }
   }
}
/* FixTLoopEnds: connect TLOOP_BEGIN and TLOOP_END as loop ends */
/*               and clean up initial loop ends                 */
static void FixTLoopEnds(int numElements, Link *hd, Link *tl, Link a, Link b)                 
{
   *hd = a->succ->links[numElements-1];  /* connect the ends */
   *tl = a->succ->links[numElements];
   (*hd)->modelName = NULL;            /* make TLOOP_BEGIN & TLOOP_END */
   (*tl)->modelName = NULL;            /* into glue                    */
   FreeLinkSet(a->succ); a->succ = NULL;
   FreeLinkSet(a->pred); a->pred = NULL;
   FreeLinkSet(b->succ); b->succ = NULL;
   FreeLinkSet(b->pred); b->pred = NULL;
}

/* MakeTriLoop:  builds a context dependent triphone loop around
      given expression which must be a simple list of alternatives.
      Each triphone in list must have a name of the form L-X+R 
      where L and R are either simple names or the names of
      subnetworks which again must be simple lists.  Each triphone 
      L1-X1+R1 is looped back to all phones L2-X2+R2 for which X1 
      is in L2 and X2 is in R1.  Either the left or right context
      may be missing in which case simple right or left context
      dependence is implemented. The special symbols TLOOP_BEGIN
      and TLOOP_END control entry and exit to/from the loop
*/
static void MakeTriLoop(Link *hd, Link *tl)
{
   int numElements;
   SplitName *trilist;
   Link a, b;

   a = FindLoopBegin(hd);   /* skip (and free) nodes at either end */
   b = FindLoopEnd(tl);
   if (a->succ->numLinks != b->pred->numLinks)
      HError(3131,"MakeTriLoop: Incorrectly formed tri-loop detected");
   numElements = a->succ->numLinks;              /* num elements in the tri loop */
   trilist = MakeTriList(numElements,a->succ);   /* split all the triphone names */
   numElements = AddTLoopBeginEnd(numElements,trilist,a,b);
   MakeTriSubNets(a->succ,numElements,trilist);  
   jmRows = numElements; jmCols = (jmRows+7)/8;
   CreateJMat();                               /* create the join matrix */
   ClearJMat();
   FillSuccJM(numElements, trilist);   /* load jmat with succ first info */
   MakeSuccLinks(numElements,a->succ);                   
   ClearJMat();
   FillPredJM(numElements, trilist);   /* load jmat with pred first info */
   MakePredLinks(numElements,a->succ);
   FixTLoopEnds(numElements,hd,tl,a,b);
   FreeJMat();
   DeleteHeap(&splitNameHeap);
   DeleteHeap(&subNetStoreHeap);
}

/*  ------------ Expand Sub Net Defs ------------------   */

void PrintChain(Link chain)
{
   Link p = chain;
   
   printf("\n");
   while (p!=NULL) {
      PrintNode(p);
      p=p->chain;
   }
}

static void SubstituteSubNet(HPNetwork *subNet, Link p)
{
   Link predNode,succNode;
   int i,j;

   /* first do case of  self-loop on p */
   for (i=1; i <= p->pred->numLinks; i++) 
      if (p->pred->links[i] == p)
         p->pred->links[i] = subNet->exitNode;
   for (i=1; i <= p->succ->numLinks; i++) 
      if (p->succ->links[i] == p)
         p->succ->links[i] = subNet->entryNode;

   /* now go through all the pred nodes of p */
   for (i=1; i <= p->pred->numLinks; i++) {
      predNode = p->pred->links[i];
      if (predNode->succ->nUse > 0) {
         predNode->succ->nUse = -predNode->succ->nUse; /*mark as seen*/
         for (j=1; j <= predNode->succ->numLinks; j++)
            if (predNode->succ->links[j] == p) 
               predNode->succ->links[j] = subNet->entryNode;
      }
   }
   for (i=1; i <= p->pred->numLinks; i++) {  /*restore nUse counts*/ 
      predNode = p->pred->links[i];
      if (predNode->succ->nUse < 0) 
         predNode->succ->nUse = -predNode->succ->nUse; 
   }

   /* and all the succ nodes of p */
   for (i=1; i<=p->succ->numLinks; i++) {
      succNode = p->succ->links[i];
      if (succNode->pred->nUse > 0) {
         succNode->pred->nUse = -succNode->pred->nUse; /*mark as seen*/
         for (j=1; j<= succNode->pred->numLinks; j++)
            if (succNode->pred->links[j] == p) 
               succNode->pred->links[j] = subNet->exitNode;
      }
   }
   for (i=1; i <= p->succ->numLinks; i++) {  /*restore nUse counts*/ 
      succNode = p->succ->links[i];