libjulius/src/search_bestfirst_main.c

説明を見る。

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

#include <julius/julius.h>

/* declaration of local functions */
static NODE *get_best_from_stack(NODE **start, int *stacknum);
static int put_to_stack(NODE *new, NODE **start, NODE **bottom, int *stacknum, int stacksize);
static void put_all_in_stack(NODE **start, int *stacknum, WORD_INFO *winfo);
static void free_all_nodes(NODE *node);
static void put_hypo_woutput(NODE *hypo, WORD_INFO *winfo);
static void put_hypo_wname(NODE *hypo, WORD_INFO *winfo);

/**********************************************************************/
/********** 次単語格納領域の割り当て          *************************/
/********** allocate memory for nextword data *************************/
/**********************************************************************/

static NEXTWORD **
nw_malloc(int *maxlen, NEXTWORD **root, int max)
{
  NEXTWORD *nwtmp;
  NEXTWORD **nw;
  int i;

  nw = (NEXTWORD **)mymalloc(max * sizeof(NEXTWORD *));
  nwtmp = (NEXTWORD *)mymalloc(max * sizeof(NEXTWORD));
  for (i=0;i<max; i++) {
    nw[i] = &(nwtmp[i]);
  }
  *maxlen = max;
  *root = nwtmp;
  return nw;
}

static void
nw_free(NEXTWORD **nw, NEXTWORD *root)
{
  free(root);
  free(nw);
}

static NEXTWORD **
nw_expand(NEXTWORD **nwold, int *maxlen, NEXTWORD **root, int num)
{
  NEXTWORD *nwtmp;
  NEXTWORD **nw;
  int i;
  int nwmaxlen;

  nwmaxlen = *maxlen + num;

  nwtmp = (NEXTWORD *)myrealloc(*root, nwmaxlen * sizeof(NEXTWORD));
  nw = (NEXTWORD **)myrealloc(nwold, nwmaxlen * sizeof(NEXTWORD *));
  nw[0] = nwtmp;
  for (i=1;i<nwmaxlen; i++) {
    nw[i] = &(nwtmp[i]);
  }
  *maxlen = nwmaxlen;
  *root = nwtmp;
  return nw;
}


/**********************************************************************/
/********** 仮説スタックの操作         ********************************/
/********** Hypothesis stack operation ********************************/
/**********************************************************************/

static NODE *
get_best_from_stack(NODE **start, int *stacknum)
{
  NODE *tmp;

  /* return top */
  tmp=(*start);
  if ((*start)!=NULL) {         /* delete it from stack */
    (*start)=(*start)->next;
    if ((*start)!=NULL) (*start)->prev=NULL;
    (*stacknum)--;
    return(tmp);
  }
  else {
    return(NULL);
  }
}

static int
can_put_to_stack(NODE *new, NODE **bottom, int *stacknum, int stacksize)
{
  /* stack size check */
  if ((*stacknum + 1) > stacksize && (*bottom)->score >= new->score) {
    /* new node is below the bottom: discard it */
    return(-1);
  }
  return(0);
}

static int
put_to_stack(NODE *new, NODE **start, NODE **bottom, int *stacknum, int stacksize)
{
  NODE *tmp;

  /* stack size is going to increase... */
  (*stacknum)++;

  /* stack size check */
  if ((*stacknum)>stacksize) {
    /* stack size overflow */
    (*stacknum)--;
    if ((*bottom)->score < new->score) {
      /* new node will be inserted in the stack: free the bottom */
      tmp=(*bottom);
      (*bottom)->prev->next=NULL;
      (*bottom)=(*bottom)->prev;
      free_node(tmp);
    } else {
      /* new node is below the bottom: discard it */
      free_node(new);
      return(-1);
    }
  }

  /* insert new node on edge */
  if ((*start)==NULL) {         /* no node in stack */
    /* new node is the only node */
    (*start)=new;
    (*bottom)=new;
    new->next=NULL;
    new->prev=NULL;
    return(0);
  }
  if ((*start)->score <= new->score) {
    /* insert on the top */
    new->next = (*start);
    new->next->prev = new;
    (*start)=new;
    new->prev=NULL;
    return(0);
  }
  if ((*bottom)->score >= new->score) {
    /* insert on the bottom */
    new->prev = (*bottom);
    new->prev->next = new;
    (*bottom)=new;
    new->next=NULL;
    return(0);
  }
    
  /* now the new node is between (*start) and (*bottom) */
  if (((*start)->score + (*bottom)->score) / 2 > new->score) {
    /* search from bottom */
    tmp=(*bottom);
    while(tmp->score < new->score) tmp=tmp->prev;
    new->prev=tmp;
    new->next=tmp->next;
    tmp->next->prev=new;
    tmp->next=new;
  } else {
    /* search from start */
    tmp=(*start);
    while(tmp->score > new->score) tmp=tmp->next;
    new->next=tmp;
    new->prev=tmp->prev;
    tmp->prev->next=new;
    tmp->prev=new;
  }
  return(0);
}

static void
put_all_in_stack(NODE **start, int *stacknum, WORD_INFO *winfo)
{
  NODE *ntmp;
  
  jlog("DEBUG: hypotheses remained in global stack\n");
  while ((ntmp = get_best_from_stack(start, stacknum)) != NULL) {
    jlog("DEBUG: %3d: s=%f",*stacknum, ntmp->score);
    put_hypo_woutput(ntmp, winfo);
    free_node(ntmp);
  }
}

static void
free_all_nodes(NODE *start)
{
  NODE *tmp;
  NODE *next;

  tmp=start;
  while(tmp) {
    next=tmp->next;
    free_node(tmp);
    tmp=next;
  }
}


#ifdef CONFIDENCE_MEASURE

/**********************************************************************/
/********** 単語信頼度の計算 ******************************************/
/********** Confidence scoring ****************************************/
/**********************************************************************/

#ifdef CM_SEARCH
/**************************************************************/
/**** CM computation method 1(default):                  ******/
/****   - Use local posterior probabilities while search ******/
/****   - Obtain CM at hypothesis expansion time         ******/
/**************************************************************/

static void
cm_init(StackDecode *sd, int wnum, LOGPROB cm_alpha
#ifdef CM_MULTIPLE_ALPHA
        , cm_alpha_num
#endif
        )
{
  sd->l_stacksize = wnum;
  sd->l_start = sd->l_bottom = NULL;
  sd->l_stacknum = 0;
  sd->cm_alpha = cm_alpha;
#ifdef CM_MULTIPLE_ALPHA
  if (sd->cmsumlist) {
    if (sd->cmsumlistlen < cm_alpha_num) {
      free(sd->cmsumlist);
      sd->cmsumlist = NULL;
    }
  }
  if (sd->cmsumlist == NULL) {
    sd->cmsumlist = (LOGPROB *)mymalloc(sizeof(LOGPROB) * cm_alpha_num);
    sd->cmsumlistlen = cm_alpha_num;
  }
#endif    
}

static void
cm_store(StackDecode *sd, NODE *new)
{
  /* store the generated hypo into local stack */
  put_to_stack(new, &(sd->l_start), &(sd->l_bottom), &(sd->l_stacknum), sd->l_stacksize);
}

