beam.c

julius version 4.12.about sound recognition.

 * <JA>
 * @brief  腾菇陇步辑今惧のあるノ〖ドが·附哼なんらかのト〖クンを
 * 瘦积しているかをチェックする. 
 *
 * WPAIR が年盗されている眷圭·ノ〖ドは木涟帽胳ごとに佰なるト〖クンを剩眶
 * 瘦积する. この眷圭, 回年された帽胳IDを木涟帽胳とするト〖クンが
 * そのノ〖ドに瘦积されているかどうかがチェックされる. すなわち·贷にト〖クン
 * が赂哼しても·そのト〖クンの山すパスの木涟帽胳が回年した帽胳と佰なって
 * いれば踏瘦积 (TOKENID_UNDEFINED) を手す. 
 * 
 * @param d [i/o] 妈1パス玫瑚借妄脱ワ〖クエリア
 * @param tt [in] 木涟のワ〖クエリアID (0 または 1)
 * @param node [in] ノ〖ド戎规
 * @param wid [in] 木涟帽胳のID (WPAIR年盗箕のみ铜跟, 戮では痰浑される)
 *
 * @return そのノ〖ドが贷に瘦积するト〖クン戎规·痰ければ TOKENID_UNDEFINED. 
 * </JA>
 * <EN>
 * @brief  Check if a node holds any token
 *
 * This function checks if a node on the tree lexicon already holds a token.
 *
 * If WPAIR is defined, a node has multiple tokens according to the previous
 * word context.  In this case, only token with the same previous word will be
 * checked.
 * 
 * @param d [i/o] work area for 1st pass recognition processing
 * @param tt [in] work area id (0 or 1)
 * @param node [in] node id of lexicon tree
 * @param wid [in] word id of previous word (ignored if WPAIR is not defined)
 * 
 * @return the token id on the node, or TOKENID_UNDEFINED if no token has
 * been assigned in this frame.
 * </EN>
 */
static TOKENID
node_exist_token(FSBeam *d, int tt, int node, WORD_ID wid)
{
#ifdef WPAIR
  /* In word-pair mode, multiple tokens are assigned to a node as a list.
     so we have to search for tokens with same last word ID */
#ifdef WPAIR_KEEP_NLIMIT
  /* 1ノ〖ドごとに瘦积するtoken眶の惧嘎を肋年 */
  /* tokenが痰いが惧嘎に茫しているときは办戎スコアの你いtokenを惧今きする */
  /* N-best: limit number of assigned tokens to a node */
  int i = 0;
  TOKENID lowest_token = TOKENID_UNDEFINED;
#endif
  TOKENID tmp;
  for(tmp=d->token[node]; tmp != TOKENID_UNDEFINED; tmp=d->tlist[tt][tmp].next) {
    if (d->tlist[tt][tmp].last_tre->wid == wid) {
      return(tmp);
    }
#ifdef WPAIR_KEEP_NLIMIT
    if (lowest_token == TOKENID_UNDEFINED ||
	d->tlist[tt][lowest_token].score < d->tlist[tt][tmp].score)
      lowest_token = tmp;
    if (++i >= d->wpair_keep_nlimit) break;
#endif
  }
#ifdef WPAIR_KEEP_NLIMIT
  if (i >= d->wpair_keep_nlimit) { /* overflow, overwrite lowest score */
    return(lowest_token);
  } else {
    return(TOKENID_UNDEFINED);
  }
#else 
  return(TOKENID_UNDEFINED);
#endif
  
#else  /* not WPAIR */
  /* 1つだけ瘦积,これを撅に惧今き */
  /* Only one token is kept in 1-best mode (default), so
     simply return the ID */
  return(d->token[node]);
#endif
}

#ifdef DEBUG
/* tlist と token の滦炳をチェックする(debug) */
/* for debug: check tlist <-> token correspondence
   where  tlist[tt][tokenID].node = nodeID and
          token[nodeID] = tokenID
 */
