libjulius/src/search_bestfirst_main.c File Reference

The second pass: stack decoding. More...

#include <julius/julius.h>

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

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

The second pass: stack decoding.

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.

Author:: Akinobu Lee

Date:: Thu Sep 08 11:51:12 2005

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

Referenced by put_all_in_stack().

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.

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.

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 926 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 954 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.

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.

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 wb_init ( StackDecode * s ) [static]

Initialize counters fro word enveloping.

Parameters:

[i/o] work area for 2nd pass

Definition at line 730 of file search_bestfirst_main.c.

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

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

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

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

Generated on Tue Dec 18 16:01:24 2007 for Julius by

1.5.4


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	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.
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	wchmm_fbs (HTK_Param param, RecogProcess r, int cate_bgn, int cate_num)
	Main function to perform stack decoding of the 2nd search pass.