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

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(), result_reorder_and_output(), and wchmm_fbs().

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. Referenced by wchmm_fbs().

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(), and wchmm_fbs().

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. 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. Referenced by wchmm_fbs().

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. Referenced by wchmm_fbs().

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. Referenced by wchmm_fbs().

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. Referenced by wchmm_fbs().

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. Referenced by wchmm_fbs().

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. Referenced by wchmm_fbs().

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. Referenced by wchmm_fbs().

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().

---