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

#ifndef PASS2_STRICT_IWCD

#undef TCD                      

/**********************************************************************/
/************ ²¾Àâ¥Î¡¼¥É¤Î´ðËÜÁàºî                         ************/
/************ Basic functions for hypothesis node handling ************/
/**********************************************************************/

#undef STOCKER_DEBUG

#ifdef STOCKER_DEBUG
static int stocked_num = 0;
static int reused_num = 0;
static int new_num = 0;
static int request_num = 0;
#endif

static void
free_node_exec(NODE *node)
{
  if (node == NULL) return;

  free(node->g);
  if (node->g_prev != NULL) free(node->g_prev);
#ifdef GRAPHOUT_PRECISE_BOUNDARY
  if (node->region->graphout) {
    free(node->wordend_frame);
    free(node->wordend_gscore);
  }
#endif

  free(node);
}

void
free_node(NODE *node)
{
  if (node == NULL) return;

  if (node->region->graphout) {
    if (node->prevgraph != NULL && node->prevgraph->saved == FALSE) {
      wordgraph_free(node->prevgraph);
    }
  }

  /* save to stocker */
  node->next = node->region->pass2.stocker_root;
  node->region->pass2.stocker_root = node;

#ifdef STOCKER_DEBUG
  stocked_num++;
#endif
}

void
clear_stocker(StackDecode *s)
{
  NODE *node, *tmp;
  node = s->stocker_root;
  while(node) {
    tmp = node->next;
    free_node_exec(node);
    node = tmp;
  }
  s->stocker_root = NULL;

#ifdef STOCKER_DEBUG
  jlog("DEBUG: %d times requested, %d times newly allocated, %d times reused\n", request_num, new_num, reused_num);
  stocked_num = 0;
  reused_num = 0;
  new_num = 0;
  request_num = 0;
#endif
}

NODE *
cpy_node(NODE *dst, NODE *src)
{
  int peseqlen;

  peseqlen = src->region->peseqlen;
  
  dst->next = src->next;
  dst->prev = src->prev;
  memcpy(dst->g, src->g, sizeof(LOGPROB) * peseqlen);
  memcpy(dst->seq, src->seq, sizeof(WORD_ID) * MAXSEQNUM);
#ifdef CM_SEARCH
#ifdef CM_MULTIPLE_ALPHA
  {
    int w;
    for(w=0;w<src->seqnum;w++) {
      memcpy(dst->cmscore[w], src->cmscore[w], sizeof(LOGPROB) * src->region->config->annotate.cm_alpha_num);
    }
  }     
#else
  memcpy(dst->cmscore, src->cmscore, sizeof(LOGPROB) * MAXSEQNUM);
#endif
#endif /* CM_SEARCH */
  dst->seqnum = src->seqnum;
  dst->score = src->score;
  dst->bestt = src->bestt;
  dst->estimated_next_t = src->estimated_next_t;
  dst->endflag = src->endflag;
  dst->state = src->state;
  dst->tre = src->tre;
  if (src->g_prev != NULL) { // ccd_flag == TRUE
    memcpy(dst->g_prev, src->g_prev, sizeof(LOGPROB) * peseqlen);
    dst->last_ph = src->last_ph;
    dst->last_ph_sp_attached = src->last_ph_sp_attached;
    dst->lscore = src->lscore;
  }
  dst->totallscore = src->totallscore;
  dst->final_g = src->final_g;
#ifdef VISUALIZE
  dst->popnode = src->popnode;
#endif

  if (src->region->graphout) {
#ifdef GRAPHOUT_PRECISE_BOUNDARY
    memcpy(dst->wordend_frame, src->wordend_frame, sizeof(short) * peseqlen);
    memcpy(dst->wordend_gscore, src->wordend_gscore, sizeof(LOGPROB) * peseqlen);
#endif
    dst->prevgraph = src->prevgraph;
    dst->lastcontext = src->lastcontext;
#ifndef GRAPHOUT_PRECISE_BOUNDARY
    dst->tail_g_score = src->tail_g_score;
#endif
  }

  return(dst);
}

NODE *
newnode(RecogProcess *r)
{
  NODE *tmp;
  int i;
  int peseqlen;

  peseqlen = r->peseqlen;

#ifdef STOCKER_DEBUG
  request_num++;
#endif
  if ((tmp = r->pass2.stocker_root) != NULL) {
    /* re-use ones in the stocker */
    r->pass2.stocker_root = tmp->next;
#ifdef STOCKER_DEBUG
    stocked_num--;
    reused_num++;
#endif
  } else {
    /* allocate new */
    tmp =(NODE *)mymalloc(sizeof(NODE));
    tmp->g = (LOGPROB *)mymalloc(sizeof(LOGPROB) * peseqlen);
    if (r->ccd_flag) {
      tmp->g_prev = (LOGPROB *)mymalloc(sizeof(LOGPROB) * peseqlen);
    } else {
      tmp->g_prev = NULL;
    }

#ifdef GRAPHOUT_PRECISE_BOUNDARY
    if (r->graphout) {
      tmp->wordend_frame = (short *)mymalloc(sizeof(short) * peseqlen);
      tmp->wordend_gscore = (LOGPROB *)mymalloc(sizeof(LOGPROB) * peseqlen);
    }
#endif
#ifdef STOCKER_DEBUG
    new_num++;
#endif
  }

  /* clear the data */
  /*bzero(tmp,sizeof(NODE));*/
  tmp->next=NULL;
  tmp->prev=NULL;
  tmp->last_ph = NULL;
  tmp->last_ph_sp_attached = FALSE;
  if (r->ccd_flag) {
    if (r->lmtype == LM_PROB) {
      tmp->lscore = LOG_ZERO;
      tmp->totallscore = LOG_ZERO;
    } else if (r->lmtype == LM_DFA) {
      tmp->lscore = 0.0;
      tmp->totallscore = 0.0;
    }
  }
  tmp->endflag = FALSE;
  tmp->seqnum = 0;
  for(i=0;i<peseqlen;i++) {
    tmp->g[i] = LOG_ZERO;
  }
  if (r->ccd_flag) {
    for(i=0;i<peseqlen;i++) {
      tmp->g_prev[i] = LOG_ZERO;
    }
  }
  tmp->final_g = LOG_ZERO;
#ifdef VISUALIZE
  tmp->popnode = NULL;
#endif
  tmp->tre = NULL;

  if (r->graphout) {
    tmp->prevgraph = NULL;
    tmp->lastcontext = NULL;
  }

  tmp->region = r;

  return(tmp);
}


/**********************************************************************/
/************ Á°¸þ¤­¥È¥ì¥ê¥¹Å¸³«¤ÈÌàÅÙ·×»»              ***************/
/************ Expand trellis and update forward viterbi ***************/
/**********************************************************************/

static LOGPROB *wordtrellis[2]; 
static int tn;                 
static int tl;                 
static LOGPROB *g;              
static HMM_Logical **phmmseq;   
static int phmmlen_max;         
static boolean *has_sp;         

#ifdef GRAPHOUT_PRECISE_BOUNDARY
static short *wend_token_frame[2]; 
static LOGPROB *wend_token_gscore[2]; 
#endif

