libjulius/src/graphout.c File Reference

Output word lattice. More...

#include <julius/julius.h>

Go to the source code of this file.

Functions

void wordgraph_init (WCHMM_INFO *wchmm)
 Initialize data for graphout.
static WordGraph * wordgraph_new (WORD_ID wid, HMM_Logical *headphone, HMM_Logical *tailphone, int leftframe, int rightframe, LOGPROB fscore_head, LOGPROB fscore_tail, LOGPROB gscore_head, LOGPROB gscore_tail, LOGPROB lscore, LOGPROB cm)
 Allocate a new graph word and return a new pointer to it.
void wordgraph_free (WordGraph *wg)
 Free a graph word.
static void wordgraph_add_leftword (WordGraph *wg, WordGraph *left, LOGPROB lscore)
 Add a graph word as a new left context.
static void wordgraph_add_rightword (WordGraph *wg, WordGraph *right, LOGPROB lscore)
 Add a graph word as a new right context.
boolean wordgraph_check_and_add_leftword (WordGraph *wg, WordGraph *left, LOGPROB lscore)
 Check for the left context if the specified graph already exists, and add it if not yet.
boolean wordgraph_check_and_add_rightword (WordGraph *wg, WordGraph *right, LOGPROB lscore)
 Check for the right context if the specified graph already exists, and add it if not yet.
static boolean merge_contexts (WordGraph *dst, WordGraph *src)
 Add all the context words to other for merging the same two graph words.
static void swap_leftword (WordGraph *wg, WordGraph *from, WordGraph *to, LOGPROB lscore)
 Substitute a word at left context of a graph word to another.
static void swap_rightword (WordGraph *wg, WordGraph *from, WordGraph *to, LOGPROB lscore)
 Substitute a word at right context of a graph word to another.
static void uniq_leftword (WordGraph *wg)
 Delete duplicate entries in left context list of a graph word.
static void uniq_rightword (WordGraph *wg)
 Delete duplicate entries in right context list of a graph word.
static void wordgraph_remove_context (WordGraph *wg)
 Remove the specified word graph from contexts of all left and right words.
static void wordgraph_link_context (WordGraph *wg)
 link all words at the context of the graph word.
static int wordgraph_exec_erase (WordGraph **rootp)
 Actually erase the marked words in word graph.
static int compare_lefttime (WordGraph **x, WordGraph **y)
 qsort callback for word sorting.
int wordgraph_sort_and_annotate_id (WordGraph **rootp, RecogProcess *r)
 Sort words by left time and annotate sequencial id for them in a word graph.
void wordgraph_clean (WordGraph **rootp)
 Free all the words in a word graph.
static int compare_beam (WordGraph **x, WordGraph **y)
 Callback function for qsort to do word graph depth cutting.
void wordgraph_purge_leaf_nodes (WordGraph **rootp, RecogProcess *r)
 Post-processing step 1: Extract initial word graph.
void wordgraph_depth_cut (WordGraph **rootp, RecogProcess *r)
 Post-processing step 1.5: word graph depth cutting.
static boolean wordgraph_adjust_boundary_sub (WordGraph **rootp, int *mov_num_ret, int *dup_num_ret, int *del_num_ret, int *mod_num_ret, int count, int *maxfnum, int peseqlen, int lmtype, int **p_framelist, LOGPROB **p_framescorelist)
 Execute adjustment of word boundaries.
static void wordgraph_compaction_thesame_sub (WordGraph **rootp, int *rest_ret, int *merged_ret)
 Merge duplicated words with exactly the same scores and alignments.
void wordgraph_adjust_boundary (WordGraph **rootp, RecogProcess *r)
 Post-processing step 2: Adjust word boundaries.
void wordgraph_compaction_thesame (WordGraph **rootp)
 Post-processing step 3: Bundle words (exactly the same ones).
void wordgraph_compaction_exacttime (WordGraph **rootp, RecogProcess *r)
 Post-processing step 4: Bundle words (same boundaries).
void wordgraph_compaction_neighbor (WordGraph **rootp, RecogProcess *r)
 Post-processing step 5: Bundle words (neighbor words).
