Julius: libjulius/src/search_bestfirst

Go to the source code of this file.


Functions
static NODE *	get_best_from_stack (NODE *start, int stacknum)
	Pop the best hypothesis from stack.
static int	put_to_stack (NODE new, NODE start, NODE bottom, int stacknum, int stacksize)
	Push a new hypothesis into the stack, keeping score order.
static void	put_all_in_stack (NODE *start, int stacknum, WORD_INFO *winfo)
	Output all nodes in the stack.
static void	free_all_nodes (NODE *start)
	Free all nodes in a stack.
static void	put_hypo_woutput (NODE hypo, WORD_INFO winfo)
	Output word sequence of a hypothesis for debug.
static void	put_hypo_wname (NODE hypo, WORD_INFO winfo)
	Output N-gram entries (or DFA category IDs) of a hypothesis for debug.
static NEXTWORD **	nw_malloc (int maxlen, NEXTWORD *root, int max)
	Allocate memory for next word candidates.
static void	nw_free (NEXTWORD *nw, NEXTWORD root)
	Free next word candidate area.
static NEXTWORD **	nw_expand (NEXTWORD *nwold, int maxlen, NEXTWORD **root, int num)
	expand data area of NEXTWORD.
static int	can_put_to_stack (NODE new, NODE bottom, int stacknum, int stacksize)
	Check whether a hypothesis will be stored in the stack.
static void	cm_init (StackDecode *sd, int wnum, LOGPROB cm_alpha)
	Initialize parameters for confidence scoring (will be called at each startup of 2nd pass).
static void	cm_store (StackDecode sd, NODE new)
	Store an expanded hypothesis to the local stack for later CM scoring.
static void	cm_sum_score (StackDecode *sd)
	Compute sum of probabilities for hypotheses in the local stack for CM scoring.
static void	cm_set_score (StackDecode sd, NODE node)
	Compute confidence score of a new word at the end of the given hypothesis, based on the local posterior probabilities.
static NODE *	cm_get_node (StackDecode *sd)
	Pop one node from local stack for confidence scoring.
static void	wb_init (StackDecode *s)
	Initialize counters fro word enveloping.
static boolean	wb_ok (StackDecode s, NODE now, int width)
	Consult the current word envelope to check if word expansion from the hypothesis node is allowed or not.
static void	envl_init (StackDecode *s, int framenum)
	Initialize score envelope.
static void	envl_update (StackDecode s, NODE n, int framenum)
	Update the score envelope using forward score of the given hypothesis.
void	segment_set_last_nword (NODE hypo, RecogProcess r)
	Set the previous word context for the recognition of the next input segment from the current recognition result.
static void	store_result_pass2 (NODE hypo, RecogProcess r)
	Save a hypothesis as a recognition result f 2nd pass.
static void	result_reorder_and_output (NODE r_start, NODE r_bottom, int r_stacknum, int ncan, RecogProcess r, HTK_Param *param)
	Output top N-best hypotheses in a stack as a recognition result, and free all hypotheses.
void	pass2_finalize_on_no_result (RecogProcess *r, boolean use_1pass_as_final)
	Post-process of 2nd pass when no result is obtained.
void	wchmm_fbs (HTK_Param param, RecogProcess r, int cate_bgn, int cate_num)
	Main function to perform stack decoding of the 2nd search pass.

Detailed Description

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, with their langugage probabilities, or by dfa_decode.c for grammar-based recognition, with their emitting DFA state information.

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 209 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 292 of file search_bestfirst_main.c.

Referenced by cm_store().

