graphout.c

来自「julius version 4.12.about sound recognit」· C语言 代码 · 共 2,136 行 · 第 1/5 页

 * 
 * @param rootp [i/o] 帽胳グラフのル〖トノ〖ドへのポインタ
 * </JA>
 * <EN>
 * Free all the words in a word graph.
 * 
 * @param rootp [i/o] pointer to root node of a word graph
 * </EN>
 *
 * @callgraph
 * @callergraph
 *
 */
void
wordgraph_clean(WordGraph **rootp)
{
  WordGraph *wg, *wtmp;

  wg = *rootp;
  while(wg != NULL) {
    wtmp = wg->next;
    wordgraph_free(wg);
    wg = wtmp;
  }
  *rootp = NULL;

}

/*********************************************************************/
/* Post-processing of generated word arcs after search has been done */

/** 
 * <JA>
 * 帽胳グラフ考さカットのための qsort 脱コ〖ルバック. fscore_head で
 * 惯界にソ〖トする. 
 * 
 * @param x [in] 妥燎１
 * @param y [in] 妥燎２
 * 
 * @return qsort に洁じた手り猛
 * </JA>
 * <EN>
 * Callback function for qsort to do word graph depth cutting. Graph
 * words will be sorted downward based on fscore_head.
 * 
 * @param x [in] element 1
 * @param y [in] element 2
 * 
 * @return values for qsort
 * </EN>
 */
static int
compare_beam(WordGraph **x, WordGraph **y)
{
  if ((*x)->fscore_head < (*y)->fscore_head) return 1;
  else if ((*x)->fscore_head > (*y)->fscore_head) return -1;
  else return 0;
}

/** 
 * <JA>
 * @brief  グラフ稿借妄その１¨介袋帽胳グラフの藐叫. 
 * 
 * 玫瑚面に栏喇された帽胳铬输礁圭から·琐眉から幌まるパス惧に痰いleaf帽胳を
 * 猴近することで介袋帽胳グラフを藐叫する. 
 * 
 * @param rootp [i/o] 帽胳グラフのル〖トノ〖ドへのポインタ
 * @param r [in] 千急借妄インスタンス
 * </JA>
 * <EN>
 * @brief  Post-processing step 1: Extract initial word graph.
 * 
 * Extract initial word graph from generated word arcs while search, by
 * purging leaf nodes and arcs that are not on the path from edge to edge.
 * 
 * @param rootp [i/o] pointer to root node of a word graph
 * @param r [in] recognition process instance
 * </EN>
 *
 * @callgraph
 * @callergraph
 * 
 */