WordGraph * wordgraph_assign (WORD_ID wid, WORD_ID wid_left, WORD_ID wid_right, int leftframe, int rightframe, LOGPROB fscore_head, LOGPROB fscore_tail, LOGPROB gscore_head, LOGPROB gscore_tail, LOGPROB lscore, LOGPROB cm, RecogProcess *r)
 Return a newly allocated graph word candidates.
void wordgraph_save (WordGraph *wg, WordGraph *right, WordGraph **root)
 Register a graph word candidate to the word graph as a member.
WordGraph * wordgraph_check_merge (WordGraph *now, WordGraph **root, WORD_ID next_wid, boolean *merged_p, JCONF_SEARCH *jconf)
 Check if a graph word with the same word ID and same position as the given graph word candidate exists in the already registered word graph.
void put_wordgraph (FILE *fp, WordGraph *wg, WORD_INFO *winfo)
 Output information of a graph word in text in the format below: (n means the word).
void wordgraph_dump (FILE *fp, WordGraph *root, WORD_INFO *winfo)
 Output text information of all the words in word graph.
void wordgraph_check_coherence (WordGraph *rootp, RecogProcess *r)
 For debug: Check the coherence in word graph.
static int compare_forward (WordGraph **x, WordGraph **y)
 qsort callback function to order words from right to left.
static int compare_backward (WordGraph **x, WordGraph **y)
 qsort callback function to order words from left to right.
static LOGPROB addlog10 (LOGPROB x, LOGPROB y)
 常用対数で表現されている確率の和を計算する.
void graph_forward_backward (WordGraph *root, RecogProcess *r)
 Compute graph-based confidence scores by forward-backward parsing on the generated lattice.

Detailed Description

Output word lattice.

Author:
Akinobu LEE
Date:
Thu Mar 17 12:46:31 2005
Revision
1.5

Definition in file graphout.c.

Function Documentation

void wordgraph_init ( WCHMM_INFO *  wchmm  ) 

Initialize data for graphout.

Parameters:
wchmm [in] tree lexicon

Definition at line 54 of file graphout.c.

Referenced by wchmm_fbs().

Here is the caller graph for this function:

static WordGraph* wordgraph_new ( WORD_ID  wid,
HMM_Logical *  headphone,
HMM_Logical *  tailphone,
int  leftframe,
int  rightframe,
LOGPROB  fscore_head,
LOGPROB  fscore_tail,
LOGPROB  gscore_head,
LOGPROB  gscore_tail,
LOGPROB  lscore,
LOGPROB  cm 
) [static]

Allocate a new graph word and return a new pointer to it.

Parameters:
wid [in] word ID
headphone [in] phoneme on head of word
tailphone [in] phoneme on tail of word
leftframe [in] beginning time in frames
rightframe [in] end time in frames
fscore_head [in] sentence score on search at word head (g + h)
fscore_tail [in] sentence score on search at word tail (g + h)
gscore_head [in] Viterbi score accumulated from input end at word head (g)
gscore_tail [in] Viterbi score accumulated from input end at word tail (g)
lscore [in] language score of the word (bogus in Julian)
cm [in] word confidence score (computed on search time)
Returns:
pointer to the newly created graph word.

Definition at line 102 of file graphout.c.

Referenced by wordgraph_assign().

void wordgraph_free ( WordGraph *  wg  ) 

Free a graph word.

Parameters:
wg [in] graph word to be freed.

Definition at line 181 of file graphout.c.

Referenced by free_node(), wordgraph_clean(), and wordgraph_exec_erase().

Here is the caller graph for this function:

static void wordgraph_add_leftword ( WordGraph *  wg,
WordGraph *  left,
LOGPROB  lscore 
) [static]

Add a graph word as a new left context.

Parameters:
wg [i/o] word graph to which the left word will be added as left context.
left [in] word graph which will be added to the wg as left context.
lscore [in] word connection score

Definition at line 210 of file graphout.c.

Referenced by merge_contexts(), and wordgraph_save().

