confnet.c

来自「julius version 4.12.about sound recognit」· C语言 代码 · 共 890 行 · 第 1/2 页

/**
 * @file   confnet.c
 * 
 * <JA>
 * @brief  Confusion network の栏喇
 *
 * 千急の冯蔡评られた帽胳グラフから·confusion network を栏喇する. 
 * </JA>
 * 
 * <EN>
 * @brief  Confusion network generation
 *
 * Generate confusion network from the obtained word lattice.
 * </EN>
 * 
 * @author Akinobu Lee
 * @date   Thu Aug 16 00:15:51 2007
 *
 * $Revision: 1.3 $
 * 
 */
/*
 * Copyright (c) 1991-2007 Kawahara Lab., Kyoto University
 * Copyright (c) 2000-2005 Shikano Lab., Nara Institute of Science and Technology
 * Copyright (c) 2005-2007 Julius project team, Nagoya Institute of Technology
 * All rights reserved
 */

#include <julius/julius.h>

/**
 * Define to enable debug output.
 * 
 */
#undef CDEBUG

/**
 * Define to enable further debug output.
 * 
 */
#undef CDEBUG2

/**
 * Use graph-based CM for confusion network generation.  If not
 * defined search-based CM (default of old julius) will be used.
 * However, the clustering process does not work properly with this
 * definition, since sum of the search- based CM for a word set on the
 * same position is not always 1.0.  Thus you'd better always define
 * this.
 * 
 */
#define PREFER_GRAPH_CM

/**
 * Julius identify the words by their dictionary IDs, so words with
 * different entries are treated as a different word.  If this is
 * defined, Julius treat words with the same output string as same
 * words and bundle them in confusion network generation.
 * 
 */
#define BUNDLE_WORD_WITH_SAME_OUTPUT


/** 
 * Determine whether the two words are idential in confusion network
 * generation.
 * 
 * @param w1 [in] first word
 * @param w2 [in] second word
 * @param winfo [in] word dictionary
 * 
 * @return TRUE if they are idential, FALSE if not.
 */
static boolean
is_same_word(WORD_ID w1, WORD_ID w2, WORD_INFO *winfo)
{
  if (w1 == w2
#ifdef BUNDLE_WORD_WITH_SAME_OUTPUT
      || strmatch(winfo->woutput[w1], winfo->woutput[w2])
#endif
      ) return TRUE;
  return FALSE;
}

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

/**
 * Macro to access the order matrix.
 * 
 */
#define m2i(A, B) (B) * r->order_matrix_count + (A)

/**
 * Judge order between two words by their word graph ID.
 * 
 * @param i [in] id of left graph word
 * @param j [in] id of right graph word
 * 
 * @return TRUE if they are ordered, or FALSE if not.
 */
static boolean
graph_ordered(RecogProcess *r, int i, int j) 
{
  if (i != j  && r->order_matrix[m2i(i,j)] == 0 && r->order_matrix[m2i(j,i)] == 0) {
    return FALSE;
  }
  return TRUE;
}  

/** 
 * Scan the order matrix to update it at initial step and after word
 * (set) marging.
 * 
 */
static void
graph_update_order(RecogProcess *r)
{
  int i, j, k;
  boolean changed;
  int count;

  count = r->order_matrix_count;
  
  do {
    changed = FALSE;
    for(i=0;i<count;i++) {
      for(j=0;j<count;j++) {
	if (r->order_matrix[m2i(i, j)] == 1) {
	  for(k=0;k<count;k++) {
	    if (r->order_matrix[m2i(j, k)] == 1) {
	      if (r->order_matrix[m2i(i, k)] == 0) {
		r->order_matrix[m2i(i, k)] = 1;
		changed = TRUE;
	      }
	    }
	  }
	}
      }
    }
  } while (changed == TRUE);
}

/** 
 * Extract order relationship between any two words in the word graph
 * for confusion network generation.
 * 
 * @param root [in] root pointer to the word graph
 * @param r [in] recognition process instance
 *
 * @callgraph
 * @callergraph
 */
