libjulius/src/search_bestfirst_main.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>

/* 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(sentcm, sizeof(LOGPROB)*stacknum);
    sd->sentnum = stacknum;
  }
  if (sd->wordcm == NULL) {
    sd->wordcm = (LOGPROB *)mymalloc(sizeof(LOGPROB) * 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<winfo->num;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) > 1) {
      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);
    /* do forced alignment if needed */
    if (r->config->annotate.align_result_word_flag) word_rev_align(now->seq, now->seqnum, param, &(r->result.sent[r->result.sentnum-1]), r);
    if (r->config->annotate.align_result_phoneme_flag) phoneme_rev_align(now->seq, now->seqnum, param, &(r->result.sent[r->result.sentnum-1]), r);
    if (r->config->annotate.align_result_state_flag) state_rev_align(now->seq, now->seqnum, param, &(r->result.sent[r->result.sentnum-1]), r);

    free_node(now);
  }
  r->result.status = J_RESULT_STATUS_SUCCESS;
  /* free the rest */
  if (now != NULL) free_node(now);
  free_all_nodes(*r_start);
}  


/**********************************************************************/
/********* 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) */
  static int r_stacksize;
  static int r_stacknum;
  static NODE *r_start = NULL;
  static NODE *r_bottom = NULL;

  /* ¥ï¡¼¥¯¥¨¥ê¥¢ */
  /* work area */
  static 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;
  static JCONF_SEARCH *jconf;
  static WORD_INFO *winfo;
  static NGRAM_INFO *ngram;
  static DFA_INFO *gdfa;
  static BACKTRELLIS *backtrellis;
  static 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 */

  /* prepare result storage */
  result_sentence_malloc(r, jconf->output.output_hypo_maxnum);

  /* ¥¨¥ó¥Ù¥í¡¼¥×õº÷ÍѤÎñ¸ìĹÊÌŸ³«¿ô¥«¥¦¥ó¥¿¤ò½é´ü²½ */
  /* 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 */
  /* õº÷¼ºÇԤǰì¤Ä¤â¸õÊ䤬ÆÀ¤é¤ì¤Ê¤±¤ì¤Ð¡¤Âè1¥Ñ¥¹¤Î·ë²Ì¤ò¤½¤Î¤Þ¤Þ½ÐÎϤ¹¤ë */
  /* If search failed and no candidate obtained in this pass, output
     the result of the previous 1st pass as a final result. */
  if (dwrk->finishnum == 0) {           /* if search failed */
    if (verbose_flag) {
      jlog("WARNING: %02d %s: got no candidates, output 1st pass result as a final result\n", r->config->id, r->config->name);
    }
    /* make 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);
    }
    /* do forced alignment if needed */
    if (jconf->annotate.align_result_word_flag) word_rev_align(now->seq, now->seqnum, param, &(r->result.pass1), r);
    if (jconf->annotate.align_result_phoneme_flag) phoneme_rev_align(now->seq, now->seqnum, param, &(r->result.pass1), r);
    if (jconf->annotate.align_result_state_flag) state_rev_align(now->seq, now->seqnum, param, &(r->result.pass1), r);

    /* output it */
    r->result.status = J_RESULT_STATUS_FAIL;
    //callback_exec(CALLBACK_RESULT, r);

    free_node(now);

  } 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);
      //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();
      /* 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();
#ifdef SCAN_BEAM
  free(dwrk->framemaxscore);
#endif
  //result_sentence_free(r);
  clear_stocker(dwrk);
}

/* end of file */

---