void
wordgraph_purge_leaf_nodes(WordGraph **rootp, RecogProcess *r)
{
  WordGraph *wg;
  int i, dst;
  boolean changed;
  int count, erased, del_left, del_right;

  /* count whole */
  count = 0;
  for(wg=*rootp;wg;wg=wg->next) count++;
  if (verbose_flag) jlog("STAT: graphout: %d initial word arcs generated\n", count);
  if (count == 0) return;
  
  if (verbose_flag) jlog("STAT: graphout: step 1: purge leaf nodes\n");

  /* mark words to be erased */
  del_left = del_right = 0;
  do {
    changed = FALSE;
    for(wg=*rootp;wg;wg=wg->next) {
      if (wg->mark == TRUE) continue;
      /* mark if wg has no left context, or all leftwords are marked */
      if (wg->lefttime != 0) {
	for(i=0;i<wg->leftwordnum;i++) {
	  if (wg->leftword[i]->mark == FALSE) break;
	}
	if (i >= wg->leftwordnum) {
	  wg->mark = TRUE;
	  changed = TRUE;
	  del_left++;
	  continue;
	}
      }
      /* mark if wg has no right context, or all rightwords are marked */
      if (wg->righttime != r->peseqlen - 1) {
	for(i=0;i<wg->rightwordnum;i++) {
	  if (wg->rightword[i]->mark == FALSE) break;
	}
	if (i >= wg->rightwordnum) {
	  wg->mark = TRUE;
	  changed = TRUE;
	  del_right++;
	  continue;
	}
      }
    }
  } while (changed == TRUE);

  if (verbose_flag) jlog("STAT: graphout: %d leaf words found (left_blank=%d, right_blank=%d)\n", del_left + del_right, del_left, del_right);

  /* do compaction of left/rightwords */
    for(wg=*rootp;wg;wg=wg->next) {
      if (wg->mark) continue;
      dst = 0;
      for(i=0;i<wg->leftwordnum;i++) {
	if (wg->leftword[i]->mark == FALSE) {
	  if (dst != i) {
	    wg->leftword[dst] = wg->leftword[i];
	    wg->left_lscore[dst] = wg->left_lscore[i];
	  }
	  dst++;
	}
      }
      wg->leftwordnum = dst;
    }
    for(wg=*rootp;wg;wg=wg->next) {
      if (wg->mark) continue;
      dst = 0;
      for(i=0;i<wg->rightwordnum;i++) {
	if (wg->rightword[i]->mark == FALSE) {
	  if (dst != i) {
	    wg->rightword[dst] = wg->rightword[i];
	    wg->right_lscore[dst] = wg->right_lscore[i];
	  }
	  dst++;
	}
      }
      wg->rightwordnum = dst;
    }

  /* execute erase of marked words */
  erased = wordgraph_exec_erase(rootp);
  if (verbose_flag) jlog("STAT: graphout: %d words purged, %d words left in lattice\n", erased, count - erased);

}

/** 
 * <JA>
 * @brief  グラフ稿借妄その１. ５¨グラフの考さによる帽胳铬输のカット
 * 
 * GRAPHOUT_DEPTHCUT 回年箕·グラフの考さによる帽胳铬输のカットを乖う. 
 * 
 * @param rootp [i/o] 帽胳グラフのル〖トノ〖ドへのポインタ
 * @param r [in] 千急借妄インスタンス
 * </JA>
 * <EN>
 * @brief  Post-processing step 1.5: word graph depth cutting
 * 
 * If GRAPHOUT_DEPTHCUT is defined, perform word graph depth cutting.
 * 
 * @param rootp [i/o] pointer to root node of a word graph
 * @param r [in] recognition process instance
 * </EN>
 *
 * @callgraph
 * @callergraph
 * 
 */