void
graph_make_order(WordGraph *root, RecogProcess *r)
{
  int count;
  WordGraph *wg, *right;
  int i;
  
  /* make sure total num and id are valid */
  count = 0;
  for(wg=root;wg;wg=wg->next) count++;
  if (count == 0) {
    r->order_matrix = NULL;
    return;
  }
  if (count != r->graph_totalwordnum) {
    jlog("Error: graph_make_order: r->graph_totalwordnum differ from actual number?\n");
    r->order_matrix = NULL;
    return;
  }
  r->order_matrix_count = count;
  for(wg=root;wg;wg=wg->next) {
    if (wg->id >= count) {
      jlog("Error: graph_make_order: wordgraph id >= count (%d >= %d)\n", wg->id, count);
      r->order_matrix = NULL;
      return;
    }
  }

  /* allocate and clear matrix */
  r->order_matrix = (char *)mymalloc(count * count);
  for(i=0;i<count*count;i++) r->order_matrix[i] = 0;
  
  /* set initial order info */
  for(wg=root;wg;wg=wg->next) {
    for(i=0;i<wg->rightwordnum;i++) {
      right = wg->rightword[i];
      r->order_matrix[m2i(wg->id, right->id)] = 1;
    }
  }

  /* right propagate loop */
  graph_update_order(r);
}

/**
 * Free the order relation data.
 * 
 * @callgraph
 * @callergraph
 */
void
graph_free_order(RecogProcess *r)
{
  if (r->order_matrix) {
    free(r->order_matrix);
    r->order_matrix = NULL;
  }
}

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

/**
 * Create a new cluster holder.
 * 
 * @return the newly allocated cluster holder.
 */
static CN_CLUSTER *
cn_new()
{
  CN_CLUSTER *new;
  new = (CN_CLUSTER *)mymalloc(sizeof(CN_CLUSTER));
  new->wg = (WordGraph **)mymalloc(sizeof(WordGraph *) * CN_CLUSTER_WG_STEP);
  new->wgnum_alloc = CN_CLUSTER_WG_STEP;
  new->wgnum = 0;
  new->words = NULL;
  new->pp = NULL;
  new->next = NULL;
  return new;
}

/**
 * Free a cluster holder
 * 
 * @param c [out] a cluster holder to be released.
 * </EN>
 */
static void
cn_free(CN_CLUSTER *c)
{
  free(c->wg);
  if (c->words) free(c->words);
  if (c->pp) free(c->pp);
  free(c);
}

/** 
 * Free all cluster holders.
 * 
 * @param croot [out] pointer to root pointer of cluster holder list.
 *
 * @callgraph
 * @callergraph
 * 
 */
void
cn_free_all(CN_CLUSTER **croot)
{
  CN_CLUSTER *c, *ctmp;
  c = *croot;
  while(c) {
    ctmp = c->next;
    cn_free(c);
    c = ctmp;
  }
  *croot = NULL;
}

/** 
 * Add a graph word to a cluster holder.
 * 
 * @param c [out] cluster holder
 * @param wg [in] graph word to be added
 */
static void
cn_add_wg(CN_CLUSTER *c, WordGraph *wg)
{
  if (c->wgnum >= c->wgnum_alloc) {
    c->wgnum_alloc += CN_CLUSTER_WG_STEP;
    c->wg = (WordGraph **)myrealloc(c->wg, sizeof(WordGraph *) * c->wgnum_alloc);
  }
  c->wg[c->wgnum] = wg;
  c->wgnum++;
}

/** 
 * Merge a cluster holder into another.
 * 
 * @param dst [i/o] target cluster holder
 * @param src [in] source cluster holder.
 */
static void
cn_merge(RecogProcess *r, CN_CLUSTER *dst, CN_CLUSTER *src)
{
  WordGraph *wg;
  int i, j, n;

  /* update order matrix */
  for(i=0;i<src->wgnum;i++) {
    wg = src->wg[i];
    for(j=0;j<dst->wgnum;j++) {
      for(n=0;n<wg->leftwordnum;n++) {
	r->order_matrix[m2i(wg->leftword[n]->id, dst->wg[j]->id)] = 1;
      }
      for(n=0;n<wg->rightwordnum;n++) {
	r->order_matrix[m2i(dst->wg[j]->id, wg->rightword[n]->id)] = 1;
      }
    }
  }
  graph_update_order(r);
  /* add words in the source cluster to target cluster */
  for(i=0;i<src->wgnum;i++) {
    cn_add_wg(dst, src->wg[i]);
  }
}

