julius/factoring_sub.c

Go to the documentation of this file.

/*
 * Copyright (c) 1991-2006 Kawahara Lab., Kyoto University
 * Copyright (c) 2000-2005 Shikano Lab., Nara Institute of Science and Technology
 * Copyright (c) 2005-2006 Julius project team, Nagoya Institute of Technology
 * All rights reserved
 */

#include <julius.h>

#ifndef CATEGORY_TREE
   
/*----------------------------------------------------------------------*/

static void
add_successor(WCHMM_INFO *wchmm, int node, WORD_ID w)
{
  S_CELL *sctmp, *sc;

  /* malloc a new successor list element */
  sctmp=(S_CELL *) mymalloc(sizeof(S_CELL));
  if (sctmp == NULL) {
    j_error("malloc fault at add_succesor(%d,%d)\n",node,w);
  }
  /* assign word ID to the new element */
  sctmp->word = w;
  /* add the new element to existing list (keeping order) */
  if (wchmm->state[node].scid == 0) {
    j_error("InternalError: sclist id not assigned to branch node?\n");
  }
  sc = wchmm->sclist[wchmm->state[node].scid];
  if (sc == NULL || sctmp->word < sc->word) {
    sctmp->next = sc;
    wchmm->sclist[wchmm->state[node].scid] = sctmp;
  } else {
    for(;sc;sc=sc->next) {
      if (sc->next == NULL || sctmp->word < (sc->next)->word) {
        if (sctmp->word == sc->word) break; /* avoid duplication */
        sctmp->next = sc->next;
        sc->next = sctmp;
        break;
      }
    }
  }
}

static boolean
match_successor(WCHMM_INFO *wchmm, int node1, int node2)
{
  S_CELL *sc1,*sc2;

  /* assume successor is sorted by ID */
  if (wchmm->state[node1].scid == 0 || wchmm->state[node2].scid == 0) {
    j_error("InternalError: sclist id not assigned to branch node?\n");
  }
  sc1 = wchmm->sclist[wchmm->state[node1].scid];
  sc2 = wchmm->sclist[wchmm->state[node2].scid];
  for (;;) {
    if (sc1 == NULL || sc2 == NULL) {
      if (sc1 == NULL && sc2 == NULL) {
        return TRUE;
      } else {
        return FALSE;
      }
    } else if (sc1->word != sc2->word) {
      return FALSE;
    }
    sc1 = sc1->next;
    sc2 = sc2->next;
  }
}

static void
free_successor(WCHMM_INFO *wchmm, int scid)
{
  S_CELL *sc;
  S_CELL *sctmp;

  /* free sclist */
  sc = wchmm->sclist[scid];
  while (sc != NULL) {
    sctmp = sc;
    sc = sc->next;
    free(sctmp);
  }
}

static void
compaction_successor(WCHMM_INFO *wchmm)
{
  int src, dst;

  dst = 1;
  for(src=1;src<wchmm->scnum;src++) {
    if (wchmm->state[wchmm->sclist2node[src]].scid <= 0) {
      /* already freed, skip */
      continue;
    }
    if (dst != src) {
      wchmm->sclist[dst] = wchmm->sclist[src];
      wchmm->sclist2node[dst] = wchmm->sclist2node[src];
      wchmm->state[wchmm->sclist2node[dst]].scid = dst;
    }
    dst++;
  }
  if (debug2_flag) j_printerr("  successor list shrinked from %d to %d...\n", wchmm->scnum, dst);
  wchmm->scnum = dst;
}

static void
shrink_successor(WCHMM_INFO *wchmm)
{
  wchmm->sclist = (S_CELL **)myrealloc(wchmm->sclist, sizeof(S_CELL *) * wchmm->scnum);
  wchmm->sclist2node = (int *)myrealloc(wchmm->sclist2node, sizeof(int) * wchmm->scnum);
}

