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

#undef DEBUG


/* ---------------------------------------------------------- */
/*                     Â裱¥Ñ¥¹¤Î·ë²Ì½èÍý                     */
/*              end procedure to get result of 1st pass       */
/* ---------------------------------------------------------- */

#ifdef WORD_GRAPH

static void
generate_lattice(int frame, RecogProcess *r)
{
  BACKTRELLIS *bt;
  WORD_INFO *winfo;
  TRELLIS_ATOM *ta;
  int i, j;
  LOGPROB l;
  WordGraph *new;

  bt = r->backtrellis;
  winfo = r->lm->winfo;

  if (frame >= 0) {
    for (i=0;i<bt->num[frame];i++) {
      ta = bt->rw[frame][i];
      /* words will be saved as a part of graph only if any of its
         following word has been survived in a beam */
      if (! ta->within_context) continue; /* not a candidate */
      if (ta->within_wordgraph) continue; /* already marked */
      /* mark  */
      ta->within_wordgraph = TRUE;

      new = (WordGraph *)mymalloc(sizeof(WordGraph));
      new->wid = ta->wid;
      new->lefttime = ta->begintime;
      new->righttime = ta->endtime;
      new->fscore_head = ta->backscore;
      new->fscore_tail = 0.0;
      new->gscore_head = 0.0;
      new->gscore_tail = 0.0;
      new->lscore_tmp = ta->lscore;
#ifdef CM_SEARCH
      new->cmscore = 0.0;
#endif
      new->forward_score = new->backward_score = 0.0;
      new->headphone = winfo->wseq[ta->wid][0];
      new->tailphone = winfo->wseq[ta->wid][winfo->wlen[ta->wid]-1];

      new->leftwordmaxnum = FANOUTSTEP;
      new->leftword = (WordGraph **)mymalloc(sizeof(WordGraph *) * new->leftwordmaxnum);
      new->left_lscore = (LOGPROB *)mymalloc(sizeof(LOGPROB) * new->leftwordmaxnum);
      new->leftwordnum = 0;
      new->rightwordmaxnum = FANOUTSTEP;
      new->rightword = (WordGraph **)mymalloc(sizeof(WordGraph *) * new->rightwordmaxnum);
      new->right_lscore = (LOGPROB *)mymalloc(sizeof(LOGPROB) * new->rightwordmaxnum);
      new->rightwordnum = 0;

      l = ta->backscore;
      if (ta->last_tre->wid != WORD_INVALID) {
        l -= ta->last_tre->backscore;
      }
      l -= ta->lscore;
      new->amavg = l / (float)(ta->endtime - ta->begintime + 1);

#ifdef GRAPHOUT_DYNAMIC
      new->purged = FALSE;
#endif
      new->saved = FALSE;
      new->graph_cm = 0.0;
      new->mark = FALSE;

      new->next = r->result.wg1;
      r->result.wg1 = new;

      /* recursive call */
      generate_lattice(ta->last_tre->endtime, r);
    }
  }
}

static void
link_lattice_by_time(WordGraph *root)
{
  WordGraph *wg;
  WordGraph *wtmp;
  int lefttime, righttime;
  
  for(wg=root;wg;wg=wg->next) {
    
    for(wtmp=root;wtmp;wtmp=wtmp->next) {
      if (wg->righttime + 1 == wtmp->lefttime) {
        wordgraph_check_and_add_leftword(wtmp, wg, wtmp->lscore_tmp);
        wordgraph_check_and_add_rightword(wg, wtmp, wtmp->lscore_tmp);
      }
      if (wtmp->righttime + 1 == wg->lefttime) {
        wordgraph_check_and_add_leftword(wg, wtmp, wg->lscore_tmp);
        wordgraph_check_and_add_rightword(wtmp, wg, wg->lscore_tmp);
      }
    }
  }

}

static void
re_compute_lattice_lm(WordGraph *root, WCHMM_INFO *wchmm)
{
  int i;
  
  for(wg=root;wg;wg=wg->next) {
    for(i=0;i<wg->leftwordnum;i++) {
      wg->left_lscore[i] = (*(wchmm->ngram->bigram_prob))(wchmm->ngram, wchmm->winfo->wton[wg->leftword[i]->wid], wchmm->winfo->wton[wg->wid]);
    }
    for(i=0;i<wg->rightwordnum;i++) {
      wg->right_lscore[i] = (*(wchmm->ngram->bigram_prob))(wchmm->ngram, wchmm->winfo->wton[wg->wid], wchmm->winfo->wton[wg->rightword[i]->wid]);
    }
  }
}

#endif

static void
put_atom(TRELLIS_ATOM *atom, WORD_INFO *winfo)
{
  int i;
  jlog("DEBUG: %3d,%3d %f %16s (id=%5d)", atom->begintime, atom->endtime,
       atom->backscore, winfo->wname[atom->wid], atom->wid);
  for (i=0;i<winfo->wlen[atom->wid]; i++) {
    jlog(" %s",winfo->wseq[atom->wid][i]->name);
  }
  jlog("\n");
}

static LOGPROB
trace_backptr(WORD_ID wordseq_rt[MAXSEQNUM], int *rt_wordlen, TRELLIS_ATOM *atom, WORD_INFO *winfo)
{
  int wordlen = 0;              /* word length of best sentence hypothesis */
  TRELLIS_ATOM *tretmp;
  LOGPROB langscore = 0.0;
  static WORD_ID wordseq[MAXSEQNUM];    /* temporal: in reverse order */
  int i;

  /* initialize */
  wordseq[0] = atom->wid;       /* start from specified atom */
  wordlen = 1;
  tretmp = atom;
  langscore += tretmp->lscore;
  if (debug2_flag) {
    put_atom(tretmp, winfo);
  }
  
  /* trace the backtrellis */
  while (tretmp->begintime > 0) {/* until beginning of input */
    tretmp = tretmp->last_tre;
/*    t = tretmp->boundtime - 1;
    tretmp = bt_binsearch_atom(backtrellis, tretmp->boundtime-1, tretmp->last_wid);*/
    if (tretmp == NULL) {       /* should not happen */
      j_internal_error("trace_backptr: last trellis missing while backtracking");
    }
    langscore += tretmp->lscore;
    wordseq[wordlen] = tretmp->wid;
    wordlen++;
    if (debug2_flag) {
      put_atom(tretmp, winfo);
    }
    if (wordlen >= MAXSEQNUM) {
      j_internal_error("trace_backptr: sentence length exceeded ( > %d)\n",MAXSEQNUM);
    }
  }
  *rt_wordlen = wordlen;
  /* reverse order -> normal order */
  for(i=0;i<wordlen;i++) wordseq_rt[i] = wordseq[wordlen-i-1];
  return(langscore);
}

static void
find_1pass_result(int framelen, RecogProcess *r)
{
  BACKTRELLIS *backtrellis;
  WORD_INFO *winfo;
  WORD_ID wordseq[MAXSEQNUM];
  int wordlen;
  int i;
  TRELLIS_ATOM *best;
  int last_time;
  LOGPROB total_lscore;
  LOGPROB maxscore;
  TRELLIS_ATOM *tmp;
#ifdef SPSEGMENT_NAIST
  boolean ok_p;
#endif

  backtrellis = r->backtrellis;
  winfo = r->lm->winfo;

  /* look for the last trellis word */

  if (r->lmtype == LM_PROB) {

    for (last_time = framelen - 1; last_time >= 0; last_time--) {

      maxscore = LOG_ZERO;
      for (i=0;i<backtrellis->num[last_time];i++) {
        tmp = backtrellis->rw[last_time][i];
#ifdef WORD_GRAPH
        /* treat only words on a graph path */
        if (!tmp->within_context) continue;
#endif
        if (r->config->successive.enabled) {
          /* short-pause segmentation mode */
          /* ºÇ½ª¥Õ¥ì¡¼¥à¤Ë»Ä¤Ã¤¿ºÇÂ祹¥³¥¢¤Îñ¸ì */
          /* it should be the best trellis word on the last frame */
          if (maxscore < tmp->backscore) {
            maxscore = tmp->backscore;
            best = tmp;
          }
        } else {
          /* not segmentation mode */
          /* ºÇ½ªÃ±¸ì¤Ï winfo->tail_silwid ¤Ë¸ÇÄê */
          /* it is fixed to the tail silence model (winfo->tail_silwid) */
          if (tmp->wid == winfo->tail_silwid && maxscore < tmp->backscore) {
            maxscore = tmp->backscore;
            best = tmp;
            break;
          }
        }
      }
      if (maxscore != LOG_ZERO) break;
    }

    if (last_time < 0) {                /* not found */
      jlog("WARNING: %02d %s: no tail silence word survived on the last frame, search failed\n", r->config->id, r->config->name);
      r->result.status = J_RESULT_STATUS_FAIL;
      //callback_exec(CALLBACK_RESULT, r);
      return;
    }
  
  }

  if (r->lmtype == LM_DFA) {

    for (last_time = framelen - 1; last_time >= 0; last_time--) {

      /* ËöÈø¤Ë»Ä¤Ã¤¿Ã±¸ì¤ÎÃæ¤ÇºÇÂ祹¥³¥¢¤Îñ¸ì(cp_end¤Ï»ÈÍѤ·¤Ê¤¤) */
      /* the best trellis word on the last frame (not use cp_end[]) */
      maxscore = LOG_ZERO;
      for (i=0;i<backtrellis->num[last_time];i++) {
        tmp = backtrellis->rw[last_time][i];
#ifdef WORD_GRAPH
        /* treat only words on a graph path */
        if (!tmp->within_context) continue;
#endif
        /*      if (dfa->cp_end[winfo->wton[tmp->wid]] == TRUE) {*/
        if (maxscore < tmp->backscore) {
          maxscore = tmp->backscore;
          best = tmp;
        }
        /*      }*/
      }
      if (maxscore != LOG_ZERO) break;
    }

    if (last_time < 0) {                /* not found */
      jlog("WARNING: %02d %s: no sentence-end word survived on last beam\n", r->config->id, r->config->name);
      r->result.status = J_RESULT_STATUS_FAIL;
      //callback_exec(CALLBACK_RESULT, r);
      return;
    }
  
  }

  /* traceback word trellis from the best word */
  total_lscore = trace_backptr(wordseq, &wordlen, best, r->lm->winfo);
#ifdef SPSEGMENT_NAIST
  if (r->config->successive.enabled) {
    /* on segmentation mode, recognition result that only consists of
       short-pause words will be treated as recognition rejection */
    ok_p = FALSE;
    for(i=0;i<wordlen;i++) {
      if (! is_sil(wordseq[i], r)) ok_p = TRUE;
    }
    if (ok_p == FALSE) {
      r->result.status = J_RESULT_STATUS_ONLY_SILENCE;
      return;
    }
  }
#endif

  /* just flush last progress output */
  /*
  if (recog->jconf->output.progout_flag) {
    recog->result.status = 1;
    recog->result.num_frame = last_time;
    recog->result.pass1.word = wordseq;
    recog->result.pass1.word_num = wordlen;
    recog->result.pass1.score = best->backscore;
    recog->result.pass1.score_lm = total_lscore;
    recog->result.pass1.score_am = best->backscore - total_lscore;
    //callback_exec(CALLBACK_RESULT_PASS1_INTERIM, recog);
    }*/

  /* output 1st pass result */    
  if (verbose_flag || ! r->config->output.progout_flag) {
    r->result.status = J_RESULT_STATUS_SUCCESS;
    r->result.num_frame = framelen;
    for(i=0;i<wordlen;i++) r->result.pass1.word[i] = wordseq[i];
    r->result.pass1.word_num = wordlen;
    r->result.pass1.score = best->backscore;
    r->result.pass1.score_lm = total_lscore;
    r->result.pass1.score_am = best->backscore - total_lscore;
    //callback_exec(CALLBACK_RESULT_PASS1, r);
  }

  /* store the result to global val (notice: in reverse order) */
  for(i=0;i<wordlen;i++) r->pass1_wseq[i] = wordseq[i];
  r->pass1_wnum = wordlen;
  r->pass1_score = best->backscore;

#ifdef WORD_GRAPH
  /* ñ¸ì¥È¥ì¥ê¥¹¤«¤é¡¤¥é¥Æ¥£¥¹¤òÀ¸À®¤¹¤ë */
  /* generate word graph from the word trellis */
  r->peseqlen = backtrellis->framelen;
  r->result.wg1 = NULL;
  generate_lattice(last_time, r);
  link_lattice_by_time(r->result.wg1);
  if (r->lmtype == LM_PROB) re_compute_lattice_lm(r->result.wg1, r->wchmm);
  r->result.wg1_num = wordgraph_sort_and_annotate_id(&(r->result.wg1), r);
  /* compute graph CM by forward-backward processing */
  graph_forward_backward(r->result.wg1, r);
  //callback_exec(CALLBACK_RESULT_PASS1_GRAPH, r);
  //wordgraph_clean(&(r->result.wg1));
#endif

}

