libjulius/src/factoring_sub.c

Go to the documentation of this file.

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

#include <julius/julius.h>

/*----------------------------------------------------------------------*/

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));
  /* 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_internal_error("add_successor: 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_internal_error("match_successor: 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) {
    jlog("DEBUG: 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;

  jlog("STAT: 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) {
    jlog("DEBUG: 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]) {
        /* 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);

  jlog("STAT: done\n");
}

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_CELL2 *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) {
            jlog("STAT: 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) {
            jlog("STAT: 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_internal_error("adjust_sc_index: outprob exist in word-head node??\n");
    }
    if (wchmm->next_a[node] != LOG_ZERO) {
      if (wchmm->state[node+1].scid != 0) {
        if (wchmm->state[node].scid != 0 && wchmm->state[node].scid != wchmm->state[node+1].scid) {
          j_internal_error("adjust_sc_index: different successor list within word-head phone?\n");
        }
        wchmm->state[node].scid = wchmm->state[node+1].scid;
        wchmm->state[node+1].scid = 0;
      }
    }
    for(ac=wchmm->ac[node];ac;ac=ac->next) {
      for(k=0;k<ac->n;k++) {
        if (wchmm->state[ac->arc[k]].scid != 0) {
          if (wchmm->state[node].scid != 0 && wchmm->state[node].scid != wchmm->state[ac->arc[k]].scid) {
            j_internal_error("adjust_sc_index: different successor list within word-head phone?\n");
          }
          wchmm->state[node].scid = wchmm->state[ac->arc[k]].scid;
          wchmm->state[ac->arc[k]].scid = 0;
        }
      }
    }
  }
}

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

void
max_successor_cache_init(WCHMM_INFO *wchmm)
{
  int i;
  LM_PROB_CACHE *l;
  WORD_ID wnum;

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

  /* for word-internal */
  l = &(wchmm->lmcache);

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

static void
max_successor_prob_iw_free(WCHMM_INFO *wchmm)
{
  int i;
  LM_PROB_CACHE *l;
  l = &(wchmm->lmcache);
  for (i=0;i<l->iw_cache_num;i++) {
    if (l->iw_sc_cache[i] != NULL) free(l->iw_sc_cache[i]);
    l->iw_sc_cache[i] = NULL;
  }
}