static void wordgraph_add_rightword ( WordGraph *  wg,
WordGraph *  right,
LOGPROB  lscore 
) [static]

Add a graph word as a new right context.

Parameters:
wg [i/o] word graph to which the right word will be added as right context.
right [in] word graph which will be added to the wg as right context.
lscore [in] word connection score

Definition at line 247 of file graphout.c.

Referenced by wordgraph_save().

boolean wordgraph_check_and_add_leftword ( WordGraph *  wg,
WordGraph *  left,
LOGPROB  lscore 
)

Check for the left context if the specified graph already exists, and add it if not yet.

Parameters:
wg [i/o] graph word whose left context will be checked
left [in] graph word to be checked as left context of wg
lscore [in] word connection score
Returns:
TRUE if not exist yet and has been added, or FALSE if already exist and thus not added.

Definition at line 295 of file graphout.c.

Referenced by wordgraph_link_context().

Here is the caller graph for this function:

boolean wordgraph_check_and_add_rightword ( WordGraph *  wg,
WordGraph *  right,
LOGPROB  lscore 
)

Check for the right context if the specified graph already exists, and add it if not yet.

Parameters:
wg [i/o] graph word whose right context will be checked
right [in] graph word to be checked as right context of wg
lscore [in] word connection score
Returns:
TRUE if not exist yet and has been added, or FALSE if already exist and thus not added.

Definition at line 347 of file graphout.c.

Referenced by wordgraph_link_context().

Here is the caller graph for this function:

static boolean merge_contexts ( WordGraph *  dst,
WordGraph *  src 
) [static]

Add all the context words to other for merging the same two graph words.

Parameters:
dst [i/o] destination graph word
src [in] source graph word
Returns:
TRUE if at least one context word has been newly added, or FALSE if context on dst has not been updated.

Definition at line 390 of file graphout.c.

Referenced by wordgraph_compaction_exacttime(), wordgraph_compaction_neighbor(), and wordgraph_compaction_thesame_sub().

static void swap_leftword ( WordGraph *  wg,
WordGraph *  from,
WordGraph *  to,
LOGPROB  lscore 
) [static]

Substitute a word at left context of a graph word to another.

Parameters:
wg [i/o] target graph word.
from [in] left context word to be substituted
to [in] substitution destination.
lscore [in] word connection score

Definition at line 498 of file graphout.c.

Referenced by wordgraph_compaction_exacttime(), wordgraph_compaction_neighbor(), and wordgraph_compaction_thesame_sub().

static void swap_rightword ( WordGraph *  wg,
WordGraph *  from,
WordGraph *  to,
LOGPROB  lscore 
) [static]

Substitute a word at right context of a graph word to another.

Parameters:
wg [i/o] target graph word.
from [in] right context word to be substituted
to [in] substitution destination.
lscore [in] word connection score

Definition at line 536 of file graphout.c.

Referenced by wordgraph_compaction_exacttime(), wordgraph_compaction_neighbor(), and wordgraph_compaction_thesame_sub().

static void uniq_leftword ( WordGraph *  wg  )  [static]

Delete duplicate entries in left context list of a graph word.

Parameters:
wg [i/o] target graph word

Definition at line 568 of file graphout.c.

static void uniq_rightword ( WordGraph *  wg  )  [static]

Delete duplicate entries in right context list of a graph word.

Parameters:
wg [i/o] target graph word

Definition at line 604 of file graphout.c.

static void wordgraph_remove_context ( WordGraph *  wg  )  [static]

Remove the specified word graph from contexts of all left and right words.

Parameters:
wg [in] target graph word

Definition at line 640 of file graphout.c.

Referenced by wordgraph_adjust_boundary_sub().

static void wordgraph_link_context ( WordGraph *  wg  )  [static]

link all words at the context of the graph word.

Parameters:
wg [in] target graph word

Definition at line 698 of file graphout.c.

static int wordgraph_exec_erase ( WordGraph **  rootp  )  [static]

Actually erase the marked words in word graph.

Parameters:
rootp [i/o] pointer to root node of a word graph
Returns:
the number of erased words.