void
wordgraph_depth_cut(WordGraph **rootp, RecogProcess *r)
{
#ifdef GRAPHOUT_DEPTHCUT

  WordGraph *wg;
  int i, dst;
  boolean changed;
  int count, erased, del_left, del_right;
  WordGraph **wlist;
  boolean f;
  int *wc;
  int t;
  int pruned;


  if (r->config->graph.graphout_cut_depth < 0) return;

  if (verbose_flag) jlog("STAT: graphout: step 1.5: cut less likely hypothesis by depth of %d\n", r->config->graph.graphout_cut_depth);

  /* count whole */
  count = 0;
  for(wg=*rootp;wg;wg=wg->next) count++;
  if (count == 0) return;
  
  /* prepare buffer to count words per frame */
  wc = (int *)mymalloc(sizeof(int) * r->peseqlen);
  for (t=0;t<r->peseqlen;t++) wc[t] = 0;
  /* sort words by fscore_head */
  wlist = (WordGraph **)mymalloc(sizeof(WordGraph *) * count);
  i = 0;
  for(wg=*rootp;wg;wg=wg->next) {
    wlist[i++] = wg;
  }
  qsort(wlist, count, sizeof(WordGraph *), (int (*)(const void *, const void *))compare_beam);
  /* count words per frame, and unlink/mark them if below beam width */
  pruned = 0;
  for (i=0;i<count;i++) {
    wg = wlist[i];
    f = TRUE;
    for (t=wg->lefttime;t<=wg->righttime;t++) {
      wc[t]++;
      if (wc[t] <= r->config->graph.graphout_cut_depth) f = FALSE;
    }
    if (f) {
      //wordgraph_remove_context(wg);
      wg->mark = TRUE;
      pruned++;
    }
  }
#ifdef GDEBUG2
  jlog("DEBUG: GRAPH DEPTH STATISTICS: NUMBER OF WORDS PER FRAME\n");
  for(t=0;t<r->peseqlen;t++) {
    if (wc[t] > r->config->graph.graphout_cut_depth) {
      jlog("*");
    } else {
      jlog(" ");
    }
    jlog("%4d: %d\n", t, wc[t]);
  }
#endif
  if (verbose_flag) jlog("STAT: graphout: %d words out of %d are going to be pruned by depth cutting\n", pruned, count);
  free(wlist);
  free(wc);

  /* mark words to be erased */
  del_left = del_right = 0;
  do {
    changed = FALSE;
    for(wg=*rootp;wg;wg=wg->next) {
      if (wg->mark == TRUE) continue;
      /* mark if wg has no left context, or all leftwords are marked */
      if (wg->lefttime != 0) {
	for(i=0;i<wg->leftwordnum;i++) {
	  if (wg->leftword[i]->mark == FALSE) break;
	}
	if (i >= wg->leftwordnum) {
	  wg->mark = TRUE;
	  changed = TRUE;
	  del_left++;
	  continue;
	}
      }
      /* mark if wg has no right context, or all rightwords are marked */
      if (wg->righttime != r->peseqlen - 1) {
	for(i=0;i<wg->rightwordnum;i++) {
	  if (wg->rightword[i]->mark == FALSE) break;
	}
	if (i >= wg->rightwordnum) {
	  wg->mark = TRUE;
	  changed = TRUE;
	  del_right++;
	  continue;
	}
      }
    }
  } while (changed == TRUE);

  if (verbose_flag) jlog("STAT: graphout: %d new leaves found (left_blank=%d, right_blank=%d)\n", del_left + del_right, del_left, del_right);

  /* do compaction of left/rightwords */
    for(wg=*rootp;wg;wg=wg->next) {
      if (wg->mark) continue;
      dst = 0;
      for(i=0;i<wg->leftwordnum;i++) {
	if (wg->leftword[i]->mark == FALSE) {
	  if (dst != i) {
	    wg->leftword[dst] = wg->leftword[i];
	    wg->left_lscore[dst] = wg->left_lscore[i];
	  }
	  dst++;
	}
      }
      wg->leftwordnum = dst;
    }
    for(wg=*rootp;wg;wg=wg->next) {
      if (wg->mark) continue;
      dst = 0;
      for(i=0;i<wg->rightwordnum;i++) {
	if (wg->rightword[i]->mark == FALSE) {
	  if (dst != i) {
	    wg->rightword[dst] = wg->rightword[i];
	    wg->right_lscore[dst] = wg->right_lscore[i];
	  }
	  dst++;
	}
      }
      wg->rightwordnum = dst;
    }

  /* execute erase of marked words */
  erased = wordgraph_exec_erase(rootp);
  if (verbose_flag) jlog("STAT: graphout: total %d words purged, %d words left in lattice\n", erased, count - erased);

#else  /* ~GRAPHOUT_DEPTHCUT */

  if (verbose_flag) jlog("STAT: graphout: step 1.5: graph depth cutting has been disabled, skipped\n");

#endif

}