void
malloc_wordtrellis(RecogProcess *r)
{
  int maxwn;

  maxwn = r->lm->winfo->maxwn + 10;
  wordtrellis[0] = (LOGPROB *)mymalloc(sizeof(LOGPROB) * maxwn);
  wordtrellis[1] = (LOGPROB *)mymalloc(sizeof(LOGPROB) * maxwn);

  g = (LOGPROB *)mymalloc(sizeof(LOGPROB) * r->peseqlen);

  phmmlen_max = r->lm->winfo->maxwlen + 2;
  phmmseq = (HMM_Logical **)mymalloc(sizeof(HMM_Logical *) * phmmlen_max);
  if (r->am->hmminfo->multipath) {
    has_sp = (boolean *)mymalloc(sizeof(boolean) * phmmlen_max);
  } else {
    has_sp = NULL;
  }

  wend_token_frame[0] = NULL;
  wend_token_frame[1] = NULL;
  wend_token_gscore[0] = NULL;
  wend_token_gscore[1] = NULL;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
  if (r->graphout) {
    wend_token_frame[0] = (short *)mymalloc(sizeof(short) * maxwn);
    wend_token_frame[1] = (short *)mymalloc(sizeof(short) * maxwn);
    wend_token_gscore[0] = (LOGPROB *)mymalloc(sizeof(LOGPROB) * maxwn);
    wend_token_gscore[1] = (LOGPROB *)mymalloc(sizeof(LOGPROB) * maxwn);
  }
#endif
  
}

void
free_wordtrellis()
{
  int i;

  free(wordtrellis[0]);
  free(wordtrellis[1]);
  free(g);
  free(phmmseq);
  if (has_sp) {
    free(has_sp);
    has_sp = NULL;
  }
#ifdef GRAPHOUT_PRECISE_BOUNDARY
  for(i=0;i<2;i++) {
    if (wend_token_frame[i]) {
      free(wend_token_frame[i]);
      wend_token_frame[i] = NULL;
    }
    if (wend_token_gscore[i]) {
      free(wend_token_gscore[i]);
      wend_token_gscore[i] = NULL;
    }
  }
#endif
}


/**********************************************************************/
/************ ²¾Àâ¤ÎÁ°¸þ¤­ÌàÅÙ·×»»                  *******************/
/************ Compute forward score of a hypothesis *******************/
/**********************************************************************/

static LOGPROB
get_max_out_arc(HTK_HMM_Trans *tr, int state_num)
{
  LOGPROB max_a;
  int afrom;
  LOGPROB a;
  
  max_a = LOG_ZERO;
  for (afrom = 0; afrom < state_num - 1; afrom++) {
    a = tr->a[afrom][state_num-1];
    if (max_a < a) max_a = a;
  }
  return(max_a);
}

static LOGPROB
max_out_arc(HMM_Logical *l)
{
  return(get_max_out_arc(hmm_logical_trans(l), hmm_logical_state_num(l)));
}

