graphout.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 GRAPHOUT

#undef GDEBUG


/**************************************************************/
/* allocation and free of a WordGraph instance */

static WordGraph *
wordgraph_new(WORD_ID wid, int leftframe, int rightframe, LOGPROB fscore_head, LOGPROB fscore_tail, LOGPROB gscore_head, LOGPROB gscore_tail, LOGPROB lscore, LOGPROB cm)
{
  WordGraph *new;

  new = (WordGraph *)mymalloc(sizeof(WordGraph));
  new->wid = wid;
  new->lefttime = leftframe;
  new->righttime = rightframe;
  new->fscore_head = fscore_head;
  new->fscore_tail = fscore_tail;
  new->gscore_head = gscore_head;
  new->gscore_tail = gscore_tail;
#ifdef USE_NGRAM
  new->lscore = lscore;
#endif
#ifdef CM_SEARCH
  new->cmscore = cm;
#endif
  new->leftwordmaxnum = FANOUTSTEP;
  new->leftword = (WordGraph **)mymalloc(sizeof(WordGraph *) * new->leftwordmaxnum);
  new->leftwordnum = 0;
  new->rightwordmaxnum = FANOUTSTEP;
  new->rightword = (WordGraph **)mymalloc(sizeof(WordGraph *) * new->rightwordmaxnum);
  new->rightwordnum = 0;
  new->mark = FALSE;
#ifdef GRAPHOUT_DYNAMIC
  new->purged = FALSE;
#endif
  new->next = NULL;
  new->saved = FALSE;

#ifdef GDEBUG
 {
   int i;
   WordGraph *w;
   printf("NEW: \"%s\"[%d..%d]\n", wchmm->winfo->woutput[new->wid], new->lefttime, new->righttime);
   for(i=0;i<new->leftwordnum;i++) {
     w = new->leftword[i];
     printf("\t left%d:  \"%15s\"[%d..%d]\n", i, wchmm->winfo->woutput[w->wid], w->lefttime, w->righttime);
   }
   for(i=0;i<new->rightwordnum;i++) {
     w = new->rightword[i];
     printf("\tright%d:  \"%15s\"[%d..%d]\n", i, wchmm->winfo->woutput[w->wid], w->lefttime, w->righttime);
   }
 }
#endif

  return(new);
}

void
wordgraph_free(WordGraph *wg)
{
  free(wg->rightword);
  free(wg->leftword);
  free(wg);
}


/**************************************************************/
/* Handling contexts */

static void
wordgraph_add_leftword(WordGraph *wg, WordGraph *left)
{
  if (wg == NULL) return;
  if (left == NULL) return;
  if (wg->leftwordnum >= wg->leftwordmaxnum) {
    /* expand */
    wg->leftwordmaxnum += FANOUTSTEP;
    wg->leftword = (WordGraph **)myrealloc(wg->leftword, sizeof(WordGraph *) * wg->leftwordmaxnum);
  }
  wg->leftword[wg->leftwordnum] = left;
  wg->leftwordnum++;
#ifdef GDEBUG
  printf("addleft: \"%s\"[%d..%d] added as %dth left of \"%s\"[%d..%d]\n", wchmm->winfo->woutput[left->wid], left->lefttime, left->righttime, wg->leftwordnum, wchmm->winfo->woutput[wg->wid], wg->lefttime, wg->righttime);
#endif
}

static void
wordgraph_add_rightword(WordGraph *wg, WordGraph *right)
{
  if (wg == NULL) return;
  if (right == NULL) return;
  if (wg->rightwordnum >= wg->rightwordmaxnum) {
    /* expand */
    wg->rightwordmaxnum += FANOUTSTEP;
    wg->rightword = (WordGraph **)myrealloc(wg->rightword, sizeof(WordGraph *) * wg->rightwordmaxnum);
  }
  wg->rightword[wg->rightwordnum] = right;
  wg->rightwordnum++;
#ifdef GDEBUG
  printf("addright: \"%s\"[%d..%d] added as %dth right of \"%s\"[%d..%d]\n", wchmm->winfo->woutput[right->wid], right->lefttime, right->righttime, wg->rightwordnum, wchmm->winfo->woutput[wg->wid], wg->lefttime, wg->righttime);
#endif
}