Definition at line 739 of file graphout.c.

Referenced by wordgraph_adjust_boundary().

static int compare_lefttime ( WordGraph **  x,
WordGraph **  y 
) [static]

qsort callback for word sorting.

Parameters:
x [in] element 1
y [in] element 2
Returns:
1 if x>y, -1 if x<y, 0 if x = y.

Definition at line 786 of file graphout.c.

Referenced by wordgraph_sort_and_annotate_id().

int wordgraph_sort_and_annotate_id ( WordGraph **  rootp,
RecogProcess *  r 
)

Sort words by left time and annotate sequencial id for them in a word graph.

Parameters:
rootp [i/o] address of pointer to root node of a word graph
r [i/o] recognition process instance

Definition at line 820 of file graphout.c.

void wordgraph_clean ( WordGraph **  rootp  ) 

Free all the words in a word graph.

Parameters:
rootp [i/o] pointer to root node of a word graph

Definition at line 871 of file graphout.c.

Referenced by clear_result().

Here is the caller graph for this function:

static int compare_beam ( WordGraph **  x,
WordGraph **  y 
) [static]

Callback function for qsort to do word graph depth cutting.

Graph words will be sorted downward based on fscore_head.

Parameters:
x [in] element 1
y [in] element 2
Returns:
values for qsort

Definition at line 909 of file graphout.c.

Referenced by wordgraph_depth_cut().

void wordgraph_purge_leaf_nodes ( WordGraph **  rootp,
RecogProcess *  r 
)

Post-processing step 1: Extract initial word graph.

Extract initial word graph from generated word arcs while search, by purging leaf nodes and arcs that are not on the path from edge to edge.

Parameters:
rootp [i/o] pointer to root node of a word graph
r [in] recognition process instance

Definition at line 941 of file graphout.c.

void wordgraph_depth_cut ( WordGraph **  rootp,
RecogProcess *  r 
)

Post-processing step 1.5: word graph depth cutting.

If GRAPHOUT_DEPTHCUT is defined, perform word graph depth cutting.

Parameters:
rootp [i/o] pointer to root node of a word graph
r [in] recognition process instance

Definition at line 1050 of file graphout.c.

static boolean wordgraph_adjust_boundary_sub ( WordGraph **  rootp,
int *  mov_num_ret,
int *  dup_num_ret,
int *  del_num_ret,
int *  mod_num_ret,
int  count,
int *  maxfnum,
int  peseqlen,
int  lmtype,
int **  p_framelist,
LOGPROB **  p_framescorelist 
) [static]

Execute adjustment of word boundaries.

It looks through the graph to check correspondence of word boundary information among context, and if there is a gap, the beginning frame of right word will be moved to the end frame of left word. If several alignment is found among contexts, the word will be duplicated and each will be fit to each context. Also, words with invalid alignment will be eliminated.

Parameters:
rootp [in] root pointer to the list of graph words
mov_num_ret [out] pointer to hold resulted number of moved words
dup_num_ret [out] pointer to hold resulted number of duplicated words
del_num_ret [out] pointer to hold resulted number of eliminated words
mod_num_ret [out] pointer to hold resulted number of modified words
count [in] number of words in graph
maxfnum 
peseqlen 
lmtype 
p_framelist 
p_framescorelist 
Returns:
TRUE if any word has been changed, or FALSE if no word has been altered.

Definition at line 1237 of file graphout.c.

Referenced by wordgraph_adjust_boundary().

static void wordgraph_compaction_thesame_sub ( WordGraph **  rootp,
int *  rest_ret,
int *  merged_ret 
) [static]

Merge duplicated words with exactly the same scores and alignments.

Parameters:
rootp [i/o] root pointer to the list of graph words
rest_ret [out] pointer to hold resulted number of words left in graph
merged_ret [out] pointer to hold resuled number of merged words

Definition at line 1502 of file graphout.c.

Referenced by wordgraph_adjust_boundary(), and wordgraph_compaction_thesame().

void wordgraph_adjust_boundary ( WordGraph **  rootp,
RecogProcess *  r 
)