void
scan_word(NODE *now, HTK_Param *param, RecogProcess *r)
{
  int   i,t, j;
  HMM *whmm;
  A_CELL *ac;
  WORD_ID word;
  LOGPROB tmpmax, tmptmp, score1;
  int startt = 0, endt;
  int wordhmmnum;
  LOGPROB tmpmax_store, store_point_maxarc; /* multipath */
  LOGPROB tmpmax2 = LOG_ZERO;
  int phmmlen;
  HMM_Logical *ret, *wend;
  int store_point;
  int crossword_point = 0;
  boolean back_rescan = FALSE;
  boolean node_exist_p;

  /* store global values to local for rapid access */
  WORD_INFO *winfo;
  HTK_HMM_INFO *hmminfo;
  LOGPROB *framemaxscore;
  int peseqlen;
  boolean ccd_flag;
  boolean enable_iwsp;
#ifdef SCAN_BEAM
  LOGPROB scan_beam_thres;
#endif

  winfo = r->lm->winfo;
  hmminfo = r->am->hmminfo;
  peseqlen = r->peseqlen;
  framemaxscore = r->pass2.framemaxscore;
  ccd_flag = r->ccd_flag;
  enable_iwsp = r->lm->config->enable_iwsp; /* multipath */
#ifdef SCAN_BEAM
  scan_beam_thres = r->config->pass2.scan_beam_thres;
#endif

  if (hmminfo->multipath) {
    store_point = -1;
  } else {
    store_point = 0;
  }
  
  /* ----------------------- prepare HMM ----------------------- */

  if (ccd_flag) {
    /* ľÁ°¤Î²»ÁǤ¬¤¢¤ì¤Ð¡¤¤½¤³¤Þ¤Ç¤µ¤«¤Î¤Ü¤Ã¤Æ scan ¤¹¤ë */
    /* if there are any last phone, enable backscan */
    if (now->last_ph == NULL) {
      /* initial score: now->g[] */
      /* scan range: phones in now->seq[now->seqnum-1] */
      back_rescan = FALSE;
    } else {
      /* initial score: now->g_prev[] (1-phone before)*/
      /* scan range: phones in now->seq[now->seqnum-1] + now->last_ph */
      back_rescan = TRUE;
    }
  }
#ifdef TCD
  if (now->last_ph != NULL) {
    jlog("DEBUG: inherited last_ph: %s\n", (now->last_ph)->name);
    if (now->last_ph_sp_attached) jlog("DEBUG: (sp attached)\n"); /* multipath */
  } else {
    jlog("DEBUG: no last_ph inherited\n");
  }
#endif

  /* scan ÈÏ°Ïʬ¤ÎHMM¤ò½àÈ÷ */
  /* prepare HMM of the scan range */
  word = now->seq[now->seqnum-1];

  if (ccd_flag) {

    if (back_rescan) {
      
      /* scan range: phones in now->seq[now->seqnum-1] + now->last_ph */
      
      phmmlen = winfo->wlen[word] + 1;
      if (phmmlen > phmmlen_max) {
        j_internal_error("scan_word: num of phonemes in a word exceed phmmlenmax (%d) ?\n", phmmlen_max);
      }
      for (i=0;i<phmmlen - 2;i++) phmmseq[i] = winfo->wseq[word][i];
      if (hmminfo->multipath) {
        for (i=0;i<phmmlen - 2;i++) has_sp[i] = FALSE;
      }

      /* ºÇ½ªÃ±¸ì¤È last_ph ´Ö¤Îñ¸ì´Ötriphone¤ò¹Íθ */
      /* consider cross-word context dependency between the last word and now->last_ph */
      wend = winfo->wseq[word][winfo->wlen[word]-1];
      ret = get_right_context_HMM(wend, now->last_ph->name, hmminfo);
      if (ret == NULL) {        /* triphone not found */
        /* fallback to the original bi/mono-phone */
        /* error if the original is pseudo phone (not explicitly defined
           in hmmdefs/hmmlist) */
        /* exception: word with 1 phone (triphone may exist in the next expansion */
        if (winfo->wlen[word] > 1 && wend->is_pseudo) {
          error_missing_right_triphone(wend, now->last_ph->name);
        }
        phmmseq[phmmlen-2] = wend;
      } else {
        phmmseq[phmmlen-2] = ret;
      }
      ret = get_left_context_HMM(now->last_ph, wend->name, hmminfo);
      if (ret == NULL) {
        /* fallback to the original bi/mono-phone */
        /* error if the original is pseudo phone (not explicitly defined
           in hmmdefs/hmmlist) */
        if (now->last_ph->is_pseudo) {
          error_missing_left_triphone(now->last_ph, wend->name);
        }
        phmmseq[phmmlen-1] = now->last_ph;
      } else {
        phmmseq[phmmlen-1] = ret;
      }

      if (hmminfo->multipath) {
        has_sp[phmmlen-2] = has_sp[phmmlen-1] = FALSE;
        if (enable_iwsp) {
          has_sp[phmmlen-2] = TRUE;
          if (now->last_ph_sp_attached) {
            has_sp[phmmlen-1] = TRUE;
          }
        }
      }
 
#ifdef TCD
      jlog("DEBUG: w=");
      for(i=0;i<winfo->wlen[word];i++) {
        jlog(" %s",(winfo->wseq[word][i])->name);
        if (hmminfo->multipath && has_sp[i]) jlog("(sp)");
      }
      jlog(" | %s\n", (now->last_ph)->name);
      if (hmminfo->multipath && now->last_ph_sp_attached) jlog("DEBUG:   (sp)\n");
      jlog("DEBUG: scan for:");
      
      for (i=0;i<phmmlen;i++) {
        jlog(" %s", phmmseq[i]->name);
        if (hmminfo->multipath && has_sp[i]) jlog("(sp)");
      }
      jlog("\n");
#endif

      /* ñ¸ìHMM¤òºî¤ë */
      /* make word HMM */
      whmm = new_make_word_hmm(hmminfo, phmmseq, phmmlen, hmminfo->multipath ? has_sp : NULL);
      if (whmm == NULL) {
        j_internal_error("Error: failed to make word hmm for word #%d \"%s [%s]\"\n", word, winfo->wname[word], winfo->woutput[word]);
      }
      
      /* backscan ¤Ê¤Î¤Ç¡¤·×»»Á°¤Î g[] ½é´üÃÍ¤Ï now->g_prev[] ¤ò»ÈÍÑ */
      /* As backscan enabled, the initial forward score g[] is set by
         now->g_prev[] */
      for (t=0;t<peseqlen;t++) {
        g[t]=now->g_prev[t];

      }
      
      /* ¼¡ÃÊÍѤÎg_prev¤ò³ÊǼ¤¹¤ë¥Î¡¼¥É°ÌÃÖ¤òÀßÄê */
      /* set where to store scores as new g_prev[] for the next backscan
         in the HMM */
      if (hmminfo->multipath) {
        store_point = hmm_logical_state_num(phmmseq[0]) - 2;
        store_point_maxarc = max_out_arc(phmmseq[0]);
        if (enable_iwsp && has_sp[0]) {
          store_point += hmm_logical_state_num(hmminfo->sp) - 2;
          if (store_point_maxarc < max_out_arc(hmminfo->sp)) {
            store_point_maxarc = max_out_arc(hmminfo->sp);
          }
        }
      } else {
        store_point = hmm_logical_state_num(phmmseq[0]) - 2 - 1;
      }
      /* scanÃæ¤ËľÁ°Ã±¸ì¤È¤³¤Îñ¸ì¤ò¤Þ¤¿¤°¾ì½ê¤òÀßÄê */
      /* set where is the connection point of the last word in the HMM */
      if (hmminfo->multipath) {
        crossword_point = whmm->len - hmm_logical_state_num(phmmseq[phmmlen-1]);
        if (enable_iwsp && has_sp[phmmlen-1]) {
          crossword_point -= hmm_logical_state_num(hmminfo->sp) - 2;
        }
      } else {
        crossword_point = whmm->len - (hmm_logical_state_num(phmmseq[phmmlen-1]) - 2) - 1;
      }
      
    } else {                    /* not backscan mode */
      
      /* scan range: phones in now->seq[now->seqnum-1] */
      
#ifdef TCD
      jlog("DEBUG: scan(org):");
      for (i=0;i<winfo->wlen[word];i++) {
        jlog(" %s", (winfo->wseq[word][i])->name);
      }
      jlog("\n");
#endif

      if (hmminfo->multipath) {
        /* ɬÍפʤé¤Ð¥·¥ç¡¼¥È¥Ý¡¼¥º¤ò¶´¤ß¹þ¤à°ÌÃÖ¤ò»ØÄꤹ¤ë */
        for(i=0;i<winfo->wlen[word];i++) {
          has_sp[i] = FALSE;
        }
        if (enable_iwsp) {
          has_sp[winfo->wlen[word]-1] = TRUE;
        }
      }
      
      /* ñ¸ìHMM¤òºî¤ë */
      /* make word HMM */
      whmm = new_make_word_hmm(hmminfo, winfo->wseq[word], winfo->wlen[word], hmminfo->multipath ? has_sp : NULL);
      if (whmm == NULL) {
        j_internal_error("Error: failed to make word hmm for word #%d \"%s [%s]\"\n", word, winfo->wname[word], winfo->woutput[word]);
      }
      
      /* ·×»»Á°¤Î g[] ½é´üÃÍ¤Ï now->g[] ¤ò»ÈÍÑ */
      /* the initial forward score g[] is set by now->g[] */
      for (t=0;t<peseqlen;t++) {
        g[t]=now->g[t];
      }
      
      /* ¼¡ÃÊÍѤÎg_prev¤ò³ÊǼ¤¹¤ë¥Î¡¼¥É°ÌÃÖ¤òÀßÄê */
      /* set where to store scores as new g_prev[] for the next backscan
         in the HMM */
      if (hmminfo->multipath) {
        store_point = hmm_logical_state_num(winfo->wseq[word][0]) - 2;
        store_point_maxarc = max_out_arc(winfo->wseq[word][0]);
        if (enable_iwsp && has_sp[0]) {
          store_point += hmm_logical_state_num(hmminfo->sp) - 2;
          if (store_point_maxarc < max_out_arc(hmminfo->sp)) {
            store_point_maxarc = max_out_arc(hmminfo->sp);
          }
        }
      } else {
        store_point = hmm_logical_state_num(winfo->wseq[word][0]) - 2 - 1;
      }

      /* scanÃæ¤ËľÁ°Ã±¸ì¤È¤³¤Îñ¸ì¤ò¤Þ¤¿¤°¾ì½ê¤Ï¡¤¤Ê¤· */
      /* the connection point of the last word is not exist in the HMM */
      crossword_point = -1;
    }
    
  } else {                      /* ccd_flag == FALSE */

    if (hmminfo->multipath) {
      /* ɬÍפʤé¤Ð¥·¥ç¡¼¥È¥Ý¡¼¥º¤ò¶´¤ß¹þ¤à°ÌÃÖ¤ò»ØÄꤹ¤ë */
      for(i=0;i<winfo->wlen[word];i++) {
        has_sp[i] = FALSE;
      }
      if (enable_iwsp) {
        has_sp[winfo->wlen[word]-1] = TRUE;
      }
    }

    /* ²»ÁǴĶ­Èó°Í¸¤Î¾ì¹ç¤Ïñ½ã¤ËºÇ½ªÃ±¸ìʬ¤Î HMM ¤òºîÀ® */
    /* for monophone: simple make HMM for the last word */
    whmm = new_make_word_hmm(hmminfo, winfo->wseq[word], winfo->wlen[word], hmminfo->multipath ? has_sp : NULL);
    if (whmm == NULL) {
      j_internal_error("Error: failed to make word hmm for word #%d \"%s [%s]\"\n", word, winfo->wname[word], winfo->woutput[word]);
    }

    /* ·×»»Á°¤Î g[] ½é´üÃÍ¤Ï now->g[] ¤ò»ÈÍÑ */
    /* the initial forward score g[] is set by now->g[] */
    for (t=0;t<peseqlen;t++) {
      g[t]=now->g[t];
    }
    
  }

#ifdef TCD
  jlog("DEBUG: whmm len   = %d\n",whmm->len);
  jlog("DEBUG: crossword_point = %d\n", crossword_point);
  jlog("DEBUG: g[] store point = %d\n", store_point);
#endif

  wordhmmnum = whmm->len;
  if (wordhmmnum >= winfo->maxwn + 10) {
    j_internal_error("scan_word: word too long (>%d)\n", winfo->maxwn + 10);
  }

#ifndef GRAPHOUT_PRECISE_BOUNDARY
  if (r->graphout) {
    if (ccd_flag) {
      now->tail_g_score = now->g[now->bestt];
    }
  }
#endif

  /* ----------------------- do scan ----------------------- */
  
  /* scan³«»ÏÅÀ¤ò¸¡º÷ -> startt¤Ø*/
  /* search for the start frame -> set to startt */
  for(t = peseqlen-1; t >=0 ; t--) {
    if (
#ifdef SCAN_BEAM
        g[t] > framemaxscore[t] - scan_beam_thres &&
#endif
        g[t] > LOG_ZERO) {
      break;
    }
  }
  if (t < 0) {                  /* no node has score > LOG_ZERO */
    for(t=0;t<peseqlen;t++) {
      if (ccd_flag) now->g_prev[t] = LOG_ZERO;
      now->g[t] = LOG_ZERO;
    }
#ifdef GRAPHOUT_PRECISE_BOUNDARY
    if (r->graphout) {
      for(t=0;t<peseqlen;t++) {
        now->wordend_frame[t] = -1;
        now->wordend_gscore[t] = LOG_ZERO;
      }
    }
#endif
    goto end_of_scan;
  }
  startt = t;
  
  /* clear [startt+1..peseqlen-1] */
  for(t=peseqlen-1;t>startt;t--) {
    if (ccd_flag) now->g_prev[t] = LOG_ZERO;
    now->g[t] = LOG_ZERO;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
    if (r->graphout) {
      now->wordend_frame[t] = -1;
      now->wordend_gscore[t] = LOG_ZERO;
    }
#endif
  }

  /* ¥Ð¥Ã¥Õ¥¡¥Ý¥¤¥ó¥¿½é´ü²½ */
  tn = 0; tl = 1;

#ifdef GRAPHOUT_PRECISE_BOUNDARY
  if (r->graphout) {
    for(i=0;i<wordhmmnum;i++) {
      wend_token_frame[tn][i] = -1;
      wend_token_gscore[tn][i] = LOG_ZERO;
    }
  }
#endif
  
  if (! hmminfo->multipath) {
    /* Below initialization is not needed on multipath version, since
       the actual viterbi will begin at frame 0 in multipath mode in main loop */
    
    /* »þ´Ö [startt] ¾å¤ÎÃͤò½é´ü²½ */
    /* initialize scores on frame [startt] */
    for(i=0;i<wordhmmnum-1;i++) wordtrellis[tn][i] = LOG_ZERO;
    wordtrellis[tn][wordhmmnum-1] = g[startt] + outprob(&(r->am->hmmwrk), startt, &(whmm->state[wordhmmnum-1]), param);
    if (ccd_flag) {
      now->g_prev[startt] = wordtrellis[tn][store_point];
    }
    now->g[startt] = wordtrellis[tn][0];
    
#ifdef GRAPHOUT_PRECISE_BOUNDARY
    if (r->graphout) {
      if (ccd_flag) {
        if (back_rescan) {
          if (wordhmmnum-1 == crossword_point) {
            wend_token_frame[tn][wordhmmnum-1] = startt;
            wend_token_gscore[tn][wordhmmnum-1] = g[startt];
          } else {
            wend_token_frame[tn][wordhmmnum-1] = -1;
            wend_token_gscore[tn][wordhmmnum-1] = LOG_ZERO;
          }
        } else {
          wend_token_frame[tn][wordhmmnum-1] = startt;
          wend_token_gscore[tn][wordhmmnum-1] = g[startt];
        }
      } else {
        wend_token_frame[tn][wordhmmnum-1] = startt;
        wend_token_gscore[tn][wordhmmnum-1] = g[startt];
      }
      now->wordend_frame[startt] = wend_token_frame[tn][0];
      now->wordend_gscore[startt] = wend_token_gscore[tn][0];
    }
#endif
  } /* end of hmminfo->multipath */
  
  endt = startt;

  /* ¥á¥¤¥ó¥ë¡¼¥×: startt ¤«¤é»Ï¤Þ¤ê 0 ¤Ë¸þ¤«¤Ã¤Æ Viterbi ·×»» */
  /* main loop: start from [startt], and compute Viterbi toward [0] */
  for(t = hmminfo->multipath ? startt : startt - 1; t >= 0; t--) {
    
    /* wordtrellis¤Î¥ï¡¼¥¯¥¨¥ê¥¢¤ò¥¹¥ï¥Ã¥× */
    i = tn; tn = tl; tl = i;
    
    node_exist_p = FALSE;       /* TRUE if there is at least 1 survived node in this frame */

    if (hmminfo->multipath) {

      /* ü¤Î¥Î¡¼¥É [t][wordhmmnum-1]¤Ï g[] ¤ò»²¾È¤¹¤ë */
      /* the edge node [t][wordhmmnum-1] is equal to g[] */

      /* ¥Î¡¼¥É [t][wordhmmnum-2..0] ¤Ë¤Ä¤¤¤Æ¥È¥ì¥ê¥¹¤ò·×»» */
      /* expand trellis for node [t][wordhmmnum-2..0] */
      tmpmax_store = LOG_ZERO;

    } else {
    
      /* ü¤Î¥Î¡¼¥É [t][wordhmmnum-1]¤Ï¡¤ÆâÉôÁ«°Ü ¤« g[]¤Î¹â¤¤Êý¤Ë¤Ê¤ë */
      /* the edge node [t][wordhmmnum-1] is either internal transitin or g[] */
      tmptmp = LOG_ZERO;
      for (ac=whmm->state[wordhmmnum-1].ac;ac;ac=ac->next) {
        score1 = wordtrellis[tl][ac->arc] + ac->a;
        if (tmptmp < score1) {
          j = ac->arc;
          tmptmp = score1;
        }
      }
      if (g[t] > tmptmp) {
        tmpmax = g[t];
#ifdef GRAPHOUT_PRECISE_BOUNDARY
        if (r->graphout) {
          if (!back_rescan || wordhmmnum-1 == crossword_point) {
            wend_token_frame[tn][wordhmmnum-1] = t;
            wend_token_gscore[tn][wordhmmnum-1] = g[t];
          } else {
            wend_token_frame[tn][wordhmmnum-1] = wend_token_frame[tl][j];
            wend_token_gscore[tn][wordhmmnum-1] = wend_token_gscore[tl][j];
          }
        }
#endif
      } else {
        tmpmax = tmptmp;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
        if (r->graphout) {
          wend_token_frame[tn][wordhmmnum-1] = wend_token_frame[tl][j];
          wend_token_gscore[tn][wordhmmnum-1] = wend_token_gscore[tl][j];
        }
#endif
      }

      /* ü¤Î¥Î¡¼¥É¤Î¥¹¥³¥¢¥¨¥ó¥Ù¥í¡¼¥×¥Á¥§¥Ã¥¯: °ìÄêÉý³°¤Ê¤éÍî¤È¤¹ */
      /* check if the edge node is within score envelope */
      if (
#ifdef SCAN_BEAM
          tmpmax <= framemaxscore[t] - scan_beam_thres ||
#endif
          tmpmax <= LOG_ZERO
          ) {
        wordtrellis[tn][wordhmmnum-1] = LOG_ZERO;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
        if (r->graphout) {
          wend_token_frame[tn][wordhmmnum-1] = -1;
          wend_token_gscore[tn][wordhmmnum-1] = LOG_ZERO;
        }
#endif
      } else {
        node_exist_p = TRUE;
        wordtrellis[tn][wordhmmnum-1] = tmpmax + outprob(&(r->am->hmmwrk), t, &(whmm->state[wordhmmnum-1]), param);
      }

    } /* end of ~multipath */

    /* ¥Î¡¼¥É [t][wordhmmnum-2..0] ¤Ë¤Ä¤¤¤Æ¥È¥ì¥ê¥¹¤ò·×»» */
    /* expand trellis for node [t][wordhmmnum-2..0] */
    for(i=wordhmmnum-2;i>=0;i--) {

      if (ccd_flag) {

        /* ºÇÌà¥Ñ¥¹¤ÈºÇÌॹ¥³¥¢ tmpmax ¤ò¸«¤Ä¤±¤ë */
        /* tmpmax2 ¤Ï¼¡²óÍÑ g_prev[] ¤Î¤¿¤á¤ÎºÇÂçÃÍ(¼«¸ÊÁ«°Ü¤ò½ü¤¤¤¿ºÇÂçÃÍ) */
        /* find most likely path and the max score 'tmpmax' */
        /* 'tmpmax2' is max score excluding self transition, for next g_prev[] */
        if (! hmminfo->multipath) {
          if (i == store_point) {
            tmpmax2 = LOG_ZERO;
          }
        }
        tmpmax = LOG_ZERO;
        for (ac=whmm->state[i].ac;ac;ac=ac->next) {
          if (hmminfo->multipath) {
            if (ac->arc == wordhmmnum-1) score1 = g[t];
            else if (t + 1 > startt) score1 = LOG_ZERO;
            else score1 = wordtrellis[tl][ac->arc];
            score1 += ac->a;
          } else {
            score1 = wordtrellis[tl][ac->arc] + ac->a;
          }
          if (i <= crossword_point && ac->arc > crossword_point) {
            /* ¤³¤ì¤Ïñ¸ì¤ò±Û¤¨¤ëÁ«°Ü (backscan ¼Â¹Ô»þ) */
            /* this is a transition across word (when backscan is enabled) */
            score1 += now->lscore; /* add LM score */
          }

          if (hmminfo->multipath) {
            if (i <= store_point && ac->arc > store_point) {
              if (tmpmax_store < score1) tmpmax_store = score1;
            }
          } else {
            if (i == store_point && i != ac->arc) {
              if (tmpmax2 < score1) tmpmax2 = score1;
            }
          }

          if (tmpmax < score1) {
            tmpmax = score1;
            j = ac->arc;
          }
        }

        /* ¥¹¥³¥¢¥¨¥ó¥Ù¥í¡¼¥×¥Á¥§¥Ã¥¯: °ìÄêÉý³°¤Ê¤éÍî¤È¤¹ */
        /* check if score of this node is within the score envelope */
        if (
#ifdef SCAN_BEAM
            tmpmax <= framemaxscore[t] - scan_beam_thres ||
#endif
            tmpmax <= LOG_ZERO
            ) {  /* invalid node */
          wordtrellis[tn][i] = LOG_ZERO;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
          if (r->graphout) {
            wend_token_frame[tn][i] = -1;
            wend_token_gscore[tn][i] = LOG_ZERO;
          }
#endif
          if (! hmminfo->multipath) {
            if (i == store_point) now->g_prev[t] = LOG_ZERO;
          }
        } else { /* survived node */
          if (! hmminfo->multipath) {
            if (i == store_point) now->g_prev[t] = tmpmax2;
          }
#ifdef GRAPHOUT_PRECISE_BOUNDARY
          if (r->graphout) {

            if (hmminfo->multipath) {
              if ((back_rescan && i <= crossword_point && j > crossword_point)
                  || j == wordhmmnum-1) {
                wend_token_frame[tn][i] = t;
                wend_token_gscore[tn][i] = tmpmax;
              } else {
                wend_token_frame[tn][i] = wend_token_frame[tl][j];
                wend_token_gscore[tn][i] = wend_token_gscore[tl][j];
              }
            } else {
              if (i <= crossword_point && j > crossword_point) {
                wend_token_frame[tn][i] = t;
                wend_token_gscore[tn][i] = tmpmax;
              } else {
                wend_token_frame[tn][i] = wend_token_frame[tl][j];
                wend_token_gscore[tn][i] = wend_token_gscore[tl][j];
              }
            }
          }
#endif
          node_exist_p = TRUE;  /* at least one node survive in this frame */

          wordtrellis[tn][i] = tmpmax;
          if (! hmminfo->multipath || i > 0) {
            /* compute output probability */
            wordtrellis[tn][i] += outprob(&(r->am->hmmwrk), t, &(whmm->state[i]), param);
          }
        }
        
      } else {                  /* not triphone */

        /* backscan ̵¤·: store_point, crossword_point ¤Ï̵´Ø·¸ */
        /* no backscan: store_point, crossword_point ignored */
        tmpmax = LOG_ZERO;
        if (hmminfo->multipath) {
          for (ac=whmm->state[i].ac;ac;ac=ac->next) {
            if (ac->arc == wordhmmnum-1) score1 = g[t];
            else if (t + 1 > startt) score1 = LOG_ZERO;
            else score1 = wordtrellis[tl][ac->arc];
            score1 += ac->a;
            if (tmpmax < score1) {
              tmpmax = score1;
              j = ac->arc;
            }
          }
        } else {
          for (ac=whmm->state[i].ac;ac;ac=ac->next) {
            score1 = wordtrellis[tl][ac->arc] + ac->a;
            if (tmpmax < score1) {
              tmpmax = score1;
              j = ac->arc;
            }
          }
        }

        /* ¥¹¥³¥¢¥¨¥ó¥Ù¥í¡¼¥×¥Á¥§¥Ã¥¯: °ìÄêÉý³°¤Ê¤éÍî¤È¤¹ */
        /* check if score of this node is within the score envelope */
        if (
#ifdef SCAN_BEAM
            tmpmax <= framemaxscore[t] - scan_beam_thres ||
#endif
            tmpmax <= LOG_ZERO
            ) {
          /* invalid node */
          wordtrellis[tn][i] = LOG_ZERO;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
          if (r->graphout) {
            wend_token_frame[tn][i] = -1;
            wend_token_gscore[tn][i] = LOG_ZERO;
          }
#endif
        } else {
          /* survived node */
          node_exist_p = TRUE;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
          if (r->graphout) {
            if (hmminfo->multipath) {
              if (j == wordhmmnum-1) {
                wend_token_frame[tn][i] = t;
                wend_token_gscore[tn][i] = tmpmax;
              } else {
                wend_token_frame[tn][i] = wend_token_frame[tl][j];
                wend_token_gscore[tn][i] = wend_token_gscore[tl][j];
              }
            } else {
              wend_token_frame[tn][i] = wend_token_frame[tl][j];
              wend_token_gscore[tn][i] = wend_token_gscore[tl][j];
            }
          }
#endif
          /* score of node [t][i] has been determined here */
          wordtrellis[tn][i] = tmpmax;
          if (! hmminfo->multipath || i > 0) {
            wordtrellis[tn][i] += outprob(&(r->am->hmmwrk), t, &(whmm->state[i]), param);
          }
        }
        
      }
    } /* end of node loop */

    /* »þ´Ö t ¤ÎViterbi·×»»½ªÎ». Á°¸þ¤­¥¹¥³¥¢¤Ïscan¤·¤¿Ã±¸ì¤Î»Ïü */
    /* Viterbi end for frame [t].  the forward score is the score of word
       beginning scanned */
    now->g[t] = wordtrellis[tn][0];
#ifdef GRAPHOUT_PRECISE_BOUNDARY
    if (r->graphout) {
      now->wordend_frame[t] = wend_token_frame[tn][0];
      now->wordend_gscore[t] = wend_token_gscore[tn][0];
    }
#endif

    if (hmminfo->multipath) {
      /* triphone »þ, ¼¡ÃʤΤ¿¤á¤Ë store_point ¤Î¥Ç¡¼¥¿¤òg_prev¤ËÊݸ */
      /* store the scores crossing the store_point to g_prev, for next scan */
      if (ccd_flag) {
        /* the max arc crossing the store_point always selected as tmpmax_score */ 
        tmpmax_store -= store_point_maxarc;
        if (tmpmax_store < LOG_ZERO) tmpmax_store = LOG_ZERO;
        now->g_prev[t] = tmpmax_store;
      }
    }

    /* store the number of last computed frame */
    if (node_exist_p) endt = t;
    
    /* scan¤·¤¿Ã±¸ì¤ÎÂ裱¥Ñ¥¹¤Ç¤Î»Ïü»þ¹ï¤è¤êÀè¤Þ¤Ç t ¤¬¿Ê¤ó¤Ç¤ª¤ê¡¤¤«¤Ä
       ¤³¤Î t ¤Ë¤ª¤¤¤Æ¥¹¥³¥¢¥¨¥ó¥Ù¥í¡¼¥×¤Ë¤è¤Ã¤ÆÀ¸¤­»Ä¤Ã¤¿¥Î¡¼¥É¤¬°ì¤Ä¤â
       ̵¤«¤Ã¤¿¤Ê¤é¤Ð,¤³¤Î¥Õ¥ì¡¼¥à¤Ç·×»»¤òÂǤÁÀڤꤽ¤ì°Ê¾åÀè([0..t-1])¤Ï
       ·×»»¤·¤Ê¤¤ */
    /* if frame 't' already reached the beginning frame of scanned word
       in 1st pass and no node was survived in this frame (all nodes pruned
       by score envelope), terminate computation at this frame and
       do not computer further frame ([0..t-1]). */
    if (t < now->estimated_next_t && (!node_exist_p)) {
      /* clear the rest scores */
      for (i=t-1;i>=0;i--) {
        now->g[i] = LOG_ZERO;
#ifdef GRAPHOUT_PRECISE_BOUNDARY
        if (r->graphout) {
          now->wordend_frame[i] = -1;
          now->wordend_gscore[i] = LOG_ZERO;
        }
#endif
        if (ccd_flag) now->g_prev[i] = LOG_ZERO;
      }
      /* terminate loop */
      break;
    }
    
  } /* end of time loop */
  
  if (debug2_flag) jlog("DEBUG: scanned: [%3d-%3d]\n", endt, startt);

 end_of_scan:

  if (hmminfo->multipath) {
    /* Á°¸þ¤­¥¹¥³¥¢¤ÎºÇ½ªÃͤò·×»» (¾õÂÖ 0 ¤«¤é»þ´Ö 0 ¤Ø¤ÎÁ«°Ü) */
    /* compute the total forward score (transition from state 0 to frame 0 */
    if (endt == 0) {
      tmpmax = LOG_ZERO;
      for(ac=whmm->state[0].ac;ac;ac=ac->next) {
        score1 = wordtrellis[tn][ac->arc] + ac->a;
        if (tmpmax < score1) tmpmax = score1;
      }
      now->final_g = score1;
    } else {
      now->final_g = LOG_ZERO;
    }
  }
  
  /* ¼¡²ó backscan ¤Î¤¿¤á¤Î¾ðÊó³ÊǼ */
  /* store data for next backscan */
  if (ccd_flag) {
    if (store_point == (hmminfo->multipath ? wordhmmnum - 2 : wordhmmnum - 1)) {
      /* last_ph̵¤·¡¤¤«¤Äñ¸ì¤Î²»ÁÇĹ=1¤Î¾ì¹ç¡¢¼¡²ó¤Î scan_word() ¤Ç
         ñ¸ìÁ´ÂΤ¬¤â¤¦°ìÅٺƷ׻»¤µ¤ì¤ë. ¤³¤Î¾ì¹ç,
         g_prev ¤Ï¡¤¤³¤Îscan_word¤ò³«»Ï¤¹¤ëÁ°¤Î¥¹¥³¥¢¤òÆþ¤ì¤Æ¤ª¤¯É¬Íפ¬¤¢¤ë */
      /* if there was no 'last_ph' and the scanned word consists of only
         1 phone, the whole word should be re-computed in the future scan_word().
         So the next 'g_prev[]' should be the initial forward scores
         before we begin Viterbi (= g[t]). */
      for (t = startt; t>=0; t--) {
        now->g_prev[t] = g[t];
      }
    }
#ifndef GRAPHOUT_PRECISE_BOUNDARY
    if (r->graphout) {
      if (now->tail_g_score != LOG_ZERO) {
        if (now->prevgraph != NULL) {
          (now->prevgraph)->leftscore = now->tail_g_score;
        }
      }
    }
#endif
    /* ¼¡²ó¤Î¤¿¤á¤Ë now->last_ph ¤ò¹¹¿· */
    /* update 'now->last_ph' for future scan_word() */
    if (back_rescan) {
      now->last_ph = phmmseq[0];
    } else {
      now->last_ph = winfo->wseq[word][0];
    }
    if (hmminfo->multipath) {
      now->last_ph_sp_attached = has_sp[0];
    }
  }

#ifdef GRAPHOUT_PRECISE_BOUNDARY
  if (! hmminfo->multipath) {
    if (r->graphout) {
      /* ¼¡²ó¤Î next_word ÍѤ˶­³¦¾ðÊó¤òÄ´À° */
      /* proceed word boundary for one step for next_word */
      now->wordend_frame[peseqlen-1] = now->wordend_frame[0];
      now->wordend_gscore[peseqlen-1] = now->wordend_gscore[0];
      for (t=0;t<peseqlen-1;t++) {
        now->wordend_frame[t] = now->wordend_frame[t+1];
        now->wordend_gscore[t] = now->wordend_gscore[t+1];
      }
    }
  }
#endif

  /* free work area */
  free_hmm(whmm);
#ifdef TCD
  if (hmminfo->multipath) {
    if (ccd_flag) {
      jlog("DEBUG: last_ph = %s", (now->last_ph)->name);
      if (now->last_ph_sp_attached) jlog(" (sp attached)");
      jlog("\n");
    }
  } else {
    jlog("DEBUG: last_ph = %s\n", (now->last_ph)->name);
  }
#endif
}