void
make_successor_list(WCHMM_INFO *wchmm)
{
  int node;
  WORD_ID w;
  int i;
  boolean *freemark;
  int s;

  VERMES("  make successor lists for factoring...\n");

  /* 1. initialize */
  /* initialize node->sclist index */
  for (node=0;node<wchmm->n;node++) wchmm->state[node].scid = 0;
  /* parse tree to get the possible maximum number of successor list */
  s = 1;
  for (w=0;w<wchmm->winfo->num;w++) {
    for (i=0;i<wchmm->winfo->wlen[w];i++) {
      if (wchmm->state[wchmm->offset[w][i]].scid == 0) {
        wchmm->state[wchmm->offset[w][i]].scid = s;
        s++;
      }
    }
    if (wchmm->state[wchmm->wordend[w]].scid == 0) {
      wchmm->state[wchmm->wordend[w]].scid = s;
      s++;
    }
  }
  wchmm->scnum = s;
  if (debug2_flag) j_printerr("  initial successor list size = %d...\n", wchmm->scnum);
  /* allocate successor list */
  wchmm->sclist = (S_CELL **)mymalloc(sizeof(S_CELL *) * wchmm->scnum);
  for (i=1;i<wchmm->scnum;i++) wchmm->sclist[i] = NULL;
  wchmm->sclist2node = (int *)mymalloc(sizeof(int) * wchmm->scnum);
  /* allocate misc. work area */
  freemark = (boolean *)mymalloc(sizeof(boolean) * wchmm->scnum);
  for (i=1;i<wchmm->scnum;i++) freemark[i] = FALSE;

  /* 2. make initial successor list: assign at all possible nodes */
  for (w=0;w<wchmm->winfo->num;w++) {
    /* at each start node of phonemes */
    for (i=0;i<wchmm->winfo->wlen[w];i++) {
      wchmm->sclist2node[wchmm->state[wchmm->offset[w][i]].scid] = wchmm->offset[w][i];
      add_successor(wchmm, wchmm->offset[w][i], w);
    }
    /* at word end */
    wchmm->sclist2node[wchmm->state[wchmm->wordend[w]].scid] = wchmm->wordend[w];
    add_successor(wchmm, wchmm->wordend[w], w);
  }
  
  /* 3. erase unnecessary successor list */
  /* sucessor list same as the previous node is not needed, so */
  /* parse lexicon tree from every leaf to find the same succesor list */
  for (w=0;w<wchmm->winfo->num;w++) {
    node = wchmm->wordend[w];   /* begin from the word end node */
    i = wchmm->winfo->wlen[w]-1;
    while (i >= 0) {            /* for each phoneme start node */
      if (node == wchmm->offset[w][i]) {
        /*      printf("same:w=%d,phoneloc=%d,node=%d,%d\n", w, i, wchmm->offset[w][i], node);
        {
          S_CELL *sc;
          for(sc=wchmm->state[node].sc;sc;sc=sc->next) {
            printf("%d[%s],", sc->word, ngram->wname[sc->word]);
          }
          printf("\n");
          }*/
        /* word with only 1 state: skip */
        i--;
        continue;
      }
      if (match_successor(wchmm, node, wchmm->offset[w][i])) {
        freemark[wchmm->state[node].scid] = TRUE;       /* mark the node */
      }
/* 
 *       if (freemark[wchmm->offset[w][i]] != FALSE) {
 *         break;
 *       }
 */
      node = wchmm->offset[w][i];
      i--;
    }
  }
  /* really free */
  for (i=1;i<wchmm->scnum;i++) {
    if (freemark[i] == TRUE) {
      free_successor(wchmm, i);
      /* reset node -> sclist link */
      wchmm->state[wchmm->sclist2node[i]].scid = 0;
    }
  }
  /* garbage collection of deleted sclist */
  compaction_successor(wchmm);

  free(freemark);

  VERMES("done\n");
}

#ifndef CATEGORY_TREE
# ifdef MULTIPATH_VERSION

