Main Page | Modules | Data Structures | Directories | File List | Data Fields | Globals | Related Pages
julius

beam.c

Go to the documentation of this file.
00001 
00052 /*
00053  * Copyright (c) 1991-2006 Kawahara Lab., Kyoto University
00054  * Copyright (c) 2000-2005 Shikano Lab., Nara Institute of Science and Technology
00055  * Copyright (c) 2005-2006 Julius project team, Nagoya Institute of Technology, Nagoya Institute of Technology
00056  * All rights reserved
00057  */
00058 
00059 #include <julius.h>
00060 
00061 #undef DEBUG
00062 
00063 static boolean idc_on;          
00064 static int progout_interval_frame; 
00065 
00066 
00067 /* -------------------------------------------------------------------- */
00068 /*                     第１パスの結果出力と終了処理                     */
00069 /*              result output and end procedure of 1st pass             */
00070 /* -------------------------------------------------------------------- */
00071 
00072 #ifdef WORD_GRAPH
00073 /* 第１パス結果から単語グラフを生成 */
00074 /* generate word graphs from result of 1st pass (=backtrellis) */
00075 static int glevel;              
00076 static int gnodes;              
00077 static int garcs;               
00078 
00109 static void
00110 generate_lattice(int endtime, WORD_ID wid, BACKTRELLIS *bt, WORD_INFO *winfo)
00111 {
00112   TRELLIS_ATOM *ta, *ta_last;
00113   int i,j;
00114   boolean new_node = FALSE;
00115 
00116   glevel++;
00117 
00118   if (endtime >= 0) {
00119     for (i=0;i<bt->num[endtime];i++) {
00120       ta = bt->rw[endtime][i];
00121       if (ta->wid == wid) {
00122         if (ta->within_wordgraph) {
00123           /* already marked */
00124         } else {
00125           /* mark  */
00126           ta->within_wordgraph = TRUE;
00127           garcs++;
00128           new_node = TRUE;      /* new node mark */
00129           ta_last = ta->last_tre;
00130           if (debug2_flag) {
00131             for(j=0;j<glevel;j++) j_printf(" ");
00132             j_printf("%s: %d->", winfo->wname[ta->wid], ta->endtime);
00133             if (ta_last->wid == WORD_INVALID) {
00134               j_printf("%d(WORD_INVALID)\n", ta_last->endtime);
00135             } else {
00136               j_printf("%d(%s)\n", ta_last->endtime, winfo->wname[ta_last->wid]);
00137             }
00138           }
00139           /* recursive call */
00140           generate_lattice(ta_last->endtime, ta_last->wid, bt, winfo);
00141         }
00142       }
00143     }
00144   }
00145   if (new_node) {
00146     gnodes++;
00147   }
00148   glevel--;
00149 }
00150 #endif
00151 
00166 static void
00167 put_atom(TRELLIS_ATOM *atom, WORD_INFO *winfo)
00168 {
00169   int i;
00170   j_printf("%3d,%3d %f %16s (id=%5d)", atom->begintime, atom->endtime,
00171          atom->backscore, winfo->wname[atom->wid], atom->wid);
00172   for (i=0;i<winfo->wlen[atom->wid]; i++) {
00173     j_printf(" %s",winfo->wseq[atom->wid][i]->name);
00174   }
00175   j_printf("\n");
00176 }
00177 
00210 static LOGPROB
00211 trace_backptr(WORD_ID wordseq_rt[MAXSEQNUM], int *rt_wordlen, TRELLIS_ATOM *atom, BACKTRELLIS *backtrellis, WORD_INFO *winfo)
00212 {
00213   int wordlen = 0;              /* word length of best sentence hypothesis */
00214   TRELLIS_ATOM *tretmp;
00215   LOGPROB langscore = 0.0;
00216   static WORD_ID wordseq[MAXSEQNUM];    /* temporal: in reverse order */
00217   int i;
00218   
00219   /* initialize */
00220   wordseq[0] = atom->wid;       /* start from specified atom */
00221   wordlen = 1;
00222   tretmp = atom;
00223 #ifdef USE_NGRAM
00224   langscore += tretmp->lscore;
00225 #endif
00226   if (debug2_flag) {
00227     put_atom(tretmp, winfo);
00228   }
00229   
00230   /* trace the backtrellis */
00231   while (tretmp->begintime > 0) {/* until beginning of input */
00232     tretmp = tretmp->last_tre;
00233 /*    t = tretmp->boundtime - 1;
00234     tretmp = bt_binsearch_atom(backtrellis, tretmp->boundtime-1, tretmp->last_wid);*/
00235     if (tretmp == NULL) {       /* should not happen */
00236       j_error("ERROR: BackTrellis Pass missing??\n");
00237     }
00238 #ifdef USE_NGRAM
00239     langscore += tretmp->lscore;
00240 #endif
00241     wordseq[wordlen] = tretmp->wid;
00242     wordlen++;
00243     if (debug2_flag) {
00244       put_atom(tretmp, winfo);
00245     }
00246     if (wordlen >= MAXSEQNUM) {
00247       j_error("sentence length exceeded ( > %d)\n",MAXSEQNUM);
00248     }
00249   }
00250   *rt_wordlen = wordlen;
00251   /* reverse order -> normal order */
00252   for(i=0;i<wordlen;i++) wordseq_rt[i] = wordseq[wordlen-i-1];
00253   return(langscore);
00254 }
00255 
00305 static LOGPROB
00306 print_1pass_result(BACKTRELLIS *backtrellis, int framelen, WORD_INFO *winfo)
00307 {
00308   WORD_ID wordseq[MAXSEQNUM];
00309   int wordlen;
00310   int i;
00311   TRELLIS_ATOM *best;
00312   int last_time;
00313   LOGPROB total_lscore;
00314 #if defined(USE_DFA) || defined(SP_BREAK_CURRENT_FRAME)
00315   LOGPROB maxscore;
00316   TRELLIS_ATOM *tmp;
00317 #endif
00318 
00319   /* look for the last trellis word */
00320   for (last_time = framelen - 1; last_time >= 0; last_time--) {
00321 #ifdef USE_NGRAM
00322 #ifdef SP_BREAK_CURRENT_FRAME   /*  in case of sp segmentation */
00323     /* 最終フレームに残った最大スコアの単語 */
00324     /* it should be the best trellis word on the last frame */
00325     maxscore = LOG_ZERO;
00326     for (i=0;i<backtrellis->num[last_time];i++) {
00327       tmp = backtrellis->rw[last_time][i];
00328       if (maxscore < tmp->backscore) {
00329         maxscore = tmp->backscore;
00330         best = tmp;
00331       }
00332     }
00333     if (maxscore != LOG_ZERO) break;
00334 #else  /* normal mode */
00335     /* 最終単語は winfo->tail_silwid に固定 */
00336     /* it is fixed to the tail silence model (winfo->tail_silwid) */
00337     best = bt_binsearch_atom(backtrellis, last_time, winfo->tail_silwid);
00338     if (best != NULL) break;
00339 #endif
00340 #else  /* USE_DFA */
00341     /* 末尾に残った単語の中で最大スコアの単語(cp_endは使用しない) */
00342     /* the best trellis word on the last frame (not use cp_end[]) */
00343     maxscore = LOG_ZERO;
00344     for (i=0;i<backtrellis->num[last_time];i++) {
00345       tmp = backtrellis->rw[last_time][i];
00346       /*      if (dfa->cp_end[winfo->wton[tmp->wid]] == TRUE) {*/
00347         if (maxscore < tmp->backscore) {
00348           maxscore = tmp->backscore;
00349           best = tmp;
00350         }
00351         /*      }*/
00352     }
00353     if (maxscore != LOG_ZERO) break;
00354 #endif /* USE_NGRAM */
00355   }
00356   if (last_time < 0) {          /* not found */
00357     j_printerr("[no sentence-end word survived on last beam]\n");
00358     /* print null result */
00359     result_pass1_final(NULL, 0, LOG_ZERO, LOG_ZERO, winfo);
00360     return(LOG_ZERO);
00361   }
00362   
00363   /* traceback word trellis from the best word */
00364   total_lscore = trace_backptr(wordseq, &wordlen, best, backtrellis, winfo);
00365 
00366   if (progout_flag) {           /* just flush last progress output */
00367     result_pass1_current(last_time, wordseq, wordlen, best->backscore, total_lscore, winfo);
00368   }
00369 
00370   /* output 1st pass result */    
00371   if (verbose_flag || !progout_flag) {
00372     result_pass1_final(wordseq, wordlen, best->backscore, total_lscore, winfo);
00373   }
00374   result_pass1_end();
00375   
00376   /* store the result to global val (notice: in reverse order) */
00377   for(i=0;i<wordlen;i++) pass1_wseq[i] = wordseq[i];
00378   pass1_wnum = wordlen;
00379   pass1_score = best->backscore;
00380 
00381 #ifdef WORD_GRAPH
00382   /* 単語トレリスから，ラティスを生成する */
00383   /* 実際には within_wordgraph を on にするだけ */
00384   /* generate word graph from the word trellis */
00385   /* actually generate_lattice() does not construct graph:
00386      it only marks words in trellis that are on the word graph */
00387   glevel = 0;
00388   gnodes = 1;                   /* frame = 0 の分 */
00389   garcs = 0;
00390   generate_lattice(last_time, winfo->tail_silwid, backtrellis, winfo);
00391   if (verbose_flag) j_printf("word graph generated (nodes=%d,arcs=%d)\n",gnodes, garcs);
00392 #endif
00393 
00394   /* return maximum score */
00395   return(best->backscore);
00396 }
00397 
00415 static void
00416 bt_current_max(BACKTRELLIS *bt, int t, WORD_INFO *winfo)
00417 {
00418   static WORD_ID wordseq[MAXSEQNUM];
00419   int wordlen;
00420   TRELLIS_ATOM *tre;
00421   TRELLIS_ATOM *tremax;
00422   LOGPROB maxscore;
00423   LOGPROB lscore;
00424 
00425   /* bt->list is ordered by time frame */
00426   maxscore = LOG_ZERO;
00427   tremax = NULL;
00428   tre = bt->list;
00429   while (tre != NULL && tre->endtime == t) {
00430     if (maxscore < tre->backscore) {
00431       maxscore = tre->backscore;
00432       tremax = tre;
00433     }
00434     tre = tre->next;
00435   }
00436 
00437   if (maxscore != LOG_ZERO) {
00438     lscore = trace_backptr(wordseq, &wordlen, tremax, bt, winfo);
00439     result_pass1_current(t, wordseq, wordlen, tremax->backscore, lscore, winfo);
00440   } else {
00441     wordlen = 0;
00442     result_pass1_current(t, wordseq, wordlen, LOG_ZERO, LOG_ZERO, winfo);
00443   }
00444 }
00445 
00463 static void
00464 bt_current_max_word(BACKTRELLIS *bt, int t, WORD_INFO *winfo)
00465 {
00466   TRELLIS_ATOM *tre;
00467   TRELLIS_ATOM *tremax;
00468   LOGPROB maxscore;
00469   WORD_ID w;
00470 
00471   /* bt->list は時間順に格納されている */
00472   /* bt->list is order by time */
00473   maxscore = LOG_ZERO;
00474   tremax = NULL;
00475   tre = bt->list;
00476   while (tre != NULL && tre->endtime == t) {
00477     if (maxscore < tre->backscore) {
00478       maxscore = tre->backscore;
00479       tremax = tre;
00480     }
00481     tre = tre->next;
00482   }
00483 
00484   if (maxscore != LOG_ZERO) {
00485     j_printf("%3d: ",t);
00486     w = tremax->wid;
00487     j_printf("\"%s [%s]\"(id=%d)",
00488            winfo->wname[w], winfo->woutput[w], w);
00489     j_printf(" [%d-%d] %f <- ", tremax->begintime, t, tremax->backscore);
00490     w = tremax->last_tre->wid;
00491     if (w != WORD_INVALID) {
00492       j_printf("\"%s [%s]\"(id=%d)\n",
00493              winfo->wname[w], winfo->woutput[w], w);
00494     } else {
00495       j_printf("bgn\n");
00496     }
00497   }
00498 }
00499 
00500 /* -------------------------------------------------------------------- */
00501 /*                 ビーム探索中のトークンを扱うサブ関数                 */
00502 /*                functions to handle hypothesis tokens                  */
00503 /* -------------------------------------------------------------------- */
00504 
00505 /* Token structure: */
00506    
00507 /* How tokens are managed:
00508    o  tlist[][] is a token stocker.  It holds all tokens in sequencial
00509       buffer.  They are malloced first on startup, and refered by ID while
00510       Viterbi procedure.  In word-pair mode, each token also has a link to
00511       another token to allow a node to have more than 1 token.
00512       
00513    o  token[n] holds the current ID number of a token associated to a
00514       lexicon tree node 'n'.
00515 
00516  */
00517 
00518 /* Token space */
00519 static TOKEN2 *tlist[2];        
00520 static TOKENID *tindex[2];      
00521 static int maxtnum = 0;         
00522 static int expand_step = 0;     
00523 static int tnum[2];             
00524 static int n_start;             
00525 static int n_end;               
00526 static int tl;          
00527 static int tn;          
00528 
00529 /* Active token list */
00530 static TOKENID *token;          
00531 static int totalnodenum;        
00532 
00533 
00534 static TRELLIS_ATOM bos;        
00535 static boolean nodes_malloced = FALSE; 
00536 
00555 static void
00556 malloc_nodes(int n, int ntoken_init, int ntoken_step)
00557 {
00558   totalnodenum = n;
00559   token        = mymalloc(sizeof(TOKENID)*totalnodenum);
00560   if (maxtnum < ntoken_init) maxtnum = ntoken_init;
00561   tlist[0]     = mymalloc(sizeof(TOKEN2)*maxtnum);
00562   tlist[1]     = mymalloc(sizeof(TOKEN2)*maxtnum);
00563   tindex[0]     = mymalloc(sizeof(TOKENID)*maxtnum);
00564   tindex[1]     = mymalloc(sizeof(TOKENID)*maxtnum);
00565   tnum[0] = tnum[1] = 0;
00566   if (expand_step < ntoken_step) expand_step = ntoken_step;
00567   nodes_malloced = TRUE;
00568 }
00569 
00578 static void
00579 expand_tlist()
00580 {
00581   maxtnum += expand_step;
00582   tlist[0]     = myrealloc(tlist[0],sizeof(TOKEN2)*maxtnum);
00583   tlist[1]     = myrealloc(tlist[1],sizeof(TOKEN2)*maxtnum);
00584   tindex[0]     = myrealloc(tindex[0],sizeof(TOKENID)*maxtnum);
00585   tindex[1]     = myrealloc(tindex[1],sizeof(TOKENID)*maxtnum);
00586   /*j_printerr("warn: token space expanded\n");*/
00587 }
00588 
00597 static void
00598 free_nodes()
00599 {
00600   if (nodes_malloced) {
00601     free(token);
00602     free(tlist[0]);
00603     free(tlist[1]);
00604     free(tindex[0]);
00605     free(tindex[1]);
00606     nodes_malloced = FALSE;
00607   }
00608 }
00609 
00622 static void
00623 clear_tlist(int tt)
00624 {
00625   tnum[tt] = 0;
00626 }
00627 
00640 static void
00641 clear_tokens(int tt)
00642 {
00643   int j;
00644   /* initialize active token list: only clear ones used in the last call */
00645   for (j=0; j<tnum[tt]; j++) {
00646     token[tlist[tt][j].node] = TOKENID_UNDEFINED;
00647   }
00648 }
00649 
00662 static TOKENID
00663 create_token()
00664 {
00665   TOKENID newid;
00666   newid = tnum[tn];
00667   tnum[tn]++;
00668   if (tnum[tn]>=maxtnum) expand_tlist();
00669   tindex[tn][newid] = newid;
00670 #ifdef WPAIR
00671   /* initialize link */
00672   tlist[tn][newid].next = TOKENID_UNDEFINED;
00673 #endif
00674   return(newid);
00675 }
00676 
00704 static void
00705 node_assign_token(int node, TOKENID tkid)
00706 {
00707 #ifdef WPAIR
00708   /* add to link list */
00709   tlist[tn][tkid].next = token[node];
00710 #endif
00711   token[node] = tkid;
00712   tlist[tn][tkid].node = node;
00713 }
00714 
00749 static TOKENID
00750 node_exist_token(int tt, int node, WORD_ID wid)
00751 {
00752 #ifdef WPAIR
00753   /* In word-pair mode, multiple tokens are assigned to a node as a list.
00754      so we have to search for tokens with same last word ID */
00755 #ifdef WPAIR_KEEP_NLIMIT
00756   /* 1ノードごとに保持するtoken数の上限を設定 */
00757   /* tokenが無いが上限に達しているときは一番スコアの低いtokenを上書きする */
00758   /* N-best: limit number of assigned tokens to a node */
00759   int i = 0;
00760   TOKENID lowest_token = TOKENID_UNDEFINED;
00761 #endif
00762   TOKENID tmp;
00763   for(tmp=token[node]; tmp != TOKENID_UNDEFINED; tmp=tlist[tt][tmp].next) {
00764     if (tlist[tt][tmp].last_tre->wid == wid) {
00765       return(tmp);
00766     }
00767 #ifdef WPAIR_KEEP_NLIMIT
00768     if (lowest_token == TOKENID_UNDEFINED ||
00769         tlist[tt][lowest_token].score < tlist[tt][tmp].score)
00770       lowest_token = tmp;
00771     if (++i >= wpair_keep_nlimit) break;
00772 #endif
00773   }
00774 #ifdef WPAIR_KEEP_NLIMIT
00775   if (i >= wpair_keep_nlimit) { /* overflow, overwrite lowest score */
00776     return(lowest_token);
00777   } else {
00778     return(TOKENID_UNDEFINED);
00779   }
00780 #else 
00781   return(TOKENID_UNDEFINED);
00782 #endif
00783   
00784 #else  /* not WPAIR */
00785   /* 1つだけ保持,これを常に上書き */
00786   /* Only one token is kept in 1-best mode (default), so
00787      simply return the ID */
00788   return(token[node]);
00789 #endif
00790 }
00791 
00792 #ifdef DEBUG
00793 /* tlist と token の対応をチェックする(debug) */
00794 /* for debug: check tlist <-> token correspondence
00795    where  tlist[tt][tokenID].node = nodeID and
00796           token[nodeID] = tokenID
00797  */
00798 static void
00799 node_check_token(int tt)
00800 {
00801   int i;
00802   for(i=0;i<tnum[tt];i++) {
00803     if (node_exist_token(tt, tlist[tt][i].node, tlist[tt][i].last_tre->wid) != i) {
00804       j_printerr("token %d not found on node %d\n", i, tlist[tt][i].node);
00805     }
00806   }
00807 }
00808 #endif
00809 
00810 
00811 
00812 /* -------------------------------------------------------------------- */
00813 /*       トークンをソートし 上位 N トークンを判別する (heap sort)       */
00814 /*        Sort generated tokens and get N-best (use heap sort)          */
00815 /* -------------------------------------------------------------------- */
00816 /* ビームの閾値として上位 N 番目のスコアが欲しいだけであり，実際にソート
00817    される必要はない */
00818 /* we only want to know the N-th score for determining beam threshold, so
00819    order is not considered here */
00820 
00821 #define SD(A) tindex[tn][A-1]   
00822 #define SCOPY(D,S) D = S        
00823 #define SVAL(A) (tlist[tn][tindex[tn][A-1]].score) 
00824 #define STVAL (tlist[tn][s].score) 
00825 
00826 
00848 static void
00849 sort_token_upward(int neednum, int totalnum)
00850 {
00851   int n,root,child,parent;
00852   TOKENID s;
00853   for (root = totalnum/2; root >= 1; root--) {
00854     SCOPY(s, SD(root));
00855     parent = root;
00856     while ((child = parent * 2) <= totalnum) {
00857       if (child < totalnum && SVAL(child) < SVAL(child+1)) {
00858         child++;
00859       }
00860       if (STVAL >= SVAL(child)) {
00861         break;
00862       }
00863       SCOPY(SD(parent), SD(child));
00864       parent = child;
00865     }
00866     SCOPY(SD(parent), s);
00867   }
00868   n = totalnum;
00869   while ( n > totalnum - neednum) {
00870     SCOPY(s, SD(n));
00871     SCOPY(SD(n), SD(1));
00872     n--;
00873     parent = 1;
00874     while ((child = parent * 2) <= n) {
00875       if (child < n && SVAL(child) < SVAL(child+1)) {
00876         child++;
00877       }
00878       if (STVAL >= SVAL(child)) {
00879         break;
00880       }
00881       SCOPY(SD(parent), SD(child));
00882       parent = child;
00883     }
00884     SCOPY(SD(parent), s);
00885   }
00886 }
00887 
00912 static void
00913 sort_token_downward(int neednum, int totalnum)
00914 {
00915   int n,root,child,parent;
00916   TOKENID s;
00917   for (root = totalnum/2; root >= 1; root--) {
00918     SCOPY(s, SD(root));
00919     parent = root;
00920     while ((child = parent * 2) <= totalnum) {
00921       if (child < totalnum && SVAL(child) > SVAL(child+1)) {
00922         child++;
00923       }
00924       if (STVAL <= SVAL(child)) {
00925         break;
00926       }
00927       SCOPY(SD(parent), SD(child));
00928       parent = child;
00929     }
00930     SCOPY(SD(parent), s);
00931   }
00932   n = totalnum;
00933   while ( n > totalnum - neednum) {
00934     SCOPY(s, SD(n));
00935     SCOPY(SD(n), SD(1));
00936     n--;
00937     parent = 1;
00938     while ((child = parent * 2) <= n) {
00939       if (child < n && SVAL(child) > SVAL(child+1)) {
00940         child++;
00941       }
00942       if (STVAL <= SVAL(child)) {
00943         break;
00944       }
00945       SCOPY(SD(parent), SD(child));
00946       parent = child;
00947     }
00948     SCOPY(SD(parent), s);
00949   }
00950 }
00951 
00982 static void
00983 sort_token_no_order(int neednum, int *start, int *end)
00984 {
00985   int totalnum = tnum[tn];
00986   int restnum;
00987 
00988   restnum = totalnum - neednum;
00989 
00990   if (neednum >= totalnum) {
00991     /* no need to sort */
00992     *start = 0;
00993     *end = totalnum - 1;
00994   } else if (neednum < restnum)  {
00995     /* needed num is smaller than rest, so sort for the needed tokens */
00996     sort_token_upward(neednum,totalnum);
00997     *start = totalnum - neednum;
00998     *end = totalnum - 1;
00999   } else {
01000     /* needed num is bigger than rest, so sort for the rest token */
01001     sort_token_downward(restnum,totalnum);
01002     *start = 0;
01003     *end = neednum - 1;
01004   }
01005 }
01006     
01007 
01008 #ifdef SP_BREAK_CURRENT_FRAME
01009 /* -------------------------------------------------------------------- */
01010 /*                     ショートポーズ・セグメンテーション               */
01011 /*                     short pause segmentation                         */
01012 /* -------------------------------------------------------------------- */
01013 /* ====================================================================== */
01014 /* sp segmentation */
01015 /*
01016   |---************-----*********************-------*******--|
01017 [input segments]
01018   |-------------------|
01019                   |-------------------------------|
01020                                             |---------------|
01021 
01022                      
01023   |-------------------|t-2
01024                        |t-1 ... token processed (= lastlen)
01025                         |t  ... outprob computed
01026                        
01027 */
01028 
01029 static boolean in_sparea;       /* TRUE if we are within a pause area */
01030 static int sparea_start;        /* start frame of pause area */
01031 static int tmp_sparea_start;
01032 #ifdef SP_BREAK_RESUME_WORD_BEGIN
01033 static WORD_ID tmp_sp_break_last_word;
01034 #else
01035 static WORD_ID last_tre_word;
01036 #endif
01037 static boolean first_sparea;    /* TRUE if this is the first pause segment in a input stream */
01038 static int sp_duration;         /* number of current successive sp frame */
01039 
01066 boolean
01067 is_sil(WORD_ID w, WORD_INFO *winfo, HTK_HMM_INFO *hmm)
01068 {
01069   /* num of phones should be 1 */
01070   if (winfo->wlen[w] > 1) return FALSE;
01071 
01072   /* short pause (specified by "-spmodel") */
01073   if (winfo->wseq[w][0] == hmm->sp) return TRUE;
01074 
01075   /* head/tail sil */
01076   if (w == winfo->head_silwid || w == winfo->tail_silwid) return TRUE;
01077 
01078   /* otherwise */
01079   return FALSE;
01080 }
01081 
01105 static boolean
01106 detect_end_of_segment(BACKTRELLIS *backtrellis, int time, WCHMM_INFO *wchmm)
01107 {
01108   TRELLIS_ATOM *tre;
01109   LOGPROB maxscore = LOG_ZERO;
01110   TRELLIS_ATOM *tremax = NULL;
01111   int count = 0;
01112   boolean detected = FALSE;
01113 
01114   /* look for the best trellis word on the given time frame */
01115   for(tre = backtrellis->list; tre != NULL && tre->endtime == time; tre = tre->next) {
01116     if (maxscore < tre->backscore) {
01117       maxscore = tre->backscore;
01118       tremax = tre;
01119     }
01120     count++;
01121   }
01122   if (tremax == NULL) { /* no word end: possible in the very beggining of input*/
01123     detected = TRUE;            /* assume it's in the short-pause duration */
01124   } else if (count > 0) {       /* many words found --- check if maximum is sp */
01125     if (is_sil(tremax->wid, wchmm->winfo, wchmm->hmminfo)) {
01126       detected = TRUE;
01127     }
01128   }
01129   
01130   /* sp区間持続チェック */
01131   /* check sp segment duration */
01132   if (in_sparea && detected) {  /* we are already in sp segment and sp continues */
01133     sp_duration++;              /* increment count */
01134 #ifdef SP_BREAK_RESUME_WORD_BEGIN
01135     /* resume word at the "beggining" of sp segment */
01136     /* if this segment has triggered by (tremax == NULL) (in case the first
01137        several frame of input), the sp word (to be used as resuming
01138        word in the next segment) is not yet set. it will be detected here */
01139     if (tmp_sp_break_last_word == WORD_INVALID) {
01140       if (tremax != NULL) tmp_sp_break_last_word = tremax->wid;
01141     }
01142 #else
01143     /* resume word at the "end" of sp segment */
01144     /* simply update the best sp word */
01145     if (tremax != NULL) last_tre_word = tremax->wid;
01146 #endif
01147   }
01148 
01149   /* sp区間開始チェック */
01150   /* check if sp segment begins at this frame */
01151   else if (!in_sparea && detected) {
01152     /* 一時的に開始フレームとしてマーク */
01153     /* mark this frame as "temporal" begging of short-pause segment */
01154     tmp_sparea_start = time;
01155 #ifdef SP_BREAK_RESUME_WORD_BEGIN
01156     /* sp 区間開始時点の最尤単語を保存 */
01157     /* store the best word in this frame as resuming word */
01158     tmp_sp_break_last_word = tremax ? tremax->wid : WORD_INVALID;
01159 #endif
01160     in_sparea = TRUE;           /* yes, we are in sp segment */
01161     sp_duration = 1;            /* initialize duration count */
01162 #ifdef SP_BREAK_DEBUG
01163     printf("sp start %d\n", time);
01164 #endif /* SP_BREAK_DEBUG */
01165   }
01166   
01167   /* sp 区間終了チェック */
01168   /* check if sp segment ends at this frame */
01169   else if (in_sparea && !detected) {
01170     /* (time-1) is end frame of pause segment */
01171     in_sparea = FALSE;          /* we are not in sp segment */
01172 #ifdef SP_BREAK_DEBUG
01173     printf("sp end %d\n", time);
01174 #endif /* SP_BREAK_DEBUG */
01175     /* sp 区間長チェック */
01176     /* check length of the duration*/
01177     if (sp_duration < sp_frame_duration) {
01178       /* 短すぎる: 第１パスを中断せず続行 */
01179       /* too short segment: not break, continue 1st pass */
01180 #ifdef SP_BREAK_DEBUG
01181       printf("too short (%d<%d), ignored\n", sp_duration, sp_frame_duration);
01182 #endif /* SP_BREAK_DEBUG */
01183     } else if (first_sparea) {
01184       /* 最初のsp区間は silB にあたるので,第１パスを中断せず続行 */
01185       /* do not break at first sp segment: they are silB */
01186       first_sparea = FALSE;
01187 #ifdef SP_BREAK_DEBUG
01188       printf("first silence, ignored\n");
01189 #endif /* SP_BREAK_DEBUG */
01190     } else {
01191       /* 区間終了確定, 第１パスを中断して第2パスへ */
01192       /* break 1st pass */
01193 #ifdef SP_BREAK_DEBUG
01194       printf(">> segment [%d..%d]\n", sparea_start, time-1);
01195 #else
01196       if (idc_on) j_printerr("|");
01197 #endif /* SP_BREAK_DEBUG */
01198       /* store begging frame of the segment */
01199       sparea_start = tmp_sparea_start;
01200 #ifdef SP_BREAK_RESUME_WORD_BEGIN
01201       /* resume word = most likely sp word on beginning frame of the segment */
01202       sp_break_last_word = tmp_sp_break_last_word;
01203 #else
01204       /* resume word = most likely sp word on end frame of the segment */
01205       sp_break_last_word = last_tre_word;
01206 #endif
01207 
01208       /*** segment: [sparea_start - time-1] ***/
01209       return(TRUE);
01210     }
01211   }
01212     
01213 #ifdef SP_BREAK_EVAL
01214   printf("[%d %d %d]\n", time, count, (detected) ? 50 : 0);
01215 #endif
01216   return (FALSE);
01217 }
01218 
01219 #endif /* SP_BREAK_CURRENT_FRAME */
01220 
01221 
01222 
01223 /* -------------------------------------------------------------------- */
01224 /*             第１パス(フレーム同期ビームサーチ) メイン                */
01225 /*           main routines of 1st pass (frame-synchronous beam search)  */
01226 /* -------------------------------------------------------------------- */
01227 
01246 static void
01247 init_nodescore(HTK_Param *param, WCHMM_INFO *wchmm)
01248 {
01249   TOKENID newid;
01250   TOKEN2 *new;
01251 #ifdef USE_NGRAM
01252   WORD_ID beginword;
01253 #endif
01254   int node;
01255 #ifdef USE_DFA
01256   int i;
01257 #endif
01258 
01259   /* 初期仮説用単語履歴 */
01260   /* setup initial word context */
01261 #ifdef SP_BREAK_CURRENT_FRAME
01262   /* initial word context = last non-sp word of previous 2nd pass at last segment*/
01263   if (sp_break_last_nword == wchmm->winfo->tail_silwid) {
01264     /* if end with silE, initialize as normal start of sentence */
01265     bos.wid = WORD_INVALID;
01266   } else {
01267     bos.wid = sp_break_last_nword;
01268   }
01269 #else
01270   bos.wid = WORD_INVALID;       /* no context */
01271 #endif
01272   bos.begintime = bos.endtime = -1;
01273 
01274   /* ノード・トークンを初期化 */
01275   /* clear tree lexicon nodes and tokens */
01276   for(node=0;node<totalnodenum;node++) {
01277     token[node] = TOKENID_UNDEFINED;
01278   }
01279   tnum[0] = tnum[1]  = 0;
01280   
01281 #ifdef PASS1_IWCD
01282   /* 出力確率計算キャッシュを初期化 */
01283   /* initialize outprob cache */
01284   outprob_style_cache_init(wchmm);
01285 #endif
01286 
01287   /* 初期仮説の作成: 初期単語の決定と初期トークンの生成 */
01288   /* initial word hypothesis */
01289 #ifdef USE_NGRAM
01290   
01291 #ifdef SP_BREAK_CURRENT_FRAME
01292   if (sp_break_last_word != WORD_INVALID) { /* last segment exist */
01293     /* 開始単語＝前のセグメント計算時の最後の最尤単語 */
01294     /* 文終了単語(silE,句点(IPAモデル))なら，silB で開始 */
01295     /* initial word = best last word hypothesis on the last segment */
01296     /* if silE or sp, begin with silB */
01297     /*if (is_sil(sp_break_last_word, wchmm->winfo, wchmm->hmminfo)) {*/
01298     if (sp_break_last_word == wchmm->winfo->tail_silwid) {
01299       beginword = wchmm->winfo->head_silwid;
01300       bos.wid = WORD_INVALID;   /* reset initial word context */
01301     } else {
01302       beginword = sp_break_last_word;
01303     }
01304   } else {
01305     /* initial word fixed to silB */
01306     beginword = wchmm->winfo->head_silwid;
01307   }
01308 #else
01309   /* initial word fixed to silB */
01310   beginword = wchmm->winfo->head_silwid;
01311 #endif
01312 #ifdef SP_BREAK_DEBUG
01313   printf("startword=[%s], last_nword=[%s]\n",
01314          (beginword == WORD_INVALID) ? "WORD_INVALID" : wchmm->winfo->wname[beginword],
01315          (bos.wid == WORD_INVALID) ? "WORD_INVALID" : wchmm->winfo->wname[bos.wid]);
01316 #endif
01317   /* create the first token at the first node of initial word */
01318   newid = create_token();
01319   new = &(tlist[tn][newid]);
01320   /* initial node = head node of the beginword */
01321 #ifdef MULTIPATH_VERSION
01322   node = wchmm->wordbegin[beginword];
01323 #else
01324   node = wchmm->offset[beginword][0];
01325 #endif /* MULTIPATH_VERSION */
01326   /* set initial LM score */
01327   if (wchmm->state[node].scid != 0) {
01328     /* if initial node is on a factoring branch, use the factored score */
01329     new->last_lscore = max_successor_prob(wchmm, bos.wid, node);
01330   } else {
01331     /* else, set to 0.0 */
01332     new->last_lscore = 0.0;
01333   }
01334 #ifdef FIX_PENALTY
01335   new->last_lscore = new->last_lscore * lm_weight;
01336 #else
01337   new->last_lscore = new->last_lscore * lm_weight + lm_penalty;
01338 #endif
01339   /* set initial word history */
01340   new->last_tre = &bos;
01341   new->last_cword = bos.wid;
01342 #ifdef MULTIPATH_VERSION
01343   /* set initial score using the initial LM score */
01344   new->score = new->last_lscore;
01345 #else
01346   /* set initial score using the initial LM score and AM score of the first state */
01347   new->score = outprob_style(wchmm, node, bos.wid, 0, param) + new->last_lscore;
01348 #endif /* MULTIPATH_VERSION */
01349   /* assign the initial node to token list */
01350   node_assign_token(node, newid);
01351   
01352 #else  /* USE_DFA */
01353   
01354   /* 初期仮説: 文法上文頭に接続しうる単語集合 */
01355   /* initial words: all words that can be begin of sentence grammatically */
01356   /* アクティブな文法に属する単語のみ許す */
01357   /* only words in active grammars are allowed to be an initial words */
01358   {
01359     MULTIGRAM *m;
01360     int t,tb,te;
01361     WORD_ID iw;
01362 
01363     /* for all active grammar */
01364     for(m = gramlist; m; m = m->next) {
01365       if (m->active) {
01366         tb = m->cate_begin;
01367         te = tb + m->dfa->term_num;
01368         for(t=tb;t<te;t++) {
01369           /* for all word categories that belong to the grammar */
01370           if (dfa_cp_begin(dfa, t) == TRUE) {
01371             /* if the category can appear at beginning of sentence, */
01372             for (iw=0;iw<dfa->term.wnum[t];iw++) {
01373               /* create the initial token at the first node of all words that belongs to the category */
01374               i = dfa->term.tw[t][iw];
01375 #ifdef MULTIPATH_VERSION
01376               node = wchmm->wordbegin[i];
01377 #else
01378               node = wchmm->offset[i][0];
01379 #endif /* MULTIPATH_VERSION */
01380               /* in tree lexicon, words in the same category may share the same root node, so skip it if the node has already existed */
01381               if (node_exist_token(tn, node, bos.wid) != TOKENID_UNDEFINED) continue;
01382               newid = create_token();
01383               new = &(tlist[tn][newid]);
01384               new->last_tre = &bos;
01385 #ifdef MULTIPATH_VERSION
01386               new->score = 0.0;
01387 #else
01388               new->score = outprob_style(wchmm, node, bos.wid, 0, param);
01389 #endif /* MULTIPATH_VERSION */
01390               node_assign_token(node, newid);
01391             }
01392           }
01393         }
01394       }
01395     }
01396   }
01397 /* 
01398  *   for (i=0;i<wchmm->winfo->num;i++) {
01399  *     if (dfa->cp_begin[wchmm->winfo->wton[i]] == TRUE) {
01400  *       node = wchmm->offset[i][0];
01401  *       if (node_exist_token(tn, node, bos.wid) != TOKENID_UNDEFINED) continue;
01402  *       newid = create_token();
01403  *       new = &(tlist[tn][newid]);
01404  *       new->last_tre = &bos;
01405  *       new->score = outprob_style(wchmm, node, bos.wid, 0, param);
01406  *       node_assign_token(node, newid);
01407  *     }
01408  *   }
01409  */
01410   
01411 #endif /* USE_DFA */
01412 }
01413 
01414 /******************************************************/
01415 /* フレーム同期ビーム探索の実行 --- 最初のフレーム用  */
01416 /* frame synchronous beam search --- first frame only */
01417 /******************************************************/
01418 
01444 void
01445 get_back_trellis_init(HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis)
01446 {
01447   
01448   /* Viterbi演算用ワークエリアのスイッチャー tl,tn の初期値設定 */
01449   /* tn: このフレーム用ID   tl: １フレーム前のID */
01450   /* initialize switch tl, tn for Viterbi computation */
01451   /* tn: this frame  tl: last frame */
01452   tn = 0;
01453   tl = 1;
01454 
01455   /* 結果の単語トレリスを格納するバックトレリス構造体を初期化 */
01456   /* initialize backtrellis structure to store resulting word trellis */
01457   bt_prepare(backtrellis);
01458 
01459   /* ワークエリアを確保 */
01460   /* malloc work area */
01461   /* 使用するトークン量 = viterbi時に遷移先となる状態候補の数
01462    * 予測: ビーム数 x 2 (自己遷移+次状態) + 木構造化辞書のルートノード数
01463    */
01464   /* assumed initial number of needed tokens: beam width x 2 (self + next trans.)
01465    * + root node on the tree lexicon (for inter-word trans.)
01466    */
01467   /*malloc_nodes(wchmm->n);*/
01468   malloc_nodes(wchmm->n, trellis_beam_width * 2 + wchmm->startnum, trellis_beam_width);
01469   
01470   /* 初期スコアを nodescore[tn] にセット */
01471   /* set initial score to nodescore[tn] */
01472   init_nodescore(param, wchmm);
01473   sort_token_no_order(trellis_beam_width, &n_start, &n_end);
01474 
01475   /* テキスト出力を初期化 */
01476   /* initialize message output */
01477   result_pass1_begin();
01478   /* 漸次出力を行なう場合のインターバルを計算 */
01479   /* set interval frame for progout */
01480   progout_interval_frame = (int)((float)progout_interval / ((float)param->header.wshift / 10000.0));
01481 
01482   /* 進行状況表示を初期化 */
01483   /* progress bar setting */
01484   if (!realtime_flag && verbose_flag && (!progout_flag) && isatty(1)) {
01485     idc_on = TRUE;
01486   } else { 
01487     idc_on = FALSE;
01488   }
01489   
01490 #ifdef SP_BREAK_CURRENT_FRAME
01491   /* ショートポーズセグメンテーション用パラメータの初期化 */
01492   /* initialize parameter for short pause segmentation */
01493   in_sparea = TRUE;             /* assume beginning is silence */
01494   sparea_start = tmp_sparea_start = 0; /* set start frame to 0 */
01495 #ifdef SP_BREAK_RESUME_WORD_BEGIN
01496   tmp_sp_break_last_word = WORD_INVALID;
01497 #endif
01498   sp_break_last_word = WORD_INVALID;
01499   /* 最初のセグメント: 次の非ポーズフレームで第2パスへ移行しない */
01500   /* the first end of pause segment should be always silB, so
01501      skip the first segment */
01502   first_sparea = TRUE;
01503   sp_break_2_begin_word = WORD_INVALID;
01504 #endif
01505 
01506   if (gmm != NULL) {
01507     /* GMM 計算の初期化 */
01508     gmm_prepare(gmm);
01509   }
01510 }
01511 
01512 /* local work areas for get_back_trellis_proceed() */
01513 static TRELLIS_ATOM *tre; 
01514 static int node; 
01515 static int stid; 
01516 static A_CELL *ac; 
01517 static int next_node2;          
01518 #ifdef USE_NGRAM
01519 static LOGPROB tmpprob; 
01520 static LOGPROB *iwparray; 
01521 #endif
01522 #ifdef UNIGRAM_FACTORING
01523 /* for wordend processing with 1-gram factoring */
01524 static LOGPROB wordend_best_score; 
01525 static int wordend_best_node;   
01526 static TRELLIS_ATOM *wordend_best_tre; 
01527 static WORD_ID wordend_best_last_cword; 
01528 static int isoid; 
01529 #endif
01530 
01531 /*****************************************************/
01532 /* frame synchronous beam search --- proceed 1 frame */
01533 /* フレーム同期ビーム探索の実行 --- 1フレーム進める  */
01534 /*****************************************************/
01535 
01575 boolean
01576 get_back_trellis_proceed(int t, HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis
01577 #ifdef MULTIPATH_VERSION
01578                          , boolean final /* TRUE if this is final frame */
01579 #endif
01580                          )
01581 {
01582   LOGPROB tmpsum;
01583   int j, next_node, sword;
01584   TOKEN2  *tk, *tknext;
01585   TOKENID  tknextid;
01586 #ifdef USE_NGRAM
01587   LOGPROB ngram_score_cache;
01588 #endif
01589 
01590   /*********************/
01591   /* 1. 初期化         */
01592   /*    initialization */
01593   /*********************/
01594 
01595   /* tl と tn を入れ替えて作業領域を切り替え */
01596   /* tl (= 直前の tn) は直前フレームの結果を持つ */
01597   /* swap tl and tn to switch work buffer */
01598   /* tl (= last tn) holds result of the previous frame */
01599   tl = tn;
01600   if (tn == 0) tn = 1; else tn = 0;
01601 
01602   /* 進行状況表示を更新 */
01603   /* update progress bar */
01604   if (idc_on) {
01605 #ifdef SP_BREAK_CURRENT_FRAME
01606     if (in_sparea) j_printerr("."); else j_printerr("-");
01607 #else  /* normal */
01608     j_printerr(".");
01609 #endif /* SP_BREAK_CURRENT_FRAME */
01610   }
01611 
01612 #ifdef UNIGRAM_FACTORING
01613   /* 1-gram factoring では単語先頭での言語確率が一定で直前単語に依存しない
01614      ため，単語間 Viterbi において選ばれる直前単語は,次単語によらず共通である．
01615      よって単語終端からfactoring値のある単語先頭への遷移は１つにまとめられる．
01616      ただし，木から独立した単語については, 単語先頭で履歴に依存した2-gramが
01617      与えられるため, 最尤の単語間 Viterbi パスは次単語ごとに異なる．
01618      よってそれらについてはまとめずに別に計算する */
01619   /* In 1-gram factoring, the language score on the word-head node is constant
01620      and independent of the previous word.  So, the same word hypothesis will
01621      be selected as the best previous word at the inter-word Viterbi
01622      processing.  So, in inter-word processing, we can (1) select only
01623      the best word-end hypothesis, and then (2) process viterbi from the node
01624      to each word-head node.  On the other hand, the isolated words,
01625      i.e. words not sharing any node with other word, has unique word-head
01626      node and the true 2-gram language score is determined at the top node.
01627      In such case the best word hypothesis prior to each node will differ
01628      according to the language scores.  So we have to deal such words separately. */
01629   /* initialize max value to delect best word-end hypothesis */
01630   wordend_best_score = LOG_ZERO;
01631 #endif
01632 
01633 #ifdef DEBUG
01634   /* debug */
01635   /* node_check_token(tl); */
01636 #endif
01637 
01638   /* トークンバッファを初期化: 直前フレームで使われた部分だけクリアすればよい */
01639   /* initialize token buffer: for speedup, only ones used in the last call will be cleared */
01640   clear_tokens(tl);
01641 
01642   /**************************/
01643   /* 2. Viterbi計算         */
01644   /*    Viterbi computation */
01645   /**************************/
01646   /* 直前フレームからこのフレームへの Viterbi 計算を行なう */
01647   /* tindex[tl][n_start..n_end] に直前フレーム上位ノードのIDが格納されている */
01648   /* do one viterbi computation from last frame to this frame */
01649   /* tindex[tl][n_start..n_end] holds IDs of survived nodes in last frame */
01650   for (j=n_start;j<=n_end;j++) {
01651 
01652     /* tk: 対象トークン  node: そのトークンを持つ木構造化辞書ノードID */
01653     /* tk: token data  node: lexicon tree node ID that holds the 'tk' */
01654     tk = &(tlist[tl][tindex[tl][j]]);
01655     node = tk->node;
01656     if (tk->score <= LOG_ZERO) continue; /* invalid node */
01657 
01658     /*********************************/
01659     /* 2.1. 単語内遷移               */
01660     /*      word-internal transition */
01661     /*********************************/
01662     for (ac = wchmm->state[node].ac; ac; ac = ac->next) {
01663       next_node = ac->arc;
01664       /* now, 'node' is the source node, 'next_node' is the destication node,
01665          and ac-> holds transition probability */
01666       /* tk->score is the accumulated score at the 'node' on previous frame */
01667 
01668       /******************************************************************/
01669       /* 2.1.1 遷移先へのスコア計算(遷移確率＋言語スコア)               */
01670       /*       compute score of destination node (transition prob + LM) */
01671       /******************************************************************/
01672       tmpsum = tk->score + ac->a;
01673 #ifdef USE_NGRAM
01674       ngram_score_cache = LOG_ZERO;
01675 #endif
01676       /* the next score at 'next_node' will be computed on 'tmpsum', and
01677          the new LM probability (if updated) will be stored on 'ngram_score_cache' at below */
01678 
01679 #ifndef CATEGORY_TREE
01680       /* 言語スコア factoring:
01681          arcが自己遷移でない単語内の遷移で，かつ遷移先にsuccessorリスト
01682          があれば，lexicon tree の分岐部分の遷移である */
01683       /* LM factoring:
01684          If this is not a self transition and destination node has successor
01685          list, this is branching transition
01686        */
01687       if (next_node != node) {
01688         if (wchmm->state[next_node].scid != 0
01689 #ifdef UNIGRAM_FACTORING
01690             /* 1-gram factoring 使用時は, 複数で共有される枝では
01691                wchmm->state[node].scid は負の値となり，その絶対値を
01692                添字として wchmm->fscore[] に単語集合の1-gramの最大値が格納
01693                されている．末端の枝(複数単語で共有されない)では，
01694                wchmm->state[node].scid は正の値となり，
01695                １単語を sc として持つのでそこで正確な2-gramを計算する */
01696             /* When uni-gram factoring,
01697                wchmm->state[node].scid is below 0 for shared branches.
01698                In this case the maximum uni-gram probability for sub-tree
01699                is stored in wchmm->fscore[- wchmm->state[node].scid].
01700                Leaf branches (with only one successor word): the scid is
01701                larger than 0, and has
01702                the word ID in wchmm->sclist[wchmm->state[node].scid].
01703                So precise 2-gram is computed in this point */
01704 #endif
01705             ){
01706 #ifdef USE_NGRAM
01707           /* ここで言語モデル確率を更新する */
01708           /* LM value should be update at this transition */
01709           /* N-gram確率からfactoring 値を計算 */
01710           /* compute new factoring value from N-gram probabilities */
01711 #ifdef FIX_PENALTY
01712           /* if at the beginning of sentence, not add lm_penalty */
01713           if (tk->last_cword == WORD_INVALID) {
01714             ngram_score_cache = max_successor_prob(wchmm, tk->last_cword, next_node) * lm_weight;
01715           } else {
01716             ngram_score_cache = max_successor_prob(wchmm, tk->last_cword, next_node) * lm_weight + lm_penalty;
01717           }
01718 #else
01719           ngram_score_cache = max_successor_prob(wchmm, tk->last_cword, next_node) * lm_weight + lm_penalty;
01720 #endif
01721           /* スコアの更新: tk->last_lscore に単語内での最後のfactoring値が
01722            入っているので, それをスコアから引いてリセットし, 新たなスコアを
01723            セットする */
01724           /* update score: since 'tk->last_lscore' holds the last LM factoring
01725              value in this word, we first remove the score from the current
01726              score, and then add the new LM value computed above. */
01727           tmpsum -= tk->last_lscore;
01728           tmpsum += ngram_score_cache;
01729           
01730 #else  /* USE_DFA --- not CATEGORY_TREE */
01731           /* 文法を用いる場合, カテゴリ単位の木構造化がなされていれば,
01732              接続制約は単語間遷移のみで扱われるので，factoring は必要ない．
01733              カテゴリ単位木構造化が行われない場合, 文法間の接続制約はここ
01734              で factoring で行われることになる．*/
01735           /* With DFA, we use category-pair constraint extracted from the DFA
01736              at this 1st pass.  So if we compose a tree lexicon per word's
01737              category, the each category tree has the same connection
01738              constraint and thus we can apply the constraint on the cross-word
01739              transition.  This per-category tree lexicon is enabled by default,
01740              and in the case the constraint will be applied at the word end.
01741              If you disable per-category tree lexicon by undefining
01742              'CATEGORY_TREE', the word-pair contrained will be applied in a
01743              factoring style at here.
01744           */
01745           
01746           /* 決定的factoring: 直前単語に対して,sub-tree内にカテゴリ対制約上
01747              接続しうる単語が１つもなければ, この遷移は不可 */
01748           /* deterministic factoring in grammar mode:
01749              transition disabled if there are totally no sub-tree word that can
01750              grammatically (in category-pair constraint) connect
01751              to the previous word.
01752            */
01753           if (!can_succeed(wchmm, tk->last_tre->wid, next_node)) {
01754             tmpsum = LOG_ZERO;
01755           }
01756           
01757 #endif /* USE_NGRAM */
01758         }
01759       }
01760 #endif /* CATEGORY_TREE */
01761       /* factoring not needed when DFA mode and uses category-tree */
01762 
01763       /****************************************/
01764       /* 2.1.2 遷移先ノードへトークン伝搬     */
01765       /*       pass token to destination node */
01766       /****************************************/
01767 
01768       if ((tknextid = node_exist_token(tn, next_node, tk->last_tre->wid)) != TOKENID_UNDEFINED) {
01769         /* 遷移先ノードには既に他ノードから伝搬済み: スコアが高いほうを残す */
01770         /* the destination node already has a token: compare score */
01771         tknext = &(tlist[tn][tknextid]);
01772         if (tknext->score < tmpsum) {
01773           /* その遷移先ノードが持つトークンの内容を上書きする(新規トークンは作らない) */
01774           /* overwrite the content of existing destination token: not create a new token */
01775           tknext->last_tre = tk->last_tre; /* propagate last word info */
01776 #ifdef USE_NGRAM
01777           tknext->last_cword = tk->last_cword; /* propagate last context word info */
01778           tknext->last_lscore = (ngram_score_cache != LOG_ZERO) ? ngram_score_cache : tk->last_lscore; /* set new LM score */
01779 #endif /* USE_NGRAM */
01780           tknext->score = tmpsum; /* set new score */
01781         }
01782       } else {
01783         /* 遷移先ノードは未伝搬: 新規トークンを作って割り付ける */
01784         /* token unassigned: create new token and assign */
01785         if (tmpsum > LOG_ZERO) { /* valid token */
01786           tknextid = create_token(); /* get new token */
01787           tknext = &(tlist[tn][tknextid]);
01788           /* if work area has been expanded at 'create_token()' above,
01789              the inside 'remalloc()' will destroy the 'tk' pointer.
01790              so, here we again set tk from token index */
01791           tk = &(tlist[tl][tindex[tl][j]]);
01792           tknext->last_tre = tk->last_tre; /* propagate last word info */
01793 #ifdef USE_NGRAM
01794           tknext->last_cword = tk->last_cword; /* propagate last context word info */
01795           tknext->last_lscore = (ngram_score_cache != LOG_ZERO) ? ngram_score_cache : tk->last_lscore; /* set new LM score */
01796 #endif /* USE_NGRAM */
01797           tknext->score = tmpsum; /* set new score */
01798           node_assign_token(next_node, tknextid); /* assign this new token to the next node */
01799         }
01800       }
01801     } /* END OF WORD-INTERNAL TRANSITION */
01802 
01803 #ifdef MULTIPATH_VERSION
01804     
01805   }
01806   /*******************************************************/
01807   /* 3. スコアでトークンをソートしビーム幅分の上位を決定 */
01808   /*    sort tokens by score up to beam width            */
01809   /*******************************************************/
01810   /* ヒープソートを用いてこの段のノード集合から上位(bwidth)個を得ておく */
01811   /* (上位内の順列は必要ない) */
01812   sort_token_no_order(trellis_beam_width, &n_start, &n_end);
01813   
01814   /*************************/
01815   /* 4. 単語間Viterbi計算  */
01816   /*    cross-word viterbi */
01817   /*************************/
01818   
01819   for(j=n_start; j<=n_end; j++) {
01820     tk = &(tlist[tn][tindex[tn][j]]);
01821     node = tk->node;
01822      
01823 #endif /* MULTIPATH_VERSION */
01824 
01825     /* 遷移元ノードが単語終端ならば */
01826     /* if source node is end state of a word, */
01827     if (wchmm->stend[node] != WORD_INVALID) {
01828 
01829       sword = wchmm->stend[node];
01830 
01831       /**************************/
01832       /* 2.2. トレリス単語保存  */
01833       /*      save trellis word */
01834       /**************************/
01835 
01836       /* この遷移元の単語終端ノードは「直前フレームで」生き残ったノード．
01837          (「このフレーム」でないことに注意！！)
01838          よってここで, 時間(t-1) を単語終端とするトレリス上の単語仮説
01839          (TRELLIS_ATOM)として，単語トレリス構造体に保存する．*/
01840       /* This source node (= word end node) has been survived in the
01841          "last" frame (notice: not "this" frame!!).  So this word end
01842          is saved here to the word trellis structure (BACKTRELLIS) as a
01843          trellis word (TRELLIS_ATOM) with end frame (t-1). */
01844       tre = (TRELLIS_ATOM *)mymalloc(sizeof(TRELLIS_ATOM));
01845       tre->wid = sword;         /* word ID */
01846       tre->backscore = tk->score; /* log score (AM + LM) */
01847       tre->begintime = tk->last_tre->endtime + 1; /* word beginning frame */
01848       tre->endtime   = t-1;     /* word end frame */
01849       tre->last_tre  = tk->last_tre; /* link to previous trellis word */
01850 #ifdef USE_NGRAM
01851       tre->lscore    = tk->last_lscore; /* log score (LM only) */
01852 #endif
01853       bt_store(backtrellis, tre); /* save to backtrellis */
01854       
01855       /******************************/
01856       /* 2.3. 単語間遷移            */
01857       /*      cross-word transition */
01858       /******************************/
01859 
01860 #ifdef MULTIPATH_VERSION
01861       /* 最終フレームであればここまで：遷移はさせない */
01862       /* If this is a final frame, does not do cross-word transition */
01863       if (final) continue;
01864 #endif
01865 
01866       /* 先ほどのトレリス単語treが，ここからの遷移先の単語先頭ノード以降の
01867          直前単語情報としても参照される */
01868       /* The trellis atom 'tre' will be refered as the word context
01869          information for next word-beginning nodes */
01870 
01871 #ifdef UNIGRAM_FACTORING
01872       /* ここで処理されるのは isolated words のみ，
01873          shared nodes はまとめてこのループの外で計算する */
01874       /* Only the isolated words will be processed here.
01875          The shared nodes with constant factoring values will be computed
01876          after this loop */
01877 #endif
01878 
01879 #ifdef USE_NGRAM
01880       /* 遷移元単語が末尾単語の終端なら，どこへも遷移させない */
01881       /* do not allow transition if the source word is end-of-sentence word */
01882       if (sword == wchmm->winfo->tail_silwid) continue;
01883 
01884 #ifdef UNIGRAM_FACTORING
01885       /* あとで共有単語先頭ノードに対して単語間遷移をまとめて計算するため，*/
01886       /* このループ内では最大尤度を持つ単語終端ノードを記録しておく */
01887       /* here we will record the best wordend node of maximum likelihood
01888          at this frame, to compute later the cross-word transitions toward
01889          shared factoring word-head node */
01890       if (wordend_best_score < tk->score
01891 #ifndef MULTIPATH_VERSION
01892           + wchmm->wordend_a[sword]
01893 #endif
01894           ) {
01895         wordend_best_score = tk->score
01896 #ifndef MULTIPATH_VERSION
01897           + wchmm->wordend_a[sword]
01898 #endif
01899           ;
01900         wordend_best_node = node;
01901         wordend_best_tre = tre;
01902         wordend_best_last_cword = tk->last_cword;
01903       }
01904 #endif
01905       
01906       /* N-gramにおいては常に全単語の接続を考慮する必要があるため，
01907          ここで単語間の言語確率値をすべて計算しておく．
01908          キャッシュは max_successor_prob_iw() 内で考慮．*/
01909       /* As all words are possible to connect in N-gram, we first compute
01910          all the inter-word LM probability here.
01911          Cache is onsidered in max_successor_prob_iw(). */
01912       if (wchmm->winfo->is_transparent[sword]) {
01913         iwparray = max_successor_prob_iw(wchmm, tk->last_cword);
01914       } else {
01915         iwparray = max_successor_prob_iw(wchmm, sword);
01916       }
01917 #endif
01918 
01919       /* すべての単語始端ノードに対して以下を実行 */
01920       /* for all beginning-of-word nodes, */
01921       /* wchmm->startnode[0..stid-1] ... 単語始端ノードリスト */
01922       /* wchmm->startnode[0..stid-1] ... list of word start node (shared) */
01923       for (stid = wchmm->startnum - 1; stid >= 0; stid--) {
01924         next_node = wchmm->startnode[stid];
01925 #ifdef MULTIPATH_VERSION
01926 #ifdef USE_NGRAM
01927         /* connection to the head silence word is not allowed */
01928         if (wchmm->wordbegin[wchmm->winfo->head_silwid] == next_node) continue;
01929 #endif
01930 #endif
01931 
01932         /*****************************************/
01933         /* 2.3.1. 単語間言語制約を適用           */
01934         /*        apply cross-word LM constraint */
01935         /*****************************************/
01936         
01937 #ifdef USE_NGRAM
01938         /* N-gram確率を計算 */
01939         /* compute N-gram probability */
01940 #ifdef UNIGRAM_FACTORING
01941         /* 1-gram factoring における単語間言語確率キャッシュの効率化:
01942            1-gram factoring は単語履歴に依存しないので，
01943            ここで参照する factoring 値の多くは
01944            wchmm->fscore[] に既に格納され, 探索中も不変である．
01945            よって計算が必要な単語(どの単語ともノードを共有しない単語)
01946            についてのみ iwparray[] で計算・キャッシュする． */
01947         /* Efficient cross-word LM cache:
01948            As 1-gram factoring values are independent of word context,
01949            they remain unchanged while search.  So, in cross-word LM
01950            computation, beginning-of-word states which share nodes with
01951            others and has factoring value in wchmm does not need cache.
01952            So only the unshared beginning-of-word states are computed and
01953            cached here in iwparray[].
01954          */
01955         /* wchmm,start2isolate[0..stid-1] ... ノードを共有しない単語は
01956            その通しID, 共有する(キャッシュの必要のない)単語は -1 */
01957         /* wchmm->start2isolate[0..stid-1] ... isolate ID for
01958            beginning-of-word state.  value: -1 for states that has
01959            1-gram factoring value (share nodes with some other words),
01960            and ID for unshared words
01961          */
01962         isoid = wchmm->start2isolate[stid];
01963         /* 計算が必要でない単語先頭ノードはパスをまとめて後に計算するので
01964            ここではスキップ */
01965         /* the shared nodes will be computed afterward, so just skip them
01966            here */
01967         if (isoid == -1) continue;
01968         tmpprob = iwparray[isoid];
01969 #else
01970         tmpprob = iwparray[stid];
01971 #endif
01972 #endif
01973 
01974 #ifdef USE_NGRAM
01975         /* 遷移先の単語が先頭単語なら遷移させない．
01976            これは wchmm.c で該当単語に stid を割り振らないことで対応
01977            しているので，ここでは何もしなくてよい */
01978         /* do not allow transition if the destination word is
01979            beginning-of-sentence word.  This limitation is realized by
01980            not assigning 'stid' for the word in wchmm.c, so we have nothing
01981            to do here.
01982         */
01983 #endif
01984         
01985 #ifdef CATEGORY_TREE
01986         /* 文法の場合, 制約は決定的: カテゴリ対制約上許されない場合は遷移させない */
01987         /* With DFA and per-category tree lexicon,
01988            LM constraint is deterministic:
01989            do not allow transition if the category connection is not allowed
01990            (with category tree, constraint can be determined on top node) */
01991         if (dfa_cp(dfa, wchmm->winfo->wton[sword],
01992 #ifdef MULTIPATH_VERSION
01993                    wchmm->winfo->wton[wchmm->start2wid[stid]]
01994 #else
01995                    wchmm->winfo->wton[wchmm->ststart[next_node]]
01996 #endif /* MULTIPATH_VERSION */
01997                    ) == FALSE) continue;
01998 #endif
01999 
02000         /*******************************************************************/
02001         /* 2.3.2. 遷移先の単語先頭へのスコア計算(遷移確率＋言語スコア)     */
02002         /*        compute score of destination node (transition prob + LM) */
02003         /*******************************************************************/
02004         tmpsum = tk->score
02005 #ifndef MULTIPATH_VERSION
02006           + wchmm->wordend_a[sword]
02007 #endif
02008           ;
02009         /* 'tmpsum' now holds outgoing score from the wordend node */
02010 #ifdef USE_NGRAM
02011         /* 言語スコアを追加 */
02012         /* add LM score */
02013         ngram_score_cache = tmpprob * lm_weight + lm_penalty;
02014         tmpsum += ngram_score_cache;
02015         if (wchmm->winfo->is_transparent[sword] && wchmm->winfo->is_transparent[tk->last_cword]) {
02016           
02017           tmpsum += lm_penalty_trans;
02018         }
02019 #else  /* USE_DFA */
02020         /* grammar: 単語挿入ペナルティを追加 */
02021         /* grammar: add insertion penalty */
02022         tmpsum += penalty1;
02023 
02024         /* grammar: deterministic factoring (in case category-tree not enabled) */
02025 #ifdef CATEGORY_TREE
02026         /* no need to factoring */
02027 #else
02028         if (!can_succeed(wchmm, sword, next_node)) {
02029           tmpsum = LOG_ZERO;
02030         }
02031 #endif /* CATEGORY_TREE */
02032 #endif /* USE_NGRAM */
02033 
02034 
02035         /*********************************************************************/
02036         /* 2.3.3. 遷移先ノードへトークン伝搬(単語履歴情報は更新)             */
02037         /*        pass token to destination node (updating word-context info */
02038         /*********************************************************************/
02039 
02040 #ifndef MULTIPATH_VERSION
02041         next_node2 = next_node;
02042 #else
02043         for(ac=wchmm->state[next_node].ac; ac; ac=ac->next) {
02044           next_node2 = ac->arc;
02045 #endif
02046           
02047           if ((tknextid = node_exist_token(tn, next_node2, tre->wid)) != TOKENID_UNDEFINED) {
02048             /* 遷移先ノードには既に他ノードから伝搬済み: スコアが高いほうを残す */
02049             /* the destination node already has a token: compare score */
02050             tknext = &(tlist[tn][tknextid]);
02051             if (tknext->score < tmpsum) {
02052               /* その遷移先ノードが持つトークンの内容を上書きする(新規トークンは作らない) */
02053               /* overwrite the content of existing destination token: not create a new token */
02054 #ifdef USE_NGRAM
02055               tknext->last_lscore = ngram_score_cache; /* set new LM score */
02056               /* set last context word */
02057               if (wchmm->winfo->is_transparent[sword]) {
02058                 /* if this word is a "transparent" word, this word should be
02059                    excluded from a word history as a context for LM. In the case,
02060                    propagate the last context word to the new node */
02061                 tknext->last_cword = tk->last_cword;
02062               } else {
02063                 /* otherwise, set last context word to this word */
02064                 tknext->last_cword = sword;
02065               }
02066 #endif
02067               /* set new score */
02068               tknext->score = tmpsum;
02069 #ifdef MULTIPATH_VERSION
02070               tknext->score += ac->a;
02071 #endif
02072               /* 遷移先に，先ほど保存したswordのトレリス単語へのポインタを
02073                  「直前単語履歴情報」として伝搬 */
02074               /* pass destination the pointer to the saved trellis atom
02075                  corresponds to 'sword' as "previous word-context info". */
02076               tknext->last_tre = tre;
02077             }
02078           } else {
02079             /* 遷移先ノードは未伝搬: 新規トークンを作って割り付ける */
02080             /* token unassigned: create new token and assign */
02081             if (tmpsum > LOG_ZERO) { /* valid token */
02082               tknextid = create_token();
02083               tknext = &(tlist[tn][tknextid]);
02084               /* if work area has been expanded at 'create_token()' above,
02085                  the inside 'remalloc()' will destroy the 'tk' pointer.
02086                  so, here we again set tk from token index */
02087 #ifdef MULTIPATH_VERSION
02088               tk = &(tlist[tn][tindex[tn][j]]);
02089 #else
02090               tk = &(tlist[tl][tindex[tl][j]]);
02091 #endif
02092 #ifdef USE_NGRAM
02093               tknext->last_lscore = ngram_score_cache; /* set new LM score */
02094               /* set last context word */
02095               if (wchmm->winfo->is_transparent[sword]) {
02096                 /* if this word is a "transparent" word, this word should be
02097                    excluded from a word history as a context for LM. In the case,
02098                    propagate the last context word to the new node */
02099                 tknext->last_cword = tk->last_cword;
02100               } else {
02101                 /* otherwise, set last context word to this word */
02102                 tknext->last_cword = sword;
02103               }
02104 #endif
02105               tknext->score = tmpsum;
02106 #ifdef MULTIPATH_VERSION
02107               tknext->score += ac->a;
02108 #endif
02109             /* 遷移先に，先ほど保存したswordのトレリス単語へのポインタを
02110                「直前単語履歴情報」として伝搬 */
02111             /* pass destination the pointer to the saved trellis atom
02112                corresponds to 'sword' as "previous word-context info". */
02113               tknext->last_tre = tre;
02114               /* assign to the next node */
02115               node_assign_token(next_node2, tknextid);
02116             }
02117           }
02118 #ifdef MULTIPATH_VERSION
02119         }
02120 #endif
02121         
02122       } /* end of next word heads */
02123     } /* end of cross-word processing */
02124     
02125   } /* end of main viterbi loop */
02126 #ifdef UNIGRAM_FACTORING
02127   /***********************************************************/
02128   /* 2.4 単語終端からfactoring付き単語先頭への遷移 ***********/
02129   /*    transition from wordend to shared (factorized) nodes */
02130   /***********************************************************/
02131   /* wordend_best_* holds the best word ends at this frame. */
02132   if (wordend_best_score > LOG_ZERO) {
02133     node = wordend_best_node;
02134     sword = wchmm->stend[node];
02135     for (stid = wchmm->startnum - 1; stid >= 0; stid--) {
02136       next_node = wchmm->startnode[stid];
02137       /* compute transition from 'node' at end of word 'sword' to 'next_node' */
02138       /* skip isolated words already calculated in the above main loop */
02139       if (wchmm->start2isolate[stid] != -1) continue;
02140       /* rest should have 1-gram factoring score at wchmm->fscore */
02141       if (wchmm->state[next_node].scid >= 0) {
02142         j_error("InternalError: scid mismatch at 1-gram factoring of shared states\n");
02143       }
02144       tmpprob = wchmm->fscore[- wchmm->state[next_node].scid];
02145       ngram_score_cache = tmpprob * lm_weight + lm_penalty;
02146       tmpsum = wordend_best_score;
02147       tmpsum += ngram_score_cache;
02148       if (wchmm->winfo->is_transparent[sword] && wchmm->winfo->is_transparent[wordend_best_last_cword]) {
02149         tmpsum += lm_penalty_trans;
02150       }
02151       
02152 #ifndef MULTIPATH_VERSION
02153       next_node2 = next_node;
02154 #else
02155       for(ac=wchmm->state[next_node].ac; ac; ac=ac->next) {
02156         next_node2 = ac->arc;
02157 #endif
02158         if ((tknextid = node_exist_token(tn, next_node2, sword)) != TOKENID_UNDEFINED) {
02159           tknext = &(tlist[tn][tknextid]);
02160           if (tknext->score < tmpsum) {
02161             tknext->last_lscore = ngram_score_cache;
02162             if (wchmm->winfo->is_transparent[sword]) {
02163               tknext->last_cword = wordend_best_last_cword;
02164             } else {
02165               tknext->last_cword = sword;
02166             }
02167             tknext->score = tmpsum;
02168 #ifdef MULTIPATH_VERSION
02169             tknext->score += ac->a;
02170 #endif
02171             tknext->last_tre = wordend_best_tre;
02172           }
02173         } else {
02174           if (tmpsum > LOG_ZERO) { /* valid token */
02175             tknextid = create_token();
02176             tknext = &(tlist[tn][tknextid]);
02177             tknext->last_lscore = ngram_score_cache;
02178             if (wchmm->winfo->is_transparent[sword]) {
02179               tknext->last_cword = wordend_best_last_cword;
02180             } else {
02181               tknext->last_cword = sword;
02182             }
02183             tknext->score = tmpsum;
02184 #ifdef MULTIPATH_VERSION
02185             tknext->score += ac->a;
02186 #endif
02187             tknext->last_tre = wordend_best_tre;
02188             node_assign_token(next_node2, tknextid);
02189           }
02190         }
02191 #ifdef MULTIPATH_VERSION
02192       }
02193 #endif
02194       
02195     }
02196   }
02197 #endif /* UNIGRAM_FACTORING */
02198 
02199   /***************************************/
02200   /* 3. 状態の出力確率計算               */
02201   /*    compute state output probability */
02202   /***************************************/
02203 
02204   /* 次段の有効ノードについて出力確率を計算してスコアに加える */
02205   /* compute outprob for new valid (token assigned) nodes and add to score */
02206 #ifdef MULTIPATH_VERSION
02207   /* 今扱っているのが入力の最終フレームの場合出力確率は計算しない */
02208   /* don't calculate the last frame (transition only) */
02209   if (! final) {
02210 #endif
02211     for (j=0;j<tnum[tn];j++) {
02212       tk = &(tlist[tn][tindex[tn][j]]);
02213 #ifdef MULTIPATH_VERSION
02214       /* skip non-output state */
02215       if (wchmm->state[tk->node].out.state == NULL) continue;
02216 #endif
02217       tk->score += outprob_style(wchmm, tk->node, tk->last_tre->wid, t, param);
02218     }
02219 #ifdef MULTIPATH_VERSION
02220   }
02221 #endif
02222 
02223   if (gmm != NULL) {
02224     /* GMM 計算を行う */
02225     gmm_proceed(gmm, param, t);
02226   }
02227 
02228   /*******************************************************/
02229   /* 4. スコアでトークンをソートしビーム幅分の上位を決定 */
02230   /*    sort tokens by score up to beam width            */
02231   /*******************************************************/
02232 
02233   /* tlist[tl]を次段のためにリセット */
02234   clear_tlist(tl);
02235 
02236   /* ヒープソートを用いてこの段のノード集合から上位(bwidth)個を得ておく */
02237   /* (上位内の順列は必要ない) */
02238   sort_token_no_order(trellis_beam_width, &n_start, &n_end);
02239 
02240   /* check for sort result */
02241 /* 
02242  *     j_printf("%d: vwidth=%d / %d\n",t, vwidth[tn], wchmm->n);
02243  */
02244   /* make sure LOG_ZERO not exist width vwidth[tn] */
02245 /* 
02246  *     for (j=0;j<vwidth[tn];j++) {
02247  *       if (nodescore[tn][hsindex[tn][j+1]] <= LOG_ZERO) {
02248  *         j_error("dsadsadas %d %d\n",hsindex[tn][j+1], nodescore[tn][hsindex[tn][j+1]]);
02249  *       }
02250  *     }
02251  */
02252   
02253   /***************/
02254   /* 5. 終了処理 */
02255   /*    finalize */
02256   /***************/
02257   if (progout_flag) {
02258     /* 漸次出力: 現フレームのベストパスを一定時間おきに上書き出力 */
02259     /* progressive result output: output current best path in certain time interval */
02260     if ((t % progout_interval_frame) == 0) {
02261       bt_current_max(backtrellis, t-1, wchmm->winfo);
02262     }
02263   }
02264   /* j_printf("%d: %d\n",t,tnum[tn]); */
02265   /* for debug: output current max word */
02266   if (debug2_flag) {
02267     bt_current_max_word(backtrellis, t-1, wchmm->winfo);
02268   }
02269 
02270 #ifdef SP_BREAK_CURRENT_FRAME
02271   /* ショートポーズセグメンテーション: 直前フレームでセグメントが切れたかどうかチェック */
02272   if (detect_end_of_segment(backtrellis, t-1, wchmm)) {
02273     /* セグメント終了検知: 第１パスここで中断 */
02274     return FALSE;               /* segment: [sparea_start..t-2] */
02275   }
02276 #endif
02277 
02278   /* ビーム内ノード数が 0 になってしまったら，強制終了 */
02279   if (tnum[tn] == 0) {
02280     j_printerr("Error: %dth frame: no nodes left in beam! model mismatch or wrong input?\n", t);
02281     return(FALSE);
02282   }
02283 
02284   return(TRUE);
02285     
02286 }
02287 
02288 /*************************************************/
02289 /* frame synchronous beam search --- last frame  */
02290 /* フレーム同期ビーム探索の実行 --- 最終フレーム */
02291 /*************************************************/
02292 
02316 void
02317 get_back_trellis_end(HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis)
02318 {
02319   int t, node, j;
02320   TOKEN2 *tk;
02321 
02322   /* 最後にビーム内に残った単語終端トークンを処理する */
02323   /* process the last wordend tokens */
02324 
02325 #ifdef MULTIPATH_VERSION
02326   
02327   /* 単語末ノードへの遷移のみ計算 */
02328   /* only arcs to word-end node is calculated */
02329   get_back_trellis_proceed(param->samplenum, param, wchmm, backtrellis, TRUE);
02330   
02331 #else  /* ~MULTIPATH_VERSION */
02332   
02333   t = param->samplenum;
02334   tl = tn;
02335   if (tn == 0) tn = 1; else tn = 0;
02336   for (j=n_start; j<=n_end; j++) {
02337     tk = &(tlist[tl][tindex[tl][j]]);
02338     node = tk->node;
02339     if (wchmm->stend[node] != WORD_INVALID) {
02340       tre = (TRELLIS_ATOM *)mymalloc(sizeof(TRELLIS_ATOM));
02341       tre->wid = wchmm->stend[node];
02342       tre->backscore = tk->score;
02343       tre->begintime = tk->last_tre->endtime + 1;
02344       tre->endtime   = t-1;
02345       tre->last_tre  = tk->last_tre;
02346 #ifdef USE_NGRAM
02347       tre->lscore    = tk->last_lscore;
02348 #endif
02349       bt_store(backtrellis, tre);
02350     }
02351   }
02352 
02353 #endif /* MULTIPATH_VERSION */
02354 
02355 #ifdef SP_BREAK_CURRENT_FRAME
02356   /*if (detect_end_of_segment(backtrellis, param->samplenum-1, winfo)) {
02357     return;
02358     }*/
02359 #endif
02360 }
02361 
02362 /*************************/
02363 /* 探索終了 --- 終了処理 */
02364 /* end of search         */
02365 /*************************/
02398 LOGPROB
02399 finalize_1st_pass(BACKTRELLIS *backtrellis, WORD_INFO *winfo, int len)
02400 {
02401   LOGPROB lastscore;
02402   int mseclen;
02403   boolean ok_p;
02404  
02405   backtrellis->framelen = len;
02406 
02407   /* rejectshort 指定時, 入力が短ければここで第1パス結果を出力しない */
02408   /* ここでは reject はまだ行わず, 後で reject する */
02409   /* suppress 1st pass output if -rejectshort and input shorter than specified */
02410   /* the actual rejection will be done later at main */
02411   ok_p = TRUE;
02412   if (rejectshortlen > 0) {
02413     mseclen = (float)len * (float)smpPeriod * (float)fshift / 10000.0;
02414     if (mseclen < rejectshortlen) {
02415       ok_p = FALSE;
02416     }
02417   }
02418   
02419   /* 単語トレリス(backtrellis) を整理: トレリス単語の再配置とソート */
02420   /* re-arrange backtrellis: index them by frame, and sort by word ID */
02421   if (ok_p) {
02422     bt_relocate_rw(backtrellis);
02423     bt_sort_rw(backtrellis);
02424     if (backtrellis->num == NULL) {
02425       if (backtrellis->framelen > 0) j_printerr("no survived word!\n");
02426       ok_p = FALSE;
02427     }
02428   }
02429 
02430   /* 結果を表示する (best 仮説)*/
02431   /* output 1st pass result (best hypothesis) */
02432   if (verbose_flag && (!progout_flag)) j_printerr("\n");
02433   if (ok_p) {
02434     lastscore = print_1pass_result(backtrellis, len, winfo);
02435   } else {
02436     lastscore = LOG_ZERO;
02437   }
02438 
02439 #ifdef USE_NGRAM
02440   /* free succesor cache */
02441   /* 次の認識でwchmm->winfoともに無変更の場合 free する必要なし */
02442   /* no need to free if wchmm and wchmm are not changed in the next recognition */
02443   /* max_successor_cache_free(); */
02444 #endif
02445   /* free nodes */
02446   free_nodes();
02447   
02448   if (ok_p) {
02449     if (gmm != NULL) {
02450       /* GMM 計算の終了 */
02451       gmm_end(gmm);
02452     }
02453   }
02454 
02455   /* return the best score */
02456   return(lastscore);
02457 }
02458 
02459 #ifdef SP_BREAK_CURRENT_FRAME
02460 /*******************************************************************/
02461 /* 第１パスセグメント終了処理 (ショートポーズセグメンテーション用) */
02462 /* end of 1st pass for a segment (for short pause segmentation)    */
02463 /*******************************************************************/
02493 void
02494 finalize_segment(BACKTRELLIS *backtrellis, HTK_Param *param, int len)
02495 {
02496   int t;
02497 
02498   /* トレリス始終端における最尤単語を第2パスの始終端単語として格納 */
02499   /* fix initial/last word hypothesis of the next 2nd pass to the best
02500      word hypothesis at the first/last frame in backtrellis*/
02501   set_terminal_words(backtrellis);
02502 
02503   /* パラメータを, 今第１パスが終了したセグメント区間と残りの区間に分割する．
02504      ただし接続部のsp区間部分(sparea_start..len-1)は「のりしろ」として両方に
02505      コピーする */
02506   /* Divide input parameter into two: the last segment and the rest.
02507      The short-pause area (sparea_start..len-1) is considered as "tab",
02508      copied in both parameters
02509    */
02510   /* param[sparea_start..framelen] -> rest_param
02511      param[0..len-1] -> param
02512      [sparea_start...len-1] overlapped
02513   */
02514 
02515   if (len != param->samplenum) {
02516 
02517     VERMES("segmented: processed length=%d\n", len);
02518     VERMES("segmented: next decoding will restart from %d\n", sparea_start);
02519     
02520     /* copy rest parameters for next process */
02521     rest_param = new_param();
02522     memcpy(&(rest_param->header), &(param->header), sizeof(HTK_Param_Header));
02523     rest_param->samplenum = param->samplenum - sparea_start;
02524     rest_param->header.samplenum = rest_param->samplenum;
02525     rest_param->veclen = param->veclen;
02526     rest_param->parvec = (VECT **)mymalloc(sizeof(VECT *) * rest_param->samplenum);
02527     /* copy 1: overlap area (copy) */
02528     for(t=sparea_start;t<len;t++) {
02529       rest_param->parvec[t-sparea_start] = (VECT *)mymalloc(sizeof(VECT) * rest_param->veclen);
02530       memcpy(rest_param->parvec[t-sparea_start], param->parvec[t], sizeof(VECT) * rest_param->veclen);
02531     }
02532     /* copy 2: rest area (move) */
02533     for(t=len;t<param->samplenum;t++) {
02534       rest_param->parvec[t-sparea_start] = param->parvec[t];
02535     }
02536 
02537     /* shrink original param to [0..len-1] */
02538     /* just shrink the parvec */
02539     param->samplenum = len;
02540     param->parvec = (VECT **)myrealloc(param->parvec, sizeof(VECT *) * param->samplenum);
02541     sp_break_last_nword_allow_override = TRUE;
02542     
02543   } else {
02544     
02545     /* last segment is on end of input: no rest parameter */
02546     rest_param = NULL;
02547     /* reset last_word info */
02548     sp_break_last_word = WORD_INVALID;
02549     sp_break_last_nword = WORD_INVALID;
02550     sp_break_last_nword_allow_override = FALSE;
02551   }
02552 }
02553 #endif /* SP_BREAK_CURRENT_FRAME */
02554   
02555 /********************************************************************/
02556 /* 第１パスを実行するメイン関数                                     */
02557 /* 入力をパイプライン処理する場合は realtime_1stpass.c を参照のこと */
02558 /* main function to execute 1st pass                                */
02559 /* the pipeline processing is not here: see realtime_1stpass.c      */
02560 /********************************************************************/
02561 
02599 void
02600 get_back_trellis(HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis,
02601 LOGPROB *backmax)
02602 {
02603   int t;
02604 
02605   /* 初期化及び t=0 を計算 */
02606   /* initialize and compute frame = 0 */
02607   get_back_trellis_init(param, wchmm, backtrellis);
02608 
02609   /* メインループ */
02610   /* main loop */
02611   for (
02612 #ifdef MULTIPATH_VERSION
02613        /* t = 0 should be computed here */
02614        t = 0
02615 #else
02616        /* t = 0 is already computed in get_back_trellis_init() */
02617        t = 1
02618 #endif
02619          ; t < param->samplenum; t++) {
02620     if (get_back_trellis_proceed(t, param, wchmm, backtrellis
02621 #ifdef MULTIPATH_VERSION
02622                                  ,FALSE
02623 #endif
02624                                  ) == FALSE
02625         || catch_intr_flag
02626         || (module_mode && module_wants_terminate())) {
02627       /* 探索中断: 処理された入力は 0 から t-2 まで */
02628       /* search terminated: processed input = [0..t-2] */
02629       /* この時点で第1パスを終了する */
02630       /* end the 1st pass at this point */
02631       *backmax = finalize_1st_pass(backtrellis, wchmm->winfo, t-1);
02632 #ifdef SP_BREAK_CURRENT_FRAME
02633       /* ショートポーズセグメンテーションの場合,
02634          入力パラメータ分割などの最終処理も行なう */
02635       /* When short-pause segmentation enabled */
02636       finalize_segment(backtrellis, param, t-1);
02637 #endif
02638       /* terminate 1st pass here */
02639       return;
02640     }
02641   }
02642   /* 最終フレームを計算 */
02643   /* compute the last frame of input */
02644   get_back_trellis_end(param, wchmm, backtrellis);
02645   /* 第1パス終了処理 */
02646   /* end of 1st pass */
02647   *backmax = finalize_1st_pass(backtrellis, wchmm->winfo, param->samplenum);
02648 #ifdef SP_BREAK_CURRENT_FRAME
02649   /* ショートポーズセグメンテーションの場合,
02650      入力パラメータ分割などの最終処理も行なう */
02651   /* When short-pause segmentation enabled */
02652   finalize_segment(backtrellis, param, param->samplenum);
02653 #endif
02654 }
02655 
02656 /* end of file */
Generated on Tue Mar 28 16:17:42 2006 for Julius by  doxygen 1.4.2