static void
node_check_token(FSBeam *d, int tt)
{
  int i;
  for(i=0;i<d->tnum[tt];i++) {
    if (node_exist_token(d, tt, d->tlist[tt][i].node, d->tlist[tt][i].last_tre->wid) != i) {
      jlog("ERROR: token %d not found on node %d\n", i, d->tlist[tt][i].node);
    }
  }
}
#endif



/* -------------------------------------------------------------------- */
/*       ト〖クンをソ〖トし 惧疤 N ト〖クンを冉侍する (heap sort)       */
/*        Sort generated tokens and get N-best (use heap sort)          */
/* -------------------------------------------------------------------- */
/* ビ〖ムの镧猛として惧疤 N 戎誊のスコアが瓦しいだけであり·悸狠にソ〖ト
   される涩妥はない */
/* we only want to know the N-th score for determining beam threshold, so
   order is not considered here */

#define SD(A) tindex_local[A-1]	///< Index locater for sort_token_*()
#define SCOPY(D,S) D = S	///< Content copier for sort_token_*()
#define SVAL(A) (tlist_local[tindex_local[A-1]].score) ///< Score locater for sort_token_*()
#define STVAL (tlist_local[s].score) ///< Indexed score locater for sort_token_*()

/** 
 * <JA>
 * @brief  ト〖クンスペ〖スをスコアの络きい界にソ〖トする. 
 *
 * heap sort を脱いて附哼のト〖クン礁圭をスコアの络きい界にソ〖トする. 
 * 惧疤 @a neednum 改のト〖クンがソ〖トされればそこで借妄を姜位する. 
 * 
 * @param d [i/o] 妈1パス玫瑚借妄脱ワ〖クエリア
 * @param neednum [in] 惧疤 @a neednum 改が评られるまでソ〖トする
 * @param totalnum [in] ト〖クンスペ〖ス柒の铜跟なト〖クン眶
 * </JA>
 * <EN>
 * @brief  Sort the token space upward by score.
 *
 * This function sort the whole token space in upward direction, according
 * to their accumulated score.
 * This function terminates sort as soon as the top
 * @a neednum tokens has been found.
 * 
 * @param d [i/o] work area for 1st pass recognition processing
 * @param neednum [in] sort until top @a neednum tokens has been found
 * @param totalnum [in] total number of assigned tokens in the token space
 * </EN>
 */
static void
sort_token_upward(FSBeam *d, int neednum, int totalnum)
{
  int n,root,child,parent;
  TOKENID s;
  TOKEN2 *tlist_local;
  TOKENID *tindex_local;

  tlist_local = d->tlist[d->tn];
  tindex_local = d->tindex[d->tn];

  for (root = totalnum/2; root >= 1; root--) {
    SCOPY(s, SD(root));
    parent = root;
    while ((child = parent * 2) <= totalnum) {
      if (child < totalnum && SVAL(child) < SVAL(child+1)) {
	child++;
      }
      if (STVAL >= SVAL(child)) {
	break;
      }
      SCOPY(SD(parent), SD(child));
      parent = child;
    }
    SCOPY(SD(parent), s);
  }
  n = totalnum;
  while ( n > totalnum - neednum) {
    SCOPY(s, SD(n));
    SCOPY(SD(n), SD(1));
    n--;
    parent = 1;
    while ((child = parent * 2) <= n) {
      if (child < n && SVAL(child) < SVAL(child+1)) {
	child++;
      }
      if (STVAL >= SVAL(child)) {
	break;
      }
      SCOPY(SD(parent), SD(child));
      parent = child;
    }
    SCOPY(SD(parent), s);
  }
}