boolean
wordgraph_check_and_add_leftword(WordGraph *wg, WordGraph *left)
{
  int i;

  if (wg == NULL) return FALSE;
  if (left == NULL) return FALSE;
  for(i=0;i<wg->leftwordnum;i++) {
    if (wg->leftword[i] == left) {
      break;
    }
  }
  if (i >= wg->leftwordnum) { /* no leftword matched */
    wordgraph_add_leftword(wg, left);
    return TRUE;
  }
  return FALSE;
}

boolean
wordgraph_check_and_add_rightword(WordGraph *wg, WordGraph *right)
{
  int i;

  if (wg == NULL) return FALSE;
  if (right == NULL) return FALSE;
  for(i=0;i<wg->rightwordnum;i++) {
    if (wg->rightword[i] == right) {
      break;
    }
  }
  if (i >= wg->rightwordnum) { /* no rightword matched */
    wordgraph_add_rightword(wg, right);
    return TRUE;
  }
  return FALSE;
}

static boolean
merge_contexts(WordGraph *dst, WordGraph *src)
{
  int s, d;
  WordGraph *adding;
  boolean ret;

#ifdef GDEBUG
  printf("merge_contexts: merging context of \"%s\"[%d..%d] to \"%s\"[%d..%d]...\n",
         wchmm->winfo->woutput[src->wid], src->lefttime, src->righttime,
         wchmm->winfo->woutput[dst->wid], dst->lefttime, dst->righttime);
#endif

  ret = FALSE;
  
  /* left context */
  for(s=0;s<src->leftwordnum;s++) {
    adding = src->leftword[s];
    /* direct link between dst and src will disapper to avoid unneccesary loop */
    if (adding == dst) {
#ifdef GDEBUG
      printf("merge_contexts: skipping direct link (dst) -> (src)\n");
#endif
      continue;
    }
    for(d=0;d<dst->leftwordnum;d++) {
      if (dst->leftword[d] == adding) {
        break;
      }
    }
    if (d >= dst->leftwordnum) { /* no leftword matched */
      wordgraph_add_leftword(dst, adding);
#ifdef GDEBUG
      printf("merge_contexts: added \"%s\"[%d..%d] as a new left context\n",
             wchmm->winfo->woutput[adding->wid], adding->lefttime, adding->righttime);
#endif
      ret = TRUE;
    }
#ifdef GDEBUG
    else {
      printf("merge_contexts: \"%s\"[%d..%d] already exist\n",
             wchmm->winfo->woutput[adding->wid], adding->lefttime, adding->righttime);
    }
#endif
  }

  /* right context */
  for(s=0;s<src->rightwordnum;s++) {
    adding = src->rightword[s];
    /* direct link between dst and src will disapper to avoid unneccesary loop */
    if (adding == dst) {
#ifdef GDEBUG
      printf("merge_contexts: skipping direct link (src) -> (dst)\n");
#endif
      continue;
    }
    for(d=0;d<dst->rightwordnum;d++) {
      if (dst->rightword[d] == adding) {
        break;
      }
    }
    if (d >= dst->rightwordnum) { /* no rightword matched */
      wordgraph_add_rightword(dst, adding);
#ifdef GDEBUG
      printf("merge_contexts: added \"%s\"[%d..%d] as a new right context\n",
             wchmm->winfo->woutput[adding->wid], adding->lefttime, adding->righttime);
#endif
      ret = TRUE;
    }
#ifdef GDEBUG
    else {
      printf("merge_contexts: \"%s\"[%d..%d] already exist\n",
             wchmm->winfo->woutput[adding->wid], adding->lefttime, adding->righttime);
    }
#endif
  }
  
  return(ret);
}

static void
swap_leftword(WordGraph *wg, WordGraph *from, WordGraph *to)
{
  int i;
  
#ifdef GDEBUG
  printf("swapleft: replacing left of \"%s\"[%d..%d] from \"%s\"[%d..%d] to \"%s\"[%d..%d]...\n",
         wchmm->winfo->woutput[wg->wid], wg->lefttime, wg->righttime,
         wchmm->winfo->woutput[from->wid], from->lefttime, from->righttime,
         wchmm->winfo->woutput[to->wid], to->lefttime, to->righttime);
#endif
  
  for(i=0;i<wg->leftwordnum;i++) {
    if (wg->leftword[i] == from) {
      wg->leftword[i] = to;
    }
  }
}

