julius/search_bestfirst_main.c File Reference

Main search function for stack decoding on the 2nd pass. More...

#include <julius.h>

Include dependency graph for search_bestfirst_main.c:

Go to the source code of this file.

Functions

static NODE * get_best_from_stack (NODE **start, int *stacknum)
static int put_to_stack (NODE *new, NODE **start, NODE **bottom, int *stacknum, int stacksize)
static void put_all_in_stack (NODE **start, int *stacknum)
static void free_all_nodes (NODE *node)
static void put_hypo_woutput (NODE *hypo)
static void put_hypo_wname (NODE *hypo)
static NEXTWORD ** nw_malloc (int *maxlen, NEXTWORD **root)
static void nw_free (NEXTWORD **nw, NEXTWORD *root)
static NEXTWORD ** nw_expand (NEXTWORD **nwold, int *maxlen, NEXTWORD **root)
 expand data area of NEXTWORD.
static int can_put_to_stack (NODE *new, NODE **bottom, int *stacknum, int stacksize)
static void cm_init (WORD_INFO *winfo)
static void cm_store (NODE *new)
static void cm_sum_score ()
static void cm_set_score (NODE *node)
static NODE * cm_get_node ()
static void wb_init ()
static boolean wb_ok (NODE *now)
static void envl_init (int framenum)
static void envl_update (NODE *n, int framenum)
static void result_reorder_and_output (NODE **r_start, NODE **r_bottom, int *r_stacknum, int ncan, WORD_INFO *winfo)
void wchmm_fbs (HTK_Param *param, BACKTRELLIS *backtrellis, LOGPROB backmax, int stacksize, int ncan, int maxhypo, int cate_bgn, int cate_num)

Variables

static LOGPROB cm_tmpbestscore
 Temporal best score for summing up scores.
static LOGPROB cm_tmpsum
 Sum of CM score.
static int l_stacksize
 Local stack size for CM.
static int l_stacknum
 Num of hypo. in local stack for CM.
static NODE * l_start = NULL
 Top node of local stack for CM.
static NODE * l_bottom = NULL
 bottom node of local stack for CM
static int hypo_len_count [MAXSEQNUM+1]
 Count of popped hypothesis per each length.
static int maximum_filled_length
 Current least beam-filled depth.
static NEXTWORD fornoise
static HTK_Param * tparam
 Temporal parameter for forced alignment.

Detailed Description

Main search function for stack decoding on the 2nd pass.

Author:
Akinobu Lee
Date:
Thu Sep 08 11:51:12 2005
This file implements search algorithm based on best-first stack decoding on the 2nd pass. The search will be performed on backward (i.e. right-to-left) direction, using the result of 1st pass (word trellis) as heuristics of unreached area. Hypothesis are stored in a global stack, and the best one will be expanded according to the survived words in the word trellis and language constraint.

The expanding words will be given by ngram_decode.c for N-gram based recognition (Julius), with their langugage probabilities, or by dfa_decode.c for grammar-based recognition (Julian), with their emitting DFA state information.

The dynamic confidence scoring using local posterior probability, score envelope beaming, and other techniques are also implemented within this file.

Revision
1.7

Definition in file search_bestfirst_main.c.

Function Documentation

static NODE * get_best_from_stack ( NODE **  start,
int *  stacknum 
) [static]

Pop the best hypothesis from stack.

Parameters:
start [i/o] pointer to stack top node (will be modified if necessary)
stacknum [i/o] pointer to the current stack size (will be modified if necessary)
Returns:
pointer to the popped hypothesis.

Definition at line 217 of file search_bestfirst_main.c.

Referenced by cm_get_node(), put_all_in_stack(), and result_reorder_and_output().

static int put_to_stack ( NODE *  new,
NODE **  start,
NODE **  bottom,
int *  stacknum,
int  stacksize 
) [static]

Push a new hypothesis into the stack, keeping score order. If not succeeded, the given new hypothesis will be freed by free_node().

Parameters:
new [in] hypothesis to be checked
start [i/o] pointer to stack top node
bottom [i/o] pointer to stack bottom node
stacknum [i/o] pointer to current stack size
stacksize [in] pointer to maximum stack size limit
Returns:
0 if succeded, or -1 if failed to push because of number limitation or too low score.

Definition at line 300 of file search_bestfirst_main.c.

Referenced by cm_store(), and wchmm_fbs().

static void put_all_in_stack ( NODE **  start,
int *  stacknum 
) [static]

Output all nodes in the stack. All nodes will be lost (for debug).

Parameters:
start [i/o] pointer to stack top node
stacknum [i/o] pointer to current stack size

Definition at line 386 of file search_bestfirst_main.c.

static void free_all_nodes ( NODE *  start  )  [static]

Free all nodes in a stack.

Parameters:
start [i/o] stack top node

Definition at line 411 of file search_bestfirst_main.c.

Referenced by result_reorder_and_output().

static void put_hypo_woutput ( NODE *  hypo  )  [static]

Output word sequence of a hypothesis for debug.

Parameters:
hypo [in] hypothesis

Definition at line 932 of file search_bestfirst_main.c.

static void put_hypo_wname ( NODE *  hypo  )  [static]

Output N-gram entries (or DFA category IDs) of a hypothesis for debug.

Parameters:
hypo [in] hypothesis

Definition at line 958 of file search_bestfirst_main.c.

static NEXTWORD** nw_malloc ( int *  maxlen,
NEXTWORD **  root 
) [static]

Allocate NEXTWORD array for storing list of candidate next words

Parameters:
maxlen [out] maximum number of words that can be stored
root [out] pointer to the top address of allocated data
Returns:
the newly allocated pointer of NEXTWORD array.

