ngram_decode.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>

#ifdef USE_NGRAM

static int
compare_nw(NEXTWORD **a, NEXTWORD **b)
{
  if ((*a)->id > (*b)->id) return 1;
  if ((*a)->id < (*b)->id) return -1;
  return 0;
}

/* find next word candiate whose id 'w' */
static NEXTWORD *
search_nw(NEXTWORD **nw, WORD_ID w, int num)
{
  int left,right,mid;
  NEXTWORD *tmp;

  if (num == 0) return NULL;
  left = 0;
  right = num - 1;
  while (left < right) {
    mid = (left + right) / 2;
    if ((nw[mid])->id < w) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  tmp = nw[left];
  if (tmp->id == w) {
    return tmp;
  } else {
    return NULL;
  }
}

/*********** transparent words handling on 2nd pass **********/
static WORD_ID cnword[2];       
static int cnnum;               
static int last_trans;          

static void
set_word_context(WORD_ID *cseq, int n, WORD_INFO *winfo)
{
  int i;

  cnnum = 0;
  last_trans = 0;
  for(i=n-1;i>=0;i--) {
    if (! winfo->is_transparent[cseq[i]]) {
      cnword[cnnum++] = winfo->wton[cseq[i]];
      if (cnnum >= 2) break;
    } else {
      last_trans++;
    }
  }
}

/*************************************************************/

/* lookup survived words on specified frame in backtrellis, 
   compute their N-gram probabilities, and add them to NEXTWORD data */
static int
pick_backtrellis_words(BACKTRELLIS *bt, WORD_INFO *winfo, NGRAM_INFO *ngram, NEXTWORD **nw, int oldnum, NODE *hypo, short t)
{
  int i;
  WORD_ID w;
  LOGPROB rawscore;
#ifndef WORD_GRAPH
#ifdef WPAIR
  int w_old = WORD_INVALID;
#endif
#endif
  int num;

  num = oldnum;
  /* set word context to cnword[0], cnword[1] */
  set_word_context(hypo->seq, hypo->seqnum, winfo);
  /* lookup survived words in backtrellis on time frame 't' */
  for (i=0;i<bt->num[t];i++) {
    w = (bt->rw[t][i])->wid;
#ifdef WORD_GRAPH
    /* only words on the word graphs are expanded */
    if (!(bt->rw[t][i])->within_wordgraph) continue;
    /* word connection is restricted by the graph structure */
    if (w != ((hypo->tre)->last_tre)->wid) continue;
#else /* not WORD_GRAPH */
#ifdef WPAIR
    /* some word have same word ID with different previous word, so
       only one will be opened (best word will be selected later
       by next_word() */
    if (w == w_old) continue;   /* backtrellis is sorted by word ID */
    else w_old = w;
#endif /* WPAIR */
#endif /* not WORD_GRAPH */
    /* skip if already exist */
    if (search_nw(nw, w, oldnum) != NULL) continue;
    switch(cnnum) {             /* length of valid context */
    case 0:                     /* unigram */
      rawscore = uni_prob(ngram, winfo->wton[w]);
      break;
    case 1:                     /* bigram */
      rawscore = bi_prob_rl(ngram, winfo->wton[w], cnword[0]);
      break;
    default:                    /* trigram */
      rawscore = tri_prob_rl(ngram, winfo->wton[w], cnword[0], cnword[1]);
      break;
    }
#ifdef CLASS_NGRAM
    rawscore += winfo->cprob[w];
#endif
    nw[num]->tre   = bt->rw[t][i];
    nw[num]->id    = w;
    nw[num]->lscore = lm_weight2 * rawscore + lm_penalty2;
    if (winfo->is_transparent[w]) {
      /*nw[num]->lscore -= (LOGPROB)last_trans * TRANS_RENZOKU_PENALTY;*/
      if (winfo->is_transparent[hypo->seq[hypo->seqnum-1]]) {
        nw[num]->lscore += lm_penalty_trans;
      }
    }
    
    /* j_printf("%d: %s added\n", num, winfo->wname[nw[num]->id]); */
    num++;
  }
  return num;
}

/* Look for survived backtrellis words near the specified frame, and
   make NEXTWORD list.
   Words in frame [tm-lookup_range..tm+lookup_range-1] will be picked up.
   If a word exist in several frames, only one near the center frame
   will be taken: the true connection point will be determined later at
   next_word() */
int
get_backtrellis_words(BACKTRELLIS *bt, WORD_INFO *winfo, NGRAM_INFO *ngram, NEXTWORD **nw, NODE *hypo, short tm, short t_end)
{
  int num = 0;
  int t, t_step;
  int oldnum=0;

  if (tm < 0) return(0);

#ifdef PREFER_CENTER_ON_TRELLIS_LOOKUP
  /* fix for 3.2 (01/10/18 by ri) */
  /* before and after (one near center frame has high priority) */
  for (t_step = 0; t_step < lookup_range; t_step++) {
    /* before or center */
    t = tm - t_step;
    if (t < 0 || t > bt->framelen - 1 || t >= t_end) continue;
    num = pick_backtrellis_words(bt, winfo, ngram, nw, oldnum, hypo, t);
    if (num > oldnum) {
      qsort(nw, num, sizeof(NEXTWORD *),
            (int (*)(const void *,const void *))compare_nw);
      oldnum = num;
    }
    if (t_step == 0) continue;  /* center */
    /* after */
    t = tm + t_step;
    if (t < 0 || t > bt->framelen - 1 || t >= t_end) continue;
    num = pick_backtrellis_words(bt, winfo, ngram, nw, oldnum, hypo, t);
    if (num > oldnum) {
      qsort(nw, num, sizeof(NEXTWORD *),
            (int (*)(const void *,const void *))compare_nw);
      oldnum = num;
    }
  }

#else

  /* before the center frame */
  for(t = tm; t >= tm - lookup_range; t--) {
    if (t < 0) break;
    num = pick_backtrellis_words(bt, winfo, ngram, nw, oldnum, hypo, t);
    if (num > oldnum) {
      qsort(nw, num, sizeof(NEXTWORD *),
            (int (*)(const void *,const void *))compare_nw);
      oldnum = num;
    }
  }
  /* after the center frame */
  for(t = tm + 1; t < tm + lookup_range; t++) {
    if (t > bt->framelen - 1) break;
    if (t >= t_end) break;
    num = pick_backtrellis_words(bt, winfo, ngram, nw, oldnum, hypo, t);
    if (num > oldnum) {
      qsort(nw, num, sizeof(NEXTWORD *),
            (int (*)(const void *,const void *))compare_nw);
      oldnum = num;
    }
  }
#endif

  return num;
}

int
limit_nw(NEXTWORD **nw, NODE *hypo, int num)
{
  int src,dst;
  int newnum;

  /* <s>¤«¤é¤Ï²¿¤âŸ³«¤·¤Ê¤¤ */
  /* no hypothesis will be generated after "<s>" */
  if (hypo->seq[hypo->seqnum-1] == winfo->head_silwid) {
    return(0);
  }

  dst = 0;
  for (src=0; src<num; src++) {
    if (nw[src]->id == winfo->tail_silwid) {
      /* </s> ¤ÏŸ³«¤·¤Ê¤¤ */
      /* do not expand </s> (it only appears at start) */
      continue;
    }
#ifdef FIX_35_INHIBIT_SAME_WORD_EXPANSION
    /* ľÁ°Ã±¸ì¤ÈƱ¤¸¥È¥ì¥ê¥¹Ã±¸ì¤ÏŸ³«¤·¤Ê¤¤ */
    /* inhibit expanding the exactly the same trellis word twice */
    if (nw[src]->tre == hypo->tre) continue;
#endif
    
    if (src != dst) memcpy(nw[dst], nw[src], sizeof(NEXTWORD));
    dst++;
  }
  newnum = dst;

  return newnum;
}
        


/* ºÇ½é¤Îñ¸ì·²¤òÊÖ¤¹¡¥ÊÖ¤êÃÍ: ñ¸ì¿ô (-1 on error) */
/* return initial word set.  return value: num of words (-1 on error) */

int
ngram_firstwords(NEXTWORD **nw, int peseqlen, int maxnw, WORD_INFO *winfo, BACKTRELLIS *bt)
{
#ifdef WORD_GRAPH
  int last_time;
#endif

#ifdef SP_BREAK_CURRENT_FRAME
  if (rest_param != NULL) {
    /* ½é´ü²¾Àâ¤Ï ºÇ½ª¥Õ¥ì¡¼¥à¤Ë»Ä¤Ã¤¿Ã±¸ì¥È¥ì¥ê¥¹¾å¤ÎºÇÌàñ¸ì */
    /* the initial hypothesis is the best word survived on the last frame of
       the segment */
    nw[0]->id = sp_break_2_begin_word;
  } else {
    /* ºÇ½ª¥»¥°¥á¥ó¥È: ½é´ü²¾Àâ¤Ï ñ¸ì¤ÎËöÈø¤Î̵²»Ã±¸ì(=winfo->tail_silwid) */
    /* we are in the last of sentence: initial hypothesis is word-end silence word */
    nw[0]->id = winfo->tail_silwid;
  }
#else
  /* initial hypothesis is word-end silence word */
  nw[0]->id = winfo->tail_silwid;
#endif
#ifdef FIX_PENALTY
  nw[0]->lscore = 0.0;
#else
  nw[0]->lscore = lm_penalty2;
#endif
#ifdef WORD_GRAPH
  /* ½é´ü²¾Àâ¤ÎTRELLIS_ATOM¤ò¤³¤³¤Ç·èÄꤹ¤ë */
  /* in word-graph mode, the first trellis atom should be defined here */
  for (last_time = peseqlen - 1; last_time >= 0; last_time--) {
    nw[0]->tre = bt_binsearch_atom(&backtrellis, last_time, winfo->tail_silwid);
    if (nw[0]->tre != NULL) break;
  }
  if (nw[0]->tre == NULL) {             /* </s> not found */
    j_printerr("no wordend left in beam!\n");
    j_printerr("beam width too small or input speech too short\n");
    return 0;
  }
#endif

  return 1;                     /* number of words = 1 */
}

/* ¤¢¤ë²¾Àâ¤Î¼¡¤ÎÀܳñ¸ì·²¤òÊÖ¤¹¡¥µ¢¤êÃÍ: ñ¸ì¿ô (-1 on error) */
/* return next word set from the hypothesis.  return value:
   num of words (-1 on error) */
int
ngram_nextwords(
                NODE *hypo,
                NEXTWORD **nw,
                int maxnw,      /* hypo: source */
                NGRAM_INFO *ngram, /* N-gram info */
                WORD_INFO *winfo, /* word dictionary */
                BACKTRELLIS *bt) /* backtrellis info */
{
  int num, num2;

  if (hypo->seqnum == 0) {
    j_error("gs_get_next_words: hypo contains no word\n");
  }

  /* ²¾Àâ¤Î¿äÄ꽪ü»þ¹ï¤Ë¤ª¤¤¤Æ backtrellisÆâ¤Ë»Ä¤Ã¤Æ¤¤¤ëñ¸ì¤òÆÀ¤ë */
  /* get survived words on backtrellis at the estimated end frame */
  num = get_backtrellis_words(bt, winfo, ngram, nw, hypo, hypo->estimated_next_t, hypo->bestt);

  if (debug2_flag) j_printf("%d",num);

  /* Ÿ³«¤Ç¤­¤Ê¤¤Ã±¸ì¤ò¥Á¥§¥Ã¥¯¤·¤Æ³°¤¹ */
  /* exclude unallowed words */
  num2 = limit_nw(nw, hypo, num);

  if (debug2_flag) j_printf("-%d=%d unfolded\n",num-num2,num2);

  return(num2);
}

/* return if the hypothesis is "acceptable" */
boolean
ngram_acceptable(NODE *hypo, WORD_INFO *winfo)
{
  if (
#ifdef SP_BREAK_CURRENT_FRAME
      /* ºÇ¸å¤Î²¾À⤬Â裱¥Ñ¥¹ºÇÌಾÀâ¤ÎºÇ½é¤Îñ¸ì¤È°ìÃפ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤ */
      /* the last word should be equal to the first word on the best hypothesis on 1st pass */
      hypo->seq[hypo->seqnum-1] == sp_break_2_end_word
#else
      /* ºÇ¸å¤Î²¾À⤬ʸƬ̵²»Ã±¸ì¤Ç¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤ */
      /* the last word should be head silence word */
      hypo->seq[hypo->seqnum-1] == winfo->head_silwid
#endif
      ) {
    return TRUE;
  } else {
    return FALSE;
  }
}

#endif /* USE_NGRAM */

---