static void
swap_rightword(WordGraph *wg, WordGraph *from, WordGraph *to)
{
  int i;
  
#ifdef GDEBUG
  printf("swapright: replacing right of \"%s\"[%d..%d] from \"%s\"[%d..%d] to \"%s\"[%d..%d]...\n",
         wchmm->winfo->woutput[wg->wid], wg->lefttime, wg->righttime,
         wchmm->winfo->woutput[from->wid], from->lefttime, from->righttime,
         wchmm->winfo->woutput[to->wid], to->lefttime, to->righttime);
#endif

  for(i=0;i<wg->rightwordnum;i++) {
    if (wg->rightword[i] == from) {
      wg->rightword[i] = to;
    }
  }
}

static void
uniq_leftword(WordGraph *wg)
{
  int i, j, dst;
  boolean ok;

  dst = 0;
  for(i=0;i<wg->leftwordnum;i++) {
    ok = TRUE;
    for(j=0;j<dst;j++) {
      if (wg->leftword[i] == wg->leftword[j]) {
        ok = FALSE;
        break;
      }
    }
    if (ok == TRUE) {
      wg->leftword[dst] = wg->leftword[i];
      dst++;
    }
  }
  wg->leftwordnum = dst;
}

static void
uniq_rightword(WordGraph *wg)
{
  int i, j, dst;
  boolean ok;

  dst = 0;
  for(i=0;i<wg->rightwordnum;i++) {
    ok = TRUE;
    for(j=0;j<dst;j++) {
      if (wg->rightword[i] == wg->rightword[j]) {
        ok = FALSE;
        break;
      }
    }
    if (ok == TRUE) {
      wg->rightword[dst] = wg->rightword[i];
      dst++;
    }
  }
  wg->rightwordnum = dst;
}

static void
wordgraph_remove_context(WordGraph *wg)
{
  WordGraph *w;
  int i,j,k;

  if (wg == NULL) return;

  for(i=0;i<wg->leftwordnum;i++) {
    w = wg->leftword[i];
    k=0;
    for(j=0;j<w->rightwordnum;j++) {
      if (w->rightword[j] != wg) {
        if (j != k) {
          w->rightword[k] = w->rightword[j];
        }
        k++;
      }
    }
    w->rightwordnum = k;
  }
  for(i=0;i<wg->rightwordnum;i++) {
    w = wg->rightword[i];
    k=0;
    for(j=0;j<w->leftwordnum;j++) {
      if (w->leftword[j] != wg) {
        if (j != k) {
          w->leftword[k] = w->leftword[j];
        }
        k++;
      }
    }
    w->leftwordnum = k;
  }
}

static void
wordgraph_link_context(WordGraph *wg)
{
  WordGraph *w;
  int i,j;

  if (wg == NULL) return;
  for(i=0;i<wg->leftwordnum;i++) {
    for(j=0;j<wg->rightwordnum;j++) {
      wordgraph_check_and_add_leftword(wg->rightword[j], wg->leftword[i]);
      wordgraph_check_and_add_rightword(wg->leftword[i], wg->rightword[j]);
    }
  }
}


/**************************************************************/
/* Operations for organizing WordGraph set */

static int
wordgraph_exec_erase(WordGraph **rootp)
{
  WordGraph *wg, *we, *wtmp;
  int count;

  if (*rootp == NULL) return(0);
  
  wg = *rootp;
  count = 0;
  while (wg != NULL) {
    we = wg->next;
    while(we != NULL && we->mark == TRUE) {
      wtmp = we->next;
      wordgraph_free(we); count++;
      we = wtmp;
    }
    wg->next = we;
    wg = we;
  }
  if ((*rootp)->mark == TRUE) {
    wtmp = (*rootp)->next;
    wordgraph_free(*rootp); count++;
    *rootp = wtmp;
  }

  return(count);
}

static int
compare_lefttime(WordGraph **x, WordGraph **y)
{
  if ((*x)->lefttime > (*y)->lefttime) return 1;
  else if ((*x)->lefttime < (*y)->lefttime) return -1;
  else {
    if ((*x)->righttime > (*y)->righttime) return 1;
    else if ((*x)->righttime < (*y)->righttime) return -1;
    else {
      if ((*x)->fscore_head < (*y)->fscore_head) return 1;
      else if ((*x)->fscore_head > (*y)->fscore_head) return -1;
      else return 0;
    }
  }
}