/**************************************************************************/
/*** ¿·²¾Àâ¤ÎŸ³«¤È¥Ò¥å¡¼¥ê¥¹¥Æ¥£¥Ã¥¯¤ò·Ò¤¤¤ÀÁ´ÂÎ¥¹¥³¥¢¤ò·×»»           ***/
/*** Expand new hypothesis and compute the total score (with heuristic) ***/
/**************************************************************************/

void
next_word(NODE *now, NODE *new, NEXTWORD *nword, HTK_Param *param, RecogProcess *r)
{
  int   t;
  HMM_Logical *newphone;
  int lastword;
  int   i;
  LOGPROB tmpp;
  LOGPROB a_value;
  int   startt;
  int word;
  LOGPROB totalscore;
  TRELLIS_ATOM *tre;

  BACKTRELLIS *backtrellis;
  WORD_INFO *winfo;
  HTK_HMM_INFO *hmminfo;
  int peseqlen;
  boolean ccd_flag;

  backtrellis = r->backtrellis;
  winfo = r->lm->winfo;
  hmminfo = r->am->hmminfo;
  peseqlen = r->peseqlen;
  ccd_flag = r->ccd_flag;

  new->score = LOG_ZERO;

  word = nword->id;
  lastword=now->seq[now->seqnum-1];

  /* ñ¸ìʤӡ¢DFA¾õÂÖÈֹ桢¸À¸ì¥¹¥³¥¢¤ò·Ñ¾µ¡¦¹¹¿· */
  /* inherit and update word sequence, DFA state and total LM score */
  for (i=0;i< now->seqnum;i++){ 
    new->seq[i] = now->seq[i];
#ifdef CM_SEARCH
#ifdef CM_MULTIPLE_ALPHA
    memcpy(new->cmscore[i], now->cmscore[i], sizeof(LOGPROB) * r->config->annotate.cm_alpha_num);
#else
    new->cmscore[i] = now->cmscore[i];
#endif
#endif /* CM_SEARCH */
  }
  new->seq[i] = word;
  new->seqnum = now->seqnum+1;
  new->state = nword->next_state;
  new->totallscore = now->totallscore + nword->lscore;
  if (hmminfo->multipath) new->final_g = now->final_g;
  
  if (ccd_flag) {
    
    /* Ÿ³«Ã±¸ì¤ÎÀܳÅÀ¤Î²»ÁÇHMM¤ònewphone¤Ë¥»¥Ã¥È¤¹¤ë. 
       ¸µ²¾Àâ now ¤È¤Îñ¸ì´Ö¤Î²»ÁǴĶ­°Í¸À­¤ò¹Íθ¤¹¤ë */
    /* set the triphone at the connection point to 'newphone', considering
       cross-word context dependency to 'now' */
    newphone = get_right_context_HMM(winfo->wseq[word][winfo->wlen[word]-1], now->last_ph->name, hmminfo);
    if (newphone == NULL) {     /* triphone not found */
      /* fallback to the original bi/mono-phone */
      /* error if the original is pseudo phone (not explicitly defined
         in hmmdefs/hmmlist) */
      /* exception: word with 1 phone (triphone may exist in the next expansion */
      if (winfo->wlen[word] > 1 && winfo->wseq[word][winfo->wlen[word]-1]->is_pseudo){
        error_missing_right_triphone(winfo->wseq[word][winfo->wlen[word]-1], now->last_ph->name);
      }
      newphone = winfo->wseq[word][winfo->wlen[word]-1];
    }
    
    /* ¸µ²¾Àâ¤òscan¤·¤¿»þ¤ÎËöü²»ÁÇHMM -> ¿·²¾Àâ¤ÎľÁ°²»ÁÇHMM */
    /* inherit last_ph */
    new->last_ph = now->last_ph;
    if (hmminfo->multipath) {
      new->last_ph_sp_attached = now->last_ph_sp_attached;
    }
    
    /* backscanÍÑÀܳ¥Ý¥¤¥ó¥È¤Î¥¹¥³¥¢ g_prev[] ¤ò¥³¥Ô¡¼ */
    /* copy g_prev[] that are scores at backscan connection point */
    for (t=0;t<peseqlen;t++) {
      new->g_prev[t] = now->g_prev[t];
    }
    
  } else {                      /* not triphone */
    
    /* Ÿ³«Ã±¸ì¤ÎÀܳ(=½ªÃ¼)¤Î²»ÁÇHMM¤ònewphone¤Ë¥»¥Ã¥È */
    /* set the phone at the connection point to 'newphone' */
    newphone = winfo->wseq[word][winfo->wlen[word]-1];
  }


  if (r->lmtype == LM_PROB) {
    new->lscore = nword->lscore;
  } else if (r->lmtype == LM_DFA) {
    new->lscore = 0.0;
  }

  if (! hmminfo->multipath) {
    /* a_value: ÀܳÅÀ¤ÎÁ«°Ü³ÎΨ */
    /* a_value: transition probability of connection point */
    i = hmm_logical_state_num(newphone);
    a_value = (hmm_logical_trans(newphone))->a[i-2][i-1];
  }

  /***************************************************************************/
  /* Á°¸þ¤­(Â裲¥Ñ¥¹),¸å¤í¸þ¤­(Â裱¥Ñ¥¹)¥È¥ì¥ê¥¹¤òÀܳ¤·ºÇÌàÀܳÅÀ¤ò¸«¤Ä¤±¤ë */
  /* connect forward/backward trellis to look for the best connection time   */
  /***************************************************************************/

  if (hmminfo->multipath) {
    startt = peseqlen-1;
  } else {
    startt = peseqlen-2;
    new->g[startt+1] = LOG_ZERO;
  }

  /*-----------------------------------------------------------------*/
  /* ñ¸ì¥È¥ì¥ê¥¹¤òõ¤·¤Æ, ¼¡Ã±¸ì¤ÎºÇÌàÀܳÅÀ¤òȯ¸«¤¹¤ë */
  /* determine the best connection time of the new word, seeking the word
     trellis */
  /*-----------------------------------------------------------------*/

  /* update new->g[t] */
  if (hmminfo->multipath) {
    for(t=startt;t>=0;t--) {
      new->g[t] = now->g[t] + nword->lscore;
    }
  } else {
    for(t=startt;t>=0;t--) {
      new->g[t] = now->g[t+1] + a_value + nword->lscore;
    }
  }

  new->tre = NULL;

  if (r->lmtype == LM_DFA && !r->config->pass2.looktrellis_flag) {
    /* ¤¹¤Ù¤Æ¤Î¥Õ¥ì¡¼¥à¤Ë¤ï¤¿¤Ã¤ÆºÇÌà¤òõ¤¹ */
    /* search for best trellis word throughout all frame */
    for(t = startt; t >= 0; t--) {
      tre = bt_binsearch_atom(backtrellis, t, (WORD_ID) word);
      if (tre == NULL) continue;
      totalscore = new->g[t] + tre->backscore;
      if (! hmminfo->multipath) {
        if (newphone->is_pseudo) {
          tmpp = outprob_cd(&(r->am->hmmwrk), t, &(newphone->body.pseudo->stateset[newphone->body.pseudo->state_num-2]), param);
        } else {
          tmpp = outprob_state(&(r->am->hmmwrk), t, newphone->body.defined->s[newphone->body.defined->state_num-2], param);
        }
        totalscore += tmpp;
      }
      if (new->score < totalscore) {
        new->score = totalscore;
        new->bestt = t;
        new->estimated_next_t = tre->begintime - 1;
        new->tre  =  tre;
      }
    }

    return;

  }
      
  /* ¤³¤ÎŸ³«Ã±¸ì¤Î¥È¥ì¥ê¥¹¾å¤Î½ªÃ¼»þ´Ö¤ÎÁ°¸å¤Î¤ß¥¹¥­¥ã¥ó¤¹¤ë
     Á°¸å¤ËϢ³¤·¤Æ¸ºß¤¹¤ë¥Õ¥ì¡¼¥à¤Ë¤Ä¤¤¤Æ¤Î¤ß·×»» */
  /* search for best trellis word only around the estimated time */
  /* 1. search forward */
  for(t = (nword->tre)->endtime; t >= 0; t--) {
    tre = bt_binsearch_atom(backtrellis, t, (WORD_ID) word);
    if (tre == NULL) break;     /* go to 2 if the trellis word disappear */
    totalscore = new->g[t] + tre->backscore;
    if (! hmminfo->multipath) {
      if (newphone->is_pseudo) {
        tmpp = outprob_cd(&(r->am->hmmwrk), t, &(newphone->body.pseudo->stateset[newphone->body.pseudo->state_num-2]), param);
      } else {
        tmpp = outprob_state(&(r->am->hmmwrk), t, newphone->body.defined->s[newphone->body.defined->state_num-2], param);
      }
      totalscore += tmpp;
    }
    if (new->score < totalscore) {
      new->score = totalscore;
      new->bestt = t;
      new->estimated_next_t = tre->begintime - 1;
      new->tre = tre;
    }
  }
  /* 2. search backward */
  for(t = (nword->tre)->endtime + 1; t <= startt; t++) {
    tre = bt_binsearch_atom(backtrellis, t, (WORD_ID) word);
    if (tre == NULL) break;     /* end if the trellis word disapper */
    totalscore = new->g[t] + tre->backscore;
    if (! hmminfo->multipath) {
      if (newphone->is_pseudo) {
        tmpp = outprob_cd(&(r->am->hmmwrk), t, &(newphone->body.pseudo->stateset[newphone->body.pseudo->state_num-2]), param);
      } else {
        tmpp = outprob_state(&(r->am->hmmwrk), t, newphone->body.defined->s[newphone->body.defined->state_num-2], param);
      }
      totalscore += tmpp;
    }
    if (new->score < totalscore) {
      new->score = totalscore;
      new->bestt = t;
      new->estimated_next_t = tre->begintime - 1;
      new->tre = tre;
    }
  }

}