static int
compare_backscore(TRELLIS_ATOM **x1, TRELLIS_ATOM **x2)
{
  return((*x1)->backscore < (*x2)->backscore);
}

static void
find_1pass_result_word(int framelen, RecogProcess *r)
{
  BACKTRELLIS *bt;
  TRELLIS_ATOM *best, *tmp;
  int last_time;
  Sentence *s;
#ifdef CONFIDENCE_MEASURE
  LOGPROB sum;
#endif
  LOGPROB maxscore;
  int i;
  TRELLIS_ATOM **idx;

  if (r->lmvar != LM_DFA_WORD) return;

  bt = r->backtrellis;
  for (last_time = framelen - 1; last_time >= 0; last_time--) {
    maxscore = LOG_ZERO;
    for (i=0;i<bt->num[last_time];i++) {
      tmp = bt->rw[last_time][i];
#ifdef WORD_GRAPH
      /* treat only words on a graph path */
      if (!tmp->within_context) continue;
#endif
      if (maxscore < tmp->backscore) {
        maxscore = tmp->backscore;
        best = tmp;
      }
    }
    if (maxscore != LOG_ZERO) break;
  }

  if (last_time < 0) {          /* not found */
    jlog("WARNING: %02d %s: no word survived on the last frame, search failed\n", r->config->id, r->config->name);
    r->result.status = J_RESULT_STATUS_FAIL;
    //callback_exec(CALLBACK_RESULT, r);
    return;
  }

#ifdef CONFIDENCE_MEASURE
  sum = 0.0;
  for (i=0;i<bt->num[last_time];i++) {
    tmp = bt->rw[last_time][i];
#ifdef WORD_GRAPH
    /* treat only words on a graph path */
    if (!tmp->within_context) continue;
#endif
    sum += pow(10, r->config->annotate.cm_alpha * (tmp->backscore - maxscore));
  }
#endif

  /* set recognition result status to normal */
  r->result.status = J_RESULT_STATUS_SUCCESS;

  if (r->config->output.output_hypo_maxnum > 1) {
    /* more than one candidate is requested */

    /* get actual number of candidates to output */
    r->result.sentnum = r->config->output.output_hypo_maxnum;
    if (r->result.sentnum > bt->num[last_time]) {
      r->result.sentnum = bt->num[last_time];
    }

    /* prepare result storage */
    r->result.sent = (Sentence *)mymalloc(sizeof(Sentence)* r->result.sentnum);

    /* sort by score */
    idx = (TRELLIS_ATOM **)mymalloc(sizeof(TRELLIS_ATOM *)*bt->num[last_time]);
    for (i=0;i<bt->num[last_time];i++) {
      idx[i] = bt->rw[last_time][i];
    }
    qsort(idx, bt->num[last_time], sizeof(TRELLIS_ATOM *),
          (int (*)(const void *,const void *))compare_backscore);
    
    /* store to result storage */
    for(i=0;i<r->result.sentnum;i++) {
      s = &(r->result.sent[i]);
      tmp = idx[i];
      s->word_num = 1;
      s->word[0] = tmp->wid;
#ifdef CONFIDENCE_MEASURE
      s->confidence[0] = pow(10, r->config->annotate.cm_alpha * (tmp->backscore - maxscore)) / sum;
#endif
      s->score = tmp->backscore;
      s->score_lm = 0.0;
      s->score_am = tmp->backscore;
      s->gram_id = 0;
      s->align.filled = FALSE;
    }
    /* free work area for sort */
    free(idx);

  } else {                      /* only max is needed */

    /* prepare result storage */
    r->result.sent = (Sentence *)mymalloc(sizeof(Sentence));
    r->result.sentnum = 1;
    s = &(r->result.sent[0]);
    s->word_num = 1;
    s->word[0] = best->wid;
#ifdef CONFIDENCE_MEASURE
    s->confidence[0] = 1.0 / sum;
#endif
    s->score = best->backscore;
    s->score_lm = 0.0;
    s->score_am = best->backscore;
    s->gram_id = 0;
    s->align.filled = FALSE;
  }

  /* copy as 1st pass result */
  memcpy(&(r->result.pass1), &(r->result.sent[0]), sizeof(Sentence));

  //callback_exec(CALLBACK_RESULT, r);
  //free(r->result.sent);
}


#ifdef DETERMINE

static TRELLIS_ATOM *
determine_word(RecogProcess *r, int t, TRELLIS_ATOM *tremax, LOGPROB thres, int countthres)
{
  TRELLIS_ATOM *ret;
  WORD_ID w;

  //LOGPROB sum;
  //LOGPROB cm;

  int j;
  FSBeam *d;
  TOKEN2 *tk;
    
  if (tremax == NULL) {
    /* initialize */
    r->determine_count = 0;
    r->determine_maxnodescore = LOG_ZERO;
    r->determined = FALSE;
    r->determine_last_wid = WORD_INVALID;
    r->have_determine = FALSE;
    return NULL;
  }

  ret = NULL;

  /* get confidence score of the maximum word hypothesis */
/* 
 *   sum = 0.0;
 *   tre = recog->backtrellis->list;
 *   while (tre != NULL && tre->endtime == t) {
 *     sum += pow(10, recog->jconf->annotate.cm_alpha * (tre->backscore - tremax->backscore));
 *     tre = tre->next;
 *   }
 *   cm = 1.0 / sum;
 */

  /* determinization decision */
  w = tremax->wid;

  r->have_determine = FALSE;

  /* determine by score threshold from maximum node score to maximum word end node score */
  if (r->determine_last_wid == w && r->determine_maxnodescore - tremax->backscore <= thres) {
    r->determine_count++;
    if (r->determine_count > countthres) {
      if (r->determined == FALSE) {
        ret = tremax;
        r->determined = TRUE;
        r->have_determine = TRUE;
      }
    }
  } else {
    r->determine_count = 0;
  }

  //printf("determine: %d: %s: cm=%f, relscore=%f, count=%d, phase=%d\n", t, recog->model->winfo->woutput[w], cm, determine_maxnodescore - tremax->backscore, count, phase);
  r->determine_last_wid = w;

  /* update maximum node score here for next call, since
     the word path determination is always one frame later */
  d = &(r->pass1);
  r->determine_maxnodescore = LOG_ZERO;
  for (j = d->n_start; j <= d->n_end; j++) {
    tk = &(d->tlist[d->tn][d->tindex[d->tn][j]]);
    if (r->determine_maxnodescore < tk->score) r->determine_maxnodescore = tk->score;
  }

  return(ret);
}

static void
check_determine_word(RecogProcess *r, int t)
{
  TRELLIS_ATOM *tre;
  TRELLIS_ATOM *tremax;
  LOGPROB maxscore;

  /* bt->list is ordered by time frame */
  maxscore = LOG_ZERO;
  tremax = NULL;
  tre = r->backtrellis->list;
  while (tre != NULL && tre->endtime == t) {
    if (maxscore < tre->backscore) {
      maxscore = tre->backscore;
      tremax = tre;
    }
    tre = tre->next;
  }

  r->result.status = J_RESULT_STATUS_SUCCESS;
  r->result.num_frame = t;

  if (maxscore != LOG_ZERO) {
    //    if ((tre = determine_word(recog, t, tremax, 0.9, 17)) != NULL) {
    if ((tre = determine_word(r, t, tremax, r->config->pass1.determine_score_thres, r->config->pass1.determine_duration_thres)) != NULL) {
      r->result.pass1.word[0] = tremax->wid;
      r->result.pass1.word_num = 1;
      r->result.pass1.score = tremax->backscore;
      r->result.pass1.score_lm = 0.0;
      r->result.pass1.score_am = tremax->backscore;
      r->result.num_frame = t;
      //callback_exec(CALLBACK_RESULT_PASS1_DETERMINED, r);
    }
  }

  
}

#endif /* DETERMINE */

static void
bt_current_max(RecogProcess *r, int t)
{
  int wordlen;
  TRELLIS_ATOM *tre;
  TRELLIS_ATOM *tremax;
  LOGPROB maxscore;
  LOGPROB lscore;

  /* bt->list is ordered by time frame */
  maxscore = LOG_ZERO;
  tremax = NULL;
  tre = r->backtrellis->list;
  while (tre != NULL && tre->endtime == t) {
    if (maxscore < tre->backscore) {
      maxscore = tre->backscore;
      tremax = tre;
    }
    tre = tre->next;
  }

  r->result.status = J_RESULT_STATUS_SUCCESS;
  r->result.num_frame = t;

  if (maxscore == LOG_ZERO) {
    r->result.pass1.word_num = 0;
  } else {
    if (r->lmvar == LM_DFA_WORD) {
      r->result.pass1.word[0] = tremax->wid;
      r->result.pass1.word_num = 1;
      r->result.pass1.score = tremax->backscore;
      r->result.pass1.score_lm = 0.0;
      r->result.pass1.score_am = tremax->backscore;
    } else {
      lscore = trace_backptr(r->result.pass1.word, &wordlen, tremax, r->lm->winfo);
      r->result.pass1.word_num = wordlen;
      r->result.pass1.score = tremax->backscore;
      r->result.pass1.score_lm = lscore;
      r->result.pass1.score_am = tremax->backscore;
    }
  }
  //callback_exec(CALLBACK_RESULT_PASS1_INTERIM, r);
}

static void
bt_current_max_word(RecogProcess *r, int t)
{

  TRELLIS_ATOM *tre;
  TRELLIS_ATOM *tremax;
  LOGPROB maxscore;
  WORD_ID w;

  /* bt->list ¤Ï»þ´Ö½ç¤Ë³ÊǼ¤µ¤ì¤Æ¤¤¤ë */
  /* bt->list is order by time */
  maxscore = LOG_ZERO;
  tremax = NULL;
  tre = r->backtrellis->list;
  while (tre != NULL && tre->endtime == t) {
    if (maxscore < tre->backscore) {
      maxscore = tre->backscore;
      tremax = tre;
    }
    tre = tre->next;
  }

  if (maxscore != LOG_ZERO) {
    jlog("DEBUG: %3d: ",t);
    w = tremax->wid;
    jlog("\"%s [%s]\"(id=%d)",
         r->lm->winfo->wname[w], r->lm->winfo->woutput[w], w);
    jlog(" [%d-%d] %f", tremax->begintime, t, tremax->backscore);
    w = tremax->last_tre->wid;
    if (w != WORD_INVALID) {
      jlog(" <- \"%s [%s]\"(id=%d)\n",
               r->lm->winfo->wname[w], r->lm->winfo->woutput[w], w);
    } else {
      jlog(" <- bgn\n");
    }
  }
}