void
wordgraph_sort_and_annotate_id(WordGraph **rootp)
{
  WordGraph *wg;
  int cnt;
  WordGraph **wlist;
  int i;
  WordGraph *wo;

  /* count total number of words in the graph */
  cnt = 0;
  for(wg=*rootp;wg;wg=wg->next) cnt++;
  graph_totalwordnum = cnt;
  if (graph_totalwordnum == 0) return;
  /* sort them by lefttime */
  wlist = (WordGraph **)mymalloc(sizeof(WordGraph *) * graph_totalwordnum);
  i = 0;
  for(wg=*rootp;wg;wg=wg->next) {
    wlist[i++] = wg;
  }
  qsort(wlist, graph_totalwordnum, sizeof(WordGraph *), (int (*)(const void *, const void *))compare_lefttime);

  /* annotated id and re-order the link by the id */
  wo = NULL;
  for(i=graph_totalwordnum-1;i>=0;i--) {
    wg = wlist[i];
    wg->id = i;
    wg->next = wo;
    wo = wg;
  }
  *rootp = wo;
  free(wlist);
}

void
wordgraph_clean(WordGraph **rootp)
{
  WordGraph *wg, *wtmp;

  wg = *rootp;
  while(wg != NULL) {
    wtmp = wg->next;
    wordgraph_free(wg);
    wg = wtmp;
  }
  *rootp = NULL;

}


/**************************************************************/
/* Post-processing of generated word arcs after search has been done */

void
wordgraph_purge_leaf_nodes(WordGraph **rootp)
{
  WordGraph *wg;
  boolean changed;
  int i, count, erased;

  /* count whole */
  count = 0;
  for(wg=*rootp;wg;wg=wg->next) count++;
  j_printf("- %d initial word arcs generated\n", count);

  j_printf("Step 1: Purge leaf words\n");
  /* mark words to be erased */
  do {
    changed = FALSE;
    for(wg=*rootp;wg;wg=wg->next) {
      /* mark if wg has no left context, or all leftwords are marked */
      if (wg->mark == TRUE || wg->lefttime == 0) continue;
      for(i=0;i<wg->leftwordnum;i++) {
        if (wg->leftword[i]->mark == FALSE) break;
      }
      if (i >= wg->leftwordnum) {
        wg->mark = TRUE;
        changed = TRUE;
      }
    }
  } while (changed == TRUE);

  /* do compaction of leftwords */
  {
    int dst;
    for(wg=*rootp;wg;wg=wg->next) {
      dst = 0;
      for(i=0;i<wg->leftwordnum;i++) {
        if (wg->leftword[i]->mark == FALSE) {
          if (dst != i) wg->leftword[dst] = wg->leftword[i];
          dst++;
        }
      }
      wg->leftwordnum = dst;
    }
  }

  /* execute erase of marked words */
  erased = wordgraph_exec_erase(rootp);
  j_printf("- %d words purged, %d words left in lattice\n", erased, count - erased);
}