/**********************************************************************/
/********** ½é´ü²¾Àâ¤ÎÀ¸À®                 ****************************/
/********** Generate an initial hypothesis ****************************/
/**********************************************************************/

void
start_word(NODE *new, NEXTWORD *nword, HTK_Param *param, RecogProcess *r)
{
  HMM_Logical *newphone;
  WORD_ID word;
  LOGPROB tmpp;
  int t;
  TRELLIS_ATOM *tre = NULL;

  BACKTRELLIS *backtrellis;
  WORD_INFO *winfo;
  int peseqlen;
  boolean ccd_flag;

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

  /* initialize data */
  word = nword->id;
  new->score = LOG_ZERO;
  new->seqnum = 1;
  new->seq[0] = word;

  new->state = nword->next_state;
  new->totallscore = nword->lscore;

  /* cross-word triphone handling is not needed on startup */
  newphone = winfo->wseq[word][winfo->wlen[word]-1];
  if (ccd_flag) {
    new->last_ph = NULL;
    new->last_ph_sp_attached = FALSE;
  }
  new->lscore = nword->lscore;

  if (r->lmtype == LM_PROB) {
    new->g[peseqlen-1] = nword->lscore;
  } else if (r->lmtype == LM_DFA) {
    new->g[peseqlen-1] = 0;
  }
  
  for (t=peseqlen-1; t>=0; t--) {
    tre = bt_binsearch_atom(backtrellis, t, word);
    if (tre != NULL) {
      if (r->graphout) {
        new->bestt = peseqlen-1;
      } else {
        new->bestt = t;
      }
      new->score = new->g[peseqlen-1] + tre->backscore;
      if (! r->am->hmminfo->multipath) {
        if (newphone->is_pseudo) {
          tmpp = outprob_cd(&(r->am->hmmwrk), peseqlen-1, &(newphone->body.pseudo->stateset[newphone->body.pseudo->state_num-2]), param);
        } else {
          tmpp = outprob_state(&(r->am->hmmwrk), peseqlen-1, newphone->body.defined->s[newphone->body.defined->state_num-2], param);
        }
        new->score += tmpp;
      }
      new->estimated_next_t = tre->begintime - 1;
      new->tre = tre;
      break;
    }
  }
  if (tre == NULL) {            /* no word in backtrellis */
    new->score = LOG_ZERO;
  }

}


void
last_next_word(NODE *now, NODE *new, HTK_Param *param, RecogProcess *r)
{
  cpy_node(new, now);
  /* ºÇ½ª¥¹¥³¥¢¤òÀßÄê */
  /* update the final score */
  if (r->am->hmminfo->multipath) {
    new->score = now->final_g;
  } else {
    new->score = now->g[0];
  }
}


#endif /* PASS2_STRICT_IWCD */

/* end of file */

---