static void
cm_sum_score(StackDecode *sd
#ifdef CM_MULTIPLE_ALPHA
             , bgn, end, step
#endif
)
{
  NODE *node;
  LOGPROB sum;
#ifdef CM_MULTIPLE_ALPHA
  LOGPROB a;
  int j;
#endif

  if (sd->l_start == NULL) return;      /* no hypo */
  sd->cm_tmpbestscore = sd->l_start->score; /* best hypo is at the top of the stack */

#ifdef CM_MULTIPLE_ALPHA
  for (j = 0, a = bgn; a <= end; a += step) {
    sum = 0.0;
    for(node = sd->l_start; node; node = node->next) {
      sum += pow(10, a * (node->score - sd->cm_tmpbestscore));
    }
    sd->cmsumlist[j++] = sum;   /* store sums for each alpha coef. */
  }
#else
  sum = 0.0;
  for(node = sd->l_start; node; node = node->next) {
    sum += pow(10, sd->cm_alpha * (node->score - sd->cm_tmpbestscore));
  }
  sd->cm_tmpsum = sum;          /* store sum */
#endif

}

static void
cm_set_score(StackDecode *sd, NODE *node
#ifdef CM_MULTIPLE_ALPHA
             , bgn, end, step
#endif
             )
{
#ifdef CM_MULTIPLE_ALPHA
  int j;
  LOGPROB a;
#endif

#ifdef CM_MULTIPLE_ALPHA
  for (j = 0, a = bgn; a <= end; a += step) {
    node->cmscore[node->seqnum-1][j] = pow(10, a * (node->score - sd->cm_tmpbestscore)) / sd->cmsumlist[j];
    j++;
  }
#else
  node->cmscore[node->seqnum-1] = pow(10, sd->cm_alpha * (node->score - sd->cm_tmpbestscore)) / sd->cm_tmpsum;
#endif
}

static NODE *
cm_get_node(StackDecode *sd)
{
  return(get_best_from_stack(&(sd->l_start), &(sd->l_stacknum)));
}

#endif /* CM_SEARCH */

#ifdef CM_NBEST
/*****************************************************************/
/**** CM computation method 2: conventional N-best scoring *******/
/**** NOTE: enough N-best should be computed (-n 10 ~ -n 100) ****/
/*****************************************************************/

static void
cm_compute_from_nbest(StackDecode *sd, NODE *start, int stacknum, JCONF_SEARCH *jconf)
{
  NODE *node;
  LOGPROB bestscore, sum, s;
  WORD_ID w;
  int i;
  LOGPROB cm_alpha;
  int j;

  /* prepare buffer */
#ifdef CM_MULTIPLE_ALPHA
  if (sd->cmsumlist) {
    if (sd->cmsumlistlen < jconf->annotate.cm_alpha_num) {
      free(sd->cmsumlist);
      sd->cmsumlist = NULL;
    }
  }
  if (sd->cmsumlist == NULL) {
    sd->cmsumlist = (LOGPROB *)mymalloc(sizeof(LOGPROB) * jconf->annotate.cm_alpha_num);
    sd->cmsumlistlen = cm_alpha_num;
  }
#endif    
  if (sd->sentcm == NULL) {             /* not allocated yet */
    sd->sentcm = (LOGPROB *)mymalloc(sizeof(LOGPROB)*stacknum);
    sd->sentnum = stacknum;
  } else if (sd->sentnum < stacknum) { /* need expanded */
    sd->sentcm = (LOGPROB *)myrealloc(sd->sentcm, sizeof(LOGPROB)*stacknum);
    sd->sentnum = stacknum;
  }
  if (sd->wordcm == NULL) {
    sd->wordcm = (LOGPROB *)mymalloc(sizeof(LOGPROB) * winfo->num);
    sd->wordnum = winfo->num;
  } else if (sd->wordnum < winfo->num) {
    sd->wordcm = (LOGPROB *)myremalloc(sd->wordcm, sizeof(LOGPROB) * winfo->num);
    sd->wordnum = winfo->num;
  }
  
  cm_alpha = jconf->annotate.cm_alpha;
#ifdef CM_MULTIPLE_ALPHA
  for (j = 0, cm_alpha = jconf->annotate.cm_alpha_bgn; cm_alpha <= jconf->annotate.cm_alpha_end; cm_alpha += jconf->annotate.cm_alpha_step) {
#endif
    /* clear whole word cm buffer */
    for(w=0;w<sd->wordnum;w++) {
      sd->wordcm[w] = 0.0;
    }
    /* get best score */
    bestscore = start->score;
    /* compute sum score of all hypothesis */
    sum = 0.0;
    for (node = start; node != NULL; node = node->next) {
      sum += pow(10, cm_alpha * (node->score - bestscore));
    }
    /* compute sentence posteriori probabilities */
    i = 0;
    for (node = start; node != NULL; node = node->next) {
      sd->sentcm[i] = pow(10, cm_alpha * (node->score - bestscore)) / sum;
      i++;
    }
    /* compute word posteriori probabilities */
    i = 0;
    for (node = start; node != NULL; node = node->next) {
      for (w=0;w<node->seqnum;w++) {
        sd->wordcm[node->seq[w]] += sd->sentcm[i];
      }
      i++;
    }
    /* store the probabilities to node */
    for (node = start; node != NULL; node = node->next) {
      for (w=0;w<node->seqnum;w++) {
#ifdef CM_MULTIPLE_ALPHA
        node->cmscore[w][j] = sd->wordcm[node->seq[w]];
#else   
        node->cmscore[w] = sd->wordcm[node->seq[w]];
#endif
      }
    }
#ifdef CM_MULTIPLE_ALPHA
    j++;
  }
#endif
}

#endif /* CM_NBEST */

#endif /* CONFIDENCE_MEASURE */


/**********************************************************************/
/********** Enveloped best-first search *******************************/
/**********************************************************************/

/*
 * 1. Word envelope
 *
 * 一種の仮説ビーム幅を設定: 展開元となった仮説の数をその仮説長(単語数)
 * ごとにカウントする. 一定数を越えたらそれより短い仮説は以後展開しない. 
 * 
 * Introduce a kind of beam width to search tree: count the number of
 * popped hypotheses per the depth of the hypotheses, and when a count
 * in a certain depth reaches the threshold, all hypotheses shorter than
 * the depth will be dropped from candidates.
 *
 */

static void
wb_init(StackDecode *s)
{
  int i;
  for(i=0;i<=MAXSEQNUM;i++) s->hypo_len_count[i] = 0;
  s->maximum_filled_length = -1;
}

static boolean
wb_ok(StackDecode *s, NODE *now, int width)
{
  if (now->seqnum <= s->maximum_filled_length) {
    /* word expansion is not allowed because a word expansion count
       at deeper level has already reached the limit */
    return FALSE;
  } else {
    /* word expansion is possible.  Increment the word expansion count
       of the given depth */
    s->hypo_len_count[now->seqnum]++;
    if (s->hypo_len_count[now->seqnum] > width) {
      /* the word expansion count of this level has reached the limit, so
         set the beam-filled depth to this level to inhibit further
         expansion of shorter hypotheses. */
      if (s->maximum_filled_length < now->seqnum) s->maximum_filled_length = now->seqnum;
    }
    return TRUE;
  }
}

#ifdef SCAN_BEAM
/*
 * 2. Score envelope
 *
 * Viterbi計算量の削減: 入力フレームごとの最大尤度 (score envelope) を
 * 全仮説にわたって記録しておく. 仮説の前向き尤度計算時に，その envelope
 * から一定幅以上スコアが下回るとき，Viterbi パスの演算を中断する. 
 *
 * ここでは，取り出した仮説からフレームごとの score envelope を更新する
 * 部分が記述されている. Envelope を考慮した Viterbi 計算の実際は
 * scan_word() を参照のこと. 
 *
 * Reduce computation cost of hypothesis Viterbi processing by setting a
 * "score envelope" that holds the maximum scores at every frames
 * throughout the expanded hypotheses.  When calculating Viterbi path
 * on HMM trellis for updating score of popped hypothesis, Viterbi paths
 * that goes below a certain range from the score envelope are dropped.
 *
 * These functions are for updating the score envelope according to the
 * popped hypothesis.  For actual Viterbi process with score envelope, 
 * see scan_word().
 *
 */

