julius/search_bestfirst_main.c

Go to the documentation of this file.

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

#include <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);
static void free_all_nodes(NODE *node);
static void put_hypo_woutput(NODE *hypo);
static void put_hypo_wname(NODE *hypo);

/**********************************************************************/
/********** ¼¡Ã±¸ì³ÊǼÎΰè¤Î³ä¤êÅö¤Æ          *************************/
/********** allocate memory for nextword data *************************/
/**********************************************************************/

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

  /* the initial maximum number of nextwords is the size of vocabulary */
  max = winfo->num;
  
  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);
}

#ifdef USE_DFA

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

  nwmaxlen = *maxlen + winfo->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;
}
#endif


/**********************************************************************/
/********** ²¾À⥹¥¿¥Ã¥¯¤ÎÁàºî         ********************************/
/********** Hypothesis stack operation ********************************/
/**********************************************************************/

/* ʸ²¾À⥹¥¿¥Ã¥¯¤Ï double linked list ¤Ç¤¢¤ë¡¥¤Þ¤¿¾ï¤Ë¥¹¥³¥¢½ç¤¬Êݤ¿¤ì¤ë */
/* The hypothesis stack is double-linked list, and holds entries in score sorted order */

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)
{
  NODE *ntmp;
  
  j_printf("stack remains::\n");
  while ((ntmp = get_best_from_stack(start, stacknum)) != NULL) {
    j_printf("%3d: s=%f ",*stacknum, ntmp->score);
    put_hypo_woutput(ntmp);
    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 ****************************************/
/**********************************************************************/
/* scoring using multiple cmalpha value will be enabled by CM_MULTIPLE_ALPHA */

#ifdef CM_MULTIPLE_ALPHA
static LOGPROB *cmsumlist = NULL; 
#endif


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

static LOGPROB cm_tmpbestscore; 
#ifndef CM_MULTIPLE_ALPHA
static LOGPROB cm_tmpsum;       
#endif

/* local stack for CM */
static int l_stacksize;         
static int l_stacknum;          
static NODE *l_start = NULL;    
static NODE *l_bottom = NULL;   

static void
cm_init(WORD_INFO *winfo)
{
  l_stacksize = winfo->num;
  l_start = l_bottom = NULL;
  l_stacknum = 0;
#ifdef CM_MULTIPLE_ALPHA
  if (cmsumlist == NULL) {      /* allocate if not yet */
    cmsumlist = (LOGPROB *)mymalloc(sizeof(LOGPROB) * cm_alpha_num);
  }
#endif    
}

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

static void
cm_sum_score()
{
  NODE *node;
  LOGPROB sum;
#ifdef CM_MULTIPLE_ALPHA
  LOGPROB cm_alpha;
  int j;
#endif

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

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

#ifdef CM_MULTIPLE_ALPHA
  }
#endif
}

/* compute CM scores of the new word in the local stack from the sum above */
static void
cm_set_score(NODE *node)
{
#ifdef CM_MULTIPLE_ALPHA
  int j;
  LOGPROB cm_alpha;
#endif

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

static NODE *
cm_get_node()
{
  return(get_best_from_stack(&l_start, &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) ****/
/*****************************************************************/

/* CM of each word is calculated after all search had finished */

static LOGPROB *sentcm = NULL;  
static LOGPROB *wordcm = NULL;  
static int sentnum;             

static void
cm_compute_from_nbest(NODE *start, int stacknum)
{
  NODE *node;
  LOGPROB bestscore, sum, s;
  WORD_ID w;
  int i;
#ifdef CM_MULTIPLE_ALPHA
  LOGPROB cm_alpha;
  int j;
#endif

  /* prepare buffer */
#ifdef CM_MULTIPLE_ALPHA
  if (cmsumlist == NULL) {
    cmsumlist = (LOGPROB *)mymalloc(sizeof(LOGPROB) * cm_alpha_num);
  }
#endif    
  if (sentcm == NULL) {         /* not allocated yet */
    sentcm = (LOGPROB *)mymalloc(sizeof(LOGPROB)*stacknum);
    sentnum = stacknum;
  } else if (sentnum < stacknum) { /* need expanded */
    sentcm = (LOGPROB *)myrealloc(sentcm, sizeof(LOGPROB)*stacknum);
    sentnum = stacknum;
  }
  if (wordcm == NULL) {
    wordcm = (LOGPROB *)mymalloc(sizeof(LOGPROB) * winfo->num);
  }
#ifdef CM_MULTIPLE_ALPHA
  for (j = 0, cm_alpha = cm_alpha_bgn; cm_alpha <= cm_alpha_end; cm_alpha += cm_alpha_step) {
#endif
    /* clear whole word cm buffer */
    for(w=0;w<winfo->num;w++) {
      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) {
      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++) {
        wordcm[node->seq[w]] += 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] = wordcm[node->seq[w]];
#else   
        node->cmscore[w] = 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 int hypo_len_count[MAXSEQNUM+1]; 
static int maximum_filled_length; 

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

static boolean
wb_ok(NODE *now)
{
  if (now->seqnum <= maximum_filled_length) {
    /* word expansion is not allowed because a word expansion count
       at deeper level has already reached the limit */
    if (debug2_flag) {
      j_printf("popped but pruned by word envelope: ");
      put_hypo_woutput(now);
    }
    return FALSE;
  } else {
    /* word expansion is possible.  Increment the word expansion count
       of the given depth */
    hypo_len_count[now->seqnum]++;
    if (hypo_len_count[now->seqnum] > enveloped_bestfirst_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 (maximum_filled_length < now->seqnum) 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().
 *
 */

/* the score envelope is kept in framemaxscore[0..framelen-1] */

static void
envl_init(int framenum)
{
  int i;
  for(i=0;i<framenum;i++) framemaxscore[i] = LOG_ZERO;
}

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


#ifdef USE_DFA

static NEXTWORD fornoise;
#endif


#ifdef SP_BREAK_CURRENT_FRAME
/**********************************************************************/
/********** Short pause segmentation **********************************/
/**********************************************************************/

void
sp_segment_set_last_nword(NODE *hypo)
{
  int i;
  WORD_ID w;
  for(i=0;i<hypo->seqnum;i++) {
    w = hypo->seq[i];
    if (w != sp_break_last_word
       && !is_sil(w, winfo, hmminfo)
       && !winfo->is_transparent[w]
       ) {
      sp_break_last_nword = w;
      break;
    }
  }
#ifdef SP_BREAK_DEBUG
  printf("sp_break_last_nword=%d[%s]\n", sp_break_last_nword, winfo->woutput[sp_break_last_nword]);
#endif
}
#endif


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

/* Ä̾ï¤Î½ÐÎÏ´Ø¿ô¤Ï result_*.c ¤Ë¤¢¤ë */
/* normal output functions are in result_*.c */

static HTK_Param *tparam;       

/* output word sequence of a hypothesis */
static void
put_hypo_woutput(NODE *hypo)
{
  int i,w;

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

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

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

/**********************************************************************/
/******** 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, WORD_INFO *winfo)
{
  NODE *now;
  int num;

#ifdef CM_NBEST 
  /* compute CM from the N-best sentence candidates */
  cm_compute_from_nbest(*r_start, *r_stacknum);
#endif
  num = 0;
  result_pass2_begin();
  while ((now = get_best_from_stack(r_start,r_stacknum)) != NULL && num < ncan) {
    num++;
    /* output result */
    result_pass2(now, num, winfo);
#ifdef VISUALIZE
    visual2_best(now, winfo);
#endif
#ifdef SP_BREAK_CURRENT_FRAME
    /* set the last context-aware word for next recognition */
    if (sp_break_last_nword_allow_override && num == 1) sp_segment_set_last_nword(now);
#endif
    /* do forced alignment if needed */
    if (align_result_word_flag) word_rev_align(now->seq, now->seqnum, tparam);
    if (align_result_phoneme_flag) phoneme_rev_align(now->seq, now->seqnum, tparam);
    if (align_result_state_flag) state_rev_align(now->seq, now->seqnum, tparam);
    free_node(now);
  }
  result_pass2_end();
  /* free the rest */
  if (now != NULL) free_node(now);
  free_all_nodes(*r_start);
}  


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

/* subfunctions called by this main function:
     for word prediction: ngram_decode.c or dfa_decode.c
     for hypothesis expansion and forward viterbi: search_bestfirst_v{1,2}.c
                                  (v1: for efficiency   v2: for accuracy)
*/

void
wchmm_fbs(HTK_Param *param, BACKTRELLIS *backtrellis, LOGPROB backmax, int stacksize, int ncan, int maxhypo, 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 = ncan;
  int r_stacknum;
  NODE *r_start = NULL;
  NODE *r_bottom = NULL;

  /* ¼ï¡¹¤Î¥«¥¦¥ó¥¿¡¼ */
  /* monitoring counters */
  int popctr = 0;               /* num of popped hypotheses from stack */
  int genectr = 0;              /* num of generated hypotheses */
  int pushctr = 0;              /* num of hypotheses actually pushed to stack */
  int finishnum = 0;            /* num of found sentence hypothesis */

  /* ¥ï¡¼¥¯¥¨¥ê¥¢ */
  /* work area */
  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. */
#ifdef USE_DFA
  NODE *now_noise;             /* for inserting/deleting noise word */
  boolean now_noise_calced;
  int t;
#endif
  int w,i,j;
  LOGPROB last_score = LOG_ZERO;
#ifdef GRAPHOUT
  LOGPROB prev_score;
  WordGraph *wordgraph_root = NULL;
  boolean merged_p;
#ifdef GRAPHOUT_DYNAMIC
  int dynamic_merged_num = 0;
  WordGraph *wtmp;
#endif
#ifdef GRAPHOUT_SEARCH
  int terminate_search_num = 0;
#endif
#endif

  /* copy parameter pointer beforehand for forced alignment */
  if (align_result_word_flag || align_result_phoneme_flag || align_result_state_flag) tparam = param;

#ifdef USE_DFA
  if (debug2_flag) j_printf("limiting category: %d-%d\n", cate_bgn, cate_bgn + cate_num-1);
#endif

  /*
   * ½é´ü²½
   * Initialize
   */
  peseqlen = backtrellis->framelen; /* (just for quick access) */
  /* ͽ¬ñ¸ì³ÊǼÎΰè¤ò³ÎÊÝ */
  /* malloc area for word prediction */
  nextword = nw_malloc(&maxnwnum, &nwroot);
  /* Á°¸þ¤­¥¹¥³¥¢·×»»ÍѤÎÎΰè¤ò³ÎÊÝ */
  /* malloc are for forward viterbi (scan_word()) */
  malloc_wordtrellis();         /* scan_wordÍÑÎΰè */
  /* ²¾À⥹¥¿¥Ã¥¯½é´ü²½ */
  /* initialize hypothesis stack */
  start = bottom = NULL;
  stacknum = 0;
  /* ·ë²Ì³ÊǼ¥¹¥¿¥Ã¥¯½é´ü²½ */
  /* initialize result stack */
  if (result_reorder_flag) {
    r_start = r_bottom = NULL;
    r_stacknum = 0;
  }
  
#ifdef CM_SEARCH
  /* initialize local stack */
  cm_init(winfo);
#endif
#ifdef SCAN_BEAM
  /* prepare and initialize score envelope */
  framemaxscore = (LOGPROB *)mymalloc(sizeof(LOGPROB)*peseqlen);
  envl_init(peseqlen);
#endif /* SCAN_BEAM */
  
  /* ¥¨¥ó¥Ù¥í¡¼¥×õº÷ÍѤÎñ¸ìĹÊÌŸ³«¿ô¥«¥¦¥ó¥¿¤ò½é´ü²½ */
  /* initialize counters for envelope search */
  if (enveloped_bestfirst_width >= 0) wb_init();

  if (verbose_flag) j_printf("samplenum=%d\n", peseqlen);
  if (result_reorder_flag) {
    if (debug2_flag) VERMES("getting %d candidates...\n",ncan);
  }

#ifdef VISUALIZE
  visual2_init(maxhypo);
#endif

  /* 
   * ½é´ü²¾Àâ(1ñ¸ì¤«¤é¤Ê¤ë)¤òÆÀ, ʸ²¾À⥹¥¿¥Ã¥¯¤Ë¤¤¤ì¤ë
   * get a set of initial words from LM function and push them as initial
   * hypotheses
   */
  /* the first words will be stored in nextword[] */
#ifdef USE_NGRAM
  nwnum = ngram_firstwords(nextword, peseqlen, maxnwnum, winfo, backtrellis);
#else  /* USE_DFA */
  nwnum = dfa_firstwords(nextword, peseqlen, maxnwnum, dfa);
  /* °î¤ì¤¿¤é¡¢¥Ð¥Ã¥Õ¥¡¤òÁý¤ä¤·¤ÆºÆ¥Á¥ã¥ì¥ó¥¸ */
  /* If the number of nextwords can exceed the buffer size, expand the
     nextword data area */
  while (nwnum < 0) {
    nextword = nw_expand(nextword, &maxnwnum, &nwroot);
    nwnum = dfa_firstwords(nextword, peseqlen, maxnwnum, dfa);
  }
#endif

  if (debug2_flag) {
    j_printf("%d words in wordtrellis as first hypothesis\n", nwnum);
  }
  
  /* store them to stack */
  for (w = 0; w < nwnum; w++) {
#ifdef USE_DFA
    /* limit word hypothesis */
    if (! (winfo->wton[nextword[w]->id] >= cate_bgn && winfo->wton[nextword[w]->id] < cate_bgn + cate_num)) {
      continue;
    }
#endif
    /* generate new hypothesis */
    new = newnode();
    start_word(new,nextword[w],param,backtrellis);
#ifdef USE_DFA
    if (new->score <= LOG_ZERO) { /* not on trellis */
      free_node(new);
      continue;
    }
#endif
    genectr++;
#ifdef CM_SEARCH
    /* store the local hypothesis to temporal stack */
    cm_store(new);
#else 
    /* put to stack */
    if (put_to_stack(new, &start, &bottom, &stacknum, stacksize) != -1) {
#ifdef VISUALIZE
      visual2_next_word(new, NULL, popctr);
#endif
#ifdef GRAPHOUT
      new->prevgraph = NULL;
      new->lastcontext = NULL;
#endif
      pushctr++;
    }
#endif
  }
#ifdef CM_SEARCH
  /* compute score sum */
  cm_sum_score();
  /* compute CM and put the generated hypotheses to global stack */
  while ((new = cm_get_node()) != NULL) {
    cm_set_score(new);
#ifdef CM_SEARCH_LIMIT
    if (new->cmscore[new->seqnum-1] < cm_cut_thres
#ifdef CM_SEARCH_LIMIT_AFTER
        && finishnum > 0
#endif
        ) {
      free_node(new);
      continue;
    }
#endif /* CM_SEARCH_LIMIT */
    
    if (put_to_stack(new, &start, &bottom, &stacknum, stacksize) != -1) {
#ifdef VISUALIZE
      visual2_next_word(new, NULL, popctr);
#endif
#ifdef GRAPHOUT
      new->prevgraph = NULL;
      new->lastcontext = NULL;
#endif
      pushctr++;
    }
  }
#endif

  if (debug2_flag) {
    j_printf("%d pushed\n", pushctr);
  }
  
  /********************/
  /* main search loop */
  /********************/

  for (;;) {

    if (module_mode) {
      /* if terminate signal has been received, cancel this input */
      if (module_wants_terminate()) {
        j_printf("terminated\n");
        break;
      }
    }
    
    /* 
     * ²¾À⥹¥¿¥Ã¥¯¤«¤éºÇ¤â¥¹¥³¥¢¤Î¹â¤¤²¾Àâ¤ò¼è¤ê½Ð¤¹
     * pop the top hypothesis from stack
     */
#ifdef DEBUG
    VERMES("get one hypothesis\n");
#endif
    now = get_best_from_stack(&start,&stacknum);
    if (now == NULL) {  /* stack empty ---> õº÷½ªÎ»*/
      j_printf("stack empty, search terminate now\n");
      j_printf("%d sentences have found\n", finishnum);
      break;
    }
    /* (bogus score check) */
    if (now->score <= LOG_ZERO) {
      free_node(now);
      continue;
    }

#ifdef GRAPHOUT
    /* ñ¸ì¥°¥é¥ÕÍÑ¤Ë pop ²¾Àâ¤Î f ¥¹¥³¥¢¤ò°ì»þÊݸ */
    prev_score = now->score;
#endif

    /* word envelope ¥Á¥§¥Ã¥¯ */
    /* consult word envelope */
    if (enveloped_bestfirst_width >= 0) {
      if (!wb_ok(now)) {
        /* ¤³¤Î²¾ÀâŤˤª¤±¤ëŸ³«¸µ²¾Àâ¿ô¤ÎÎ߷׿ô¤Ï´û¤ËïçÃͤò±Û¤¨¤Æ¤¤¤ë¡¥
           ¤½¤Î¤¿¤á¡¤¤³¤Î²¾Àâ¤Ï¼Î¤Æ¤ë¡¥*/
        /* the number of popped hypotheses at the length already
           reaches its limit, so the current popped hypothesis should
           be discarded here with no expansion */
        free_node(now);
        continue;
      }
    }
    
#ifdef CM_SEARCH_LIMIT_POP
    if (now->cmscore[now->seqnum-1] < cm_cut_thres_pop) {
      free_node(now);
      continue;
    }
#endif /* CM_SEARCH_LIMIT_POP */

    popctr++;

    /* (for debug) ¼è¤ê½Ð¤·¤¿²¾Àâ¤È¤½¤Î¥¹¥³¥¢¤ò½ÐÎÏ */
    /*             output information of the popped hypothesis to stdout */
    if (debug2_flag) {
      j_printf("--- pop %d:\n", popctr);
      j_printf("  "); put_hypo_woutput(now);
      j_printf("  "); put_hypo_wname(now);
      j_printf("  %d words, f=%f, g=%f\n", now->seqnum, now->score, now->g[now->bestt]);
      j_printf("  last word on trellis: [%d-%d]\n", now->estimated_next_t + 1, now->bestt);
    }

#ifdef VISUALIZE
    visual2_popped(now, popctr);
#endif

#ifdef 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);
    if (wtmp != NULL) {         /* wtmp holds merged word */
      dynamic_merged_num++;
      if (now->prevgraph != NULL) {
        if (now->prevgraph->saved) {
          j_error("ERROR: already saved??\n");
        }
        wordgraph_free(now->prevgraph);
      }
      now->prevgraph = wtmp;    /* change word to the merged one */

      if (now->lastcontext != NULL
          && now->lastcontext != now->prevgraph /* avoid self loop */
          ) {
        wordgraph_check_and_add_leftword(now->lastcontext, now->prevgraph);
#ifdef GRAPHOUT_SEARCH_CONSIDER_RIGHT
        if (merged_p) {
          if (wordgraph_check_and_add_rightword(now->prevgraph, now->lastcontext) == FALSE) {
            merged_p = TRUE;
          } else {
            merged_p = FALSE;
          }
        } else {
          wordgraph_check_and_add_rightword(now->prevgraph, now->lastcontext);
        }
#else
        wordgraph_check_and_add_rightword(now->prevgraph, now->lastcontext);
#endif    
      }
      /*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. */
        && (graphout_search_delay == FALSE || 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 */
#endif /* GRAPHOUT */

    /* ¼è¤ê½Ð¤·¤¿²¾Àâ¤Î¥¹¥³¥¢¤ò¸µ¤Ë score envelope ¤ò¹¹¿· */
    /* update score envelope using the popped hypothesis */
    envl_update(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) {
        j_printf("  This is a final sentence candidate\n");
      }
      /* quick, dirty hack */
      if (now->score == last_score) {
        free_node(now);
        continue;
      } else {
        last_score = now->score;
      }
      
      finishnum++;
      if (debug2_flag) {
        j_printf("  %d-th sentence found\n", finishnum);
      }

      if (result_reorder_flag) {
        /* °ìÄê¿ô¤Î²¾À⤬ÆÀ¤é¤ì¤¿¤¢¤È¥¹¥³¥¢¤Ç¥½¡¼¥È¤¹¤ë¤¿¤á¡¤
           °ì»þŪ¤ËÊ̤Υ¹¥¿¥Ã¥¯¤Ë³ÊǼ¤·¤Æ¤ª¤¯ */
        /* 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 (finishnum >= ncan) {
          if (debug2_flag) VERMES("%d\n",finishnum);
          break;
        } else {
          if (debug2_flag) VERMES("%d..", finishnum);
          continue;
        }
      } else {                  /* result_reorder ¤Ç¤Ê¤¤¾ì¹ç¤Ï */
        /* ·ë²Ì¤Ï¸«¤Ä¤«¤ê¼¡Â褹¤°¤Ë½ÐÎÏ */
        /* result are directly output as soon as found */
        if (finishnum == 1) result_pass2_begin(); /* first time */
        result_pass2(now, finishnum, winfo);
#ifdef VISUALIZE
        visual2_best(now, winfo);
#endif
#ifdef SP_BREAK_CURRENT_FRAME
        /* ¥·¥ç¡¼¥È¥Ý¡¼¥º¥»¥°¥á¥ó¥Æ¡¼¥·¥ç¥ó»þ¤Ï¼¡¤Î¥»¥°¥á¥ó¥Èǧ¼±³«»Ï»þ¤Ë
           ñ¸ìÍúÎò¤òÅÁȤµ¤»¤ë */
        /* set the last context-aware word for next recognition */
        if (sp_break_last_nword_allow_override && finishnum == 1) sp_segment_set_last_nword(now);
#endif
        /* ɬÍפǤ¢¤ì¤Ð, ǧ¼±·ë²Ì¤òÍѤ¤¤ÆÆþÎϤΥ»¥°¥á¥ó¥Æ¡¼¥·¥ç¥ó¤ò¹Ô¤Ê¤¦ */
        /* do forced alignment with the result if needed */
        if (align_result_word_flag) word_rev_align(now->seq, now->seqnum, tparam);
        if (align_result_phoneme_flag) phoneme_rev_align(now->seq, now->seqnum, tparam);
        if (align_result_state_flag) state_rev_align(now->seq, now->seqnum, tparam);
        /* ²¾Àâ¤ò²òÊü¤·¤Æ¼¡¤Î²¾Àâ¤Ø */
        /* free the hypothesis and continue to next */
        free_node(now);
        /* ¤³¤ì¤Ç»ØÄê¿ô¤Îʸ²¾À⤬ÆÀ¤é¤ì¤¿¤Ê¤é, ¤³¤³¤Çõº÷¤ò½ªÎ»¤¹¤ë */
        /* finish search if specified number of results are found */
        if (finishnum >= ncan) {
          result_pass2_end();
          break;                /* end of search */
        }
        else continue;
      }
      
    } /* end of now->endflag */

    
    /* 
     * õº÷¼ºÇÔ¤ò¸¡½Ð¤¹¤ë¡¥
     * ²¾Àâ¿ô¤¬ maxhypo °Ê¾åŸ³«¤µ¤ì¤¿¤é, ¤â¤¦¤³¤ì°Ê¾å¤Ïõº÷¤·¤Ê¤¤
     *
     * detecting search failure:
     * if the number of expanded hypotheses reaches maxhypo, giveup further search
     */
#ifdef DEBUG
    VERMES("loop end check\n");
#endif
    if (popctr >= maxhypo) {
      j_printf("num of hypotheses overflow\n");
      /* (for debug) õº÷¼ºÇÔ»þ¤Ë¡¢¥¹¥¿¥Ã¥¯¤Ë»Ä¤Ã¤¿¾ðÊó¤òÅǤ­½Ð¤¹ */
      /* (for debug) output all hypothesis remaining in the stack */
      if (debug2_flag) put_all_in_stack(&start, &stacknum);
      free_node(now);
      break;                    /* end of search */
    }
    /* ²¾À⍬°ìÄêÃͤò±Û¤¨¤¿¤È¤­¡¤¤½¤Î²¾Àâ¤òÇË´þ¤¹¤ë */
    /* check hypothesis word length overflow */
    if (now->seqnum >= MAXSEQNUM) {
      j_printerr("sentence length exceeded ( > %d)\n",MAXSEQNUM);
      free_node(now);
      continue;
    }

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

    /*
     * Á°¸þ¤­¥¹¥³¥¢¤ò¹¹¿·¤¹¤ë¡§ ºÇ¸å¤Îñ¸ì¤ÎÉôʬ¤ÎÁ°¸þ¤­¥¹¥³¥¢¤ò·×»»¤¹¤ë¡¥
     * update forward score: compute forward trellis for the last word
     */
#ifdef DEBUG
    VERMES("scan_word\n");
#endif
    scan_word(now, param);
    if (now->score < backmax + LOG_ZERO) { /* another end-of-search detecter */
      j_printf("now->score = %f?\n",now->score);
      put_hypo_woutput(now);
      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
    VERMES("accept check\n");
#endif
    if (
#ifdef USE_NGRAM
        ngram_acceptable(now, winfo)
#else  /* USE_DFA */
        dfa_acceptable(now, dfa)
#endif
        && now->estimated_next_t <= 5) {
      new = newnode();
      /* new ¤Ë now ¤ÎÃæ¿È¤ò¥³¥Ô¡¼¤·¤Æ¡¤ºÇ½ªÅª¤Ê¥¹¥³¥¢¤ò·×»» */
      /* copy content of 'now' to 'new', and compute the final score */
      last_next_word(now, new, param);
      if (debug2_flag) {
        j_printf("  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) {
          j_printf("  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) {
        j_printf("  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) {
#ifdef 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
#ifdef USE_NGRAM
                                            now->lscore,
#else
                                            LOG_ZERO,
#endif
#ifdef CM_SEARCH
                                            new->cmscore[new->seqnum-1]
#else
                                            LOG_ZERO
#endif
                                            );
        } else {
          new->lastcontext = now->lastcontext;
          new->prevgraph = now->prevgraph;
        }
#endif
      }
      /* ¤³¤Î²¾Àâ¤Ï¤³¤³¤Ç½ª¤ï¤é¤º¤Ë, ¤³¤³¤«¤é¤µ¤é¤Ëñ¸ìŸ³«¤¹¤ë */
      /* 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
    VERMES("get next words\n");
#endif
#ifdef USE_NGRAM
    nwnum = ngram_nextwords(now, nextword, maxnwnum, ngram, winfo, backtrellis);
#else  /* USE_DFA */
    nwnum = dfa_nextwords(now, nextword, maxnwnum, dfa);
    /* 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);
      nwnum = dfa_nextwords(now, nextword, maxnwnum, dfa);
    }
#endif
    if (debug2_flag) {
      j_printf("  %d words extracted from wordtrellis\n", nwnum);
    }

    /* 
     * ²¾Àâ¤È¼¡Ã±¸ì½¸¹ç¤«¤é¿·¤¿¤Êʸ²¾Àâ¤òÀ¸À®¤·¡¤¥¹¥¿¥Ã¥¯¤Ë¤¤¤ì¤ë¡¥
     */
    /*
     * generate new hypotheses from 'now' and 'nextword', 
     * and push them to stack
     */
#ifdef DEBUG
    VERMES("generate hypo\n");
#endif

#ifdef USE_DFA
    now_noise_calced = FALSE;   /* TRUE is noise-inserted score has been calculated */
#endif
    i = pushctr;                /* store old value */

#ifdef CM_SEARCH
    /* initialize local stack */
    cm_init(winfo);
#endif

    /* for each nextword, generate a new hypothesis */
    for (w = 0; w < nwnum; w++) {
#ifdef USE_DFA
      /* limit word hypothesis */
      if (! (winfo->wton[nextword[w]->id] >= cate_bgn && winfo->wton[nextword[w]->id] < cate_bgn + cate_num)) {
        continue;
      }
#endif
      new = newnode();
#ifdef USE_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 = dfa->sp_id;
          now_noise = newnode();
          cpy_node(now_noise, now);
#if 0
          now_noise_tmp = newnode();
          next_word(now, now_noise_tmp, &fornoise, param, backtrellis);
          scan_word(now_noise_tmp, param);
          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 (looktrellis_flag) {
            if(!dfa_look_around(&fornoise, now, backtrellis)){
              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, backtrellis);
          scan_word(now_noise, param);
          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 (looktrellis_flag) {
          if(!dfa_look_around(nextword[w], now_noise, backtrellis)){
            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, backtrellis);
        
      } else {
        
        /* expand word only if it exists in backward trellis */
        /* begin patch by kashima */
        if (looktrellis_flag) {
          if(!dfa_look_around(nextword[w], now, backtrellis)){
            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, backtrellis);
        
      }
#else  /* not USE_DFA */

      /* ¿·¤·¤¤²¾Àâ' 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, backtrellis);

#endif /* USE_DFA */

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

#ifdef CM_SEARCH
      /* store the local hypothesis to temporal stack */
      cm_store(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;
      }
      
#ifdef 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,
                                        now->g[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_gscore[new->bestt],
#else
                                        now->wordend_gscore[new->bestt],
#endif
#else
                                        now->tail_g_score,
#endif
#ifdef USE_NGRAM
                                        now->lscore,
#else
                                        LOG_ZERO,
#endif
#ifdef CM_SEARCH
                                        new->cmscore[new->seqnum-2]
#else
                                        LOG_ZERO
#endif
                                        );
#endif /* GRAPHOUT */
      put_to_stack(new, &start, &bottom, &stacknum, stacksize);
      if (debug2_flag) {
        j = new->seq[new->seqnum-1];
        j_printf("  %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);
      }
#ifdef VISUALIZE
      visual2_next_word(new, now, popctr);
#endif
      pushctr++;
#endif
    } /* end of nextword loop */

#ifdef CM_SEARCH
    /* compute score sum */
    cm_sum_score();
    /* compute CM and put the generated hypotheses to global stack */
    while ((new = cm_get_node()) != NULL) {
      cm_set_score(new);
#ifdef CM_SEARCH_LIMIT
      if (new->cmscore[new->seqnum-1] < cm_cut_thres
#ifdef CM_SEARCH_LIMIT_AFTER
          && 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;
      }

#ifdef 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,
                                        now->g[new->bestt+1],
#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
#ifdef USE_NGRAM
                                        now->lscore,
#else
                                        LOG_ZERO,
#endif
#ifdef CM_SEARCH
                                        new->cmscore[new->seqnum-2]
#else
                                        LOG_ZERO
#endif
                                        );
#endif /* GRAPHOUT */
      
      put_to_stack(new, &start, &bottom, &stacknum, stacksize);
      if (debug2_flag) {
        j = new->seq[new->seqnum-1];
        j_printf("  %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);
      }
#ifdef VISUALIZE
      visual2_next_word(new, now, popctr);
#endif
      pushctr++;
    }
#endif

    if (debug2_flag) {
      j_printf("%d pushed\n",pushctr-i);
    }
#ifdef USE_DFA
    if (now_noise_calced == TRUE) free_node(now_noise);
#endif

    /* 
     * ¼è¤ê½Ð¤·¤¿²¾Àâ¤ò¼Î¤Æ¤ë
     * free the source hypothesis
     */
    free_node(now);

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

  /* output */
  if (!result_reorder_flag && finishnum < ncan) {
    result_pass2_end();
  }
  /* õº÷¼ºÇԤǰì¤Ä¤â¸õÊ䤬ÆÀ¤é¤ì¤Ê¤±¤ì¤Ð¡¤Âè1¥Ñ¥¹¤Î·ë²Ì¤ò¤½¤Î¤Þ¤Þ½ÐÎϤ¹¤ë */
  /* If search failed and no candidate obtained in this pass, output
     the result of the previous 1st pass as a final result. */
  if (finishnum == 0) {         /* if search failed */
    if (verbose_flag) {
      j_printf("got no candidates, output 1st pass result as a final result\n",finishnum);
    }
    /* make hypothesis data from the result of previous 1st pass */
    now = newnode();
    for (i=0;i<pass1_wnum;i++) {
      now->seq[i] = pass1_wseq[pass1_wnum-1-i];
    }
    now->seqnum = pass1_wnum;
    now->score = pass1_score;
#ifdef CONFIDENCE_MEASURE
    /* fill in null values */
#ifdef CM_MULTIPLE_ALPHA
    for(j=0;j<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 */
    
    /* output it */
    if (module_mode) {
      /* ¥â¥¸¥å¡¼¥ë¥â¡¼¥É¤Ç¤Ï¡¤Âè2¥Ñ¥¹¤¬¼ºÇÔ¤·¤¿¤é²¿¤â½ÐÎϤ·¤Ê¤¤ */
      result_pass2_failed(winfo);
    } else {
      /* output the result of the first pass as the final output */
      result_pass2_begin();
      result_pass2(now, 1, winfo);
      result_pass2_end();
    }
#ifdef SP_BREAK_CURRENT_FRAME
    /* segment restart processing */
    if (sp_break_last_nword_allow_override) sp_segment_set_last_nword(now);
#endif
    /* do forced alignment if needed */
    if (align_result_word_flag) word_rev_align(now->seq, now->seqnum, tparam);
    if (align_result_phoneme_flag) phoneme_rev_align(now->seq, now->seqnum, tparam);
    if (align_result_state_flag) state_rev_align(now->seq, now->seqnum, tparam);
    free_node(now);
  } else {                      /* if at least 1 candidate found */
    if (debug2_flag) {
      j_printf("got %d candidates\n",finishnum);
    }
    if (result_reorder_flag) {
      /* ·ë²Ì¤Ï¤Þ¤À½ÐÎϤµ¤ì¤Æ¤¤¤Ê¤¤¤Î¤Ç¡¤Ê¸¸õÊäÍÑ¥¹¥¿¥Ã¥¯Æâ¤ò¥½¡¼¥È¤·¤Æ
         ¤³¤³¤Ç½ÐÎϤ¹¤ë */
      /* As all of the found candidate are in result stack, we sort them
         and output them here  */
      if (debug2_flag) VERMES("done\n");
      result_reorder_and_output(&r_start, &r_bottom, &r_stacknum, output_hypo_maxnum, winfo);
    }
  }

  /* ³Æ¼ï¥«¥¦¥ó¥¿¤ò½ÐÎÏ */
  /* output counters */
  if (verbose_flag) {
    j_printf("%d generated, %d pushed, %d nodes popped in %d\n",
             genectr, pushctr, popctr, backtrellis->framelen);
    j_flushprint();
#ifdef GRAPHOUT_DYNAMIC
    j_printf("graph: %d merged", dynamic_merged_num);
#ifdef GRAPHOUT_SEARCH
    j_printf(", %d terminated", terminate_search_num);
#endif
    j_printf(" in %d\n", popctr);
#endif
  }
    
#ifdef GRAPHOUT
  printf("------ 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);
#ifdef GRAPHOUT_DEPTHCUT
  /* perform word graph depth cutting here */
  wordgraph_depth_cut(&wordgraph_root);
#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);
  /* 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);
  /* merge words of near time (skip if "-graphrange" value <= 0 */
  wordgraph_compaction_neighbor(&wordgraph_root);
  /* finalize: sort and annotate ID */
  wordgraph_sort_and_annotate_id(&wordgraph_root);
  /* check coherence */
  wordgraph_check_coherence(wordgraph_root);
  printf("------ wordgraph post-processing end ------\n");
  /* debug: output all graph word info */
  wordgraph_dump(wordgraph_root);
  /* output graph */
  result_graph(wordgraph_root, winfo);
  /* clear all wordgraph */
  wordgraph_clean(&wordgraph_root);
#endif
  
  /* ½ªÎ»½èÍý */
  /* finalize */
  nw_free(nextword, nwroot);
  free_all_nodes(start);
  free_wordtrellis();
#ifdef SCAN_BEAM
  free(framemaxscore);
#endif
  clear_stocker();
}

---