void
wordgraph_adjust_boundary(WordGraph **rootp)
{
#ifdef GRAPHOUT_PRECISE_BOUNDARY
  WordGraph *wg, *left, *new;
  int i, j;
  int new_lefttime;
  int *framelist;
  LOGPROB *framescorelist;
  int maxfnum;
  int fnum;
  int mov_num, dup_num, del_num;
  int count;
  boolean changed;

  j_printf("Step 2: Fit word boundaries\n");
  mov_num = dup_num = del_num = 0;

  /* count number of all words and get maximum number of left context words */
  count = 0;
  maxfnum = 0;
  for(wg=*rootp;wg;wg=wg->next) {
    count++;
    if (maxfnum < wg->leftwordnum) maxfnum = wg->leftwordnum;
  }
  /* allocate temporal work area */
  framelist = (int *)mymalloc(sizeof(int) * maxfnum);
  framescorelist = (LOGPROB *)mymalloc(sizeof(LOGPROB) * maxfnum);

  do {
    /* loop until no word has been changed on the last step */
    changed = FALSE;
    for(wg=*rootp;wg;wg=wg->next) {
      if (wg->mark) continue;   /* already marked */
      if (wg->leftwordnum == 0) continue;       /* no leftword */
      /* correct lefttime variation to framelist[] and framescorelist[] */
      fnum = 0;
      for(i=0;i<wg->leftwordnum;i++) {
        left = wg->leftword[i];
        if (left->mark) continue;
        for(j=0;j<fnum;j++) {
          if (framelist[j] == left->righttime + 1) break;
        }
        if (j >= fnum) {
          framelist[fnum] = left->righttime + 1;
          framescorelist[fnum] = left->gscore_tail
#ifdef USE_NGRAM
            /* the tail gscore contains the language score of the word,
               so the head gscore of its right context should consider this */
            - left->lscore
#endif
            ;
          fnum++;
        }
      }
      if (fnum == 0) continue;  /* no left context */
      /* one candidate: just move the original (or not move) */
      if (fnum == 1) {
        if (wg->lefttime != framelist[0]) {
          /* adjust time and score */
          //printf("    moved: %d -> %d\n", wg->lefttime, framelist[0]);
          wg->lefttime = framelist[0];
          wg->gscore_head = framescorelist[0];
          /* check the time correctness: if the lefttime is larger than
             righttime, this graph word has been completely overridden by
             the left word (i.e. the aligned frames are absorbed by
             re-alignment.  In this case this word should be removed.
          */
          if (wg->lefttime > wg->righttime) {
            wordgraph_link_context(wg);
            wordgraph_remove_context(wg);
            wg->mark = TRUE;
            del_num++;
          } else {
            mov_num++;
          }
          changed = TRUE;
        } else if (wg->gscore_head != framescorelist[0]) {
          /* adjust only score */
          wg->gscore_head = framescorelist[0];
          changed = TRUE;
        }
      }
      if (fnum > 1) {
        /* multiple candidate: make copy for each (fnum)*/
        for(j=0;j<fnum;j++) {
          //printf("    duped: (%d) %d -> %d\n", j+1, wg->lefttime, framelist[j]);
          dup_num++;
          /* check the time correctness: if the lefttime is larger than
             righttime, this graph word has been completely overridden by
             the left word (i.e. the aligned frames are absorbed by
             re-alignment.  In this case this word should not be duplicated
          */
          if (framelist[j] > wg->righttime) {
            del_num++;
            continue;
          }
          
          /* duplicate */
          new = wordgraph_new(wg->wid, framelist[j], wg->righttime, wg->fscore_head, wg->fscore_tail, framescorelist[j], wg->gscore_tail
#ifdef USE_NGRAM
                              , wg->lscore
#else
                              , LOG_ZERO
#endif
#ifdef CM_SEARCH
                              , wg->cmscore
#else
                              , LOG_ZERO
#endif
                              );
          /* copy corresponding link */
          for(i=0;i<wg->leftwordnum;i++) {
            if ((wg->leftword[i])->mark) continue;
            if ((wg->leftword[i])->righttime + 1 == framelist[j]) {
              wordgraph_add_leftword(new, wg->leftword[i]);
              wordgraph_add_rightword(wg->leftword[i], new);
            }
          }
          for(i=0;i<wg->rightwordnum;i++) {
            if ((wg->rightword[i])->mark) continue;
            wordgraph_add_rightword(new, wg->rightword[i]);
            wordgraph_add_leftword(wg->rightword[i], new);
          }
          new->saved = TRUE;
          new->next = *rootp;
          *rootp = new;
        }
        /* º¸±¦¤Îñ¸ì¤Î¥³¥ó¥Æ¥­¥¹¥È¤«¤éWG¤ò½ü³°¤¹¤ë¡Ê´Ø¿ô²½¡Ë */
        wordgraph_remove_context(wg);
        /* remove the original */
        wg->mark = TRUE;
        dup_num--;
        changed = TRUE;
      }
    }
  } while (changed == TRUE);
  /* execute erase of marked words */
  wordgraph_exec_erase(rootp);
  free(framelist);
  free(framescorelist);
  j_printf("- %d moved, %d duplicated, %d purged (bad align), %d words left in lattice\n", mov_num, dup_num, del_num, count + dup_num - del_num);

#else

  j_printf("# Step 2: SKIP (adjusting re-aligned word boundaries)\n");

#endif /* GRAPHOUT_PRECISE_BOUNDARY */

}

 
void
wordgraph_compaction_thesame(WordGraph **rootp)
{
  WordGraph *wg, *we;
  int i, count, erased;
  WordGraph *wtmp;

  j_printf("Step 3: Merge same words with exactly same time and score\n");

  count = 0;
  for(wg=*rootp;wg;wg=wg->next) {
    count++;
    if (wg->mark == TRUE) continue;
    for(we=wg->next;we;we=we->next) {
      if (we->mark == TRUE) continue;
      /* find the word with exactly the same time and score */
      if (wg->wid == we->wid &&
          wg->lefttime == we->lefttime &&
          wg->righttime == we->righttime &&
          wg->fscore_head == we->fscore_head &&
          wg->fscore_tail == we->fscore_tail) {
        /* merge contexts */
        merge_contexts(wg, we);
        /* swap contexts of left / right contexts */
        for(i=0;i<we->leftwordnum;i++) {
          swap_rightword(we->leftword[i], we, wg);
        }
        for(i=0;i<we->rightwordnum;i++) {
          swap_leftword(we->rightword[i], we, wg);
        }
        we->mark = TRUE;
      }
    }
  }
  erased = wordgraph_exec_erase(rootp);
  j_printf("- %d words merged, %d words left in lattice\n", erased, count - erased);
  for(wg=*rootp;wg;wg=wg->next) {
    uniq_leftword(wg);
    uniq_rightword(wg);
  }
}