void
adjust_sc_index(WCHMM_INFO *wchmm)
{
  WORD_ID w;
  int i,j,k;
  HMM_Logical *ltmp;
  int ltmp_state_num;
  int ato;
  LOGPROB prob;
  int node, scid;
  A_CELL *ac;
  
  /* duplicate scid for HMMs with more than one arc from initial state */
  for(w=0;w<wchmm->winfo->num;w++) {
    for(k=0;k<wchmm->winfo->wlen[w];k++) {
      node = wchmm->offset[w][k];
      scid = wchmm->state[node].scid;
      if (scid == 0) continue;
      ltmp = wchmm->winfo->wseq[w][k];
      ltmp_state_num = hmm_logical_state_num(ltmp);
      if ((hmm_logical_trans(ltmp))->a[0][ltmp_state_num-1] != LOG_ZERO) {
        j = k + 1;
        if (j == wchmm->winfo->wlen[w]) {
          if (wchmm->state[wchmm->wordend[w]].scid == 0) {
            printf("word %d: factoring node copied for skip phone\n", w);
            wchmm->state[wchmm->wordend[w]].scid = scid;
          }
        } else {
          if (wchmm->state[wchmm->offset[w][j]].scid == 0) {
            printf("word %d: factoring node copied for skip phone\n", w);
            wchmm->state[wchmm->offset[w][j]].scid = scid;
          }
        }
      }
      for(ato=1;ato<ltmp_state_num;ato++) {
        prob = (hmm_logical_trans(ltmp))->a[0][ato];
        if (prob != LOG_ZERO) {
          wchmm->state[node+ato-1].scid = scid;
        }
      }
    }
  }

  /* move scid and fscore on the head state to the head grammar state */
  for(i=0;i<wchmm->startnum;i++) {
    node = wchmm->startnode[i];
    if (wchmm->state[node].out.state != NULL) {
      j_error("Error: outprob exist in word-head node??\n");
    }
    for(ac=wchmm->state[node].ac;ac;ac=ac->next) {
      if (wchmm->state[ac->arc].scid != 0) {
        if (wchmm->state[node].scid != 0 && wchmm->state[node].scid != wchmm->state[ac->arc].scid) {
          j_error("Error: different successor list within word-head phone?\n");
        }
        wchmm->state[node].scid = wchmm->state[ac->arc].scid;
        wchmm->state[ac->arc].scid = 0;
      }
    }
  }
}

# endif /* MULTIPATH_VERSION */
#endif /* ~CATEGORY_TREE */


/* -------------------------------------------------------------------- */
/* factoring computation */

#ifdef USE_NGRAM

/* cache should be conditioned by N-gram entry ID */

/* word-internal factoring value cache:
   a branch node (that has successor list) will keep the factoring value
   on search, and re-use it if incoming token in the next frame has the
   same word context.
 */
static LOGPROB *probcache;      
static WORD_ID *lastwcache;     
/* cross-word factoring value cache:
   when computing cross-word transition, (1)factoring values on all word
   start nodes should be computed for each word end, and thus (2)each start
   node has more than one transition within a frame.  So factoring value
   is better cached by the word end (last word) than by nodes.
 */
static LOGPROB **iw_sc_cache;
static int iw_cache_num;
#ifdef HASH_CACHE_IW
static WORD_ID *iw_lw_cache; 
#endif
/* once initialized on startup, the factoring value caches will not be
   cleared */

void
max_successor_cache_init(WCHMM_INFO *wchmm)
{
  int i;

  /* finally shrink the memory area of successor list here */
  shrink_successor(wchmm);

  /* for word-internal */
  probcache = (LOGPROB *) mymalloc(sizeof(LOGPROB) * wchmm->scnum);
  lastwcache = (WORD_ID *) mymalloc(sizeof(WORD_ID) * wchmm->scnum);
  for (i=0;i<wchmm->scnum;i++) {
    lastwcache[i] = WORD_INVALID;
  }
  /* for cross-word */
#ifdef HASH_CACHE_IW
  iw_cache_num = wchmm->ngram->max_word_num * iw_cache_rate / 100;
  if (iw_cache_num < 10) iw_cache_num = 10;
#else
  iw_cache_num = wchmm->ngram->max_word_num;
#endif /* HASH_CACHE_IW */
  iw_sc_cache = (LOGPROB **)mymalloc(sizeof(LOGPROB *) * iw_cache_num);
  for (i=0;i<iw_cache_num;i++) {
    iw_sc_cache[i] = NULL;
  }
#ifdef HASH_CACHE_IW
  iw_lw_cache = (WORD_ID *)mymalloc(sizeof(WORD_ID) * iw_cache_num);
  for (i=0;i<iw_cache_num;i++) {
    iw_lw_cache[i] = WORD_INVALID;
  }
#endif
}

static void
max_successor_prob_iw_free()
{
  int i;
  for (i=0;i<iw_cache_num;i++) {
    if (iw_sc_cache[i] != NULL) free(iw_sc_cache[i]);
    iw_sc_cache[i] = NULL;
  }
}

void
max_successor_cache_free()
{
  free(probcache);
  free(lastwcache);
  max_successor_prob_iw_free();
  free(iw_sc_cache);
#ifdef HASH_CACHE_IW
  free(iw_lw_cache);
#endif
}

#ifdef UNIGRAM_FACTORING