static void put_all_in_stack	(	NODE **	start,
		int *	stacknum,
		WORD_INFO *	winfo
	)			`[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
	winfo	[in] word dictionary

Definition at line 380 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 405 of file search_bestfirst_main.c.

Referenced by result_reorder_and_output().

static void put_hypo_woutput	(	NODE *	hypo,
		WORD_INFO *	winfo
	)			`[static]`

Output word sequence of a hypothesis for debug.

Parameters:

	hypo	[in] hypothesis
	winfo	[in] word dictionary

Definition at line 948 of file search_bestfirst_main.c.

static void put_hypo_wname	(	NODE *	hypo,
		WORD_INFO *	winfo
	)			`[static]`

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

Parameters:

	hypo	[in] hypothesis
	winfo	[in] word dictionary

Definition at line 976 of file search_bestfirst_main.c.

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

Allocate memory for next word candidates.

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
	max	[in] number of elementes to be allocated

Returns:: the newly allocated pointer of NEXTWORD array.

Definition at line 86 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

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

Free next word candidate area.

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 118 of file search_bestfirst_main.c.

static NEXTWORD** nw_expand	(	NEXTWORD **	nwold,
		int *	maxlen,
		NEXTWORD **	root,
		int	num
	)			`[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.
	num	[in] size to expand

Returns:: the newlly re-allocated pointer of NEXTWORD array.

Definition at line 163 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 253 of file search_bestfirst_main.c.

static void cm_init	(	StackDecode *	sd,
		int	wnum,
		LOGPROB	cm_alpha
	)			`[static]`

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

Parameters:

	sd	[i/o] work area for 2nd pass
	wnum	[in] stack size
	cm_alpha	[in] scaling value to use at confidence scoring

Definition at line 452 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static void cm_store	(	StackDecode *	sd,
		NODE *	new
	)			`[static]`

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

Parameters:

	sd	[i/o] work area for 2nd pass
	new	[in] expanded hypothesis

Definition at line 491 of file search_bestfirst_main.c.

static void cm_sum_score ( StackDecode * sd ) [static]

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

Parameters:

[i/o] work area for 2nd pass

Definition at line 513 of file search_bestfirst_main.c.

static void cm_set_score	(	StackDecode *	sd,
		NODE *	node
	)			`[static]`

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

Parameters:

	sd	[i/o] work area for 2nd pass
	node	[i/o] expanded hypothesis

Definition at line 564 of file search_bestfirst_main.c.

static NODE* cm_get_node ( StackDecode * sd ) [static]

Pop one node from local stack for confidence scoring.

Parameters:

[i/o] work area for 2nd pass

Returns:: the popped hypothesis.

Definition at line 602 of file search_bestfirst_main.c.

static void wb_init ( StackDecode * s ) [static]

Initialize counters fro word enveloping.

Parameters:

[i/o] work area for 2nd pass

Definition at line 749 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

static boolean wb_ok	(	StackDecode *	s,
		NODE *	now,
		int	width
	)			`[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:

	s	[i/o] work area for 2nd pass
	now	[in] popped hypothesis
	width	[in] maximum limit of expansion count

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 783 of file search_bestfirst_main.c.

static void envl_init	(	StackDecode *	s,
		int	framenum
	)			`[static]`

Initialize score envelope.

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

Parameters:

	s	[i/o] work area for 2nd pass
	framenum	[in] input frame length

Definition at line 843 of file search_bestfirst_main.c.

Referenced by wchmm_fbs().

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

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

Parameters:

	s	[i/o] work area for 2nd pass
	n	[in] hypothesis
	framenum	[in] input frame length

Definition at line 866 of file search_bestfirst_main.c.

void segment_set_last_nword	(	NODE *	hypo,
		RecogProcess *	r
	)

Set the previous word context for the recognition of the next input segment from the current recognition result.

The initial context word will be chosen from the current recognition result skipping transparent word and multiplied words.

Parameters:

	hypo	[in] sentence candidate as a recognition result of current input segment
	r	[in] recognition process instance

Definition at line 904 of file search_bestfirst_main.c.

Referenced by pass2_finalize_on_no_result(), and result_reorder_and_output().

Here is the caller graph for this function:

static void store_result_pass2	(	NODE *	hypo,
		RecogProcess *	r
	)			`[static]`

Save a hypothesis as a recognition result f 2nd pass.

Parameters:

	hypo	[in] hypothesis to save
	r	[in] recognition process instance

Definition at line 1002 of file search_bestfirst_main.c.

Referenced by result_reorder_and_output().

static void result_reorder_and_output	(	NODE **	r_start,
		NODE **	r_bottom,
		int *	r_stacknum,
		int	ncan,
		RecogProcess *	r,
		HTK_Param *	param
	)			`[static]`

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

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.

Additionally, forced alignment for the recognized sentence will be executed here if required.

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
	r	[in] recognition process instance
	param	[in] input parameter

Definition at line 1084 of file search_bestfirst_main.c.

void pass2_finalize_on_no_result	(	RecogProcess *	r,
		boolean	use_1pass_as_final
	)

Post-process of 2nd pass when no result is obtained.

This is a post-process for the 2nd pass which should be called when the 2nd pass has no result. This will occur when the 2nd pass was executed but failed with no sentence candidate, or skipped by an option.

When the 2nd argument is set to TRUE, the result of the 1st pass will be copied as final result of 2nd pass and the recognition status flag is set to SUCCESS. If FALSE, recognition status will be set to FAILED. On sp-segment decoding, the initial hypothesis marker for the next input segment will be set up from the 1st pass result also.

Parameters:

	r	[in] recognition process instance
	use_1pass_as_final	[in] when TRUE the 1st pass result will be used as final recognition result of 2nd pass.

Definition at line 1146 of file search_bestfirst_main.c.

Referenced by j_recognize_stream_core().

void wchmm_fbs	(	HTK_Param *	param,
		RecogProcess *	r,
		int	cate_bgn,
		int	cate_num
	)

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

The cate_bgn and cate_num (third and fourth argument) will have no effect when N-gram is used.

Parameters:

	param	[in] input parameter vector
	r	[i/o] recognition process instance
	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 1225 of file search_bestfirst_main.c.

Referenced by j_recognize_stream_core().

Here is the caller graph for this function:

libjulius/src/search_bestfirst_main.c File Reference

Functions

Detailed Description

Function Documentation