void
wordgraph_compaction_exacttime(WordGraph **rootp)
{
  WordGraph *wg, *we;
  int i, count, erased;
  WordGraph *wtmp;

  j_printf("Step 4: Merge same words at same time, keep max score\n");

  count = 0;
  for(wg=*rootp;wg;wg=wg->next) {
    count++;
    if (wg->mark == TRUE) continue;
    for(we=wg->next;we;we=we->next) {
      if (we->mark == TRUE) continue;
      /* find same words at same position */
      if (wg->wid == we->wid &&
          wg->lefttime == we->lefttime &&
          wg->righttime == we->righttime) {
        /* merge contexts */
        merge_contexts(wg, we);
        /* swap contexts of left / right contexts */
        for(i=0;i<we->leftwordnum;i++) {
          swap_rightword(we->leftword[i], we, wg);
        }
        for(i=0;i<we->rightwordnum;i++) {
          swap_leftword(we->rightword[i], we, wg);
        }
        /* keep the max score */
        if (wg->fscore_head < we->fscore_head) {
          wg->fscore_head = we->fscore_head;
          wg->fscore_tail = we->fscore_tail;
          wg->gscore_head = we->gscore_head;
          wg->gscore_tail = we->gscore_tail;
#ifdef USE_NGRAM
          wg->lscore = we->lscore;
#endif
#ifdef CM_SEARCH
          wg->cmscore = we->cmscore;
#endif
        }
        we->mark = TRUE;
      }
    }
  }
  erased = wordgraph_exec_erase(rootp);
  j_printf("- %d words merged, %d words left in lattice\n", erased, count-erased);

  for(wg=*rootp;wg;wg=wg->next) {
    uniq_leftword(wg);
    uniq_rightword(wg);
  }
}

void
wordgraph_compaction_neighbor(WordGraph **rootp)
{
  WordGraph *wg, *we;
  int i, count, erased;
  WordGraph *wtmp;

  if (graph_merge_neighbor_range == 0) {
    j_printf("# Step 5: SKIP (merge same words at near place)\n");
    return;
  }

  j_printf("Step 5: Merge same words at near place (allow %d frame margin)\n", graph_merge_neighbor_range);

  count = 0;
  for(wg=*rootp;wg;wg=wg->next) {
    count++;
    if (wg->mark == TRUE) continue;
    for(we=wg->next;we;we=we->next) {
      if (we->mark == TRUE) continue;
      if (wg->wid == we->wid &&
          abs(wg->lefttime - we->lefttime) <= graph_merge_neighbor_range &&
          abs(wg->righttime - we->righttime) <= graph_merge_neighbor_range) {
        /* merge contexts */
        merge_contexts(wg, we);
        /* swap contexts of left / right contexts */
        for(i=0;i<we->leftwordnum;i++) {
          swap_rightword(we->leftword[i], we, wg);
        }
        for(i=0;i<we->rightwordnum;i++) {
          swap_leftword(we->rightword[i], we, wg);
        }
        /* keep the max score */
        if (wg->fscore_head < we->fscore_head) {
          wg->fscore_head = we->fscore_head;
          wg->fscore_tail = we->fscore_tail;
          wg->gscore_head = we->gscore_head;
          wg->gscore_tail = we->gscore_tail;
#ifdef USE_NGRAM
          wg->lscore = we->lscore;
#endif
#ifdef CM_SEARCH
          wg->cmscore = we->cmscore;
#endif
        }
        we->mark = TRUE;
      }
    }
  }
  erased = wordgraph_exec_erase(rootp);
  j_printf("- %d words merged, %d words left in lattice\n", erased, count-erased);

  for(wg=*rootp;wg;wg=wg->next) {
    uniq_leftword(wg);
    uniq_rightword(wg);
  }
 
}