/** 
 * Erase a cluster holder and remove it from the list.
 * 
 * @param target [i/o] a cluster holder to be erased
 * @param root [i/o] pointer to root pointer of cluster holder list
 */
static void
cn_destroy(CN_CLUSTER *target, CN_CLUSTER **root)
{
  CN_CLUSTER *c, *cprev;

  cprev = NULL;
  for(c = *root; c; c = c->next) {
    if (c == target) {
      if (cprev) {
	cprev->next = c->next;
      } else {
	*root = c->next;
      }
      cn_free(c);
      break;
    }
    cprev = c;
  }
}

/** 
 * Build / update word list from graph words for a cluster holder.
 * 
 * @param c [i/o] cluster holder to process
 * @param winfo [in] word dictionary 
 */
static void
cn_build_wordlist(CN_CLUSTER *c, WORD_INFO *winfo)
{
  int i, j;

  if (c->words) {
    free(c->words);
  }
  c->words = (WORD_ID *)mymalloc(sizeof(WORD_ID) * c->wgnum + 1);
  c->wordsnum = 0;
  for(i=0;i<c->wgnum;i++) {
    for(j=0;j<c->wordsnum;j++) {
      if (is_same_word(c->words[j], c->wg[i]->wid, winfo)) break;
    }
    if (j>=c->wordsnum) {
      c->words[c->wordsnum] = c->wg[i]->wid;
      c->wordsnum++;
    }
  }
}

/** 
 * qsort_reentrant callback to sort clusters by their time order.
 * 
 * @param x [in] element 1
 * @param y [in] element 2
 * @param r [in] recognition process instance
 * 
 * @return order value
 */
static int
compare_cluster(CN_CLUSTER **x, CN_CLUSTER **y, RecogProcess *r)
{
  //int i, min1, min2;
/* 
 * 
 *   for(i=0;i<(*x)->wgnum;i++) {
 *     if (i == 0 || min1 > (*x)->wg[i]->lefttime) min1 = (*x)->wg[i]->lefttime;
 *   }
 *   for(i=0;i<(*y)->wgnum;i++) {
 *     if (i == 0 || min2 > (*y)->wg[i]->lefttime) min2 = (*y)->wg[i]->lefttime;
 *   }
 *   if (min1 < min2) return -1;
 *   else if (min1 > min2) return 1;
 *   else return 0;
 */
  int i, j;

  if (x == y) return 0;
  for(i=0;i<(*x)->wgnum;i++) {
    for(j=0;j<(*y)->wgnum;j++) {
      //if (graph_ordered((*x)->wg[i]->id, (*y)->wg[j]->id)) dir = 1;
      if (r->order_matrix[m2i((*x)->wg[i]->id, (*y)->wg[j]->id)] == 1) {
	return -1;
      }
    }
  }
  return 1;
}


/** 
 * Compute intra-word similarity of two graph words for confusion network
 * generation.
 * 
 * @param w1 [in] graph word 1
 * @param w2 [in] graph word 2
 * 
 * @return the similarity value.
 */
static PROB
get_intraword_similarity(WordGraph *w1, WordGraph *w2)
{
  PROB overlap;
  int overlap_frame, sum_len;
  PROB sim;

  /* compute overlap_frame */
  if (w1->lefttime < w2->lefttime) {
    if (w1->righttime < w2->lefttime) {
      overlap_frame = 0;
    } else if (w1->righttime > w2->righttime) {
      overlap_frame = w2->righttime - w2->lefttime + 1;
    } else {
      overlap_frame = w1->righttime - w2->lefttime + 1;
    }
  } else if (w1->lefttime > w2->righttime) {
    overlap_frame = 0;
  } else {
    if (w1->righttime > w2->righttime) {
      overlap_frame = w2->righttime - w1->lefttime + 1;
    } else {
      overlap_frame = w1->righttime - w1->lefttime + 1;
    }
  }
  sum_len = (w1->righttime - w1->lefttime + 1) + (w2->righttime - w2->lefttime + 1);