Post-processing step 2: Adjust word boundaries.

When GRAPHOUT_PRECISE_BOUNDARY is defined, the word boundaries will be moved depending on the later word expansion to get context-dependent precise boundaries. So the precise boundary, modified after generation while search, should be propagated to the context words in the post processing.

Since the affect of word boundaries may propagate to the context words, the adjustment procedure has to be executed iteratively until all the boundaries are fixated. However, when graph is large, the oscillation of short words will results in very long loop. By defining GRAPHOUT_LIMIT_BOUNDARY_LOOP, the number of the adjustment loop can be up to the number specified by graphout_limit_bounrady_loop_num.

Parameters:
rootp [i/o] pointer to root node of a word graph
r [i/o] recognition process instance

< frame list for adjust_boundary_sub

< frame score list for adjust_boundary_sub

Definition at line 1595 of file graphout.c.

void wordgraph_compaction_thesame ( WordGraph **  rootp  ) 

Post-processing step 3: Bundle words (exactly the same ones).

This function bundles same words which have exactly the same boundaries and partial sentence scores.

Parameters:
rootp [i/o] pointer to root node of a word graph

Definition at line 1671 of file graphout.c.

void wordgraph_compaction_exacttime ( WordGraph **  rootp,
RecogProcess *  r 
)

Post-processing step 4: Bundle words (same boundaries).

This function bundles the same words which have exactly the same boundaries, allowing having different scores. The word with the best partial sentence score will be adopted. This function will not take effect when graph_merge_neightbor_range is lower than 0.

Parameters:
rootp [i/o] pointer to root node of a word graph
r [i/o] recognition process instance

Definition at line 1709 of file graphout.c.

void wordgraph_compaction_neighbor ( WordGraph **  rootp,
RecogProcess *  r 
)

Post-processing step 5: Bundle words (neighbor words).

This function bundles the same words which appears at similar place. If the difference of both the left boundary and right right boundary is under graph_merge_neighbor_range, it will be bundled. If its value is lower than or equal to 0, this function does not take effect.

Parameters:
rootp [i/o] pointer to root node of a word graph
r [i/o] recognition process instance

Definition at line 1795 of file graphout.c.

WordGraph* wordgraph_assign ( WORD_ID  wid,
WORD_ID  wid_left,
WORD_ID  wid_right,
int  leftframe,
int  rightframe,
LOGPROB  fscore_head,
LOGPROB  fscore_tail,
LOGPROB  gscore_head,
LOGPROB  gscore_tail,
LOGPROB  lscore,
LOGPROB  cm,
RecogProcess *  r 
)

Return a newly allocated graph word candidates.

The resulting word is not registered to the word graph yet.

Parameters:
wid [in] word ID
wid_left [in] word ID of left context for determining head phone
wid_right [in] word ID of right context for determining tail phone
leftframe [in] beginning time in frames
rightframe [in] end time in frames
fscore_head [in] sentence score on search at word head (g + h)
fscore_tail [in] sentence score on search at word tail (g + h)
gscore_head [in] Viterbi score accumulated from input end at word head (g)
gscore_tail [in] Viterbi score accumulated from input end at word tail (g)
lscore [in] language score
cm [in] confidence score
r [in] recognition process instance
Returns:
pointer to the newly created graph word candidate.

Definition at line 1901 of file graphout.c.

void wordgraph_save ( WordGraph *  wg,
WordGraph *  right,
WordGraph **  root 
)

Register a graph word candidate to the word graph as a member.

The registered word will have the saved member to be set to TRUE.

Parameters:
wg [i/o] graph word candidate to be registered
right [i/o] right context graph word
root [i/o] pointer to root node of already registered word graph

Definition at line 1957 of file graphout.c.

WordGraph* wordgraph_check_merge ( WordGraph *  now,
WordGraph **  root,
WORD_ID  next_wid,
boolean *  merged_p,
JCONF_SEARCH *  jconf 
)

Check if a graph word with the same word ID and same position as the given graph word candidate exists in the already registered word graph.