/* -------------------------------------------------------------------- */
/*                 ¥Ó¡¼¥àõº÷Ãæ¤Î¥È¡¼¥¯¥ó¤ò°·¤¦¥µ¥Ö´Ø¿ô                 */
/*                functions to handle hypothesis tokens                 */
/* -------------------------------------------------------------------- */

static void
malloc_nodes(FSBeam *d, int n, int ntoken_init)
{
  d->totalnodenum = n;
  d->token     = (TOKENID *)mymalloc(sizeof(TOKENID) * d->totalnodenum);
  //d->maxtnum = ntoken_init;
  if (d->maxtnum < ntoken_init) d->maxtnum = ntoken_init;
  d->tlist[0]  = (TOKEN2 *)mymalloc(sizeof(TOKEN2) * d->maxtnum);
  d->tlist[1]  = (TOKEN2 *)mymalloc(sizeof(TOKEN2) * d->maxtnum);
  d->tindex[0] = (TOKENID *)mymalloc(sizeof(TOKENID) * d->maxtnum);
  d->tindex[1] = (TOKENID *)mymalloc(sizeof(TOKENID) * d->maxtnum);
  //d->expand_step = ntoken_step;
  d->nodes_malloced = TRUE;
  d->expanded = FALSE;
}

static void
expand_tlist(FSBeam *d)
{
  d->maxtnum += d->expand_step;
  d->tlist[0]  = (TOKEN2 *)myrealloc(d->tlist[0],sizeof(TOKEN2) * d->maxtnum);
  d->tlist[1]  = (TOKEN2 *)myrealloc(d->tlist[1],sizeof(TOKEN2) * d->maxtnum);
  d->tindex[0] = (TOKENID *)myrealloc(d->tindex[0],sizeof(TOKENID) * d->maxtnum);
  d->tindex[1] = (TOKENID *)myrealloc(d->tindex[1],sizeof(TOKENID) * d->maxtnum);
  if (debug2_flag) jlog("STAT: token space expanded to %d\n", d->maxtnum);
  d->expanded = TRUE;
}

static void
prepare_nodes(FSBeam *d, int ntoken_step)
{
  d->tnum[0] = d->tnum[1] = 0;
  if (d->expand_step < ntoken_step) d->expand_step = ntoken_step;
}

static void
free_nodes(FSBeam *d)
{
  if (d->nodes_malloced) {
    free(d->token);
    free(d->tlist[0]);
    free(d->tlist[1]);
    free(d->tindex[0]);
    free(d->tindex[1]);
    d->nodes_malloced = FALSE;
  }
}

static void
clear_tlist(FSBeam *d, int tt)
{
  d->tnum[tt] = 0;
}

static void
clear_tokens(FSBeam *d, int tt)
{
  int j;
  /* initialize active token list: only clear ones used in the last call */
  for (j=0; j<d->tnum[tt]; j++) {
    d->token[d->tlist[tt][j].node] = TOKENID_UNDEFINED;
  }
}

static TOKENID
create_token(FSBeam *d)
{
  TOKENID newid;
  int tn;
  tn = d->tn;
  newid = d->tnum[tn];
  d->tnum[tn]++;
  while (d->tnum[tn]>=d->maxtnum) expand_tlist(d);
  d->tindex[tn][newid] = newid;
#ifdef WPAIR
  /* initialize link */
  d->tlist[tn][newid].next = TOKENID_UNDEFINED;
#endif
  return(newid);
}

static void
node_assign_token(FSBeam *d, int node, TOKENID tkid)
{
#ifdef WPAIR
  /* add to link list */
  d->tlist[d->tn][tkid].next = d->token[node];
#endif
  d->token[node] = tkid;
  d->tlist[d->tn][tkid].node = node;
}

static TOKENID
node_exist_token(FSBeam *d, int tt, int node, WORD_ID wid)
{
#ifdef WPAIR
  /* In word-pair mode, multiple tokens are assigned to a node as a list.
     so we have to search for tokens with same last word ID */
#ifdef WPAIR_KEEP_NLIMIT
  /* 1¥Î¡¼¥É¤´¤È¤ËÊÝ»ý¤¹¤ëtoken¿ô¤Î¾å¸Â¤òÀßÄê */
  /* token¤¬Ìµ¤¤¤¬¾å¸Â¤Ë㤷¤Æ¤¤¤ë¤È¤­¤Ï°ìÈÖ¥¹¥³¥¢¤ÎÄ㤤token¤ò¾å½ñ¤­¤¹¤ë */
  /* N-best: limit number of assigned tokens to a node */
  int i = 0;
  TOKENID lowest_token = TOKENID_UNDEFINED;
#endif
  TOKENID tmp;
  for(tmp=d->token[node]; tmp != TOKENID_UNDEFINED; tmp=d->tlist[tt][tmp].next) {
    if (d->tlist[tt][tmp].last_tre->wid == wid) {
      return(tmp);
    }
#ifdef WPAIR_KEEP_NLIMIT
    if (lowest_token == TOKENID_UNDEFINED ||
        d->tlist[tt][lowest_token].score < d->tlist[tt][tmp].score)
      lowest_token = tmp;
    if (++i >= d->wpair_keep_nlimit) break;
#endif
  }
#ifdef WPAIR_KEEP_NLIMIT
  if (i >= d->wpair_keep_nlimit) { /* overflow, overwrite lowest score */
    return(lowest_token);
  } else {
    return(TOKENID_UNDEFINED);
  }
#else 
  return(TOKENID_UNDEFINED);
#endif
  
#else  /* not WPAIR */
  /* 1¤Ä¤À¤±ÊÝ»ý,¤³¤ì¤ò¾ï¤Ë¾å½ñ¤­ */
  /* Only one token is kept in 1-best mode (default), so
     simply return the ID */
  return(d->token[node]);
#endif
}

#ifdef DEBUG
/* tlist ¤È token ¤ÎÂбþ¤ò¥Á¥§¥Ã¥¯¤¹¤ë(debug) */
/* for debug: check tlist <-> token correspondence
   where  tlist[tt][tokenID].node = nodeID and
          token[nodeID] = tokenID
 */
static void
node_check_token(FSBeam *d, int tt)
{
  int i;
  for(i=0;i<d->tnum[tt];i++) {
    if (node_exist_token(d, tt, d->tlist[tt][i].node, d->tlist[tt][i].last_tre->wid) != i) {
      jlog("ERROR: token %d not found on node %d\n", i, d->tlist[tt][i].node);
    }
  }
}
#endif



/* -------------------------------------------------------------------- */
/*       ¥È¡¼¥¯¥ó¤ò¥½¡¼¥È¤· ¾å°Ì N ¥È¡¼¥¯¥ó¤òȽÊ̤¹¤ë (heap sort)       */
/*        Sort generated tokens and get N-best (use heap sort)          */
/* -------------------------------------------------------------------- */
/* ¥Ó¡¼¥à¤ÎïçÃͤȤ·¤Æ¾å°Ì N ÈÖÌܤΥ¹¥³¥¢¤¬Íߤ·¤¤¤À¤±¤Ç¤¢¤ê¡¤¼ÂºÝ¤Ë¥½¡¼¥È
   ¤µ¤ì¤ëɬÍפϤʤ¤ */
/* we only want to know the N-th score for determining beam threshold, so
   order is not considered here */

#define SD(A) tindex_local[A-1] 
#define SCOPY(D,S) D = S        
#define SVAL(A) (tlist_local[tindex_local[A-1]].score) 
#define STVAL (tlist_local[s].score) 