static void
envl_init(StackDecode *s, int framenum)
{
  int i;
  for(i=0;i<framenum;i++) s->framemaxscore[i] = LOG_ZERO;
}

static void
envl_update(StackDecode *s, NODE *n, int framenum)
{
  int t;
  for(t=framenum-1;t>=0;t--) {
    if (s->framemaxscore[t] < n->g[t]) s->framemaxscore[t] = n->g[t];
  }
}
#endif /* SCAN_BEAM */


/**********************************************************************/
/********** Short pause segmentation **********************************/
/**********************************************************************/

void
segment_set_last_nword(NODE *hypo, RecogProcess *r)
{
  int i;
  WORD_ID w;

  if (r->sp_break_last_nword_allow_override) {
    for(i=0;i<hypo->seqnum;i++) {
      w = hypo->seq[i];
      if (w != r->sp_break_last_word
          && !is_sil(w, r)
          && !r->lm->winfo->is_transparent[w]
          ) {
        r->sp_break_last_nword = w;
        break;
      }
    }
#ifdef SP_BREAK_DEBUG
    printf("sp_break_last_nword=%d[%s]\n", r->sp_break_last_nword, r->lm->winfo->woutput[r->sp_break_last_nword]);
#endif
  } else {
    r->sp_break_last_nword = WORD_INVALID;
  }
}


/**********************************************************************/
/********* Debug output of hypothesis while search ********************/
/**********************************************************************/

static void
put_hypo_woutput(NODE *hypo, WORD_INFO *winfo)
{
  int i,w;

  if (hypo != NULL) {
    for (i=hypo->seqnum-1;i>=0;i--) {
      w = hypo->seq[i];
      jlog(" %s", winfo->woutput[w]);
    }
  }
  jlog("\n");  
}

static void
put_hypo_wname(NODE *hypo, WORD_INFO *winfo)
{
  int i,w;

  if (hypo != NULL) {
    for (i=hypo->seqnum-1;i>=0;i--) {
      w = hypo->seq[i];
      jlog(" %s", winfo->wname[w]);
    }
  }
  jlog("\n");  
}

static void
store_result_pass2(NODE *hypo, RecogProcess *r)
{
  int i;
  Sentence *s;

  s = &(r->result.sent[r->result.sentnum]);

  s->word_num = hypo->seqnum;
  for (i = 0; i < hypo->seqnum; i++) {
    s->word[i] = hypo->seq[hypo->seqnum - 1 - i];
  }
#ifdef CONFIDENCE_MEASURE
  for (i = 0; i < hypo->seqnum; i++) {
    s->confidence[i] = hypo->cmscore[hypo->seqnum - 1 - i];
  }
#endif

  s->score = hypo->score;
  s->score_lm = hypo->totallscore;
  s->score_am = hypo->score - hypo->totallscore;
  if (r->lmtype == LM_DFA) {
    /* output which grammar the hypothesis belongs to on multiple grammar */
    /* determine only by the last word */
    if (multigram_get_all_num(r->lm) > 0) {
      s->gram_id = multigram_get_gram_from_category(r->lm->winfo->wton[hypo->seq[0]], r->lm);
    } else {
      s->gram_id = 0;
    }
  }

  r->result.sentnum++;
  /* add to tail */
}


/**********************************************************************/
/******** Output top 'ncan' hypotheses in a stack and free all ********/
/**********************************************************************/

static void
result_reorder_and_output(NODE **r_start, NODE **r_bottom, int *r_stacknum, int ncan, RecogProcess *r, HTK_Param *param)
{
  NODE *now;
  int num;

#ifdef CM_NBEST 
  /* compute CM from the N-best sentence candidates */
  cm_compute_from_nbest(&(r->pass2), *r_start, *r_stacknum, r->config);
#endif
  num = 0;
  while ((now = get_best_from_stack(r_start,r_stacknum)) != NULL && num < ncan) {
    num++;
    /* output result */
    store_result_pass2(now, r);

    /* if in sp segmentation mode, */
    /* set the last context-aware word for next recognition */
    if (r->lmtype == LM_PROB && r->config->successive.enabled && num == 1) segment_set_last_nword(now, r);

    free_node(now);
  }
  /* free the rest */
  if (now != NULL) free_node(now);
  free_all_nodes(*r_start);
}  

void
pass2_finalize_on_no_result(RecogProcess *r, boolean use_1pass_as_final)
{
  NODE *now;
  int i, j;

  /* 探索失敗 */
  /* search failed */

  /* make temporal hypothesis data from the result of previous 1st pass */
  now = newnode(r);
  for (i=0;i<r->pass1_wnum;i++) {
    now->seq[i] = r->pass1_wseq[r->pass1_wnum-1-i];
  }
  now->seqnum = r->pass1_wnum;
  now->score = r->pass1_score;
#ifdef CONFIDENCE_MEASURE
  /* fill in null values */
#ifdef CM_MULTIPLE_ALPHA
  for(j=0;j<jconf->annotate.cm_alpha_num;j++) {
    for(i=0;i<now->seqnum;i++) now->cmscore[i][j] = 0.0;
  }
#else
  for(i=0;i<now->seqnum;i++) now->cmscore[i] = 0.0;
#endif
#endif /* CONFIDENCE_MEASURE */
  
  if (r->lmtype == LM_PROB && r->config->successive.enabled) {
    /* if in sp segment mode, */
    /* find segment restart words from 1st pass result */
    segment_set_last_nword(now, r);
  }
    
  if (use_1pass_as_final) {
    /* 第1パスの結果をそのまま出力する */
    /* output the result of the previous 1st pass as a final result. */
    store_result_pass2(now, r);
    r->result.status = J_RESULT_STATUS_SUCCESS;
  } else {
    /* store output as failure */
    r->result.status = J_RESULT_STATUS_FAIL;
    //callback_exec(CALLBACK_RESULT, r);
  }
  
  free_node(now);
}


/**********************************************************************/
/********* Main stack decoding function *******************************/
/**********************************************************************/