If such graph word is found, the word contexts of the given word graph candidate will be merged to the found graph word in the registered word graph.

When GRAPHOUT_SEARCH is defined, whether to terminate the search at here will be determined here. That is, if the next word in search already exists in the list of left context words of the merged graph word, it is determined that the next path has already been expanded and thus there is no need to proceed more on this hypothesis.

Parameters:
now [i/o] graph word candidate
root [i/o] pointer to root node of already registered word graph
next_wid [in] next word on search
merged_p [out] will be set to TRUE if search should be terminated, or FALSE if search should be proceeded (when GRAPHOUT_SEARCH defined)
jconf [in] configuration parameters for this search
Returns:
the pointer to the already registered graph word when the same word was found on the same position, or NULL if such word not found in already registered word graph.

Definition at line 2020 of file graphout.c.

void put_wordgraph ( FILE *  fp,
WordGraph *  wg,
WORD_INFO *  winfo 
)

Output information of a graph word in text in the format below: (n means the word). 

   ID: left=left_context_ID[,ID,...] right=right_context_ID[,ID,...]
   [left_edge_frame...right_edge_frame]
   wid=word_id
   name="word string"
   lname="N-gram word string (Julius) or category number (Julian)"
   f="partial sentence score at left edge (g(n) + h(n+1)) on search time"
   f_prev="partial sentence score at right edge (g(n-1) + h(n)) on search time"
   g_head="accumulated viterbi score at left edge (g(n))"
   g_prev="accumulated viterbi score at right edge (g(n-1) + LM(n)"
   lscore="language score LM(n)  (Julius only)"
   AMavg="average acoustic likelihood per frame"
   cmscore="confidence score"
Parameters:
fp [in] file pointer to which output should go
wg [in] graph word to output
winfo [in] word dictionary

Definition at line 2193 of file graphout.c.

Referenced by graph_forward_backward(), result_confnet(), wordgraph_check_coherence(), and wordgraph_dump().

Here is the caller graph for this function:

void wordgraph_dump ( FILE *  fp,
WordGraph *  root,
WORD_INFO *  winfo 
)

Output text information of all the words in word graph.

Parameters:
fp [in] file pointer to which output should go
root [in] pointer to root node of a word graph
winfo [in] word dictionary

Definition at line 2252 of file graphout.c.

Referenced by graph_forward_backward(), outfile_graph(), and result_graph().

Here is the caller graph for this function:

void wordgraph_check_coherence ( WordGraph *  rootp,
RecogProcess *  r 
)

For debug: Check the coherence in word graph.

Parameters:
rootp [in] pointer to root node of a word graph
r [i/o] recognition process instance

Definition at line 2281 of file graphout.c.

static int compare_forward ( WordGraph **  x,
WordGraph **  y 
) [static]

qsort callback function to order words from right to left.

Parameters:
x [in] 1st element
y [in] 2nd element
Returns:
value required by qsort

Definition at line 2352 of file graphout.c.

Referenced by graph_forward_backward().

static int compare_backward ( WordGraph **  x,
WordGraph **  y 
) [static]

qsort callback function to order words from left to right.

Parameters:
x [in] 1st element
y [in] 2nd element
Returns:
value required by qsort

Definition at line 2374 of file graphout.c.

static LOGPROB addlog10 ( LOGPROB  x,
LOGPROB  y 
) [static]

常用対数で表現されている確率の和を計算する.

Parameters:
x [in] first value
y [in] second value
Returns:
value of log(10^x + 10^y)

Definition at line 2396 of file graphout.c.

void graph_forward_backward ( WordGraph *  root,
RecogProcess *  r 
)

Compute graph-based confidence scores by forward-backward parsing on the generated lattice.

The computed scores are stored in graph_cm of each graph words. The same alpha value of search-time confidence scoring (r->config->annotate.cm_alpha) will be used to compute the posterior probabilities.

Parameters:
root [in] root graph node
r [in] recognition process instance

Definition at line 2430 of file graphout.c.

Generated on Thu Jul 23 12:13:51 2009 for Julius by  doxygen 1.5.1