void
make_iwcache_index(WCHMM_INFO *wchmm)
{
  int i, node, num;

  wchmm->start2isolate = (int *)mymalloc(sizeof(int) * wchmm->startnum);
  num = 0;
  for(i=0;i<wchmm->startnum;i++) {
    node = wchmm->startnode[i];
    if (wchmm->state[node].scid >= 0) { /* not a factoring node (isolated node, has no 1-gram factoring value) */
      wchmm->start2isolate[i] = num;
      num++;
    } else {                    /* factoring node (shared) */
      wchmm->start2isolate[i] = -1;
    }
  }
  wchmm->isolatenum = num;
}

void
calc_all_unigram_factoring_values(WCHMM_INFO *wchmm)
{
  S_CELL *sc, *sctmp;
  LOGPROB tmpprob, maxprob;
  int i, n;

  /* count needed number of 1-gram factoring nodes */
  n = 0;
  for (i=1;i<wchmm->scnum;i++) {
    sc = wchmm->sclist[i];
    if (sc == NULL) {
      j_error("InternalError: sclist has no sc?\n");
    }
    if (sc->next != NULL) {
      /* more than two words, so compute maximum 1-gram probability */
      n++;
    }
  }
  wchmm->fsnum = n + 1;
  /* allocate area */
  wchmm->fscore = (LOGPROB *)mymalloc(sizeof(LOGPROB) * wchmm->fsnum);
  /* assign values */
  n = 1;
  for (i=1;i<wchmm->scnum;i++) {
    sc = wchmm->sclist[i];
    if (sc->next != NULL) {
      maxprob = LOG_ZERO;
      for (sctmp = sc; sctmp; sctmp = sctmp->next) {
        tmpprob = uni_prob(wchmm->ngram, wchmm->winfo->wton[sctmp->word])
#ifdef CLASS_NGRAM
          + wchmm->winfo->cprob[sctmp->word] 
#endif
          ;
        if (maxprob < tmpprob) maxprob = tmpprob;
      }
      wchmm->fscore[n] = maxprob;
      free_successor(wchmm, i);
      wchmm->state[wchmm->sclist2node[i]].scid = - n;
      n++;
    }
  }
  /* garbage collection of factored sclist */
  compaction_successor(wchmm);
}

#else  /* ~UNIGRAM_FACTORING */

static LOGPROB
calc_successor_prob(WCHMM_INFO *wchmm, WORD_ID last_nword, int node)
{
  S_CELL *sc;
  LOGPROB tmpprob, maxprob;

  maxprob = LOG_ZERO;
  for (sc = wchmm->sclist[wchmm->state[node].scid]; sc; sc = sc->next) {
    tmpprob = bi_prob_lr(wchmm->ngram, last_nword, wchmm->winfo->wton[sc->word])
#ifdef CLASS_NGRAM
      + wchmm->winfo->cprob[sc->word]
#endif
      ;
    if (maxprob < tmpprob) maxprob = tmpprob;
  }
  return(maxprob);
}

#endif  /* ~UNIGRAM_FACTORING */

LOGPROB
max_successor_prob(WCHMM_INFO *wchmm, WORD_ID lastword, int node)
{
  LOGPROB maxprob;
  WORD_ID last_nword, w;
  int scid;

  if (lastword != WORD_INVALID) { /* return nothing if no previous word */
    last_nword = wchmm->winfo->wton[lastword];
    scid = wchmm->state[node].scid;
#ifdef UNIGRAM_FACTORING
    if (scid < 0) {
      /* return 1-gram factoring value already calced */
      return(wchmm->fscore[(- scid)]);
    } else {
      /* this node has only one successor */
      /* return precise 2-gram score */
      if (last_nword != lastwcache[scid]) {
        /* calc and cache */
        w = (wchmm->sclist[scid])->word;
        maxprob = bi_prob_lr(wchmm->ngram, last_nword, wchmm->winfo->wton[w])
#ifdef CLASS_NGRAM
          + wchmm->winfo->cprob[w]
#endif
          ;
        lastwcache[scid] = last_nword;
        probcache[scid] = maxprob;
        return(maxprob);
      } else {
        /* return cached */
        return (probcache[scid]);
      }
    }
#else  /* UNIGRAM_FACTORING */
    /* 2-gram */
    if (last_nword != lastwcache[scid]) {
      maxprob = calc_successor_prob(wchmm, last_nword, node);
      /* store to cache */
      lastwcache[scid] = last_nword;
      probcache[scid] = maxprob;
      return(maxprob);
    } else {
      return (probcache[scid]);
    }
#endif /* UNIGRAM_FACTORING */
  } else {
    return(0.0);
#if 0
    maxprob = LOG_ZERO;
    for (sc=wchmm->state[node].sc;sc;sc=sc->next) {
      tmpprob = uni_prob(wchmm->ngram, sc->word);
      if (maxprob < tmpprob) maxprob = tmpprob;
    }
    return(maxprob);
#endif
  }

}