/** 
 * <JA>
 * 帽胳粗の董肠攫鼠のずれ输赖を悸乖する. グラフ面の帽胳をチェックし,
 * 儡鲁帽胳粗で董肠箕粗攫鼠にずれがあるときは·そのずれを饯赖する. 
 * 剩眶のコンテキスト粗で佰なる董肠攫鼠が赂哼する眷圭は,铬输を
 * コピ〖してそれぞれに圭わせる. またアラインメントが稍赖な帽胳を近殿する. 
 * 
 * @param rootp [i/o] グラフ帽胳リストのル〖トポインタ
 * @param mov_num_ret [out] 董肠箕粗が瓢いた帽胳眶を呈羌する恃眶へのポインタ
 * @param dup_num_ret [out] コピ〖された帽胳眶を呈羌する恃眶へのポインタ
 * @param del_num_ret [out] 猴近された帽胳眶を呈羌する恃眶へのポインタ
 * @param mod_num_ret [out] 恃构された帽胳眶を呈羌する恃眶へのポインタ
 * @param count [in] グラフ惧の帽胳眶
 * @param maxfnum
 * @param peseqlen
 * @param lmtype
 * @param p_framelist
 * @param p_framescorelist
 * 
 * @return グラフ柒の帽胳が１つ笆惧恃构されれば TRUE·恃构なしであれば FALSE
 * を手す. 
 * </JA>
 * <EN>
 * Execute adjustment of word boundaries.  It looks through the graph to
 * check correspondence of word boundary information among context, and if
 * there is a gap, the beginning frame of right word will be moved to the
 * end frame of left word.  If several alignment is found among contexts,
 * the word will be duplicated and each will be fit to each context.  Also,
 * words with invalid alignment will be eliminated.
 * 
 * @param rootp [in] root pointer to the list of graph words
 * @param mov_num_ret [out] pointer to hold resulted number of moved words
 * @param dup_num_ret [out] pointer to hold resulted number of duplicated words
 * @param del_num_ret [out] pointer to hold resulted number of eliminated words
 * @param mod_num_ret [out] pointer to hold resulted number of modified words
 * @param count [in] number of words in graph
 * @param maxfnum
 * @param peseqlen
 * @param lmtype
 * @param p_framelist
 * @param p_framescorelist
 * 
 * @return TRUE if any word has been changed, or FALSE if no word has been altered.
 * </EN>
 */
static boolean
wordgraph_adjust_boundary_sub(WordGraph **rootp, int *mov_num_ret, int *dup_num_ret, int *del_num_ret, int *mod_num_ret, int count, int *maxfnum, int peseqlen, int lmtype, int **p_framelist, LOGPROB **p_framescorelist)
{
  WordGraph *wg, *left, *new;
  int i, j, k;
  int fnum;
  int mov_num, dup_num, del_num, mod_num;
  boolean changed = FALSE;
  int *framelist;
  LOGPROB *framescorelist;

  mov_num = dup_num = del_num = mod_num = 0;

  framelist = *p_framelist;
  framescorelist = *p_framescorelist;

  /* maximum number of left context words does not exceed total word num */
  /* allocate temporal work area.  these are permanent buffer that will
     be kept between recognition sessions. */
  if (*maxfnum == 0) {
    /* when this is called for the first time, allocate buffer */
    *maxfnum = count;
    framelist = (int *)mymalloc(sizeof(int) * (*maxfnum));
    framescorelist = (LOGPROB *)mymalloc(sizeof(LOGPROB) * (*maxfnum));
#ifdef GDEBUG
    jlog("DEBUG: Notice: maxfnum starts at %d\n", *maxfnum);
#endif
  } else if (*maxfnum < count) {
    /* for later call, expand buffer if necessary */
    free(framescorelist);
    free(framelist);
    *maxfnum = count;
    framelist = (int *)mymalloc(sizeof(int) * (*maxfnum));
    framescorelist = (LOGPROB *)mymalloc(sizeof(LOGPROB) * (*maxfnum));
#ifdef GDEBUG
    jlog("DEBUG: Notice: maxfnum expanded by count (%d)\n", *maxfnum);
#endif
  }

#ifdef GDEBUG2
  jlog("DEBUG: ***CHECK LOOP BEGIN***\n");
#endif
  for(wg=*rootp;wg;wg=wg->next) {
    if (wg->mark) continue;	/* already marked */
#ifdef GDEBUG2
    jlog("DEBUG:   [%d..%d] \"%s\"\n", wg->lefttime, wg->righttime, wchmm_local->winfo->woutput[wg->wid]);
#endif
    if (wg->leftwordnum == 0) {	/* no leftword */
      if (wg->lefttime != 0) {