static void
sort_token_upward(FSBeam *d, int neednum, int totalnum)
{
  int n,root,child,parent;
  TOKENID s;
  TOKEN2 *tlist_local;
  TOKENID *tindex_local;

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

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

static void
sort_token_downward(FSBeam *d, int neednum, int totalnum)
{
  int n,root,child,parent;
  TOKENID s;
  TOKEN2 *tlist_local;
  TOKENID *tindex_local;

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

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

static void
sort_token_no_order(FSBeam *d, int neednum, int *start, int *end)
{
  int totalnum;
  int restnum;

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

  restnum = totalnum - neednum;

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

/* -------------------------------------------------------------------- */
/*             Â裱¥Ñ¥¹(¥Õ¥ì¡¼¥àƱ´ü¥Ó¡¼¥à¥µ¡¼¥Á) ¥á¥¤¥ó                */
/*           main routines of 1st pass (frame-synchronous beam search)  */
/* -------------------------------------------------------------------- */

static boolean
init_nodescore(HTK_Param *param, RecogProcess *r)
{
  WCHMM_INFO *wchmm;
  FSBeam *d;
  TOKENID newid;
  TOKEN2 *new;
  WORD_ID beginword;
  int node;
  int i;

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

  /* ½é´ü²¾ÀâÍÑñ¸ìÍúÎò */
  /* setup initial word context */
  if (r->config->successive.enabled) { /* sp segment mode */
    /* initial word context = last non-sp word of previous 2nd pass at last segment*/
    if (r->lmtype == LM_PROB) {
      if (r->sp_break_last_nword == wchmm->winfo->tail_silwid) {
        /* if end with silE, initialize as normal start of sentence */
        d->bos.wid = WORD_INVALID;
      } else {
        d->bos.wid = r->sp_break_last_nword;
      }
    } else {
      d->bos.wid = WORD_INVALID;
    }
  } else {                      /* not sp segment mode */
    d->bos.wid = WORD_INVALID;  /* no context */
  }

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

  /* ¥Î¡¼¥É¡¦¥È¡¼¥¯¥ó¤ò½é´ü²½ */
  /* clear tree lexicon nodes and tokens */
  for(node = 0; node < d->totalnodenum; node++) {
    d->token[node] = TOKENID_UNDEFINED;
  }
  d->tnum[0] = d->tnum[1]  = 0;
  
#ifdef PASS1_IWCD
  /* ½ÐÎϳÎΨ·×»»¥­¥ã¥Ã¥·¥å¤ò½é´ü²½ */
  /* initialize outprob cache */
  outprob_style_cache_init(wchmm);
#endif

  /* ½é´ü²¾Àâ¤ÎºîÀ®: ½é´üñ¸ì¤Î·èÄê¤È½é´ü¥È¡¼¥¯¥ó¤ÎÀ¸À® */
  /* initial word hypothesis */

  if (r->lmtype == LM_PROB) {

    if (r->config->successive.enabled) { /* sp segment mode */
      if (r->sp_break_last_word != WORD_INVALID) { /* last segment exist */
        /* ³«»Ïñ¸ì¡áÁ°¤Î¥»¥°¥á¥ó¥È·×»»»þ¤ÎºÇ¸å¤ÎºÇÌàñ¸ì */
        /* ʸ½ªÎ»Ã±¸ì(silE,¶çÅÀ(IPA¥â¥Ç¥ë))¤Ê¤é¡¤silB ¤Ç³«»Ï */
        /* initial word = best last word hypothesis on the last segment */
        /* if silE or sp, begin with silB */
        /*if (is_sil(recog.sp_break_last_word, wchmm->winfo, wchmm->hmminfo)) {*/
        if (r->sp_break_last_word == wchmm->winfo->tail_silwid) {
          beginword = wchmm->winfo->head_silwid;
          d->bos.wid = WORD_INVALID;    /* reset initial word context */
        } else {
          beginword = r->sp_break_last_word;
        }
      } else {
        /* initial segment: initial word set to silB */
        beginword = wchmm->winfo->head_silwid;
      }
    } else {                    /* not sp segment mode */
      /* initial word fixed to silB */
      beginword = wchmm->winfo->head_silwid;
    }

#ifdef SP_BREAK_DEBUG
    jlog("DEBUG: startword=[%s], last_nword=[%s]\n",
           (beginword == WORD_INVALID) ? "WORD_INVALID" : wchmm->winfo->wname[beginword],
           (d->bos.wid == WORD_INVALID) ? "WORD_INVALID" : wchmm->winfo->wname[d->bos.wid]);
#endif
    /* create the first token at the first node of initial word */
    newid = create_token(d);
    new = &(d->tlist[d->tn][newid]);

    /* initial node = head node of the beginword */
    if (wchmm->hmminfo->multipath) {
      node = wchmm->wordbegin[beginword];
    } else {
      node = wchmm->offset[beginword][0];
    }

    /* set initial LM score */
    if (wchmm->state[node].scid != 0) {
      /* if initial node is on a factoring branch, use the factored score */
      new->last_lscore = max_successor_prob(wchmm, d->bos.wid, node);
    } else {
      /* else, set to 0.0 */
      new->last_lscore = 0.0;
    }
#ifdef FIX_PENALTY
    new->last_lscore = new->last_lscore * d->lm_weight;
#else
    new->last_lscore = new->last_lscore * d->lm_weight + d->lm_penalty;
#endif
    /* set initial word history */
    new->last_tre = &(d->bos);
    new->last_cword = d->bos.wid;
    if (wchmm->hmminfo->multipath) {
      /* set initial score using the initial LM score */
      new->score = new->last_lscore;
    } else {
      /* set initial score using the initial LM score and AM score of the first state */
      new->score = outprob_style(wchmm, node, d->bos.wid, 0, param) + new->last_lscore;
    }
    /* assign the initial node to token list */
    node_assign_token(d, node, newid);

  }

  if (r->lmtype == LM_DFA && r->lmvar == LM_DFA_GRAMMAR) {
  
    /* ½é´ü²¾Àâ: ʸˡ¾åʸƬ¤ËÀܳ¤·¤¦¤ëñ¸ì½¸¹ç */
    /* initial words: all words that can be begin of sentence grammatically */
    /* ¥¢¥¯¥Æ¥£¥Ö¤Êʸˡ¤Ë°¤¹¤ëñ¸ì¤Î¤ßµö¤¹ */
    /* only words in active grammars are allowed to be an initial words */
    MULTIGRAM *m;
    int t,tb,te;
    WORD_ID iw;
    boolean flag;
    DFA_INFO *gdfa;

    gdfa = r->lm->dfa;

    flag = FALSE;
    /* for all active grammar */
    for(m = r->lm->grammars; m; m = m->next) {
      if (m->active) {
        tb = m->cate_begin;
        te = tb + m->dfa->term_num;
        for(t=tb;t<te;t++) {
          /* for all word categories that belong to the grammar */
          if (dfa_cp_begin(gdfa, t) == TRUE) {
            /* if the category can appear at beginning of sentence, */
            flag = TRUE;
            for (iw=0;iw<gdfa->term.wnum[t];iw++) {
              /* create the initial token at the first node of all words that belongs to the category */
              i = gdfa->term.tw[t][iw];
              if (wchmm->hmminfo->multipath) {
                node = wchmm->wordbegin[i];
              } else {
                node = wchmm->offset[i][0];
              }
              /* in tree lexicon, words in the same category may share the same root node, so skip it if the node has already existed */
              if (node_exist_token(d, d->tn, node, d->bos.wid) != TOKENID_UNDEFINED) continue;
              newid = create_token(d);
              new = &(d->tlist[d->tn][newid]);
              new->last_tre = &(d->bos);
              new->last_lscore = 0.0;
              if (wchmm->hmminfo->multipath) {
                new->score = 0.0;
              } else {
                new->score = outprob_style(wchmm, node, d->bos.wid, 0, param);
              }
              node_assign_token(d, node, newid);
            }
          }
        }
      }
    }
    if (!flag) {
      jlog("ERROR: init_nodescore: no initial state found in active DFA grammar\n");
      return FALSE;
    }
  }

  if (r->lmtype == LM_DFA && r->lmvar == LM_DFA_WORD) {
    /* all words can appear at start */
    for (i=0;i<wchmm->winfo->num;i++) {
      if (wchmm->hmminfo->multipath) {
        node = wchmm->wordbegin[i];
      } else {
        node = wchmm->offset[i][0];
      }
      if (node_exist_token(d, d->tn, node, d->bos.wid) != TOKENID_UNDEFINED) continue;
      newid = create_token(d);
      new = &(d->tlist[d->tn][newid]);
      new->last_tre = &(d->bos);
      new->last_lscore = 0.0;
      if (wchmm->hmminfo->multipath) {
        new->score = 0.0;
      } else {
        new->score = outprob_style(wchmm, node, d->bos.wid, 0, param);
      }
      node_assign_token(d, node, newid);
    }
  }

  return TRUE;

}

/******************************************************/
/* ¥Õ¥ì¡¼¥àƱ´ü¥Ó¡¼¥àõº÷¤Î¼Â¹Ô --- ºÇ½é¤Î¥Õ¥ì¡¼¥àÍÑ  */
/* frame synchronous beam search --- first frame only */
/******************************************************/

boolean
get_back_trellis_init(HTK_Param *param, RecogProcess *r)
{
  WCHMM_INFO *wchmm;
  BACKTRELLIS *backtrellis;
  FSBeam *d;

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

  /* Viterbi±é»»Íѥ¥¯¥¨¥ê¥¢¤Î¥¹¥¤¥Ã¥Á¥ã¡¼ tl,tn ¤Î½é´üÃÍÀßÄê */
  /* tn: ¤³¤Î¥Õ¥ì¡¼¥àÍÑID   tl: £±¥Õ¥ì¡¼¥àÁ°¤ÎID */
  /* initialize switch tl, tn for Viterbi computation */
  /* tn: this frame  tl: last frame */
  d->tn = 0;
  d->tl = 1;

  /* ·ë²Ì¤Îñ¸ì¥È¥ì¥ê¥¹¤ò³ÊǼ¤¹¤ë¥Ð¥Ã¥¯¥È¥ì¥ê¥¹¹½Â¤ÂΤò½é´ü²½ */
  /* initialize backtrellis structure to store resulting word trellis */
  bt_prepare(backtrellis);

  /* ·×»»Íѥ¥¯¥¨¥ê¥¢¤ò½é´ü²½ */
  /* initialize some data on work area */

  if (r->lmtype == LM_PROB) {
    d->lm_weight  = r->config->lmp.lm_weight;
    d->lm_penalty = r->config->lmp.lm_penalty;
  }
  if (r->lmtype == LM_DFA) {
    d->penalty1 = r->config->lmp.penalty1;
  }
#if defined(WPAIR) && defined(WPAIR_KEEP_NLIMIT)
  d->wpair_keep_nlimit = r->config->pass1.wpair_keep_nlimit;
#endif

  /* ¥ï¡¼¥¯¥¨¥ê¥¢¤ò³ÎÊÝ */
  /* malloc work area */
  /* »ÈÍѤ¹¤ë¥È¡¼¥¯¥óÎÌ = viterbi»þ¤ËÁ«°ÜÀè¤È¤Ê¤ë¾õÂÖ¸õÊä¤Î¿ô
   * ͽ¬: ¥Ó¡¼¥à¿ô x 2 (¼«¸ÊÁ«°Ü+¼¡¾õÂÖ) + ÌÚ¹½Â¤²½¼­½ñ¤Î¥ë¡¼¥È¥Î¡¼¥É¿ô
   */
  /* assumed initial number of needed tokens: beam width x 2 (self + next trans.)
   * + root node on the tree lexicon (for inter-word trans.)
   */
  if (d->totalnodenum != wchmm->n) {
    free_nodes(d);
  }
  if (d->nodes_malloced == FALSE) {
    malloc_nodes(d, wchmm->n, r->trellis_beam_width * 2 + wchmm->startnum);
  }
  prepare_nodes(d, r->trellis_beam_width);
  
  /* ½é´ü¥¹¥³¥¢¤ò nodescore[tn] ¤Ë¥»¥Ã¥È */
  /* set initial score to nodescore[tn] */
  if (init_nodescore(param, r) == FALSE) {
    jlog("ERROR: get_back_trellis_init: failed to set initial node scores\n");
    return FALSE;
  }

  sort_token_no_order(d, r->trellis_beam_width, &(d->n_start), &(d->n_end));

  /* Á²¼¡½ÐÎϤò¹Ô¤Ê¤¦¾ì¹ç¤Î¥¤¥ó¥¿¡¼¥Ð¥ë¤ò·×»» */
  /* set interval frame for progout */
  r->config->output.progout_interval_frame = (int)((float)r->config->output.progout_interval / ((float)param->header.wshift / 10000.0));

  if (r->config->successive.enabled) {
    /* ¥·¥ç¡¼¥È¥Ý¡¼¥º¥»¥°¥á¥ó¥Æ¡¼¥·¥ç¥óÍѥѥé¥á¡¼¥¿¤Î½é´ü²½ */
    /* initialize parameter for short pause segmentation */
    d->in_sparea = TRUE;                /* assume beginning is silence */
    r->am->mfcc->sparea_start = d->tmp_sparea_start = 0; /* set start frame to 0 */
#ifdef SP_BREAK_RESUME_WORD_BEGIN
    d->tmp_sp_break_last_word = WORD_INVALID;
#endif
    r->sp_break_last_word = WORD_INVALID;
    /* ºÇ½é¤Î¥»¥°¥á¥ó¥È: ¼¡¤ÎÈó¥Ý¡¼¥º¥Õ¥ì¡¼¥à¤ÇÂè2¥Ñ¥¹¤Ø°Ü¹Ô¤·¤Ê¤¤ */
    /* the first end of pause segment should be always silB, so
       skip the first segment */
    d->first_sparea = TRUE;
    r->sp_break_2_begin_word = WORD_INVALID;
  }

#ifdef DETERMINE
  if (r->lmvar == LM_DFA_WORD) {
    /* initialize */
    determine_word(r, 0, NULL, 0, 0);
  }
#endif

  return TRUE;
}

/*****************************************************/
/* frame synchronous beam search --- proceed 1 frame */
/* ¥Õ¥ì¡¼¥àƱ´ü¥Ó¡¼¥àõº÷¤Î¼Â¹Ô --- 1¥Õ¥ì¡¼¥à¿Ê¤á¤ë  */
/*****************************************************/

static void
propagate_token(FSBeam *d, int next_node, LOGPROB next_score, TRELLIS_ATOM *last_tre, WORD_ID last_cword, LOGPROB last_lscore)
{
  TOKEN2 *tknext;
  TOKENID tknextid;

  if ((tknextid = node_exist_token(d, d->tn, next_node, last_tre->wid)) != TOKENID_UNDEFINED) {
    /* Á«°ÜÀè¥Î¡¼¥É¤Ë¤Ï´û¤Ë¾¥Î¡¼¥É¤«¤éÅÁȺѤß: ¥¹¥³¥¢¤¬¹â¤¤¤Û¤¦¤ò»Ä¤¹ */
    /* the destination node already has a token: compare score */
    tknext = &(d->tlist[d->tn][tknextid]);
    if (tknext->score < next_score) {
      /* ¤½¤ÎÁ«°ÜÀè¥Î¡¼¥É¤¬»ý¤Ä¥È¡¼¥¯¥ó¤ÎÆâÍƤò¾å½ñ¤­¤¹¤ë(¿·µ¬¥È¡¼¥¯¥ó¤Ïºî¤é¤Ê¤¤) */
      /* overwrite the content of existing destination token: not create a new token */
      tknext->last_tre = last_tre; /* propagate last word info */
      tknext->last_cword = last_cword; /* propagate last context word info */
      tknext->last_lscore = last_lscore; /* set new LM score */
      tknext->score = next_score; /* set new score */
    }
  } else {
    /* Á«°ÜÀè¥Î¡¼¥É¤Ï̤ÅÁÈÂ: ¿·µ¬¥È¡¼¥¯¥ó¤òºî¤Ã¤Æ³ä¤êÉÕ¤±¤ë */
    /* token unassigned: create new token and assign */
    if (next_score > LOG_ZERO) { /* valid token */
      tknextid = create_token(d); /* get new token */
    }
    tknext = &(d->tlist[d->tn][tknextid]);
    tknext->last_tre = last_tre; /* propagate last word info */
    tknext->last_cword = last_cword; /* propagate last context word info */
    tknext->last_lscore = last_lscore;
    tknext->score = next_score; /* set new score */
    node_assign_token(d, next_node, tknextid); /* assign this new token to the next node */
  }
}

static void
beam_intra_word_core(WCHMM_INFO *wchmm, FSBeam *d, TOKEN2 **tk_ret, int j, int next_node, LOGPROB next_a)
{
  int node; 
  LOGPROB tmpsum;
  LOGPROB ngram_score_cache;
  TOKEN2 *tk;

  tk = *tk_ret;

  node = tk->node;

  /* now, 'node' is the source node, 'next_node' is the destication node,
     and ac-> holds transition probability */
  /* tk->score is the accumulated score at the 'node' on previous frame */
  
  /******************************************************************/
  /* 2.1.1 Á«°ÜÀè¤Ø¤Î¥¹¥³¥¢·×»»(Á«°Ü³ÎΨ¡Ü¸À¸ì¥¹¥³¥¢)               */
  /*       compute score of destination node (transition prob + LM) */
  /******************************************************************/
  tmpsum = tk->score + next_a;
  ngram_score_cache = LOG_ZERO;
  /* the next score at 'next_node' will be computed on 'tmpsum', and
     the new LM probability (if updated) will be stored on 'ngram_score_cache' at below */
  
  if (!wchmm->category_tree) {
    /* ¸À¸ì¥¹¥³¥¢ factoring:
       arc¤¬¼«¸ÊÁ«°Ü¤Ç¤Ê¤¤Ã±¸ìÆâ¤ÎÁ«°Ü¤Ç¡¤¤«¤ÄÁ«°ÜÀè¤Ësuccessor¥ê¥¹¥È
       ¤¬¤¢¤ì¤Ð¡¤lexicon tree ¤Îʬ´ôÉôʬ¤ÎÁ«°Ü¤Ç¤¢¤ë */
    /* LM factoring:
       If this is not a self transition and destination node has successor
       list, this is branching transition
    */
    if (next_node != node) {
      if (wchmm->state[next_node].scid != 0
#ifdef UNIGRAM_FACTORING
          /* 1-gram factoring »ÈÍÑ»þ¤Ï, Ê£¿ô¤Ç¶¦Í­¤µ¤ì¤ë»Þ¤Ç¤Ï
             wchmm->state[node].scid ¤ÏÉé¤ÎÃͤȤʤꡤ¤½¤ÎÀäÂÐÃͤò
             ź»ú¤È¤·¤Æ wchmm->fscore[] ¤Ëñ¸ì½¸¹ç¤Î1-gram¤ÎºÇÂçÃͤ¬³ÊǼ
             ¤µ¤ì¤Æ¤¤¤ë. Ëöü¤Î»Þ(Ê£¿ôñ¸ì¤Ç¶¦Í­¤µ¤ì¤Ê¤¤)¤Ç¤Ï¡¤
             wchmm->state[node].scid ¤ÏÀµ¤ÎÃͤȤʤꡤ
             £±Ã±¸ì¤ò sc ¤È¤·¤Æ»ý¤Ä¤Î¤Ç¤½¤³¤ÇÀµ³Î¤Ê2-gram¤ò·×»»¤¹¤ë */
          /* When uni-gram factoring,
             wchmm->state[node].scid is below 0 for shared branches.
             In this case the maximum uni-gram probability for sub-tree
             is stored in wchmm->fscore[- wchmm->state[node].scid].
             Leaf branches (with only one successor word): the scid is
             larger than 0, and has
             the word ID in wchmm->sclist[wchmm->state[node].scid].
             So precise 2-gram is computed in this point */
#endif
          ){
        
        if (wchmm->lmtype == LM_PROB) {
          /* ¤³¤³¤Ç¸À¸ì¥â¥Ç¥ë³ÎΨ¤ò¹¹¿·¤¹¤ë */
          /* LM value should be update at this transition */
          /* N-gram³ÎΨ¤«¤éfactoring Ãͤò·×»» */
          /* compute new factoring value from N-gram probabilities */
#ifdef FIX_PENALTY
          /* if at the beginning of sentence, not add lm_penalty */
          if (tk->last_cword == WORD_INVALID) {
            ngram_score_cache = max_successor_prob(wchmm, tk->last_cword, next_node) * d->lm_weight;
          } else {
            ngram_score_cache = max_successor_prob(wchmm, tk->last_cword, next_node) * d->lm_weight + d->lm_penalty;
          }
#else
          ngram_score_cache = max_successor_prob(wchmm, tk->last_cword, next_node) * d->lm_weight + d->lm_penalty;
#endif
          /* ¥¹¥³¥¢¤Î¹¹¿·: tk->last_lscore ¤Ëñ¸ìÆâ¤Ç¤ÎºÇ¸å¤ÎfactoringÃͤ¬
             Æþ¤Ã¤Æ¤¤¤ë¤Î¤Ç, ¤½¤ì¤ò¥¹¥³¥¢¤«¤é°ú¤¤¤Æ¥ê¥»¥Ã¥È¤·, ¿·¤¿¤Ê¥¹¥³¥¢¤ò
             ¥»¥Ã¥È¤¹¤ë */
          /* update score: since 'tk->last_lscore' holds the last LM factoring
             value in this word, we first remove the score from the current
             score, and then add the new LM value computed above. */
          tmpsum -= tk->last_lscore;
          tmpsum += ngram_score_cache;
        }
        
        if (wchmm->lmtype == LM_DFA && wchmm->lmvar == LM_DFA_GRAMMAR) {
          /* ʸˡ¤òÍѤ¤¤ë¾ì¹ç, ¥«¥Æ¥´¥êñ°Ì¤ÎÌÚ¹½Â¤²½¤¬¤Ê¤µ¤ì¤Æ¤¤¤ì¤Ð,
             ÀܳÀ©Ìó¤Ïñ¸ì´ÖÁ«°Ü¤Î¤ß¤Ç°·¤ï¤ì¤ë¤Î¤Ç¡¤factoring ¤ÏɬÍפʤ¤. 
             ¥«¥Æ¥´¥êñ°ÌÌÚ¹½Â¤²½¤¬¹Ô¤ï¤ì¤Ê¤¤¾ì¹ç, ʸˡ´Ö¤ÎÀܳÀ©Ìó¤Ï¤³¤³
             ¤Ç factoring ¤Ç¹Ô¤ï¤ì¤ë¤³¤È¤Ë¤Ê¤ë. */
          /* With DFA, we use category-pair constraint extracted from the DFA
             at this 1st pass.  So if we compose a tree lexicon per word's
             category, the each category tree has the same connection
             constraint and thus we can apply the constraint on the cross-word
             transition.  This per-category tree lexicon is enabled by default,
             and in the case the constraint will be applied at the word end.
             If you disable per-category tree lexicon by undefining
             'CATEGORY_TREE', the word-pair contrained will be applied in a
             factoring style at here.
          */
          
          /* ·èÄêŪfactoring: ľÁ°Ã±¸ì¤ËÂФ·¤Æ,sub-treeÆâ¤Ë¥«¥Æ¥´¥êÂÐÀ©Ìó¾å
             Àܳ¤·¤¦¤ëñ¸ì¤¬£±¤Ä¤â¤Ê¤±¤ì¤Ð, ¤³¤ÎÁ«°Ü¤ÏÉÔ²Ä */
          /* deterministic factoring in grammar mode:
             transition disabled if there are totally no sub-tree word that can
             grammatically (in category-pair constraint) connect
             to the previous word.
          */
          if (!can_succeed(wchmm, tk->last_tre->wid, next_node)) {
            tmpsum = LOG_ZERO;
          }
        }
        
      }
    }
  }
  /* factoring not needed when DFA mode and uses category-tree */
  
  /****************************************/
  /* 2.1.2 Á«°ÜÀè¥Î¡¼¥É¤Ø¥È¡¼¥¯¥óÅÁÈ     */
  /*       pass token to destination node */
  /****************************************/
  
  if (ngram_score_cache == LOG_ZERO) ngram_score_cache = tk->last_lscore;
  propagate_token(d, next_node, tmpsum, tk->last_tre, tk->last_cword, ngram_score_cache);
  
  if (d->expanded) {
    /* if work area has been expanded at 'create_token()' above,
       the inside 'realloc()' will destroy the pointers.
       so, reset local pointers from token index */
    tk = &(d->tlist[d->tl][d->tindex[d->tl][j]]);
    d->expanded = FALSE;
  }
  
  *tk_ret = tk;

}

static void
beam_intra_word(WCHMM_INFO *wchmm, FSBeam *d, TOKEN2 **tk_ret, int j)
{
  A_CELL2 *ac; 
  TOKEN2 *tk;
  int node;
  int k;

  tk = *tk_ret;

  node = tk->node;

  if (wchmm->self_a[node] != LOG_ZERO) {
    beam_intra_word_core(wchmm, d, tk_ret, j, node, wchmm->self_a[node]);
  }

  if (wchmm->next_a[node] != LOG_ZERO) {
    beam_intra_word_core(wchmm, d, tk_ret, j, node+1, wchmm->next_a[node]);
  }

  for(ac=wchmm->ac[node];ac;ac=ac->next) {
    for(k=0;k<ac->n;k++) {
      beam_intra_word_core(wchmm, d, tk_ret, j, ac->arc[k], ac->a[k]);
    }
  }
}

/**************************/
/* 2.2. ¥È¥ì¥ê¥¹Ã±¸ìÊݸ  */
/*      save trellis word */
/**************************/
static TRELLIS_ATOM *
save_trellis(BACKTRELLIS *bt, WCHMM_INFO *wchmm, TOKEN2 *tk, int t, boolean final_for_multipath)
{
  TRELLIS_ATOM *tre;
  int sword;
 
  sword = wchmm->stend[tk->node];

  /* ¤³¤ÎÁ«°Ü¸µ¤Îñ¸ì½ªÃ¼¥Î¡¼¥É¤Ï¡ÖľÁ°¥Õ¥ì¡¼¥à¤Ç¡×À¸¤­»Ä¤Ã¤¿¥Î¡¼¥É. 
     (¡Ö¤³¤Î¥Õ¥ì¡¼¥à¡×¤Ç¤Ê¤¤¤³¤È¤ËÃí°Õ¡ª¡ª)
     ¤è¤Ã¤Æ¤³¤³¤Ç, »þ´Ö(t-1) ¤òñ¸ì½ªÃ¼¤È¤¹¤ë¥È¥ì¥ê¥¹¾å¤Îñ¸ì²¾Àâ
     (TRELLIS_ATOM)¤È¤·¤Æ¡¤Ã±¸ì¥È¥ì¥ê¥¹¹½Â¤ÂΤËÊݸ¤¹¤ë. */
  /* This source node (= word end node) has been survived in the
     "last" frame (notice: not "this" frame!!).  So this word end
     is saved here to the word trellis structure (BACKTRELLIS) as a
     trellis word (TRELLIS_ATOM) with end frame (t-1). */
  tre = bt_new(bt);
  tre->wid = sword;             /* word ID */
  tre->backscore = tk->score; /* log score (AM + LM) */
  tre->begintime = tk->last_tre->endtime + 1; /* word beginning frame */
  tre->endtime   = t-1; /* word end frame */
  tre->last_tre  = tk->last_tre; /* link to previous trellis word */
  if (wchmm->lmtype == LM_PROB) {
    tre->lscore    = tk->last_lscore;   /* log score (LM only) */
  } else if (wchmm->lmtype == LM_DFA) {
    tre->lscore = 0.0;
  }
  bt_store(bt, tre); /* save to backtrellis */
#ifdef WORD_GRAPH
  if (tre->last_tre != NULL) {
    /* mark to indicate that the following words was survived in beam */
    tre->last_tre->within_context = TRUE;
  }
  if (final_for_multipath) {
    /* last node */
    if (tre->wid == wchmm->winfo->tail_silwid) {
      tre->within_context = TRUE;
    }
  }
#endif /* WORD_GRAPH */

  return tre;
}
      

static void
beam_inter_word(WCHMM_INFO *wchmm, FSBeam *d, TOKEN2 **tk_ret, TRELLIS_ATOM *tre, int j)
{
  A_CELL2 *ac;
  TOKEN2 *tk;
  int sword;
  int node, next_node;
  LOGPROB *iwparray; 
  int stid;
#ifdef UNIGRAM_FACTORING
  int isoid; 
#endif
  LOGPROB tmpprob, tmpsum, ngram_score_cache;
  int k;
  WORD_ID last_word;

  tk = *tk_ret;
 
  node = tk->node;
  sword = wchmm->stend[node];
  last_word = wchmm->winfo->is_transparent[sword] ? tk->last_cword : sword;

  if (wchmm->lmtype == LM_PROB) {

    /* Á«°Ü¸µÃ±¸ì¤¬ËöÈøñ¸ì¤Î½ªÃ¼¤Ê¤é¡¤¤É¤³¤Ø¤âÁ«°Ü¤µ¤»¤Ê¤¤ */
    /* do not allow transition if the source word is end-of-sentence word */
    if (sword == wchmm->winfo->tail_silwid) return;

#ifdef UNIGRAM_FACTORING
    /* ¤¢¤È¤Ç¶¦Í­Ã±¸ìÀèƬ¥Î¡¼¥É¤ËÂФ·¤Æñ¸ì´ÖÁ«°Ü¤ò¤Þ¤È¤á¤Æ·×»»¤¹¤ë¤¿¤á¡¤*/
    /* ¤³¤Î¥ë¡¼¥×Æâ¤Ç¤ÏºÇÂçÌàÅÙ¤ò»ý¤Äñ¸ì½ªÃ¼¥Î¡¼¥É¤òµ­Ï¿¤·¤Æ¤ª¤¯ */
    /* here we will record the best wordend node of maximum likelihood
       at this frame, to compute later the cross-word transitions toward
       shared factoring word-head node */
    tmpprob = tk->score;
    if (!wchmm->hmminfo->multipath) tmpprob += wchmm->wordend_a[sword];
    if (d->wordend_best_score < tmpprob) {
      d->wordend_best_score = tmpprob;
      d->wordend_best_node = node;
      d->wordend_best_tre = tre;
      d->wordend_best_last_cword = tk->last_cword;
    }
#endif
    
    /* N-gram¤Ë¤ª¤¤¤Æ¤Ï¾ï¤ËÁ´Ã±¸ì¤ÎÀܳ¤ò¹Íθ¤¹¤ëɬÍפ¬¤¢¤ë¤¿¤á¡¤
       ¤³¤³¤Çñ¸ì´Ö¤Î¸À¸ì³ÎΨÃͤò¤¹¤Ù¤Æ·×»»¤·¤Æ¤ª¤¯. 
       ¥­¥ã¥Ã¥·¥å¤Ï max_successor_prob_iw() Æâ¤Ç¹Íθ. */
    /* As all words are possible to connect in N-gram, we first compute
       all the inter-word LM probability here.
       Cache is onsidered in max_successor_prob_iw(). */
    if (wchmm->winfo->is_transparent[sword]) {
      iwparray = max_successor_prob_iw(wchmm, tk->last_cword);
    } else {
      iwparray = max_successor_prob_iw(wchmm, sword);
    }
  }

  /* ¤¹¤Ù¤Æ¤Îñ¸ì»Ïü¥Î¡¼¥É¤ËÂФ·¤Æ°Ê²¼¤ò¼Â¹Ô */
  /* for all beginning-of-word nodes, */
  /* wchmm->startnode[0..stid-1] ... ñ¸ì»Ïü¥Î¡¼¥É¥ê¥¹¥È */
  /* wchmm->startnode[0..stid-1] ... list of word start node (shared) */
  for (stid = wchmm->startnum - 1; stid >= 0; stid--) {
    next_node = wchmm->startnode[stid];
    if (wchmm->hmminfo->multipath) {
      if (wchmm->lmtype == LM_PROB) {
        /* connection to the head silence word is not allowed */
        if (wchmm->wordbegin[wchmm->winfo->head_silwid] == next_node) continue;
      }
    }
    
    /*****************************************/
    /* 2.3.1. ñ¸ì´Ö¸À¸ìÀ©Ìó¤òŬÍÑ           */
    /*        apply cross-word LM constraint */
    /*****************************************/
        
    if (wchmm->lmtype == LM_PROB) {
      /* N-gram³ÎΨ¤ò·×»» */
      /* compute N-gram probability */
#ifdef UNIGRAM_FACTORING
      /* 1-gram factoring ¤Ë¤ª¤±¤ëñ¸ì´Ö¸À¸ì³ÎΨ¥­¥ã¥Ã¥·¥å¤Î¸úΨ²½:
         1-gram factoring ¤Ïñ¸ìÍúÎò¤Ë°Í¸¤·¤Ê¤¤¤Î¤Ç¡¤
         ¤³¤³¤Ç»²¾È¤¹¤ë factoring Ãͤο¤¯¤Ï
         wchmm->fscore[] ¤Ë´û¤Ë³ÊǼ¤µ¤ì, õº÷Ãæ¤âÉÔÊѤǤ¢¤ë. 
         ¤è¤Ã¤Æ·×»»¤¬É¬ÍפÊñ¸ì(¤É¤Îñ¸ì¤È¤â¥Î¡¼¥É¤ò¶¦Í­¤·¤Ê¤¤Ã±¸ì)
         ¤Ë¤Ä¤¤¤Æ¤Î¤ß iwparray[] ¤Ç·×»»¡¦¥­¥ã¥Ã¥·¥å¤¹¤ë.  */
      /* Efficient cross-word LM cache:
         As 1-gram factoring values are independent of word context,
         they remain unchanged while search.  So, in cross-word LM
         computation, beginning-of-word states which share nodes with
         others and has factoring value in wchmm does not need cache.
         So only the unshared beginning-of-word states are computed and
         cached here in iwparray[].
      */
      /* wchmm,start2isolate[0..stid-1] ... ¥Î¡¼¥É¤ò¶¦Í­¤·¤Ê¤¤Ã±¸ì¤Ï
         ¤½¤ÎÄ̤·ID, ¶¦Í­¤¹¤ë(¥­¥ã¥Ã¥·¥å¤ÎɬÍפΤʤ¤)ñ¸ì¤Ï -1 */
      /* wchmm->start2isolate[0..stid-1] ... isolate ID for
         beginning-of-word state.  value: -1 for states that has
         1-gram factoring value (share nodes with some other words),
         and ID for unshared words
      */
      isoid = wchmm->start2isolate[stid];
      /* ·×»»¤¬É¬ÍפǤʤ¤Ã±¸ìÀèƬ¥Î¡¼¥É¤Ï¥Ñ¥¹¤ò¤Þ¤È¤á¤Æ¸å¤Ë·×»»¤¹¤ë¤Î¤Ç
         ¤³¤³¤Ç¤Ï¥¹¥­¥Ã¥× */
      /* the shared nodes will be computed afterward, so just skip them
         here */
      if (isoid == -1) continue;
      tmpprob = iwparray[isoid];
#else
      tmpprob = iwparray[stid];
#endif
    }

    /* Á«°ÜÀè¤Îñ¸ì¤¬ÀèƬñ¸ì¤Ê¤éÁ«°Ü¤µ¤»¤Ê¤¤. 
       ¤³¤ì¤Ï wchmm.c ¤Ç³ºÅöñ¸ì¤Ë stid ¤ò³ä¤ê¿¶¤é¤Ê¤¤¤³¤È¤ÇÂбþ
       ¤·¤Æ¤¤¤ë¤Î¤Ç¡¤¤³¤³¤Ç¤Ï²¿¤â¤·¤Ê¤¯¤Æ¤è¤¤ */
    /* do not allow transition if the destination word is
       beginning-of-sentence word.  This limitation is realized by
       not assigning 'stid' for the word in wchmm.c, so we have nothing
       to do here.
    */
    
    if (wchmm->category_tree) {
      /* ʸˡ¤Î¾ì¹ç, À©Ìó¤Ï·èÄêŪ: ¥«¥Æ¥´¥êÂÐÀ©Ìó¾åµö¤µ¤ì¤Ê¤¤¾ì¹ç¤ÏÁ«°Ü¤µ¤»¤Ê¤¤ */
      /* With DFA and per-category tree lexicon,
         LM constraint is deterministic:
         do not allow transition if the category connection is not allowed
         (with category tree, constraint can be determined on top node) */
      if (dfa_cp(wchmm->dfa, wchmm->winfo->wton[sword], wchmm->winfo->wton[wchmm->start2wid[stid]]) == FALSE) continue;
    }

    /*******************************************************************/
    /* 2.3.2. Á«°ÜÀè¤Îñ¸ìÀèƬ¤Ø¤Î¥¹¥³¥¢·×»»(Á«°Ü³ÎΨ¡Ü¸À¸ì¥¹¥³¥¢)     */
    /*        compute score of destination node (transition prob + LM) */
    /*******************************************************************/
    tmpsum = tk->score;
    if (!wchmm->hmminfo->multipath) tmpsum += wchmm->wordend_a[sword];

    /* 'tmpsum' now holds outgoing score from the wordend node */
    if (wchmm->lmtype == LM_PROB) {
      /* ¸À¸ì¥¹¥³¥¢¤òÄɲà */
      /* add LM score */
      ngram_score_cache = tmpprob * d->lm_weight + d->lm_penalty;
      tmpsum += ngram_score_cache;
      if (wchmm->winfo->is_transparent[sword] && wchmm->winfo->is_transparent[tk->last_cword]) {
            
        tmpsum += d->lm_penalty_trans;
      }
    }
    if (wchmm->lmtype == LM_DFA) {
      /* grammar: ñ¸ìÁÞÆþ¥Ú¥Ê¥ë¥Æ¥£¤òÄɲà */
      /* grammar: add insertion penalty */
      tmpsum += d->penalty1;

      /* grammar: deterministic factoring (in case category-tree not enabled) */
      if (!wchmm->category_tree) {
        if (!can_succeed(wchmm, sword, next_node)) {
          tmpsum = LOG_ZERO;
        }
      }
    }
    
    /*********************************************************************/
    /* 2.3.3. Á«°ÜÀè¥Î¡¼¥É¤Ø¥È¡¼¥¯¥óÅÁÈÂ(ñ¸ìÍúÎò¾ðÊó¤Ï¹¹¿·)             */
    /*        pass token to destination node (updating word-context info */
    /*********************************************************************/

    if (wchmm->hmminfo->multipath) {
      /* since top node has no ouput, we should go one more step further */
      if (wchmm->self_a[next_node] != LOG_ZERO) {
        propagate_token(d, next_node, tmpsum + wchmm->self_a[next_node], tre, last_word, ngram_score_cache);
        if (d->expanded) {
          /* if work area has been expanded at 'create_token()' above,
             the inside 'realloc()' will destroy the pointers.
             so, reset local pointers from token index */
          tk = &(d->tlist[d->tn][d->tindex[d->tn][j]]);
          d->expanded = FALSE;
        }
      }
      if (wchmm->next_a[next_node] != LOG_ZERO) {
        propagate_token(d, next_node+1, tmpsum + wchmm->next_a[next_node], tre, last_word, ngram_score_cache);
        if (d->expanded) {
          /* if work area has been expanded at 'create_token()' above,
             the inside 'realloc()' will destroy the pointers.
             so, reset local pointers from token index */
          tk = &(d->tlist[d->tn][d->tindex[d->tn][j]]);
          d->expanded = FALSE;
        }
      }
      for(ac=wchmm->ac[next_node];ac;ac=ac->next) {
        for(k=0;k<ac->n;k++) {
          propagate_token(d, ac->arc[k], tmpsum + ac->a[k], tre, last_word, ngram_score_cache);
          if (d->expanded) {
            /* if work area has been expanded at 'create_token()' above,
               the inside 'realloc()' will destroy the pointers.
               so, reset local pointers from token index */
            tk = &(d->tlist[d->tn][d->tindex[d->tn][j]]);
            d->expanded = FALSE;
          }
        }
      }
    } else {
      propagate_token(d, next_node, tmpsum, tre, last_word, ngram_score_cache);
      if (d->expanded) {
        /* if work area has been expanded at 'create_token()' above,
           the inside 'realloc()' will destroy the pointers.
           so, reset local pointers from token index */
        tk = &(d->tlist[d->tl][d->tindex[d->tl][j]]);
        d->expanded = FALSE;
      }
    }
        
  }     /* end of next word heads */

  *tk_ret = tk;


} /* end of cross-word processing */


#ifdef UNIGRAM_FACTORING

static void
beam_inter_word_factoring(WCHMM_INFO *wchmm, FSBeam *d)
{
  int sword;
  int node, next_node;
  int stid;
  LOGPROB tmpprob, tmpsum, ngram_score_cache;
  A_CELL2 *ac;
  int j;
  WORD_ID last_word;

  node = d->wordend_best_node;
  sword = wchmm->stend[node];
  last_word = wchmm->winfo->is_transparent[sword] ? d->wordend_best_last_cword : sword;

  for (stid = wchmm->startnum - 1; stid >= 0; stid--) {
    next_node = wchmm->startnode[stid];
    /* compute transition from 'node' at end of word 'sword' to 'next_node' */
    /* skip isolated words already calculated in the above main loop */
    if (wchmm->start2isolate[stid] != -1) continue;
    /* rest should have 1-gram factoring score at wchmm->fscore */
    if (wchmm->state[next_node].scid >= 0) {
      j_internal_error("get_back_trellis_proceed: scid mismatch at 1-gram factoring of shared states\n");
    }
    tmpprob = wchmm->fscore[- wchmm->state[next_node].scid];
    ngram_score_cache = tmpprob * d->lm_weight + d->lm_penalty;
    tmpsum = d->wordend_best_score;
    tmpsum += ngram_score_cache;
    if (wchmm->winfo->is_transparent[sword] && wchmm->winfo->is_transparent[d->wordend_best_last_cword]) {
      tmpsum += d->lm_penalty_trans;
    }

    if (wchmm->hmminfo->multipath) {
      /* since top node has no ouput, we should go one more step further */
      if (wchmm->self_a[next_node] != LOG_ZERO) {
        propagate_token(d, next_node, tmpsum + wchmm->self_a[next_node], d->wordend_best_tre, last_word, ngram_score_cache);
        if (d->expanded) {
          d->expanded = FALSE;
        }
      }
      if (wchmm->next_a[next_node] != LOG_ZERO) {
        propagate_token(d, next_node+1, tmpsum + wchmm->next_a[next_node], d->wordend_best_tre, last_word, ngram_score_cache);
        if (d->expanded) {
          d->expanded = FALSE;
        }
      }
      for(ac=wchmm->ac[next_node];ac;ac=ac->next) {
        for(j=0;j<ac->n;j++) {
          propagate_token(d, ac->arc[j], tmpsum + ac->a[j], d->wordend_best_tre, last_word, ngram_score_cache);
          if (d->expanded) {
            d->expanded = FALSE;
          }
        }
      }
      
    } else {
      propagate_token(d, next_node, tmpsum, d->wordend_best_tre, last_word, ngram_score_cache);
      if (d->expanded) {
        d->expanded = FALSE;
      }
    }

  }
}

#endif /* UNIGRAM_FACTORING */


boolean
get_back_trellis_proceed(int t, HTK_Param *param, RecogProcess *r, boolean final_for_multipath)
{
  /* local static work area for get_back_trellis_proceed() */
  /* these are local work area and need not to be kept for another call */
  TRELLIS_ATOM *tre; 
  int node; 
  int lmtype, lmvar;

  WCHMM_INFO *wchmm;
  FSBeam *d;
  int j;
  TOKEN2  *tk;

  /* local copied variables */
  int tn, tl;

  /* store pointer to local for rapid access */
  wchmm = r->wchmm;
  d = &(r->pass1);
  

  lmtype = r->lmtype;
  lmvar  = r->lmvar;

  /*********************/
  /* 1. ½é´ü²½         */
  /*    initialization */
  /*********************/

  /* tl ¤È tn ¤òÆþ¤ìÂؤ¨¤Æºî¶ÈÎΰè¤òÀÚ¤êÂؤ¨ */
  /* tl (= ľÁ°¤Î tn) ¤ÏľÁ°¥Õ¥ì¡¼¥à¤Î·ë²Ì¤ò»ý¤Ä */
  /* swap tl and tn to switch work buffer */
  /* tl (= last tn) holds result of the previous frame */
  d->tl = d->tn;
  if (d->tn == 0) d->tn = 1; else d->tn = 0;
  
  /* store locally for rapid access */
  tl = d->tl;
  tn = d->tn;

#ifdef UNIGRAM_FACTORING
  /* 1-gram factoring ¤Ç¤Ïñ¸ìÀèƬ¤Ç¤Î¸À¸ì³ÎΨ¤¬°ìÄê¤ÇľÁ°Ã±¸ì¤Ë°Í¸¤·¤Ê¤¤
     ¤¿¤á¡¤Ã±¸ì´Ö Viterbi ¤Ë¤ª¤¤¤ÆÁª¤Ð¤ì¤ëľÁ°Ã±¸ì¤Ï,¼¡Ã±¸ì¤Ë¤è¤é¤º¶¦Ä̤Ǥ¢¤ë. 
     ¤è¤Ã¤Æñ¸ì½ªÃ¼¤«¤éfactoringÃͤΤ¢¤ëñ¸ìÀèƬ¤Ø¤ÎÁ«°Ü¤Ï£±¤Ä¤Ë¤Þ¤È¤á¤é¤ì¤ë. 
     ¤¿¤À¤·¡¤ÌÚ¤«¤éÆÈΩ¤·¤¿Ã±¸ì¤Ë¤Ä¤¤¤Æ¤Ï, ñ¸ìÀèƬ¤ÇÍúÎò¤Ë°Í¸¤·¤¿2-gram¤¬
     Í¿¤¨¤é¤ì¤ë¤¿¤á, ºÇÌà¤Îñ¸ì´Ö Viterbi ¥Ñ¥¹¤Ï¼¡Ã±¸ì¤´¤È¤Ë°Û¤Ê¤ë. 
     ¤è¤Ã¤Æ¤½¤ì¤é¤Ë¤Ä¤¤¤Æ¤Ï¤Þ¤È¤á¤º¤ËÊ̤˷׻»¤¹¤ë */
  /* In 1-gram factoring, the language score on the word-head node is constant
     and independent of the previous word.  So, the same word hypothesis will
     be selected as the best previous word at the inter-word Viterbi
     processing.  So, in inter-word processing, we can (1) select only
     the best word-end hypothesis, and then (2) process viterbi from the node
     to each word-head node.  On the other hand, the isolated words,
     i.e. words not sharing any node with other word, has unique word-head
     node and the true 2-gram language score is determined at the top node.
     In such case the best word hypothesis prior to each node will differ
     according to the language scores.  So we have to deal such words separately. */
  /* initialize max value to delect best word-end hypothesis */
  if (lmtype == LM_PROB) {
    d->wordend_best_score = LOG_ZERO;
  }
#endif

#ifdef DEBUG
  /* debug */
  /* node_check_token(d, tl); */
#endif

  /* ¥È¡¼¥¯¥ó¥Ð¥Ã¥Õ¥¡¤ò½é´ü²½: ľÁ°¥Õ¥ì¡¼¥à¤Ç»È¤ï¤ì¤¿Éôʬ¤À¤±¥¯¥ê¥¢¤¹¤ì¤Ð¤è¤¤ */
  /* initialize token buffer: for speedup, only ones used in the last call will be cleared */
  clear_tokens(d, tl);

  /**************************/
  /* 2. Viterbi·×»»         */
  /*    Viterbi computation */
  /**************************/
  /* ľÁ°¥Õ¥ì¡¼¥à¤«¤é¤³¤Î¥Õ¥ì¡¼¥à¤Ø¤Î Viterbi ·×»»¤ò¹Ô¤Ê¤¦ */
  /* tindex[tl][n_start..n_end] ¤ËľÁ°¥Õ¥ì¡¼¥à¾å°Ì¥Î¡¼¥É¤ÎID¤¬³ÊǼ¤µ¤ì¤Æ¤¤¤ë */
  /* do one viterbi computation from last frame to this frame */
  /* tindex[tl][n_start..n_end] holds IDs of survived nodes in last frame */

  if (wchmm->hmminfo->multipath) {
    /*********************************/
    /* MULTIPATH MODE */
    /*********************************/

    for (j = d->n_start; j <= d->n_end; j++) {
      /* tk: Âоݥȡ¼¥¯¥ó  node: ¤½¤Î¥È¡¼¥¯¥ó¤ò»ý¤ÄÌÚ¹½Â¤²½¼­½ñ¥Î¡¼¥ÉID */
      /* tk: token data  node: lexicon tree node ID that holds the 'tk' */
      tk = &(d->tlist[tl][d->tindex[tl][j]]);
      if (tk->score <= LOG_ZERO) continue; /* invalid node */
      node = tk->node;
      /*********************************/
      /* 2.1. ñ¸ìÆâÁ«°Ü               */
      /*      word-internal transition */
      /*********************************/
      beam_intra_word(wchmm, d, &tk, j);
    }
    /*******************************************************/
    /* 2.2. ¥¹¥³¥¢¤Ç¥È¡¼¥¯¥ó¤ò¥½¡¼¥È¤·¥Ó¡¼¥àÉýʬ¤Î¾å°Ì¤ò·èÄê */
    /*    sort tokens by score up to beam width            */
    /*******************************************************/
    sort_token_no_order(d, r->trellis_beam_width, &(d->n_start), &(d->n_end));
  
    /*************************/
    /* 2.3. ñ¸ì´ÖViterbi·×»»  */
    /*    cross-word viterbi */
    /*************************/
    for(j = d->n_start; j <= d->n_end; j++) {
      tk = &(d->tlist[tn][d->tindex[tn][j]]);
      node = tk->node;
      
      /* Á«°Ü¸µ¥Î¡¼¥É¤¬Ã±¸ì½ªÃ¼¤Ê¤é¤Ð */
      /* if source node is end state of a word, */
      if (wchmm->stend[node] != WORD_INVALID) {

        /**************************/
        /* 2.4. ¥È¥ì¥ê¥¹Ã±¸ìÊݸ  */
        /*      save trellis word */
        /**************************/
#ifdef SPSEGMENT_NAIST
        if (r->config->successive.enabled && !d->after_trigger) {
          tre = tk->last_tre;   /* dummy */
        } else {
          tre = save_trellis(r->backtrellis, wchmm, tk, t, final_for_multipath);
        }
#else
        tre = save_trellis(r->backtrellis, wchmm, tk, t, final_for_multipath);
#endif
        /* ºÇ½ª¥Õ¥ì¡¼¥à¤Ç¤¢¤ì¤Ð¤³¤³¤Þ¤Ç¡§Á«°Ü¤Ï¤µ¤»¤Ê¤¤ */
        /* If this is a final frame, does not do cross-word transition */
        if (final_for_multipath) continue;
        /* ñ¸ìǧ¼±¥â¡¼¥É¤Ç¤Ïñ¸ì´ÖÁ«°Ü¤ÏɬÍפʤ¤ */
        if (lmvar == LM_DFA_WORD) continue;

        /******************************/
        /* 2.5. ñ¸ì´ÖÁ«°Ü            */
        /*      cross-word transition */
        /******************************/

#ifdef UNIGRAM_FACTORING
        /* ¤³¤³¤Ç½èÍý¤µ¤ì¤ë¤Î¤Ï isolated words ¤Î¤ß¡¤
           shared nodes ¤Ï¤Þ¤È¤á¤Æ¤³¤Î¥ë¡¼¥×¤Î³°¤Ç·×»»¤¹¤ë */
        /* Only the isolated words will be processed here.
           The shared nodes with constant factoring values will be computed
           after this loop */
#endif
        beam_inter_word(wchmm, d, &tk, tre, j);

      } /* end of cross-word processing */
    
    } /* end of main viterbi loop */



  } else {

    /*********************************/
    /* NORMAL MODE */
    /*********************************/

    for (j = d->n_start; j <= d->n_end; j++) {
      /* tk: Âоݥȡ¼¥¯¥ó  node: ¤½¤Î¥È¡¼¥¯¥ó¤ò»ý¤ÄÌÚ¹½Â¤²½¼­½ñ¥Î¡¼¥ÉID */
      /* tk: token data  node: lexicon tree node ID that holds the 'tk' */
      tk = &(d->tlist[tl][d->tindex[tl][j]]);
      if (tk->score <= LOG_ZERO) continue; /* invalid node */
      node = tk->node;
      
      /*********************************/
      /* 2.1. ñ¸ìÆâÁ«°Ü               */
      /*      word-internal transition */
      /*********************************/
      beam_intra_word(wchmm, d, &tk, j);

      /* Á«°Ü¸µ¥Î¡¼¥É¤¬Ã±¸ì½ªÃ¼¤Ê¤é¤Ð */
      /* if source node is end state of a word, */
      if (wchmm->stend[node] != WORD_INVALID) {
        
        /**************************/
        /* 2.2. ¥È¥ì¥ê¥¹Ã±¸ìÊݸ  */
        /*      save trellis word */
        /**************************/
#ifdef SPSEGMENT_NAIST
        if (r->config->successive.enabled && !d->after_trigger) {
          tre = tk->last_tre;   /* dummy */
        } else {
          tre = save_trellis(r->backtrellis, wchmm, tk, t, final_for_multipath);
        }
#else
        tre = save_trellis(r->backtrellis, wchmm, tk, t, final_for_multipath);
#endif
        /* ñ¸ìǧ¼±¥â¡¼¥É¤Ç¤Ïñ¸ì´ÖÁ«°Ü¤ÏɬÍפʤ¤ */
        if (lmvar == LM_DFA_WORD) continue;

        /******************************/
        /* 2.3. ñ¸ì´ÖÁ«°Ü            */
        /*      cross-word transition */
        /******************************/
        
#ifdef UNIGRAM_FACTORING
        /* ¤³¤³¤Ç½èÍý¤µ¤ì¤ë¤Î¤Ï isolated words ¤Î¤ß¡¤
           shared nodes ¤Ï¤Þ¤È¤á¤Æ¤³¤Î¥ë¡¼¥×¤Î³°¤Ç·×»»¤¹¤ë */
        /* Only the isolated words will be processed here.
           The shared nodes with constant factoring values will be computed
           after this loop */
#endif

        beam_inter_word(wchmm, d, &tk, tre, j);

      } /* end of cross-word processing */
      
    } /* end of main viterbi loop */


  }

#ifdef UNIGRAM_FACTORING

  if (lmtype == LM_PROB) {

    /***********************************************************/
    /* 2.x ñ¸ì½ªÃ¼¤«¤éfactoringÉÕ¤­Ã±¸ìÀèƬ¤Ø¤ÎÁ«°Ü ***********/
    /*    transition from wordend to shared (factorized) nodes */
    /***********************************************************/
    /* d->wordend_best_* holds the best word ends at this frame. */
    if (d->wordend_best_score > LOG_ZERO) {
      beam_inter_word_factoring(wchmm, d);
    }
  }
#endif /* UNIGRAM_FACTORING */

  /***************************************/
  /* 3. ¾õÂ֤νÐÎϳÎΨ·×»»               */
  /*    compute state output probability */
  /***************************************/

  /* ¼¡ÃʤÎÍ­¸ú¥Î¡¼¥É¤Ë¤Ä¤¤¤Æ½ÐÎϳÎΨ¤ò·×»»¤·¤Æ¥¹¥³¥¢¤Ë²Ã¤¨¤ë */
  /* compute outprob for new valid (token assigned) nodes and add to score */
  /* º£°·¤Ã¤Æ¤¤¤ë¤Î¤¬ÆþÎϤκǽª¥Õ¥ì¡¼¥à¤Î¾ì¹ç½ÐÎϳÎΨ¤Ï·×»»¤·¤Ê¤¤ */
  /* don't calculate the last frame (transition only) */

  if (wchmm->hmminfo->multipath) {
    if (! final_for_multipath) {
      for (j = 0; j < d->tnum[tn]; j++) {
        tk = &(d->tlist[tn][d->tindex[tn][j]]);
        /* skip non-output state */
        if (wchmm->state[tk->node].out.state == NULL) continue;
        tk->score += outprob_style(wchmm, tk->node, tk->last_tre->wid, t, param);
      }
    }
  } else {
    for (j = 0; j < d->tnum[tn]; j++) {
      tk = &(d->tlist[tn][d->tindex[tn][j]]);
      tk->score += outprob_style(wchmm, tk->node, tk->last_tre->wid, t, param);
    }
  }

  /*******************************************************/
  /* 4. ¥¹¥³¥¢¤Ç¥È¡¼¥¯¥ó¤ò¥½¡¼¥È¤·¥Ó¡¼¥àÉýʬ¤Î¾å°Ì¤ò·èÄê */
  /*    sort tokens by score up to beam width            */
  /*******************************************************/

  /* tlist[tl]¤ò¼¡ÃʤΤ¿¤á¤Ë¥ê¥»¥Ã¥È */
  clear_tlist(d, tl);

  /* ¥Ò¡¼¥×¥½¡¼¥È¤òÍѤ¤¤Æ¤³¤ÎÃʤΥΡ¼¥É½¸¹ç¤«¤é¾å°Ì(bwidth)¸Ä¤òÆÀ¤Æ¤ª¤¯ */
  /* (¾å°ÌÆâ¤Î½çÎó¤ÏɬÍפʤ¤) */
  sort_token_no_order(d, r->trellis_beam_width, &(d->n_start), &(d->n_end));
  /***************/
  /* 5. ½ªÎ»½èÍý */
  /*    finalize */
  /***************/

#ifdef SPSEGMENT_NAIST
  if (!r->config->successive.enabled || d->after_trigger) {
#endif

    /* call frame-wise callback */
    r->have_interim = FALSE;
    if (t > 0) {
      if (r->config->output.progout_flag) {
        /* Á²¼¡½ÐÎÏ: ¸½¥Õ¥ì¡¼¥à¤Î¥Ù¥¹¥È¥Ñ¥¹¤ò°ìÄê»þ´Ö¤ª¤­¤Ë¾å½ñ¤­½ÐÎÏ */
        /* progressive result output: output current best path in certain time interval */
        if (((t-1) % r->config->output.progout_interval_frame) == 0) {
          r->have_interim = TRUE;
          bt_current_max(r, t-1);
        }
      }
    }
    
    /* jlog("DEBUG: %d: %d\n",t,tnum[tn]); */
    /* for debug: output current max word */
    if (debug2_flag) {
      bt_current_max_word(r, t-1);
    }

#ifdef DETERMINE
    if (lmvar == LM_DFA_WORD) {
      check_determine_word(r, t-1);
    }
#endif

#ifdef SPSEGMENT_NAIST
  }
#endif
    
  /* ¥Ó¡¼¥àÆâ¥Î¡¼¥É¿ô¤¬ 0 ¤Ë¤Ê¤Ã¤Æ¤·¤Þ¤Ã¤¿¤é¡¤¶¯À©½ªÎ» */
  if (d->tnum[tn] == 0) {
    jlog("ERROR: get_back_trellis_proceed: %02d %s: frame %d: no nodes left in beam, now terminates search\n", r->config->id, r->config->name, t);
    return(FALSE);
  }

  return(TRUE);
    
}

/*************************************************/
/* frame synchronous beam search --- last frame  */
/* ¥Õ¥ì¡¼¥àƱ´ü¥Ó¡¼¥àõº÷¤Î¼Â¹Ô --- ºÇ½ª¥Õ¥ì¡¼¥à */
/*************************************************/

void
get_back_trellis_end(HTK_Param *param, RecogProcess *r)
{
  WCHMM_INFO *wchmm;
  FSBeam *d;
  int j;
  TOKEN2 *tk;

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

  /* ºÇ¸å¤Ë¥Ó¡¼¥àÆâ¤Ë»Ä¤Ã¤¿Ã±¸ì½ªÃ¼¥È¡¼¥¯¥ó¤ò½èÍý¤¹¤ë */
  /* process the last wordend tokens */


  if (r->am->hmminfo->multipath) {
    /* MULTI-PATH VERSION */

    /* ñ¸ìËö¥Î¡¼¥É¤Ø¤ÎÁ«°Ü¤Î¤ß·×»» */
    /* only arcs to word-end node is calculated */
    get_back_trellis_proceed(param->samplenum, param, r, TRUE);

  } else {
    /* NORMAL VERSION */

    /* ºÇ¸å¤ÎÁ«°Ü¤Î¤¢¤È¤Îñ¸ì½ªÃ¼½èÍý¤ò¹Ô¤¦ */
    /* process the word-ends at the last frame */
    d->tl = d->tn;
    if (d->tn == 0) d->tn = 1; else d->tn = 0;
    for (j = d->n_start; j <= d->n_end; j++) {
      tk = &(d->tlist[d->tl][d->tindex[d->tl][j]]);
      if (wchmm->stend[tk->node] != WORD_INVALID) {
        save_trellis(r->backtrellis, wchmm, tk, param->samplenum, TRUE);
      }
    }

  }
    
}

/*************************/
/* õº÷½ªÎ» --- ½ªÎ»½èÍý */
/* end of search         */
/*************************/
void
finalize_1st_pass(RecogProcess *r, int len)
{
  BACKTRELLIS *backtrellis;

  backtrellis = r->backtrellis;
 
  backtrellis->framelen = len;

  /* ñ¸ì¥È¥ì¥ê¥¹(backtrellis) ¤òÀ°Íý: ¥È¥ì¥ê¥¹Ã±¸ì¤ÎºÆÇÛÃ֤ȥ½¡¼¥È */
  /* re-arrange backtrellis: index them by frame, and sort by word ID */

  bt_relocate_rw(backtrellis);
  bt_sort_rw(backtrellis);
  if (backtrellis->num == NULL) {
    if (backtrellis->framelen > 0) {
      jlog("WARNING: %02d %s: input processed, but no survived word found\n", r->config->id, r->config->name);
    }
    /* reognition failed */
    r->result.status = J_RESULT_STATUS_FAIL;
    return;
  }

  /* Âè1¥Ñ¥¹¤Î¥Ù¥¹¥È¥Ñ¥¹¤ò·ë²Ì¤Ë³ÊǼ¤¹¤ë */
  /* store 1st pass result (best hypothesis) to result */
  if (r->lmvar == LM_DFA_WORD) {
    find_1pass_result_word(len, r);
  } else {
    find_1pass_result(len, r);
  }
}

void
fsbeam_free(FSBeam *d)
{
  free_nodes(d);
  if (d->pausemodelnames != NULL) {
    free(d->pausemodelnames);
    free(d->pausemodel);
  }
}

/* end of file */

---