#ifdef HASH_CACHE_IW
#define hashid(A) A % iw_cache_limit 
#endif

LOGPROB *
max_successor_prob_iw(WCHMM_INFO *wchmm, WORD_ID lastword)
{
  int i, j, x, node;
  int last_nword;
  WORD_ID w;

  last_nword = wchmm->winfo->wton[lastword];
#ifdef HASH_CACHE_IW
  x = hashid(last_nword);
  if (iw_lw_cache[x] == last_nword) { /* cache hit */
    return(iw_sc_cache[x]);
  }
#else  /* full cache */
  if (iw_sc_cache[last_nword] != NULL) { /* cache hit */
    return(iw_sc_cache[last_nword]);
  }
  x = last_nword;
  /* cache mis-hit, calc probs and cache them as new */
#endif
  /* allocate cache memory */
  if (iw_sc_cache[x] == NULL) {
#ifdef UNIGRAM_FACTORING
    iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->isolatenum);
#else
    iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->startnum);
#endif
    if (iw_sc_cache[x] == NULL) { /* malloc failed */
      /* clear existing cache, and retry */
      max_successor_prob_iw_free();
      j_printf("inter-word LM cache (%dMB) rehashed\n",
               (iw_cache_num * 
#ifdef UNIGRAM_FACTORING
                wchmm->isolatenum
#else
                wchmm->startnum
#endif
                ) / 1000 * sizeof(LOGPROB) / 1000);
#ifdef UNIGRAM_FACTORING
      iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->isolatenum);
#else
      iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->startnum);
#endif
      if (iw_sc_cache[x] == NULL) { /* malloc failed again? */
        j_error("max_successor_prob_iw: cannot malloc\n");
      }
    }
  }

  /* calc prob for all startid */
#ifdef UNIGRAM_FACTORING
  for (j=0;j<wchmm->startnum;j++) {
    i = wchmm->start2isolate[j];
    if (i == -1) continue;
    node = wchmm->startnode[j];
    if (wchmm->state[node].scid <= 0) {
      /* should not happen!!! below is just for debugging */
      j_error("No!!\n");
    } else {
      w = (wchmm->sclist[wchmm->state[node].scid])->word;
      iw_sc_cache[x][i] = bi_prob_lr(ngram, last_nword, wchmm->winfo->wton[w])
#ifdef CLASS_NGRAM
        + wchmm->winfo->cprob[w]
#endif
        ;
    }
  }
#else  /* ~UNIGRAM_FACTORING */
  for (i=0;i<wchmm->startnum;i++) {
    node = wchmm->startnode[i];
    iw_sc_cache[x][i] = calc_successor_prob(wchmm, last_nword, node);
  }
#endif
#ifdef HASH_CACHE_IW
  iw_lw_cache[x] = last_nword;
#endif

  return(iw_sc_cache[x]);
}


#else /* USE_DFA --- ¥«¥Æ¥´¥êÌڤʤéÉÔɬÍ× */

boolean
can_succeed(WCHMM_INFO *wchmm, WORD_ID lastword, int node)
{
  int lc;
  S_CELL *sc;

  /* return TRUE if at least one subtree word can connect */

  if (lastword == WORD_INVALID) { /* case at beginning-of-word */
    for (sc=wchmm->sclist[wchmm->state[node].scid];sc;sc=sc->next) {
      if (dfa_cp_begin(wchmm->dfa, sc->word) == TRUE) return(TRUE);
    }
    return(FALSE);
  } else {
    lc = winfo->wton[lastword];
    for (sc=wchmm->sclist[wchmm->state[node].scid];sc;sc=sc->next) {
      if (dfa_cp(wchmm->dfa, lc, sc->word) == TRUE) return(TRUE);
    }
    return(FALSE);
  }
}

#endif /* USE_DFA */


#endif /* CATEGORY_TREE */

---