/**************************************************************/
/* generation of graph word candidates while search */

WordGraph *
wordgraph_assign(WORD_ID wid, int leftframe, int rightframe, LOGPROB fscore_head, LOGPROB fscore_tail, LOGPROB gscore_head, LOGPROB gscore_tail, LOGPROB lscore, LOGPROB cm)
{
  /* just generate a new word */
  WordGraph *newarc;
  newarc = wordgraph_new(wid, leftframe, rightframe, fscore_head, fscore_tail, gscore_head, gscore_tail, lscore, cm);
  //printf("    [%d..%d] %d\n", leftframe, rightframe, wid);
  return newarc;
}

void
wordgraph_save(WordGraph *wg, WordGraph *right, WordGraph **root)
{
  if (wg != NULL) {
    wg->next = *root;
    *root = wg;
    wg->saved = TRUE;
    wordgraph_add_leftword(right, wg);
    wordgraph_add_rightword(wg, right);
  }
}

#ifdef GRAPHOUT_DYNAMIC

WordGraph *
wordgraph_check_merge(WordGraph *now, WordGraph **root, WORD_ID next_wid, boolean *merged_p)
{
  WordGraph *wg;
  int i;
#ifdef GDEBUG
  WordGraph *w;
#endif

#ifdef GRAPHOUT_SEARCH
  *merged_p = FALSE;
#endif

  if (now == NULL) return(NULL);

#ifdef GDEBUG
  printf("check_merge: checking \"%s\"[%d..%d]\n", wchmm->winfo->woutput[now->wid], now->lefttime, now->righttime);
  for(i=0;i<now->leftwordnum;i++) {
    w = now->leftword[i];
    printf("\t left%d:  \"%15s\"[%d..%d]\n", i, wchmm->winfo->woutput[w->wid], w->lefttime, w->righttime);
  }
  for(i=0;i<now->rightwordnum;i++) {
    w = now->rightword[i];
    printf("\tright%d:  \"%15s\"[%d..%d]\n", i, wchmm->winfo->woutput[w->wid], w->lefttime, w->righttime);
  }
#endif

  for(wg=*root;wg;wg=wg->next) {
    if (wg == now) continue;
#ifdef GRAPHOUT_DYNAMIC
    /* skip already merged word */
    if (wg->purged) continue;
#endif
    if (wg->wid == now->wid
        && wg->lefttime == now->lefttime
        && wg->righttime == now->righttime) {
      /* same word on the same position is found in current word graph */
#ifdef GDEBUG
      printf("check_merge: same word found: \"%s\"[%d..%d]\n", wchmm->winfo->woutput[wg->wid], wg->lefttime, wg->righttime);
      for(i=0;i<wg->leftwordnum;i++) {
        w = wg->leftword[i];
        printf("\t left%d:  \"%15s\"[%d..%d]\n", i, wchmm->winfo->woutput[w->wid], w->lefttime, w->righttime);
      }
      for(i=0;i<wg->rightwordnum;i++) {
        w = wg->rightword[i];
        printf("\tright%d:  \"%15s\"[%d..%d]\n", i, wchmm->winfo->woutput[w->wid], w->lefttime, w->righttime);
      }
#endif
      /* merge contexts */
      merge_contexts(wg, now);
      /* swap contexts of left / right contexts */
      for(i=0;i<now->leftwordnum;i++) {
        swap_rightword(now->leftword[i], now, wg);
        uniq_rightword(now->leftword[i]);
      }
      for(i=0;i<now->rightwordnum;i++) {
        swap_leftword(now->rightword[i], now, wg);
        uniq_leftword(now->rightword[i]);
      }
#ifdef GRAPHOUT_SEARCH
      /* if the left and right contexts of now are already included in wg,
         and wg already has left node of next word,
         it means that
         the current word and the last word context is
         already included in the existing word graph.
         So, in the case this partial path should be abandoned.
      */
      for(i=0;i<wg->leftwordnum;i++) {
        if (wg->leftword[i]->wid == next_wid) break;
      }
      if (i < wg->leftwordnum) {
        *merged_p = TRUE;
      }
#endif /* GRAPHOUT_SEARCH */
      /* the merged word should be discarded for later merging from
         another word, so disable this */
      now->purged = TRUE;
      
      /* return the found one */
      return wg;
    }
  }
  /* if the same word not found, return NULL */
  return NULL;
}
#endif /* GRAPHOUT_DYNAMIC */


