00001
00051
00052
00053
00054
00055
00056
00057
00058 #include <julius.h>
00059
00073 void
00074 bt_init(BACKTRELLIS *bt)
00075 {
00076 bt->num = NULL;
00077 bt->rw = NULL;
00078 bt->list = NULL;
00079 bt->root = NULL;
00080 }
00081
00095 void
00096 bt_prepare(BACKTRELLIS *bt)
00097 {
00098 TRELLIS_ATOM *tre, *tmp;
00099
00100
00101 mybfree2(&(bt->root));
00102
00103
00104 bt->num = NULL;
00105 bt->rw = NULL;
00106 bt->list = NULL;
00107 bt->root = NULL;
00108 }
00109
00110
00111
00133 void
00134 bt_store(BACKTRELLIS *bt, TRELLIS_ATOM *tatom)
00135 {
00136 #ifdef WORD_GRAPH
00137 tatom->within_context = FALSE;
00138 tatom->within_wordgraph = FALSE;
00139 #endif
00140 tatom->next = bt->list;
00141 bt->list = tatom;
00142
00143
00144
00145 }
00146
00160 void
00161 bt_relocate_rw(BACKTRELLIS *bt)
00162 {
00163 TRELLIS_ATOM *tre;
00164 int t;
00165 int totalnum, n;
00166 TRELLIS_ATOM **tmp;
00167
00168 if (bt->framelen == 0) {
00169 bt->num = NULL;
00170 return;
00171 }
00172
00173 bt->num = (int *)mybmalloc2(sizeof(int) * bt->framelen, &(bt->root));
00174
00175
00176 for (t=0;t<bt->framelen;t++) bt->num[t] = 0;
00177 totalnum = 0;
00178 for (tre=bt->list;tre;tre=tre->next) {
00179 #ifdef SP_BREAK_CURRENT_FRAME
00180
00181 if (tre->endtime >= bt->framelen) continue;
00182 #endif
00183 bt->num[tre->endtime]++;
00184 totalnum++;
00185 }
00186
00187 if (totalnum <= 0) {
00188 free(bt->num);
00189 bt->num = NULL;
00190 return;
00191 }
00192
00193
00194 bt->rw = (TRELLIS_ATOM ***)mybmalloc2(sizeof(TRELLIS_ATOM **) * bt->framelen, &(bt->root));
00195 tmp = (TRELLIS_ATOM **)mybmalloc2(sizeof(TRELLIS_ATOM *) * totalnum, &(bt->root));
00196 n = 0;
00197 for (t=0;t<bt->framelen;t++) {
00198 if (bt->num[t] > 0) {
00199 bt->rw[t] = (TRELLIS_ATOM **)&(tmp[n]);
00200 n += bt->num[t];
00201 }
00202 }
00203
00204 for (t=0;t<bt->framelen;t++) bt->num[t] = 0;
00205 for (tre=bt->list;tre;tre=tre->next) {
00206 #ifdef SP_BREAK_CURRENT_FRAME
00207
00208 if (tre->endtime >= bt->framelen) continue;
00209 #endif
00210 t = tre->endtime;
00211
00212 bt->rw[t][bt->num[t]] = tre;
00213 bt->num[t]++;
00214 }
00215 }
00216
00217
00218
00219
00220
00221 #ifdef SP_BREAK_CURRENT_FRAME
00222
00240 void
00241 set_terminal_words(BACKTRELLIS *bt)
00242 {
00243 LOGPROB maxscore;
00244 int i,t;
00245
00246 if (bt->num == NULL) return;
00247
00248 maxscore = LOG_ZERO;
00249
00250 for(t=bt->framelen-1;t>=0;t--) {
00251 if (bt->num[t] > 0) break;
00252 }
00253
00254 for(i=0;i<bt->num[t];i++) {
00255 if (maxscore < (bt->rw[t][i])->backscore) {
00256 maxscore = (bt->rw[t][i])->backscore;
00257 sp_break_2_begin_word = (bt->rw[t][i])->wid;
00258 }
00259 }
00260 maxscore = LOG_ZERO;
00261
00262 for(t=0;t<bt->framelen;t++) {
00263 if (bt->num[t] > 0) break;
00264 }
00265
00266 for(i=0;i<bt->num[t];i++) {
00267 if (maxscore < (bt->rw[t][i])->backscore) {
00268 maxscore = (bt->rw[t][i])->backscore;
00269 sp_break_2_end_word = (bt->rw[t][i])->wid;
00270 }
00271 }
00272 #ifdef SP_BREAK_DEBUG
00273 printf("2nd pass begin word: %s\n",
00274 (sp_break_2_begin_word == WORD_INVALID) ? "WORD_INVALID" : winfo->wname[sp_break_2_begin_word]);
00275 printf("2nd pass end word: %s\n",
00276 (sp_break_2_end_word == WORD_INVALID) ? "WORD_INVALID" : winfo->wname[sp_break_2_end_word]);
00277 #endif
00278 }
00279 #endif
00280
00281
00282
00306 void
00307 bt_discount_pescore(WCHMM_INFO *wchmm, BACKTRELLIS *bt, HTK_Param *param)
00308 {
00309 int t,i;
00310 TRELLIS_ATOM *tre;
00311
00312 if (bt->num == NULL) return;
00313
00314 for (t=0; t<bt->framelen; t++) {
00315 for (i=0; i<bt->num[t]; i++) {
00316 tre = bt->rw[t][i];
00317 #ifndef MULTIPATH_VERSION
00318
00319
00320
00321
00322 tre->backscore -= outprob_style(wchmm, wchmm->wordend[tre->wid], tre->last_tre->wid, t, param);
00323 #endif
00324 #ifdef USE_NGRAM
00325 #ifdef LM_FIX_DOUBLE_SCORING
00326
00327
00328
00329 tre->backscore -= tre->lscore;
00330 #endif
00331 #endif
00332 }
00333 }
00334
00335 }
00336
00355 static int
00356 compare_wid(TRELLIS_ATOM **a, TRELLIS_ATOM **b)
00357 {
00358 if ((*a)->wid > (*b)->wid) return 1;
00359 if ((*a)->wid < (*b)->wid) return -1;
00360 return 0;
00361 }
00362
00381 void
00382 bt_sort_rw(BACKTRELLIS *bt)
00383 {
00384 int t;
00385
00386 if (bt->num == NULL) return;
00387
00388 for (t=0;t<bt->framelen;t++) {
00389 qsort(bt->rw[t], bt->num[t], sizeof(TRELLIS_ATOM *),
00390 (int (*)(const void *,const void *))compare_wid);
00391 }
00392 }
00393
00394
00395
00396
00397
00419 TRELLIS_ATOM *
00420 bt_binsearch_atom(BACKTRELLIS *bt, int t, WORD_ID wkey)
00421 {
00422
00423
00424 int left, right, mid;
00425 TRELLIS_ATOM *tmp;
00426 #ifdef WPAIR
00427 int i;
00428 LOGPROB maxscore;
00429 TRELLIS_ATOM *maxtre;
00430 #endif
00431
00432 if (bt->num[t] == 0) return(NULL);
00433
00434 left = 0;
00435 right = bt->num[t] - 1;
00436 while (left < right) {
00437 mid = (left + right) / 2;
00438 if ((bt->rw[t][mid])->wid < wkey) {
00439 left = mid + 1;
00440 } else {
00441 right = mid;
00442 }
00443 }
00444 tmp = bt->rw[t][left];
00445 if (tmp->wid == wkey) {
00446 #ifdef WPAIR
00447
00448
00449 maxscore = LOG_ZERO;
00450 maxtre = NULL;
00451 i = left;
00452 while (i >= 0) {
00453 tmp = bt->rw[t][i];
00454 if (tmp->wid != wkey) break;
00455 #ifdef WORD_GRAPH
00456
00457 if (!tmp->within_wordgraph) {
00458 i--; continue;
00459 }
00460 #endif
00461 if (maxscore < tmp->backscore) {
00462 maxscore = tmp->backscore;
00463 maxtre = tmp;
00464 }
00465 i--;
00466 }
00467 i = left;
00468 while (i < bt->num[t]) {
00469 tmp = bt->rw[t][i];
00470 if (tmp->wid != wkey) break;
00471 #ifdef WORD_GRAPH
00472
00473 if (!tmp->within_wordgraph) {
00474 i++; continue;
00475 }
00476 #endif
00477 if (maxscore < tmp->backscore) {
00478 maxscore = tmp->backscore;
00479 maxtre = tmp;
00480 }
00481 i++;
00482 }
00483 tmp = maxtre;
00484 #else
00485 #ifdef WORD_GRAPH
00486
00487 if (! tmp->within_wordgraph) {
00488 return NULL;
00489 }
00490 #endif
00491 #endif
00492
00493 return(tmp);
00494 } else {
00495 return(NULL);
00496 }
00497 }