Definition at line 87 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static void nw_free ( NEXTWORD **  nw,
NEXTWORD *  root 
) [static]

Free given NEXTWORD data.

Parameters:
nw [in] pointer to NEXTWORD structure to be free.
root [in] pointer to the top address of allocated data previously returned by nw_malloc()

Definition at line 123 of file search_bestfirst_main.c.

static NEXTWORD** nw_expand ( NEXTWORD **  nwold,
int *  maxlen,
NEXTWORD **  root 
) [static]

expand data area of NEXTWORD.

In DFA mode, the number of nextwords can exceed the vocabulary size when more than one DFA states are expanded by short-pause skipping. In such case, the nextword data area should expanded here.

Parameters:
nwold [i/o] NEXTWORD array
maxlen [i/o] pointer to the maximum number of words that can be stored. The current number should be stored before calling this function, and the resulting new number will be stored within this function.
root [i/o] address to the pointer of the allocated data. The value will be updated by reallocation in this function.
Returns:
the newlly re-allocated pointer of NEXTWORD array.

Definition at line 167 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static int can_put_to_stack ( NODE *  new,
NODE **  bottom,
int *  stacknum,
int  stacksize 
) [static]

Check whether a hypothesis will be stored in the stack.

Parameters:
new [in] hypothesis to be checked
bottom [in] pointer to stack bottom node
stacknum [in] pointer to current stack size
stacksize [in] pointer to maximum stack size limit
Returns:
0 if it will be stored in the stack (in case stacknum < stacksize or the score of new is better than bottom. Otherwise returns -1, which means it can not be pushed to the stack.

Definition at line 261 of file search_bestfirst_main.c.

static void cm_init ( WORD_INFO *  winfo  )  [static]

Initialize parameters for confidence scoring (will be called at each startup of 2nd pass)

Parameters:
winfo [in] word dictionary

Definition at line 470 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static void cm_store ( NODE *  new  )  [static]

Store an expanded hypothesis to the local stack for later CM scoring

Parameters:
new [in] expanded hypothesis

Definition at line 495 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static void cm_sum_score (  )  [static]

Compute sum of probabilities for hypotheses in the local stack for CM scoring.

Definition at line 513 of file search_bestfirst_main.c.

static void cm_set_score ( NODE *  node  )  [static]

Compute confidence score of a new word at the end of the given hypothesis, based on the local posterior probabilities.

Parameters:
node [i/o] expanded hypothesis

Definition at line 559 of file search_bestfirst_main.c.

static NODE* cm_get_node (  )  [static]

Pop one node from local stack for confidence scoring.

Returns:
the popped hypothesis.

Definition at line 589 of file search_bestfirst_main.c.

static void wb_init (  )  [static]

Initialize counters fro word enveloping.

Definition at line 731 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static boolean wb_ok ( NODE *  now  )  [static]

Consult the current word envelope to check if word expansion from the hypothesis node is allowed or not. Also increment the counter of word envelope if needed.

Parameters:
now [in] popped hypothesis
Returns:
TRUE if word expansion is allowed (in case word envelope count of the corresponding hypothesis depth does not reach the limit), or FALSE if already prohibited.

Definition at line 761 of file search_bestfirst_main.c.

static void envl_init ( int  framenum  )  [static]

Initialize score envelope. This will be called once at the beginning of 2nd pass.

Parameters:
framenum [in] input frame length

Definition at line 825 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static void envl_update ( NODE *  n,
int  framenum 
) [static]

Update the score envelope using forward score of the given hypothesis.

Parameters:
n [in] hypothesis
framenum [in] input frame length

Definition at line 846 of file search_bestfirst_main.c.

static void result_reorder_and_output ( NODE **  r_start,
NODE **  r_bottom,
int *  r_stacknum,
int  ncan,
WORD_INFO *  winfo 
) [static]

Output top N-best hypotheses in a stack as a recognition result, and free all hypotheses.

In Julius/Julian, the sentence candidates found at the 2nd pass will be pushed to the "result stack" instead of immediate output. After recognition is over (in case the number of found sentences reaches the number specified by "-n", or search has been terminated in other reason), the top N sentence candidates in the stack will be output as a final result (where N should be specified by "-output"). After then, all the hypotheses in the stack will be freed.

Parameters:
r_start [i/o] pointer to the top node of the result stack
r_bottom [i/o] pointer to the bottom node of the result stack
r_stacknum [i/o] number of candidates in the current result stack
ncan [in] number of sentence candidates to be output
winfo [in] word dictionary

Definition at line 1011 of file search_bestfirst_main.c.

void wchmm_fbs ( HTK_Param *  param,
BACKTRELLIS *  backtrellis,
LOGPROB  backmax,
int  stacksize,
int  ncan,
int  maxhypo,
int  cate_bgn,
int  cate_num 
)

Main function to perform stack decoding of the 2nd search pass.

Parameters:
param [in] input parameter vector
backtrellis [in] backward word trellis obtained at the 1st pass
backmax [in] maximum score in the word trellis
stacksize [in] maximum size of hypothesis stack in the search
ncan [in] num of hypothesis to be found in the search
maxhypo [in] threshold num of hypothesis expansion to be treated as "search overflow"
cate_bgn [in] category id to allow word expansion from (ignored in Julius)
cate_num [in] num of category to allow word expansion from (ignored in Julius)

Definition at line 1083 of file search_bestfirst_main.c.

Referenced by main_recognition_loop().

Variable Documentation

NEXTWORD fornoise [static]

Dummy NEXTWORD data for short-pause insertion handling.

Definition at line 861 of file search_bestfirst_main.c.

Generated on Tue Dec 26 12:53:46 2006 for Julian by  doxygen 1.5.0