void
wchmm_fbs(HTK_Param *param, RecogProcess *r, int cate_bgn, int cate_num)
{
  /* 文仮説スタック */
  /* hypothesis stack (double-linked list) */
  int stacknum;                 /* current stack size */
  NODE *start = NULL;           /* top node */
  NODE *bottom = NULL;          /* bottom node */

  /* 認識結果格納スタック(結果はここへいったん集められる) */
  /* result sentence stack (found results will be stored here and then re-ordered) */
  int r_stacksize;
  int r_stacknum;
  NODE *r_start = NULL;
  NODE *r_bottom = NULL;

  /* ワークエリア */
  /* work area */
  NEXTWORD fornoise; /* Dummy NEXTWORD data for short-pause insertion handling */

  NEXTWORD **nextword, *nwroot; /* buffer to store predicted words */
  int maxnwnum;                 /* current allocated number of words in nextword */
  int nwnum;                    /* current number of words in nextword */
  NODE *now, *new;              /* popped current hypo., expanded new hypo. */
  NODE *now_noise;             /* for inserting/deleting noise word */
  boolean now_noise_calced;
  boolean acc;
  int t;
  int w,i,j;
  LOGPROB last_score = LOG_ZERO;
  /* for graph generation */
  LOGPROB prev_score;
  WordGraph *wordgraph_root = NULL;
  boolean merged_p;
#ifdef GRAPHOUT_DYNAMIC
  int dynamic_merged_num = 0;
  WordGraph *wtmp;
  LOGPROB lscore_prev;
#endif
#ifdef GRAPHOUT_SEARCH
  int terminate_search_num = 0;
#endif

  /* local temporal parameter */
  int stacksize, ncan, maxhypo, peseqlen;
  JCONF_SEARCH *jconf;
  WORD_INFO *winfo;
  NGRAM_INFO *ngram;
  DFA_INFO *gdfa;
  BACKTRELLIS *backtrellis;
  StackDecode *dwrk;

  if (r->lmtype == LM_DFA) {
    if (debug2_flag) jlog("DEBUG: only words in these categories will be expanded: %d-%d\n", cate_bgn, cate_bgn + cate_num-1);
  }

  /*
   * 初期化
   * Initialize
   */

  /* just for quick access */
  jconf = r->config;
  winfo = r->lm->winfo;
  if (r->lmtype == LM_PROB) {
    ngram = r->lm->ngram;
  } else if (r->lmtype == LM_DFA) {
    gdfa = r->lm->dfa;
  }
  backtrellis = r->backtrellis;
  dwrk = &(r->pass2);

  stacksize = jconf->pass2.stack_size;
  ncan = jconf->pass2.nbest;
  maxhypo = jconf->pass2.hypo_overflow;
  peseqlen = backtrellis->framelen;

  /* store data for sub routines */
  r->peseqlen = backtrellis->framelen;
  //recog->ccd_flag = recog->jconf->am.ccd_flag;
  /* 予測単語格納領域を確保 */
  /* malloc area for word prediction */
  /* the initial maximum number of nextwords is the size of vocabulary */
  nextword = nw_malloc(&maxnwnum, &nwroot, winfo->num);
  /* 前向きスコア計算用の領域を確保 */
  /* malloc are for forward viterbi (scan_word()) */
  malloc_wordtrellis(r);                /* scan_word用領域 */
  /* 仮説スタック初期化 */
  /* initialize hypothesis stack */
  start = bottom = NULL;
  stacknum = 0;
  /* 結果格納スタック初期化 */
  /* initialize result stack */
  r_stacksize = ncan;
  r_start = r_bottom = NULL;
  r_stacknum = 0;

  /* カウンタ初期化 */
  /* initialize counter */
  dwrk->popctr = 0;
  dwrk->genectr = 0;
  dwrk->pushctr = 0;
  dwrk->finishnum = 0;
  
#ifdef CM_SEARCH
  /* initialize local stack */
  cm_init(dwrk, winfo->num, jconf->annotate.cm_alpha
#ifdef CM_MULTIPLE_ALPHA
          , jconf->annotate.cm_alpha_num
#endif
          );
#endif
#ifdef SCAN_BEAM
  /* prepare and initialize score envelope */
  dwrk->framemaxscore = (LOGPROB *)mymalloc(sizeof(LOGPROB)*peseqlen);
  envl_init(dwrk, peseqlen);
#endif /* SCAN_BEAM */

  /* エンベロープ探索用の単語長別展開数カウンタを初期化 */
  /* initialize counters for envelope search */
  if (jconf->pass2.enveloped_bestfirst_width >= 0) wb_init(dwrk);

  if (jconf->graph.enabled) {
    wordgraph_init(r->wchmm);
  }

  /* 
   * 初期仮説(1単語からなる)を得, 文仮説スタックにいれる
   * get a set of initial words from LM function and push them as initial
   * hypotheses
   */
  /* the first words will be stored in nextword[] */
  if (r->lmtype == LM_PROB) {
    nwnum = ngram_firstwords(nextword, peseqlen, maxnwnum, r);
  } else if (r->lmtype == LM_DFA) {
    nwnum = dfa_firstwords(nextword, peseqlen, maxnwnum, r);
    /* 溢れたら、バッファを増やして再チャレンジ */
    /* If the number of nextwords can exceed the buffer size, expand the
       nextword data area */
    while (nwnum < 0) {
      nextword = nw_expand(nextword, &maxnwnum, &nwroot, winfo->num);
      nwnum = dfa_firstwords(nextword, peseqlen, maxnwnum, r);
    }
  }

  if (debug2_flag) {
    jlog("DEBUG: %d words in wordtrellis as first hypothesis\n", nwnum);
  }
  
  /* store them to stack */
  for (w = 0; w < nwnum; w++) {
    if (r->lmtype == LM_DFA) {
      /* limit word hypothesis */
      if (! (winfo->wton[nextword[w]->id] >= cate_bgn && winfo->wton[nextword[w]->id] < cate_bgn + cate_num)) {
        continue;
      }
    }
    /* generate new hypothesis */
    new = newnode(r);
    start_word(new, nextword[w], param, r);
    if (r->lmtype == LM_DFA) {
      if (new->score <= LOG_ZERO) { /* not on trellis */
        free_node(new);
        continue;
      }
    }
    dwrk->genectr++;
#ifdef CM_SEARCH
    /* store the local hypothesis to temporal stack */
    cm_store(dwrk, new);
#else 
    /* put to stack */
    if (put_to_stack(new, &start, &bottom, &stacknum, stacksize) != -1) {
      dwrk->current = new;
      //callback_exec(CALLBACK_DEBUG_PASS2_PUSH, r);
      if (jconf->graph.enabled) {
        new->prevgraph = NULL;
        new->lastcontext = NULL;
      }
      dwrk->pushctr++;
    }
#endif
  }
#ifdef CM_SEARCH
  /* compute score sum */
  cm_sum_score(dwrk
#ifdef CM_MULTIPLE_ALPHA
               , jconf->annotate.cm_alpha_bgn
               , jconf->annotate.cm_alpha_end
               , jconf->annotate.cm_alpha_step
#endif
               );

  /* compute CM and put the generated hypotheses to global stack */
  while ((new = cm_get_node(dwrk)) != NULL) {
    cm_set_score(dwrk, new
#ifdef CM_MULTIPLE_ALPHA
                 , jconf->annotate.cm_alpha_bgn
                 , jconf->annotate.cm_alpha_end
                 , jconf->annotate.cm_alpha_step
#endif
                 );
#ifdef CM_SEARCH_LIMIT
    if (new->cmscore[new->seqnum-1] < jconf->annotate.cm_cut_thres
#ifdef CM_SEARCH_LIMIT_AFTER
        && dwrk->finishnum > 0
#endif
        ) {
      free_node(new);
      continue;
    }
#endif /* CM_SEARCH_LIMIT */
    
    if (put_to_stack(new, &start, &bottom, &stacknum, stacksize) != -1) {
      dwrk->current = new;
      //callback_exec(CALLBACK_DEBUG_PASS2_PUSH, r);
      if (r->graphout) {
        new->prevgraph = NULL;
        new->lastcontext = NULL;
      }
      dwrk->pushctr++;
    }
  }
#endif

  if (debug2_flag) {
    jlog("DEBUG: %d pushed\n", dwrk->pushctr);
  }
  
  /********************/
  /* main search loop */
  /********************/

  for (;;) {

    /* if terminate signal has been received, cancel this input */
    /* 
     * if (recog->process_want_terminate) {
     *   jlog("DEBUG: process terminated by request\n");
     *   break;
     * }
     */
    
    /* 
     * 仮説スタックから最もスコアの高い仮説を取り出す
     * pop the top hypothesis from stack
     */
#ifdef DEBUG
    jlog("DEBUG: get one hypothesis\n");
#endif
    now = get_best_from_stack(&start,&stacknum);
    if (now == NULL) {  /* stack empty ---> 探索終了*/
      jlog("WARNING: %02d %s: hypothesis stack exhausted, terminate search now\n", r->config->id, r->config->name);
      jlog("STAT: %02d %s: %d sentences have been found\n", r->config->id, r->config->name, dwrk->finishnum);
      break;
    }
    /* (bogus score check) */
    if (now->score <= LOG_ZERO) {
      free_node(now);
      continue;
    }


    /* 単語グラフ用に pop 仮説の f スコアを一時保存 */
    if (r->graphout) {
      prev_score = now->score;
    }

    /* word envelope チェック */
    /* consult word envelope */
    if (jconf->pass2.enveloped_bestfirst_width >= 0) {
      if (!wb_ok(dwrk, now, jconf->pass2.enveloped_bestfirst_width)) {
        /* この仮説長における展開元仮説数の累計数は既に閾値を越えている. 
           そのため，この仮説は捨てる. */
        /* the number of popped hypotheses at the length already
           reaches its limit, so the current popped hypothesis should
           be discarded here with no expansion */
        if (debug2_flag) {
          jlog("DEBUG: popped but pruned by word envelope:");
          put_hypo_woutput(now, r->lm->winfo);
        }
        free_node(now);
        continue;
      }
    }
    
#ifdef CM_SEARCH_LIMIT_POP
    if (now->cmscore[now->seqnum-1] < jconf->annotate.cm_cut_thres_pop) {
      free_node(now);
      continue;
    }
#endif /* CM_SEARCH_LIMIT_POP */

    dwrk->popctr++;

    /* (for debug) 取り出した仮説とそのスコアを出力 */
    /*             output information of the popped hypothesis to stdout */
    if (debug2_flag) {
      jlog("DEBUG: --- pop %d:\n", dwrk->popctr);
      jlog("DEBUG:  "); put_hypo_woutput(now, r->lm->winfo);
      jlog("DEBUG:  "); put_hypo_wname(now, r->lm->winfo);
      jlog("DEBUG:  %d words, f=%f, g=%f\n", now->seqnum, now->score, now->g[now->bestt]);
      jlog("DEBUG:  last word on trellis: [%d-%d]\n", now->estimated_next_t + 1, now->bestt);
    }

    dwrk->current = now;
    //callback_exec(CALLBACK_DEBUG_PASS2_POP, r);

    if (r->graphout) {

#ifdef GRAPHOUT_DYNAMIC
      /* merge last word in popped hypo if possible */
      wtmp = wordgraph_check_merge(now->prevgraph, &wordgraph_root, now->seq[now->seqnum-1], &merged_p, jconf);
      if (wtmp != NULL) {               /* wtmp holds merged word */
        dynamic_merged_num++;

        lscore_prev = (now->prevgraph) ? now->prevgraph->lscore_tmp : 0.0;

        if (now->prevgraph != NULL) {
          if (now->prevgraph->saved) {
            j_internal_error("wchmm_fbs: already saved??\n");
          }
          wordgraph_free(now->prevgraph);
        }

        if (now->lastcontext != NULL
            && now->lastcontext != wtmp /* avoid self loop */
            ) {
          wordgraph_check_and_add_leftword(now->lastcontext, wtmp, lscore_prev);
#ifdef GRAPHOUT_SEARCH_CONSIDER_RIGHT
          if (merged_p) {
            if (wordgraph_check_and_add_rightword(wtmp, now->lastcontext, lscore_prev) == FALSE) {
              merged_p = TRUE;
            } else {
              merged_p = FALSE;
            }
          } else {
            wordgraph_check_and_add_rightword(wtmp, now->lastcontext, lscore_prev);
          }
#else
          wordgraph_check_and_add_rightword(wtmp, now->lastcontext, lscore_prev);
#endif    
        }
        
        now->prevgraph = wtmp;  /* change word to the merged one */

        /*printf("last word merged\n");*/
        /* previous still remains at memory here... (will be purged later) */
      } else {
        wordgraph_save(now->prevgraph, now->lastcontext, &wordgraph_root);
      }
#ifdef GRAPHOUT_SEARCH
      /* if recent hypotheses are included in the existing graph, terminate */
      if (merged_p && now->endflag == FALSE
#ifdef GRAPHOUT_SEARCH_DELAY_TERMINATION
          /* Do not apply search termination by graph merging
             until the first sentence candidate is found. */
          && (jconf->graph.graphout_search_delay == FALSE || dwrk->finishnum > 0)
#endif
          ) {
        terminate_search_num++;
        free_node(now);
        continue;
      }
#endif
#else  /* ~GRAPHOUT_DYNAMIC */
      /* always save */
      wordgraph_save(now->prevgraph, now->lastcontext, &wordgraph_root);
#endif /* ~GRAPHOUT_DYNAMIC */
    }

    /* 取り出した仮説のスコアを元に score envelope を更新 */
    /* update score envelope using the popped hypothesis */
    envl_update(dwrk, now, peseqlen);

    /* 
     * 取り出した仮説の受理フラグが既に立っていれば，
     * その仮説は探索終了とみなし，結果として出力して次のループへ. 
     *
     * If the popped hypothesis already reached to the end, 
     * we can treat it as a recognition result.
     */
#ifdef DEBUG
    VERMES("endflag check\n");
#endif
    
    if (now->endflag) {
      if (debug2_flag) {
        jlog("DEBUG:  This is a full sentence candidate\n");
      }
      /* quick, dirty hack */
      if (now->score == last_score) {
        free_node(now);
        continue;
      } else {
        last_score = now->score;
      }
      
      dwrk->finishnum++;
      if (debug2_flag) {
        jlog("DEBUG:  %d-th sentence found\n", dwrk->finishnum);
      }

        /* 一定数の仮説が得られたあとスコアでソートするため，
           一時的に別のスタックに格納しておく */
        /* store the result to result stack
           after search is finished, they will be re-ordered and output */
        put_to_stack(now, &r_start, &r_bottom, &r_stacknum, r_stacksize);
        /* 指定数の文仮説が得られたなら探索を終了する */
        /* finish search if specified number of results are found */
        if (dwrk->finishnum >= ncan) {
          break;
        } else {
          continue;
        }
      
    } /* end of now->endflag */

    
    /* 
     * 探索失敗を検出する. 
     * 仮説数が maxhypo 以上展開されたら, もうこれ以上は探索しない
     *
     * detecting search failure:
     * if the number of expanded hypotheses reaches maxhypo, giveup further search
     */
#ifdef DEBUG
    jlog("DEBUG: loop end check\n");
#endif
    if (dwrk->popctr >= maxhypo) {
      jlog("WARNING: %02d %s: num of popped hypotheses reached the limit (%d)\n", r->config->id, r->config->name, maxhypo);
      /* (for debug) 探索失敗時に、スタックに残った情報を吐き出す */
      /* (for debug) output all hypothesis remaining in the stack */
      if (debug2_flag) put_all_in_stack(&start, &stacknum, r->lm->winfo);
      free_node(now);
      break;                    /* end of search */
    }
    /* 仮説長が一定値を越えたとき，その仮説を破棄する */
    /* check hypothesis word length overflow */
    if (now->seqnum >= MAXSEQNUM) {
      jlog("ERROR: sentence length exceeded system limit ( > %d)\n", MAXSEQNUM);
      free_node(now);
      continue;
    }

#ifndef GRAPHOUT_PRECISE_BOUNDARY
    if (r->graphout) {
      /* if monophone (= no backscan), the tail g score should be kept here */
      /* else, updated tail g score will be computed in scan_word()  */
      if(!jconf->am.ccd_flag) {
        now->tail_g_score = now->g[now->bestt];
      }
    }
#endif

    /*
     * 前向きスコアを更新する： 最後の単語の部分の前向きスコアを計算する. 
     * update forward score: compute forward trellis for the last word
     */
#ifdef DEBUG
    jlog("DEBUG: scan_word\n");
#endif
    scan_word(now, param, r);
    if (now->score < LOG_ZERO) { /* another end-of-search detecter */
      jlog("WARNING: too low score, ignore: score=%f",now->score);
      put_hypo_woutput(now, r->lm->winfo);
      free_node(now);
      continue;
    }

    /* 
     * 取り出した仮説が文として受理可能であれば，
     * 受理フラグを立ててをスタックにいれ直しておく. 
     * (次に取り出されたら解となる)
     *
     * if the current popped hypothesis is acceptable, set endflag
     * and return it to stack: it will become the recognition result
     * when popped again.
     */
#ifdef DEBUG
    jlog("DEBUG: accept check\n");
#endif

    if (r->lmtype == LM_PROB) {
      acc = ngram_acceptable(now, r);
    } else if (r->lmtype == LM_DFA) {
      acc = dfa_acceptable(now, r);
    }
    if (acc && now->estimated_next_t <= 5) {
      new = newnode(r);
      /* new に now の中身をコピーして，最終的なスコアを計算 */
      /* copy content of 'now' to 'new', and compute the final score */
      last_next_word(now, new, param, r);
      if (debug2_flag) {
        jlog("DEBUG:  This is acceptable as a sentence candidate\n");
      }
      /* g[] が入力始端に達していなければ棄却 */
      /* reject this sentence candidate if g[] does not reach the end */
      if (new->score <= LOG_ZERO) {
        if (debug2_flag) {
          jlog("DEBUG:  But invalid because Viterbi pass does not reach the 0th frame\n");
        }
        free_node(new);
        free_node(now);
        continue;
      }
      /* 受理フラグを立てて入れ直す */
      /* set endflag and push again  */
      if (debug2_flag) {
        jlog("DEBUG  This hypo itself was pushed with final score=%f\n", new->score);
      }
      new->endflag = TRUE;
      if (put_to_stack(new, &start, &bottom, &stacknum, stacksize) != -1) {
        if (r->graphout) {
          if (new->score > LOG_ZERO) {
            new->lastcontext = now->prevgraph;
            new->prevgraph = wordgraph_assign(new->seq[new->seqnum-1],
                                              WORD_INVALID,
                                              (new->seqnum >= 2) ? new->seq[new->seqnum-2] : WORD_INVALID,
                                              0,
#ifdef GRAPHOUT_PRECISE_BOUNDARY
                                              /* wordend are shifted to the last */
#ifdef PASS2_STRICT_IWCD
                                              new->wordend_frame[0],
#else
                                              now->wordend_frame[0],
#endif
#else
                                              now->bestt,
#endif
                                              new->score,
                                              prev_score,
                                              now->g[0],
#ifdef GRAPHOUT_PRECISE_BOUNDARY
#ifdef PASS2_STRICT_IWCD
                                              new->wordend_gscore[0],
#else
                                              now->wordend_gscore[0],
#endif
#else
                                              now->tail_g_score,
#endif
                                              now->lscore,
#ifdef CM_SEARCH
                                              new->cmscore[new->seqnum-1],
#else
                                              LOG_ZERO,
#endif
                                              r
                                              );
          } else {
            new->lastcontext = now->lastcontext;
            new->prevgraph = now->prevgraph;
          }
        } /* put_to_stack() != -1 */
      } /* recog->graphout */
      /* この仮説はここで終わらずに, ここからさらに単語展開する */
      /* continue with the 'now' hypothesis, not terminate here */
    }
    
    /*
     * この仮説から，次単語集合を決定する. 
     * 次単語集合は, この仮説の推定始端フレーム周辺に存在した
     * 第１パスのトレリス単語集合. 
     *
     * N-gramの場合は各単語の n-gram 接続確率が含まれる. 
     * DFA の場合は, その中でさらに DFA 上で接続可能なもののみが返ってくる
     */
    /*
     * Determine next word set that can connect to this hypothesis.
     * They come from the trellis word that has been survived at near the
     * beginning of the last word.
     *
     * In N-gram mode, they also contain N-gram probabilities toward the
     * source hypothesis.  In DFA mode, the word set is further reduced
     * by the grammatical constraint
     */
#ifdef DEBUG
    jlog("DEBUG: get next words\n");
#endif
    if (r->lmtype == LM_PROB) {
      nwnum = ngram_nextwords(now, nextword, maxnwnum, r);
    } else if (r->lmtype == LM_DFA) {
      nwnum = dfa_nextwords(now, nextword, maxnwnum, r);
      /* nextword が溢れたら、バッファを増やして再チャレンジ */
      /* If the number of nextwords can exceed the buffer size, expand the
         nextword data area */
      while (nwnum < 0) {
        nextword = nw_expand(nextword, &maxnwnum, &nwroot, winfo->num);
        nwnum = dfa_nextwords(now, nextword, maxnwnum, r);
      }
    }
    if (debug2_flag) {
      jlog("DEBUG:  %d words extracted from wordtrellis\n", nwnum);
    }

    /* 
     * 仮説と次単語集合から新たな文仮説を生成し，スタックにいれる. 
     */
    /*
     * generate new hypotheses from 'now' and 'nextword', 
     * and push them to stack
     */
#ifdef DEBUG
    jlog("DEBUG: generate hypo\n");
#endif

    if (r->lmtype == LM_DFA) {
      now_noise_calced = FALSE; /* TRUE is noise-inserted score has been calculated */
    }
    i = dwrk->pushctr;          /* store old value */

#ifdef CM_SEARCH
    /* initialize local stack */
    cm_init(dwrk, winfo->num, jconf->annotate.cm_alpha
#ifdef CM_MULTIPLE_ALPHA
            , jconf->annotate.cm_alpha_num
#endif
            );
#endif

    /* for each nextword, generate a new hypothesis */
    for (w = 0; w < nwnum; w++) {
      if (r->lmtype == LM_DFA) {
        /* limit word hypothesis */
        if (! (winfo->wton[nextword[w]->id] >= cate_bgn && winfo->wton[nextword[w]->id] < cate_bgn + cate_num)) {
          continue;
        }
      }
      new = newnode(r);

      if (r->lmtype == LM_DFA) {

        if (nextword[w]->can_insert_sp == TRUE) {
          /* ノイズを挟んだトレリススコアを計算し，挟まない場合との最大値を取る */
          /* compute hypothesis score with noise inserted */
          
          if (now_noise_calced == FALSE) {
            /* now に sp をつけた仮説 now_noise を作り,そのスコアを計算 */
            /* generate temporal hypothesis 'now_noise' which has short-pause
               word after the original 'now' */
            fornoise.id = gdfa->sp_id;
            now_noise = newnode(r);
            cpy_node(now_noise, now);
#if 0
            now_noise_tmp = newnode(r);
            next_word(now, now_noise_tmp, &fornoise, param, r);
            scan_word(now_noise_tmp, param, r);
            for(t=0;t<peseqlen;t++) {
              now_noise->g[t] = max(now_noise_tmp->g[t], now->g[t]);
            }
            free_node(now_noise_tmp);
#else
            /* expand NOISE only if it exists in backward trellis */
            /* begin patch by kashima */
            if (jconf->pass2.looktrellis_flag) {
              if(!dfa_look_around(&fornoise, now, r)){
                free_node(now_noise);
                free_node(new);
                continue;
              }
            }
            /* end patch by kashima */
            
            /* now_nosie の スコア g[] を計算し，元の now の g[] と比較して
               高い方を採用 */
            /* compute trellis score g[], and adopt the maximum score
               for each frame compared with now->g[] */
            next_word(now, now_noise, &fornoise, param, r);
            scan_word(now_noise, param, r);
            for(t=0;t<peseqlen;t++) {
              now_noise->g[t] = max(now_noise->g[t], now->g[t]);
            }
            /* ノイズを挟んだ際を考慮したスコアを計算したので，
               ここで最後のノイズ単語を now_noise から消す */
            /* now that score has been computed considering pause insertion,
               we can delete the last noise word from now_noise here */
            now_noise->seqnum--;
#endif
            now_noise_calced = TRUE;
          }
          
          /* expand word only if it exists in backward trellis */
          /* begin patch by kashima */
          if (jconf->pass2.looktrellis_flag) {
            if(!dfa_look_around(nextword[w], now_noise, r)){
              free_node(new);
              continue;
            }
          }
          /* end patch by kashima */
          
          /* 新しい仮説' new' を 'now_noise' から生成 */
          /* generate a new hypothesis 'new' from 'now_noise' */
          next_word(now_noise, new, nextword[w], param, r);
          
        } else {
          
          /* expand word only if it exists in backward trellis */
          /* begin patch by kashima */
          if (jconf->pass2.looktrellis_flag) {
            if(!dfa_look_around(nextword[w], now, r)){
              free_node(new);
              continue;
            }
          }
          /* end patch by kashima */
          
          /* 新しい仮説' new' を 'now_noise' から生成 */
          /* generate a new hypothesis 'new' from 'now_noise' */
          next_word(now, new, nextword[w], param, r);
          
        }
      }

      if (r->lmtype == LM_PROB) {

        /* 新しい仮説' new' を 'now_noise' から生成
           N-gram の場合はノイズを特別扱いしない */
        /* generate a new hypothesis 'new' from 'now'.
           pause insertion is treated as same as normal words in N-gram mode. */
        next_word(now, new, nextword[w], param, r);

      }

      if (new->score <= LOG_ZERO) { /* not on trellis */
        free_node(new);
        continue;
      }
        
      dwrk->genectr++;

#ifdef CM_SEARCH
      /* store the local hypothesis to temporal stack */
      cm_store(dwrk, new);
#else 
      /* 生成した仮説 'new' をスタックに入れる */
      /* push the generated hypothesis 'new' to stack */

      /* stack overflow */
      if (can_put_to_stack(new, &bottom, &stacknum, stacksize) == -1) {
        free_node(new);
        continue;
      }
      
      if (r->graphout) {
        /* assign a word arc to the last fixed word */
        new->lastcontext = now->prevgraph;
        new->prevgraph = wordgraph_assign(new->seq[new->seqnum-2],
                                          new->seq[new->seqnum-1],
                                          (new->seqnum >= 3) ? new->seq[new->seqnum-3] : WORD_INVALID,
                                          new->bestt + 1,
#ifdef GRAPHOUT_PRECISE_BOUNDARY
#ifdef PASS2_STRICT_IWCD
                                          /* most up-to-date wordend_gscore is on new, because the last phone of 'now' will be computed at next_word() */
                                          new->wordend_frame[new->bestt],
#else
                                          now->wordend_frame[new->bestt],
#endif
#else
                                          now->bestt,
#endif
                                          new->score, prev_score,
#ifdef PASS2_STRICT_IWCD
                                          new->g[new->bestt] - new->lscore,
#else
                                          now->g[new->bestt+1],
#endif
#ifdef GRAPHOUT_PRECISE_BOUNDARY
#ifdef PASS2_STRICT_IWCD
                                          /* most up-to-date wordend_gscore is on new, because the last phone of 'now' will be computed at next_word() */
                                          new->wordend_gscore[new->bestt],
#else
                                          now->wordend_gscore[new->bestt],
#endif
#else
                                          now->tail_g_score,
#endif
                                          now->lscore,
#ifdef CM_SEARCH
                                          new->cmscore[new->seqnum-2],
#else
                                          LOG_ZERO,
#endif
                                          r
                                          );
      } /* recog->graphout */
      put_to_stack(new, &start, &bottom, &stacknum, stacksize);
      if (debug2_flag) {
        j = new->seq[new->seqnum-1];
        jlog("DEBUG:  %15s [%15s](id=%5d)(%f) [%d-%d] pushed\n",winfo->wname[j], winfo->woutput[j], j, new->score, new->estimated_next_t + 1, new->bestt);
      }
      dwrk->current = new;
      //callback_exec(CALLBACK_DEBUG_PASS2_PUSH, r);
      dwrk->pushctr++;
#endif
    } /* end of nextword loop */

#ifdef CM_SEARCH
    /* compute score sum */
    cm_sum_score(dwrk
#ifdef CM_MULTIPLE_ALPHA
                 , jconf->annotate.cm_alpha_bgn 
                 , jconf->annotate.cm_alpha_end
                 , jconf->annotate.cm_alpha_step
#endif
                 );
    /* compute CM and put the generated hypotheses to global stack */
    while ((new = cm_get_node(dwrk)) != NULL) {
      cm_set_score(dwrk, new
#ifdef CM_MULTIPLE_ALPHA
                   , jconf->annotate.cm_alpha_bgn
                   , jconf->annotate.cm_alpha_end
                   , jconf->annotate.cm_alpha_step
#endif
                   );
#ifdef CM_SEARCH_LIMIT
      if (new->cmscore[new->seqnum-1] < jconf->annotate.cm_cut_thres
#ifdef CM_SEARCH_LIMIT_AFTER
          && dwrk->finishnum > 0
#endif
          ) {
        free_node(new);
        continue;
      }
#endif /* CM_SEARCH_LIMIT */
      /*      j = new->seq[new->seqnum-1];
              printf("  %15s [%15s](id=%5d)(%f) [%d-%d] cm=%f\n",winfo->wname[j], winfo->woutput[j], j, new->score, new->estimated_next_t + 1, new->bestt, new->cmscore[new->seqnum-1]);*/

      /* stack overflow */
      if (can_put_to_stack(new, &bottom, &stacknum, stacksize) == -1) {
        free_node(new);
        continue;
      }

      if (r->graphout) {

        /* assign a word arc to the last fixed word */
        new->lastcontext = now->prevgraph;
        new->prevgraph = wordgraph_assign(new->seq[new->seqnum-2],
                                          new->seq[new->seqnum-1],
                                          (new->seqnum >= 3) ? new->seq[new->seqnum-3] : WORD_INVALID,
                                          new->bestt + 1,
#ifdef GRAPHOUT_PRECISE_BOUNDARY
#ifdef PASS2_STRICT_IWCD
                                          new->wordend_frame[new->bestt],
#else
                                          now->wordend_frame[new->bestt],
#endif
#else
                                          now->bestt,
#endif
                                          new->score, prev_score,
#ifdef PASS2_STRICT_IWCD
                                          new->g[new->bestt] - new->lscore,
#else
                                          now->g[new->bestt+1],
#endif
#ifdef GRAPHOUT_PRECISE_BOUNDARY
#ifdef PASS2_STRICT_IWCD
                                          new->wordend_gscore[new->bestt],
#else
                                          now->wordend_gscore[new->bestt],
#endif
#else
                                          now->tail_g_score,
#endif
                                          now->lscore,
#ifdef CM_SEARCH
                                          new->cmscore[new->seqnum-2],
#else
                                          LOG_ZERO,
#endif
                                          r
                                          );
      } /* recog->graphout */
      
      put_to_stack(new, &start, &bottom, &stacknum, stacksize);
      if (debug2_flag) {
        j = new->seq[new->seqnum-1];
        jlog("DEBUG:  %15s [%15s](id=%5d)(%f) [%d-%d] pushed\n",winfo->wname[j], winfo->woutput[j], j, new->score, new->estimated_next_t + 1, new->bestt);
      }
      dwrk->current = new;
      //callback_exec(CALLBACK_DEBUG_PASS2_PUSH, r);
      dwrk->pushctr++;
    }
#endif

    if (debug2_flag) {
      jlog("DEBUG: %d pushed\n",dwrk->pushctr-i);
    }
    if (r->lmtype == LM_DFA) {
      if (now_noise_calced == TRUE) free_node(now_noise);
    }
    
    /* 
     * 取り出した仮説を捨てる
     * free the source hypothesis
     */
    free_node(now);

  }
  /***************/
  /* End of Loop */
  /***************/

  /* output */
  if (dwrk->finishnum == 0) {           /* if search failed */

    /* finalize result when no hypothesis was obtained */
    if (verbose_flag) {
      if (r->config->sw.fallback_pass1_flag) {
        jlog("%02d %s: got no candidates, output 1st pass result as a final result\n", r->config->id, r->config->name);
      } else {
        jlog("WARNING: %02d %s: got no candidates, search failed\n", r->config->id, r->config->name);
      }
    }
    pass2_finalize_on_no_result(r, r->config->sw.fallback_pass1_flag);

  } else {                      /* if at least 1 candidate found */

    if (debug2_flag) {
      jlog("STAT: %02d %s: got %d candidates\n", r->config->id, r->config->name, dwrk->finishnum);
    }
      /* 結果はまだ出力されていないので，文候補用スタック内をソートして
         ここで出力する */
      /* As all of the found candidate are in result stack, we sort them
         and output them here  */
      if (debug2_flag) jlog("DEBUG: done\n");
      result_reorder_and_output(&r_start, &r_bottom, &r_stacknum, jconf->output.output_hypo_maxnum, r, param);

      r->result.status = J_RESULT_STATUS_SUCCESS;
      //callback_exec(CALLBACK_RESULT, r);
      //callback_exec(CALLBACK_EVENT_PASS2_END, r);
  }
  
  /* 各種カウンタを出力 */
  /* output counters */
  if (verbose_flag) {
    jlog("STAT: %02d %s: %d generated, %d pushed, %d nodes popped in %d\n",
         r->config->id, r->config->name,
         dwrk->genectr, dwrk->pushctr, dwrk->popctr, backtrellis->framelen);
    jlog_flush();
#ifdef GRAPHOUT_DYNAMIC
    if (r->graphout) {
      jlog("STAT: %02d %s: graph: %d merged", r->config->id, r->config->name, dynamic_merged_num);
#ifdef GRAPHOUT_SEARCH
      jlog("S, %d terminated", terminate_search_num);
#endif
      jlog(" in %d\n", dwrk->popctr);
    }
#endif
  }
    
  if (dwrk->finishnum > 0 && r->graphout) {
    if (verbose_flag) jlog("STAT: ------ wordgraph post-processing begin ------\n");
    /* garbage collection and word merging */
    /* words with no following word (except end of sentence) will be erased */
    wordgraph_purge_leaf_nodes(&wordgraph_root, r);
#ifdef GRAPHOUT_DEPTHCUT
    /* perform word graph depth cutting here */
    wordgraph_depth_cut(&wordgraph_root, r);
#endif

    /* if GRAPHOUT_PRECISE_BOUNDARY defined,
       propagate exact time boundary to the right context.
       words of different boundary will be duplicated here.
    */
    wordgraph_adjust_boundary(&wordgraph_root, r);

    if (jconf->graph.confnet) {
      /* CONFUSION NETWORK GENERATION */

      /* old merging functions should be skipped */

      /* finalize: sort and annotate ID */
      r->graph_totalwordnum = wordgraph_sort_and_annotate_id(&wordgraph_root, r);
      /* check coherence */
      wordgraph_check_coherence(wordgraph_root, r);
      /* compute graph CM by forward-backward processing */
      graph_forward_backward(wordgraph_root, r);
      if (verbose_flag) jlog("STAT: ------ wordgraph post-processing end ------\n");

      r->result.wg = wordgraph_root;

      /* 
       * if (jconf->graph.lattice) {
       *   callback_exec(CALLBACK_RESULT_GRAPH, r);
       * }
       */
      
      /* parse the graph to extract order relationship */
      graph_make_order(wordgraph_root, r);
      /* create confusion network */
      r->result.confnet = confnet_create(wordgraph_root, r);
      /* output confusion network */
      //callback_exec(CALLBACK_RESULT_CONFNET, r);
      /* free area for order relationship */
      graph_free_order(r);
      /* free confusion network clusters */
      //cn_free_all(&(r->result.confnet));

    } else if (jconf->graph.lattice) {
      /* WORD LATTICE POSTPROCESSING */

      /* merge words with the same time and same score */
      wordgraph_compaction_thesame(&wordgraph_root);
      /* merge words with the same time (skip if "-graphrange -1") */
      wordgraph_compaction_exacttime(&wordgraph_root, r);
      /* merge words of near time (skip if "-graphrange" value <= 0 */
      wordgraph_compaction_neighbor(&wordgraph_root, r);
      /* finalize: sort and annotate ID */
      r->graph_totalwordnum = wordgraph_sort_and_annotate_id(&wordgraph_root, r);
      /* check coherence */
      wordgraph_check_coherence(wordgraph_root, r);
      /* compute graph CM by forward-backward processing */
      graph_forward_backward(wordgraph_root, r);
      if (verbose_flag) jlog("STAT: ------ wordgraph post-processing end ------\n");
      /* output graph */
      r->result.wg = wordgraph_root;
      //callback_exec(CALLBACK_RESULT_GRAPH, r);

    } else {
      j_internal_error("InternalError: graph generation specified but no output format specified?\n");
    }

    /* clear all wordgraph */
    //wordgraph_clean(&(r->result.wg));
  } /* r->graphout */

  
  /* 終了処理 */
  /* finalize */
  nw_free(nextword, nwroot);
  free_all_nodes(start);
  free_wordtrellis(dwrk);
#ifdef SCAN_BEAM
  free(dwrk->framemaxscore);
#endif
  //result_sentence_free(r);
  clear_stocker(dwrk);
}

