backtrellis.c

Go to the documentation of this file.

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

#include <julius.h>

void
bt_init(BACKTRELLIS *bt)
{
  bt->num  = NULL;
  bt->rw   = NULL;
  bt->list = NULL;
  bt->root = NULL;
}

void
bt_prepare(BACKTRELLIS *bt)
{
  TRELLIS_ATOM *tre, *tmp;

  /* free previously allocated data */
  if (bt->root != NULL) free(bt->root);
  if (bt->rw != NULL) free(bt->rw);
  if (bt->num != NULL) free(bt->num);
  bt->num = NULL;
  bt->rw = NULL;
  bt->root = NULL;

  /* free actual trellis atoms previously allocated */
  tre = bt->list;
  while(tre) {
    tmp = tre->next;
    free(tre);
    tre = tmp;
  }
  /* reset entry point */
  bt->list = NULL;

}  



void
bt_store(BACKTRELLIS *bt, TRELLIS_ATOM *tatom)
{
#ifdef WORD_GRAPH
  tatom->within_wordgraph = FALSE;
#endif
  tatom->next = bt->list;
  bt->list = tatom;
  /*j_printf("  %3d: %15s %f < %3d %15s\n", tatom->endtime,
         winfo->woutput[tatom->wid], tatom->backscore,
         tatom->begintime, winfo->woutput[tatom->last_tre->wid]);*/
}

void
bt_relocate_rw(BACKTRELLIS *bt)
{
  TRELLIS_ATOM *tre;
  int t;
  int totalnum, n;

  if (bt->framelen == 0) {
    bt->num = NULL;
    return;
  }

  bt->num = (int *)mymalloc(sizeof(int) * bt->framelen);

  /* count number of trellis atom (= survived word end) for each frame */
  for (t=0;t<bt->framelen;t++) bt->num[t] = 0;
  totalnum = 0;
  for (tre=bt->list;tre;tre=tre->next) {
#ifdef SP_BREAK_CURRENT_FRAME
    /* the last frame (when triggered from sp to non-sp) should be discarded */
    if (tre->endtime >= bt->framelen) continue;
#endif      
    bt->num[tre->endtime]++;
    totalnum++;
  }
  /* if no atom found, return here with all bt->num[t] set to 0 */
  if (totalnum <= 0) {
    free(bt->num);
    bt->num = NULL;
    return;
  }
  
  /* allocate area */
  bt->root = (TRELLIS_ATOM **)mymalloc(sizeof(TRELLIS_ATOM *) * totalnum);
  bt->rw  = (TRELLIS_ATOM ***)mymalloc(sizeof(TRELLIS_ATOM **) * bt->framelen);
  n = 0;
  for (t=0;t<bt->framelen;t++) {
    if (bt->num[t] > 0) {
      bt->rw[t] = (TRELLIS_ATOM **)&(bt->root[n]);
      n += bt->num[t];
    }
  }
  /* then store the atoms */
  for (t=0;t<bt->framelen;t++) bt->num[t] = 0;
  for (tre=bt->list;tre;tre=tre->next) {
#ifdef SP_BREAK_CURRENT_FRAME
    /* the last frame (when triggered from sp to non-sp) should be discarded */
    if (tre->endtime >= bt->framelen) continue;
#endif      
    t = tre->endtime;
    
    bt->rw[t][bt->num[t]] = tre;
    bt->num[t]++;
  }
}


/* °Ê²¼¤Î´Ø¿ô¤Ï bt_relocate_rw ¼Â¹Ô¸å¤Ë¤Î¤ß»ÈÍѲÄǽ¤È¤Ê¤ë¡¥*/
/* functions below this line should be called after bt_relocate_rw() */

#ifdef SP_BREAK_CURRENT_FRAME