/** 
 * <JA>
 * @brief  ト〖クンスペ〖スをスコアの井さい界にソ〖トする. 
 *
 * ビ〖ムのしきい猛疯年のために·heap sort を脱いて
 * 附哼のト〖クン礁圭をスコアの井さい界にソ〖トする. 
 * 布疤 @a neednum 改のト〖クンがソ〖トされればそこで借妄を姜位する. 
 * 
 * @param d [i/o] 妈1パス玫瑚借妄脱ワ〖クエリア
 * @param neednum [in] 布疤 @a neednum 改が评られるまでソ〖トする
 * @param totalnum [in] ト〖クンスペ〖ス柒の铜跟なト〖クン眶
 * </JA>
 * <EN>
 * @brief  Sort the token space downward by score.
 *
 * This function sort the whole token space in downward direction, according
 * to their accumulated score for hypothesis pruning.
 *
 * This function terminates sort as soon as the bottom
 * @a neednum tokens has been found.
 * 
 * @param d [i/o] work area for 1st pass recognition processing
 * @param neednum [in] sort until bottom @a neednum tokens has been found
 * @param totalnum [in] total number of assigned tokens in the token space
 * </EN>
 */
static void
sort_token_downward(FSBeam *d, int neednum, int totalnum)
{
  int n,root,child,parent;
  TOKENID s;
  TOKEN2 *tlist_local;
  TOKENID *tindex_local;

  tlist_local = d->tlist[d->tn];
  tindex_local = d->tindex[d->tn];

  for (root = totalnum/2; root >= 1; root--) {
    SCOPY(s, SD(root));
    parent = root;
    while ((child = parent * 2) <= totalnum) {
      if (child < totalnum && SVAL(child) > SVAL(child+1)) {
	child++;
      }
      if (STVAL <= SVAL(child)) {
	break;
      }
      SCOPY(SD(parent), SD(child));
      parent = child;
    }
    SCOPY(SD(parent), s);
  }
  n = totalnum;
  while ( n > totalnum - neednum) {
    SCOPY(s, SD(n));
    SCOPY(SD(n), SD(1));
    n--;
    parent = 1;
    while ((child = parent * 2) <= n) {
      if (child < n && SVAL(child) > SVAL(child+1)) {
	child++;
      }
      if (STVAL <= SVAL(child)) {
	break;
      }
      SCOPY(SD(parent), SD(child));
      parent = child;
    }
    SCOPY(SD(parent), s);
  }
}

/** 
 * <JA>
 * @brief ト〖クンスペ〖スをソ〖トしてビ〖ム柒に荒るト〖クンを疯年する
 * 
 * heap sort を脱いて附哼のト〖クン礁圭をソ〖トし·惧疤スコアのト〖クン
 * 礁圭を滇める. 惧疤 @a neednum 改のト〖クン礁圭が评られれば紊いので·
 * 链挛が窗链にソ〖トされている涩妥はない. よって
 * 惧疤 @a neednum 改のト〖クンのみをソ〖トする. 悸狠には·链挛のト〖クン
 * 眶と涩妥なト〖クン眶から sort_token_upward()
 * と sort_token_downward() の玲い数が脱いられる. 
 * 
 * @param d [i/o] 妈1パス玫瑚借妄脱ワ〖クエリア
 * @param neednum [in] 滇める惧疤ト〖クンの眶
 * @param start [out] 惧疤 @a neednum のト〖クンが赂哼するト〖クンスペ〖スの呵介のインデックス戎规
 * @param end [out] 惧疤 @a neednum のト〖クンが赂哼するト〖クンスペ〖スの呵稿のインデックス戎规
 * </JA>
 * <EN>
 * @brief Sort the token space to find which tokens to be survived in the beam
 *
 * This function sorts the currrent tokens in the token space to find
 * the tokens to be survived in the current frame.  Only getting the top
 * @a neednum tokens is required, so the sort will be terminate just after
 * the top @a neednum tokens are determined.  Actually, either
 * sort_token_upward() or sort_token_downward() will be used depending of
 * the number of needed tokens and total tokens.
 * 
 * @param d [i/o] work area for 1st pass recognition processing
 * @param neednum [in] number of top tokens to be found
 * @param start [out] start index of the top @a neednum nodes
 * @param end [out] end index of the top @a neednum nodes
 * </EN>
 */