void
wchmm_fbs_prepare(RecogProcess *r)
{
  StackDecode *dwrk;
  dwrk = &(r->pass2);
  
  /* N-gram 用ワークエリアを確保 */
  /* malloc work area for N-gram */
  if (r->lmtype == LM_PROB && r->lm->ngram) {
    dwrk->cnword = (WORD_ID *)mymalloc(sizeof(WORD_ID) * r->lm->ngram->n);
    dwrk->cnwordrev = (WORD_ID *)mymalloc(sizeof(WORD_ID) * r->lm->ngram->n);
  } else {
    dwrk->cnword = dwrk->cnwordrev = NULL;
  }
  dwrk->stocker_root = NULL;
#ifdef CONFIDENVE_MEASURE
#ifdef CM_MULTIPLE_ALPHA
  dwrk->cmsumlist = NULL;
#endif
#ifdef CM_NBEST;
  dwrk->sentcm = NULL;
  dwrk->wordcm = NULL;
#endif
#endif
}

void
wchmm_fbs_free(RecogProcess *r)
{
  StackDecode *dwrk;
  dwrk = &(r->pass2);

  if (r->lmtype == LM_PROB && r->lm->ngram) {
    free(dwrk->cnword);
    free(dwrk->cnwordrev);
    dwrk->cnword = dwrk->cnwordrev = NULL;
  }

#ifdef CONFIDENVE_MEASURE
#ifdef CM_MULTIPLE_ALPHA
  if (dwrk->cmsumlist) {
    free(dwrk->cmsumlist);
    dwrk->cmsumlist = NULL;
  }
#endif
#ifdef CM_NBEST;
  if (dwrk->sentcm) {
    free(dwrk->sentcm);
    dwrk->sentcm = NULL;
  }
  if (dwrk->wordcm) {
    free(dwrk->wordcm);
    dwrk->wordcm = NULL;
  }
#endif
#endif
}

/* end of file */