void
set_terminal_words(BACKTRELLIS *bt)
{
  LOGPROB maxscore;
  int i,t;

  if (bt->num == NULL) return;

  maxscore = LOG_ZERO;
  /* find last frame where a word exists */
  for(t=bt->framelen-1;t>=0;t--) {
    if (bt->num[t] > 0) break;
  }
  /* get maximum word hypothesis at that frame */
  for(i=0;i<bt->num[t];i++) {
    if (maxscore < (bt->rw[t][i])->backscore) {
      maxscore = (bt->rw[t][i])->backscore;
      sp_break_2_begin_word = (bt->rw[t][i])->wid;
    }
  }
  maxscore = LOG_ZERO;
  /* find first frame where a word exists */
  for(t=0;t<bt->framelen;t++) {
    if (bt->num[t] > 0) break;
  }
  /* get maximum word hypothesis at that frame */
  for(i=0;i<bt->num[t];i++) {
    if (maxscore < (bt->rw[t][i])->backscore) {
      maxscore = (bt->rw[t][i])->backscore;
      sp_break_2_end_word = (bt->rw[t][i])->wid;
    }
  }
#ifdef SP_BREAK_DEBUG
  printf("2nd pass begin word: %s\n",
         (sp_break_2_begin_word == WORD_INVALID) ? "WORD_INVALID" : winfo->wname[sp_break_2_begin_word]);
  printf("2nd pass end word: %s\n",
         (sp_break_2_end_word == WORD_INVALID) ? "WORD_INVALID" : winfo->wname[sp_break_2_end_word]);
#endif
}
#endif /* SP_BREAK_CURRENT_FRAME */


/* the outprob on the trellis connection point should be discounted */
void
bt_discount_pescore(WCHMM_INFO *wchmm, BACKTRELLIS *bt, HTK_Param *param)
{
  int t,i;
  TRELLIS_ATOM *tre;

  if (bt->num == NULL) return;
  
  for (t=0; t<bt->framelen; t++) {
    for (i=0; i<bt->num[t]; i++) {
      tre = bt->rw[t][i];
#ifndef MULTIPATH_VERSION
      /* On normal version, both language score and the output prob. score
         at the connection point should removed on the trellis for the
         later connection.  On multi-path mode, removing only the language
         score is enough. */
      tre->backscore -= outprob_style(wchmm, wchmm->wordend[tre->wid], tre->last_tre->wid, t, param);
#endif /* MULTIPATH_VERSION */
#ifdef USE_NGRAM
#ifdef LM_FIX_DOUBLE_SCORING
      /* the LM score of the last word should be subtracted, because
         their LM will be assigned by 3-gram on the 2nd pass.
      */
      tre->backscore -= tre->lscore;
#endif
#endif
    }
  }

}

static int
compare_wid(TRELLIS_ATOM **a, TRELLIS_ATOM **b)
{
  if ((*a)->wid > (*b)->wid) return 1;
  if ((*a)->wid < (*b)->wid) return -1;
  return 0;
}

void
bt_sort_rw(BACKTRELLIS *bt)
{
  int t;

  if (bt->num == NULL) return;

  for (t=0;t<bt->framelen;t++) {
    qsort(bt->rw[t], bt->num[t], sizeof(TRELLIS_ATOM *),
          (int (*)(const void *,const void *))compare_wid);
  }
}


/* °Ê²¼¤Î´Ø¿ô¤Ï»öÁ°¤Ëbt_sort_rw() ¤¬¸Æ¤Ð¤ì¤Æ¤¤¤ë¤³¤È(Âè2¥Ñ¥¹ÍÑ) */
/* functions below should be called after bt_sort_rw() */

TRELLIS_ATOM *
bt_binsearch_atom(BACKTRELLIS *bt, int t, WORD_ID wkey)
{
  /* do binary search */
  /* assume rw are ordered by wid */
  int left, right, mid;
  TRELLIS_ATOM *tmp;
#ifdef WPAIR
  int i;
  LOGPROB maxscore;
  TRELLIS_ATOM *maxtre;
#endif
  
  if (bt->num[t] == 0) return(NULL);
  
  left = 0;
  right = bt->num[t] - 1;
  while (left < right) {
    mid = (left + right) / 2;
    if ((bt->rw[t][mid])->wid < wkey) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  tmp = bt->rw[t][left];
  if (tmp->wid == wkey) {
#ifdef WPAIR
    /* same word with different context will be found:
       most likely one will be returned */
    maxscore = LOG_ZERO;
    i = left;
    while (i >= 0 && (tmp = bt->rw[t][i])->wid == wkey) {
      if (maxscore < tmp->backscore) {
        maxscore = tmp->backscore;
        maxtre = tmp;
      }
      i--;
    }
    i = left;
    while (i < bt->num[t] && (tmp = bt->rw[t][i])->wid == wkey) {
      if (maxscore < tmp->backscore) {
        maxscore = tmp->backscore;
        maxtre = tmp;
      }
      i++;
    }

    tmp = maxtre;
#endif /* WORD_GRAPH */

    return(tmp);
  } else {
    return(NULL);
  }
}

---