static void
sort_token_no_order(FSBeam *d, int neednum, int *start, int *end)
{
  int totalnum;
  int restnum;

  totalnum = d->tnum[d->tn];

  restnum = totalnum - neednum;

  if (neednum >= totalnum) {
    /* no need to sort */
    *start = 0;
    *end = totalnum - 1;
  } else if (neednum < restnum)  {
    /* needed num is smaller than rest, so sort for the needed tokens */
    sort_token_upward(d, neednum,totalnum);
    *start = totalnum - neednum;
    *end = totalnum - 1;
  } else {
    /* needed num is bigger than rest, so sort for the rest token */
    sort_token_downward(d, restnum,totalnum);
    *start = 0;
    *end = neednum - 1;
  }
}

/* -------------------------------------------------------------------- */
/*             妈１パス(フレ〖ム票袋ビ〖ムサ〖チ) メイン                */
/*           main routines of 1st pass (frame-synchronous beam search)  */
/* -------------------------------------------------------------------- */

/** 
 * <JA>
 * @brief  介袋簿棱の栏喇
 *
 * 介袋簿棱は·N-gramでは winfo->head_silwid に盖年されている. DFA では
 * 矢恕惧矢片にきうる帽胳すべてが介袋簿棱となる. 帽胳千急モ〖ドでは
 * 链ての帽胳が介袋簿棱となる. 
 *
 * 不读モデルが润multipathの眷圭·ここで呵介のフレ〖ムの叫蜗澄唯
 * 纷换まで乖われる. 
 * 
 * @param param [in] 掐蜗ベクトル误攫鼠(呵介のフレ〖ムのみ涩妥)
 * @param r [in] 不兰千急借妄インスタンス
 * </JA>
 * <EN>
 * @brief  Generate initial hypotheses
 *
 * The initial hypothesis is: 1) winfo->head_silwid for N-gram, 2) all words
 * that can be at beginning of sentence for DFA, or 3) all words in dictionary
 * for isolated word recognition mode.
 *
 * If acoustic model is NOT a multi-path model, the output probabilities for
 * the first frame (t=0) will also be computed in this function.
 * 
 * @param param [in] input vectors (only the first frame will be used)
 * @param r [in] recognition process instance
 * </EN>
 */
static boolean
init_nodescore(HTK_Param *param, RecogProcess *r)
{
  WCHMM_INFO *wchmm;
  FSBeam *d;
  TOKENID newid;
  TOKEN2 *new;
  WORD_ID beginword;
  int node;
  int i;

  wchmm = r->wchmm;
  d = &(r->pass1);

  /* 介袋簿棱脱帽胳旺悟 */
  /* setup initial word context */
  if (r->config->successive.enabled) { /* sp segment mode */
    /* initial word context = last non-sp word of previous 2nd pass at last segment*/
    if (r->lmtype == LM_PROB) {
      if (r->sp_break_last_nword == wchmm->winfo->tail_silwid) {
	/* if end with silE, initialize as normal start of sentence */
	d->bos.wid = WORD_INVALID;
      } else {
	d->bos.wid = r->sp_break_last_nword;
      }
    } else {
      d->bos.wid = WORD_INVALID;
    }
  } else {			/* not sp segment mode */
    d->bos.wid = WORD_INVALID;	/* no context */
  }

  d->bos.begintime = d->bos.endtime = -1;

  /* ノ〖ドˇト〖クンを介袋步 */
  /* clear tree lexicon nodes and tokens */
  for(node = 0; node < d->totalnodenum; node++) {
    d->token[node] = TOKENID_UNDEFINED;
  }
  d->tnum[0] = d->tnum[1]  = 0;
  
#ifdef PASS1_IWCD
  /* 叫蜗澄唯纷换キャッシュを介袋步 */
  /* initialize outprob cache */
  outprob_style_cache_init(wchmm);
#endif

  /* 介袋簿棱の侯喇: 介袋帽胳の疯年と介袋ト〖クンの栏喇 */
  /* initial word hypothesis */

  if (r->lmtype == LM_PROB) {

    if (r->config->successive.enabled) { /* sp segment mode */
      if (r->sp_break_last_word != WORD_INVALID) { /* last segment exist */
	/* 倡幌帽胳♂涟のセグメント纷换箕の呵稿の呵锑帽胳 */