/**************************************************************/
/* misc. functions */

void
put_wordgraph(WordGraph *wg)
{
  int i;
  if (wg == NULL) {
    j_printf("(NULL)\n");
  } else {
    j_printf("%d:", wg->id);
    for(i=0;i<wg->leftwordnum;i++) {
      j_printf((i == 0) ? " left=%d" : ",%d", wg->leftword[i]->id);
    }
    for(i=0;i<wg->rightwordnum;i++) {
      j_printf((i == 0) ? " right=%d" : ",%d", wg->rightword[i]->id);
    }
    j_printf(" [%d..%d]", wg->lefttime, wg->righttime);
    j_printf(" wid=%d name=\"%s\" lname=\"%s\" f=%f f_prev=%f g_head=%f g_prev=%f", wg->wid, wchmm->winfo->woutput[wg->wid], wchmm->winfo->wname[wg->wid], wg->fscore_head, wg->fscore_tail, wg->gscore_head, wg->gscore_tail);
#ifdef USE_NGRAM
    j_printf(" lscore=%f", wg->lscore);
    if (wg->righttime - wg->lefttime + 1 != 0) {
      j_printf(" AMavg=%f", (wg->gscore_head - wg->gscore_tail - wg->lscore) / (float)(wg->righttime - wg->lefttime + 1));
    }
#else
    if (wg->righttime - wg->lefttime + 1 != 0) {
      j_printf(" AMavg=%f", (wg->gscore_head - wg->gscore_tail) / (float)(wg->righttime - wg->lefttime + 1));
    }
#endif
#ifdef CM_SEARCH
    j_printf(" cmscore=%f", wg->cmscore);
#endif
    j_printf("\n");
  }
}

void
wordgraph_dump(WordGraph *root)
{
  WordGraph *wg;
  j_printf("--- begin wordgraph data ---\n");
  for(wg=root;wg;wg=wg->next) {
    put_wordgraph(wg);
  }
  j_printf("--- end wordgraph data ---\n");
}

void
wordgraph_check_coherence(WordGraph *rootp)
{
  WordGraph *wg, *wl, *wr;
  int l,r;

  for(wg=rootp;wg;wg=wg->next) {
    /* check ID overflow */
    if (wg->id < 0 || wg->id >= graph_totalwordnum) {
      j_printf("ERROR: invalid id\n");
      put_wordgraph(wg);
      continue;
    }
    /* check link */
    for(l=0;l<wg->leftwordnum;l++){
      wl = wg->leftword[l];
      if (wl->id < 0 || wl->id >= graph_totalwordnum) {
        j_printf("ERROR: invalid id in left context\n");
        put_wordgraph(wg);
        continue;
      }
      for(r=0;r<wl->rightwordnum;r++){
        if (wl->rightword[r] == wg) break;
      }
      if (r >= wl->rightwordnum) {
        j_printf("ERROR: reverse link not found in left context\n");
        put_wordgraph(wg);
        put_wordgraph(wl);
        continue;
      }
    }
    for(r=0;r<wg->rightwordnum;r++){
      wr = wg->rightword[r];
      if (wr->id < 0 || wr->id >= graph_totalwordnum) {
        j_printf("ERROR: invalid id in right context\n");
        put_wordgraph(wg);
        continue;
      }
      for(l=0;l<wr->leftwordnum;l++){
        if (wr->leftword[l] == wg) break;
      }
      if (l >= wr->leftwordnum) {
        j_printf("ERROR: reverse link not found in right context\n");
        put_wordgraph(wg);
        put_wordgraph(wr);
        continue;
      }
    }
  }
}

#endif /* GRAPHOUT */

---