void
max_successor_cache_free(WCHMM_INFO *wchmm)
{
  free(wchmm->lmcache.probcache);
  free(wchmm->lmcache.lastwcache);
  max_successor_prob_iw_free(wchmm);
  free(wchmm->lmcache.iw_sc_cache);
#ifdef HASH_CACHE_IW
  free(wchmm->lmcache.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_internal_error("call_all_unigram_factoring_values: 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) {
        if (wchmm->ngram) {
          tmpprob = uni_prob(wchmm->ngram, wchmm->winfo->wton[sctmp->word])
#ifdef CLASS_NGRAM
            + wchmm->winfo->cprob[sctmp->word] 
#endif
            ;
        } else {
          tmpprob = LOG_ZERO;
        }
        if (wchmm->lmvar == LM_NGRAM_USER) {
          tmpprob = (*(wchmm->uni_prob_user))(wchmm->winfo, sctmp->word, tmpprob);
        }
        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 lastword, int node)
{
  S_CELL *sc;
  LOGPROB tmpprob, maxprob;
  WORD_ID lw;

  maxprob = LOG_ZERO;
  if (wchmm->ngram) {
    lw = wchmm->winfo->wton[lastword];
  }

  for (sc = wchmm->sclist[wchmm->state[node].scid]; sc; sc = sc->next) {
    if (wchmm->ngram) {
      tmpprob = (*(wchmm->ngram->bigram_prob))(wchmm->ngram, lw , wchmm->winfo->wton[sc->word])
#ifdef CLASS_NGRAM
        + wchmm->winfo->cprob[sc->word]
#endif
        ;
    } else {
      tmpprob = LOG_ZERO;
    }
    if (wchmm->lmvar == LM_NGRAM_USER) {
      tmpprob = (*(wchmm->bi_prob_user))(wchmm->winfo, lastword, sc->word, tmpprob);
    }
    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;
  LM_PROB_CACHE *l;

  l = &(wchmm->lmcache);

  if (lastword != WORD_INVALID) { /* return nothing if no previous word */
    if (wchmm->ngram) {
      last_nword = wchmm->winfo->wton[lastword];
    } else {
      last_nword = 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 != l->lastwcache[scid]) {
        /* calc and cache */
        w = (wchmm->sclist[scid])->word;
        if (wchmm->ngram) {
          maxprob = (*(wchmm->ngram->bigram_prob))(wchmm->ngram, last_nword, wchmm->winfo->wton[w])
#ifdef CLASS_NGRAM
            + wchmm->winfo->cprob[w]
#endif
            ;
        } else {
          maxprob = LOG_ZERO;
        }
        if (wchmm->lmvar == LM_NGRAM_USER) {
          maxprob = (*(wchmm->bi_prob_user))(wchmm->winfo, lastword, w, maxprob);
        }
        l->lastwcache[scid] = last_nword;
        l->probcache[scid] = maxprob;
        return(maxprob);
      } else {
        /* return cached */
        return (l->probcache[scid]);
      }
    }
#else  /* UNIGRAM_FACTORING */
    /* 2-gram */
    if (last_nword != l->lastwcache[scid]) {
      maxprob = calc_successor_prob(wchmm, lastword, node);
      /* store to cache */
      l->lastwcache[scid] = last_nword;
      l->probcache[scid] = maxprob;
      return(maxprob);
    } else {
      return (l->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
  }

}

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

  l = &(wchmm->lmcache);

  if (wchmm->ngram) {
    last_nword = wchmm->winfo->wton[lastword];
  } else {
    last_nword = lastword;
  }

#ifdef HASH_CACHE_IW
  x = last_nword % l->iw_cache_num;
  if (l->iw_lw_cache[x] == last_nword) { /* cache hit */
    return(l->iw_sc_cache[x]);
  }
#else  /* full cache */
  if (l->iw_sc_cache[last_nword] != NULL) { /* cache hit */
    return(l->iw_sc_cache[last_nword]);
  }
  x = last_nword;
  /* cache mis-hit, calc probs and cache them as new */
#endif
  /* allocate cache memory */
  if (l->iw_sc_cache[x] == NULL) {
#ifdef UNIGRAM_FACTORING
    l->iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->isolatenum);
#else
    l->iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->startnum);
#endif
    if (l->iw_sc_cache[x] == NULL) { /* malloc failed */
      /* clear existing cache, and retry */
      max_successor_prob_iw_free(wchmm);
      jlog("STAT: inter-word LM cache (%dMB) rehashed\n",
               (l->iw_cache_num * 
#ifdef UNIGRAM_FACTORING
                wchmm->isolatenum
#else
                wchmm->startnum
#endif
                ) / 1000 * sizeof(LOGPROB) / 1000);
#ifdef UNIGRAM_FACTORING
      l->iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->isolatenum);
#else
      l->iw_sc_cache[x] = (LOGPROB *)mymalloc(sizeof(LOGPROB)*wchmm->startnum);
#endif
      if (l->iw_sc_cache[x] == NULL) { /* malloc failed again? */
        j_internal_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_internal_error("max_successor_prob_iw: isolated (not shared) tree root node has unigram factoring value??\n");
    } else {
      w = (wchmm->sclist[wchmm->state[node].scid])->word;
      if (wchmm->ngram) {
        p = (*(wchmm->ngram->bigram_prob))(wchmm->ngram, last_nword, wchmm->winfo->wton[w])
#ifdef CLASS_NGRAM
          + wchmm->winfo->cprob[w]
#endif
          ;
      } else {
        p = LOG_ZERO;
      }
      if (wchmm->lmvar == LM_NGRAM_USER) {
        p = (*(wchmm->bi_prob_user))(wchmm->winfo, lastword, w, p);
      }
      l->iw_sc_cache[x][i] = p;
    }
  }
#else  /* ~UNIGRAM_FACTORING */
  for (i=0;i<wchmm->startnum;i++) {
    node = wchmm->startnode[i];
    l->iw_sc_cache[x][i] = calc_successor_prob(wchmm, lastword, node);
  }
#endif
#ifdef HASH_CACHE_IW
  l->iw_lw_cache[x] = last_nword;
#endif

  return(l->iw_sc_cache[x]);
}

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 = wchmm->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);
  }
}

/* end of file */

---