julius/beam.c File Reference

The first pass: frame-synchronous beam search. More...

#include <julius.h>

Include dependency graph for beam.c:

Go to the source code of this file.

Defines

#define SD(A)   tindex[tn][A-1]

Index locater for sort_token_*().

#define SCOPY(D, S)   D = S

Content copier for sort_token_*().

#define SVAL(A)   (tlist[tn][tindex[tn][A-1]].score)

Score locater for sort_token_*().

#define STVAL   (tlist[tn][s].score)

Indexed score locater for sort_token_*().

Functions

static void put_atom (TRELLIS_ATOM *atom, WORD_INFO *winfo)

static LOGPROB trace_backptr (WORD_ID wordseq_rt[MAXSEQNUM], int *rt_wordlen, TRELLIS_ATOM *atom, BACKTRELLIS *backtrellis, WORD_INFO *winfo)

Find the best word sequence in the word trellis.

static LOGPROB print_1pass_result (BACKTRELLIS *backtrellis, int framelen, WORD_INFO *winfo)

Output the result of the first pass.

static void bt_current_max (BACKTRELLIS *bt, int t, WORD_INFO *winfo)

static void bt_current_max_word (BACKTRELLIS *bt, int t, WORD_INFO *winfo)

static void malloc_nodes (int n, int ntoken_init, int ntoken_step)

static void expand_tlist ()

static void free_nodes ()

static void clear_tlist (int tt)

static void clear_tokens (int tt)

static TOKENID create_token ()

static void node_assign_token (int node, TOKENID tkid)

Assign token to a node on tree lexicon.

static TOKENID node_exist_token (int tt, int node, WORD_ID wid)

Check if a node holds any token.

static void sort_token_upward (int neednum, int totalnum)

Sort the token space upward by score.

static void sort_token_downward (int neednum, int totalnum)

Sort the token space downward by score.

static void sort_token_no_order (int neednum, int *start, int *end)

Sort the token space to find which tokens to be survived in the beam.

static void init_nodescore (HTK_Param *param, WCHMM_INFO *wchmm)

void get_back_trellis_init (HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis)

Frame synchronous beam search: the fist frame.

boolean get_back_trellis_proceed (int t, HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis)

Frame synchronous beam search: proceed for 2nd frame and later.

void get_back_trellis_end (HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis)

Frame synchronous beam search: last frame.

LOGPROB finalize_1st_pass (BACKTRELLIS *backtrellis, WORD_INFO *winfo, int len)

Finalize the 1st pass.

void get_back_trellis (HTK_Param *param, WCHMM_INFO *wchmm, BACKTRELLIS *backtrellis, LOGPROB *backmax)

Frame synchronous beam search: the main.

Variables

static boolean idc_on

set to TRUE when activating tty progress indicator

static int progout_interval_frame

Local work area to hold the output interval in frames for progressive output.

static TOKEN2 * tlist [2]

Token space to hold all token entities.

static TOKENID * tindex [2]

Token index corresponding to tlist for sort.

static int maxtnum = 0

Allocated number of tokens (will grow).

static int expand_step = 0

Number of tokens to be increased per expansion.

static int tnum [2]

Current number of tokens used in tlist.

static int n_start

Start index of in-beam nodes on tindex.

static int n_end

end index of in-beam nodes on tindex

static int tl

Current work area id (0 or 1, swapped for each frame).

static int tn

Next work area id (0 or 1, swapped for each frame).

static TOKENID * token

Active token list that holds currently assigned tokens for each tree node.

static int totalnodenum

Allocated number of nodes in token.

static TRELLIS_ATOM bos

Special token for beginning-of-sentence.

static boolean nodes_malloced = FALSE

Flag to check if tokens already allocated.

static TRELLIS_ATOM * tre

Local workarea to hold the generated trellis word.

static int node

Temporal work to hold the current node number on the lexicon tree.

static int stid

Temporal worl to specify beginning-of-word nodes on the lexicon tree.

static A_CELL * ac

Temporal work to hold the next states of a node.

static int next_node2

Temporal work to hold the next node.

Detailed Description

The first pass: frame-synchronous beam search.

Author:: Akinobu LEE

Date:: Tue Feb 22 17:00:45 2005

These functions perform a frame-synchronous beam search using a static lexicon tree, as the first pass of Julius/Julian.

When the whole input is already obtained, get_back_trellis() simply does all the processing of the 1st pass. When performing online real-time recognition with concurrent speech input, get_bcak_trellis_init(), get_back_trellis_proceed(), get_back_trellis_end() will be called separately from realtime_1stpass.c according on the basis of input processing.

1-best approximation will be performed for word context approximation, but normal word-pair approximation is also supported.

With word/class N-gram, Julius computes the language score using 1-gram factoring (can be changed to 2-gram factoring if you want). With DFA grammar, Julian can compute the connection constraint of words using the category-pair constraint on the beginning of the words, since Julian makes a per-category tree lexicon.

Revision: 1.10

Definition in file beam.c.

Function Documentation

static void put_atom	(	TRELLIS_ATOM *	atom,
		WORD_INFO *	winfo
	)			`[static]`

Output a trellis word information in text (for debug)

Parameters:

	atom	[in] trellis word to output
	winfo	[in] word dictionary

Definition at line 173 of file beam.c.

Referenced by trace_backptr().

static LOGPROB trace_backptr	(	WORD_ID	wordseq_rt[MAXSEQNUM],
		int *	rt_wordlen,
		TRELLIS_ATOM *	atom,
		BACKTRELLIS *	backtrellis,
		WORD_INFO *	winfo
	)			`[static]`

Find the best word sequence in the word trellis.

This function trace back through the word trellis to the beginning of input, to find the best word sequence. The traceback starting point should be specified as a trellis word.

Parameters:

	wordseq_rt	[out] buffer to store the best word sequence as result
	rt_wordlen	[out] length of wordseq_rt
	atom	[in] a trellis word as the starting point of the traceback
	backtrellis	[in] word trellis structure
	winfo	[in] word dictionary

Returns:: the total N-gram language score of the word sequence.

Definition at line 217 of file beam.c.

Referenced by bt_current_max().

static LOGPROB print_1pass_result	(	BACKTRELLIS *	backtrellis,
		int	framelen,
		WORD_INFO *	winfo
	)			`[static]`

Output the result of the first pass.

This function output the best word sequence on the 1st pass. The last trellis word will be determined by linguistic property or scores from words on the last frame, and trace_backptr() will be called to find the best path from the word. The resulting word sequence will be output as a result of the 1st pass.

The informations of the resulting best word sequence will also be stored to global variables such as pass1_wseq, pass1_wnum, pass1_score. They will be referred on the 2nd pass as a fallback result when the 2nd pass failed with no sentence hypothesis found.

Also, if WORD_GRAPH is defined, this function also calls generate_lattice() to extract word graph in the word trellis.

Parameters:

	backtrellis	[i/o] word trellis structure
	framelen	[in] frame length that has been processed
	winfo	[in] word dictionary

Returns:: the best score of the resulting word sequence on the 1st pass.

Definition at line 312 of file beam.c.

Referenced by finalize_1st_pass().

static void bt_current_max	(	BACKTRELLIS *	bt,
		int	t,
		WORD_INFO *	winfo
	)			`[static]`

Output the current best word sequence ending at a specified time frame in the course of the 1st pass.

Parameters:

	bt	[in] word trellis structure
	t	[in] frame
	winfo	[in] word dictionary

Definition at line 442 of file beam.c.

static void bt_current_max_word	(	BACKTRELLIS *	bt,
		int	t,
		WORD_INFO *	winfo
	)			`[static]`

Output the current best word on a specified time frame in the course of the 1st pass.

Parameters:

	bt	[in] word trellis structure
	t	[in] frame
	winfo	[in] word dictionary

Definition at line 490 of file beam.c.

static void malloc_nodes	(	int	n,
		int	ntoken_init,
		int	ntoken_step
	)			`[static]`

Allocate initial work area for beam search on the 1st pass. If filled while search, they will be expanded on demand.

Parameters:

	n	[in] number of nodes in the tree lexicon
	ntoken_init	[in] number of token space to be allocated at first
	ntoken_step	[in] number of token space to be increased for each expansion

Definition at line 582 of file beam.c.

Referenced by get_back_trellis_init().

static void expand_tlist ( ) [static]

Re-allocate work area for beam search on the 1st pass.

Definition at line 605 of file beam.c.

Referenced by create_token().

static void free_nodes ( ) [static]

Free all the work area for beam search on the 1st pass.

Definition at line 624 of file beam.c.

Referenced by finalize_1st_pass().

static void clear_tlist ( int tt ) [static]

Reset the token space.

Parameters:

[in] work area id (0 or 1)

Definition at line 649 of file beam.c.

static void clear_tokens ( int tt ) [static]

Clear the active token list.

Parameters:

[in] work area id of previous frame (0 or 1)

Definition at line 667 of file beam.c.

Referenced by get_back_trellis_proceed().

static TOKENID create_token ( ) [static]

Assign a new token from token space.

Returns:: the id of the newly assigned token.

Definition at line 689 of file beam.c.

Referenced by init_nodescore().

static void node_assign_token	(	int	node,
		TOKENID	tkid
	)			`[static]`

Assign token to a node on tree lexicon.

Save the token id to the specified node in the active token list. Also saves the link to the node from the token in token space.

If a token already exist on the node, it will be overridden by the new one. If WPAIR is defined, the new token will be simply added to the list of active tokens on the node.

Parameters:

	node	[in] node id on the tree lexicon
	tkid	[in] token id to be assigned

Definition at line 731 of file beam.c.

Referenced by init_nodescore().

static TOKENID node_exist_token	(	int	tt,
		int	node,
		WORD_ID	wid
	)			`[static]`

Check if a node holds any token.

This function checks if a node on the tree lexicon already holds a token.

If WPAIR is defined, a node has multiple tokens according to the previous word context. In this case, only token with the same previous word will be checked.

Parameters:

	tt	[in] work area id (0 or 1)
	node	[in] node id of lexicon tree
	wid	[in] word id of previous word (ignored if WPAIR is not defined)

Returns:: the token id on the node, or TOKENID_UNDEFINED if no token has been assigned in this frame.

Definition at line 776 of file beam.c.

Referenced by init_nodescore().

static void sort_token_upward	(	int	neednum,
		int	totalnum
	)			`[static]`

Sort the token space upward by score.

This function sort the whole token space in upward direction, according to their accumulated score. This function terminates sort as soon as the top neednum tokens has been found.

Parameters:

	neednum	[in] sort until top neednum tokens has been found
	totalnum	[in] total number of assigned tokens in the token space

Definition at line 875 of file beam.c.

Referenced by sort_token_no_order().

static void sort_token_downward	(	int	neednum,
		int	totalnum
	)			`[static]`

Sort the token space downward by score.

This function sort the whole token space in downward direction, according to their accumulated score for hypothesis pruning.

This function terminates sort as soon as the bottom neednum tokens has been found.

Parameters:

	neednum	[in] sort until bottom neednum tokens has been found
	totalnum	[in] total number of assigned tokens in the token space

Definition at line 939 of file beam.c.

Referenced by sort_token_no_order().

static void sort_token_no_order	(	int	neednum,
		int *	start,
		int *	end
	)			`[static]`

Sort the token space to find which tokens to be survived in the beam.

This function sorts the currrent tokens in the token space to find the tokens to be survived in the current frame. Only getting the top neednum tokens is required, so the sort will be terminate just after the top neednum tokens are determined. Actually, either sort_token_upward() or sort_token_downward() will be used depending of the number of needed tokens and total tokens.

Parameters:

	neednum	[in] number of top tokens to be found
	start	[out] start index of the top neednum nodes
	end	[out] end index of the top neednum nodes

Definition at line 1009 of file beam.c.

Referenced by get_back_trellis_init().

static void init_nodescore	(	HTK_Param *	param,
		WCHMM_INFO *	wchmm
	)			`[static]`

Initialize work areas, prepare output probability cache, and set initial hypotheses. The first frame of input parameter should be specified to compute the scores of the initial hypotheses.

Parameters:

	param	[in] input vectors (only the first frame will be used)
	wchmm	[in] tree lexicon

Definition at line 1273 of file beam.c.

Referenced by get_back_trellis_init().

void get_back_trellis_init	(	HTK_Param *	param,
		WCHMM_INFO *	wchmm,
		BACKTRELLIS *	backtrellis
	)

Frame synchronous beam search: the fist frame.

This function will initialize nodes, tokens and the resulting word trellis for the 1st pass, and then compute for the 1st frame by setting the initial hypotheses. For later frames other than the first one, get_back_trellis_proceed() should be called instead.

Parameters:

	param	[in] input vectors (onlyt the first frame will be used)
	wchmm	[in] tree lexicon
	backtrellis	[i/o] word trellis structure (will be initialized)

Definition at line 1477 of file beam.c.

Referenced by get_back_trellis(), RealTimeParam(), and RealTimePipeLine().

boolean get_back_trellis_proceed	(	int	t,
		HTK_Param *	param,
		WCHMM_INFO *	wchmm,
		BACKTRELLIS *	backtrellis
	)

Frame synchronous beam search: proceed for 2nd frame and later.

This is the main function of beam search on the 1st pass. Given a input vector of a frame, it proceeds the computation for the one frame, and store the words survived in the beam width to the word trellis structure. get_back_trellis_init() should be used for the first frame. For detailed procedure, please see the comments in this function.

Parameters:

	t	[in] current frame to be computed in param
	param	[in] input vector structure (only the vector at t will be used)
	wchmm	[in] tree lexicon
	backtrellis	[i/o] word trellis structure to hold the survived words on the t frame.

Returns:: TRUE if processing ended normally, or FALSE if the search was terminated (in case of short pause segmentation in successive decoding mode, or active nodes becomes zero).

Definition at line 1608 of file beam.c.

Referenced by get_back_trellis(), get_back_trellis_end(), RealTimeParam(), and RealTimePipeLine().

void get_back_trellis_end	(	HTK_Param *	param,
		WCHMM_INFO *	wchmm,
		BACKTRELLIS *	backtrellis
	)

Frame synchronous beam search: last frame.

This function should be called at the end of the 1st pass. The last procedure will be done for the (param->samplenum - 1) frame.

Parameters:

	param	[in] input vectors (only param->samplenum is referred)
	wchmm	[in] tree lexicon
	backtrellis	[i/o] word trellis structure (the last survived words will be stored to this)

Definition at line 2363 of file beam.c.

Referenced by get_back_trellis(), RealTimeParam(), and RealTimeTerminate().

LOGPROB finalize_1st_pass	(	BACKTRELLIS *	backtrellis,
		WORD_INFO *	winfo,
		int	len
	)

Finalize the 1st pass.

This function will be called just after get_back_trellis_end() to finalize the 1st pass. It processes the resulting word trellis structure to be accessible from the 2nd pass, and output the best sentence hypothesis by backtracing the word trellis.

Parameters:

	backtrellis	[i/o] word trellis structure (will be reconstructed internally
	winfo	[in] word dictionary
	len	[in] total number of processed frames

Returns:: the maximum score of the best hypothesis, or LOG_ZERO if search failed.

Definition at line 2455 of file beam.c.

Referenced by get_back_trellis(), RealTimeParam(), and RealTimeTerminate().

void get_back_trellis	(	HTK_Param *	param,
		WCHMM_INFO *	wchmm,
		BACKTRELLIS *	backtrellis,
		LOGPROB *	backmax
	)

Frame synchronous beam search: the main.

This function perform the 1st recognition pass of frame-synchronous beam search and output the result. It also stores all the word ends in every input frame to word trellis structure.

This function will be called if the whole input vector is already given to the end. When online recognition, where the 1st pass will be processed in parallel with input, this function will not be used. In that case, functions defined in this file will be directly called from functions in realtime-1stpass.c.

Parameters:

	param	[in] input vectors
	wchmm	[in] tree lexicon
	backtrellis	[out] pointer to structure in which the resulting word trellis data should be stored
	backmax	[out] the maximum score of the 1st pass, or LOG_ZERO if search failed.

Definition at line 2656 of file beam.c.

Referenced by main_recognition_loop().

Generated on Tue Dec 26 12:53:23 2006 for Julian by

1.5.0


Defines
#define	SD(A) tindex[tn][A-1]
	Index locater for sort_token_*().
#define	SCOPY(D, S) D = S
	Content copier for sort_token_*().
#define	SVAL(A) (tlist[tn][tindex[tn][A-1]].score)
	Score locater for sort_token_*().
#define	STVAL (tlist[tn][s].score)
	Indexed score locater for sort_token_*().
Functions
static void	put_atom (TRELLIS_ATOM atom, WORD_INFO winfo)
static LOGPROB	trace_backptr (WORD_ID wordseq_rt[MAXSEQNUM], int rt_wordlen, TRELLIS_ATOM atom, BACKTRELLIS backtrellis, WORD_INFO winfo)
	Find the best word sequence in the word trellis.
static LOGPROB	print_1pass_result (BACKTRELLIS backtrellis, int framelen, WORD_INFO winfo)
	Output the result of the first pass.
static void	bt_current_max (BACKTRELLIS bt, int t, WORD_INFO winfo)
static void	bt_current_max_word (BACKTRELLIS bt, int t, WORD_INFO winfo)
static void	malloc_nodes (int n, int ntoken_init, int ntoken_step)
static void	expand_tlist ()
static void	free_nodes ()
static void	clear_tlist (int tt)
static void	clear_tokens (int tt)
static TOKENID	create_token ()
static void	node_assign_token (int node, TOKENID tkid)
	Assign token to a node on tree lexicon.
static TOKENID	node_exist_token (int tt, int node, WORD_ID wid)
	Check if a node holds any token.
static void	sort_token_upward (int neednum, int totalnum)
	Sort the token space upward by score.
static void	sort_token_downward (int neednum, int totalnum)
	Sort the token space downward by score.
static void	sort_token_no_order (int neednum, int start, int end)
	Sort the token space to find which tokens to be survived in the beam.
static void	init_nodescore (HTK_Param param, WCHMM_INFO wchmm)
void	get_back_trellis_init (HTK_Param param, WCHMM_INFO wchmm, BACKTRELLIS *backtrellis)
	Frame synchronous beam search: the fist frame.
boolean	get_back_trellis_proceed (int t, HTK_Param param, WCHMM_INFO wchmm, BACKTRELLIS *backtrellis)
	Frame synchronous beam search: proceed for 2nd frame and later.
void	get_back_trellis_end (HTK_Param param, WCHMM_INFO wchmm, BACKTRELLIS *backtrellis)
	Frame synchronous beam search: last frame.
LOGPROB	finalize_1st_pass (BACKTRELLIS backtrellis, WORD_INFO winfo, int len)
	Finalize the 1st pass.
void	get_back_trellis (HTK_Param param, WCHMM_INFO wchmm, BACKTRELLIS backtrellis, LOGPROB backmax)
	Frame synchronous beam search: the main.
Variables
static boolean	idc_on
	set to TRUE when activating tty progress indicator
static int	progout_interval_frame
	Local work area to hold the output interval in frames for progressive output.
static TOKEN2 *	tlist [2]
	Token space to hold all token entities.
static TOKENID *	tindex [2]
	Token index corresponding to tlist for sort.
static int	maxtnum = 0
	Allocated number of tokens (will grow).
static int	expand_step = 0
	Number of tokens to be increased per expansion.
static int	tnum [2]
	Current number of tokens used in tlist.
static int	n_start
	Start index of in-beam nodes on tindex.
static int	n_end
	end index of in-beam nodes on tindex
static int	tl
	Current work area id (0 or 1, swapped for each frame).
static int	tn
	Next work area id (0 or 1, swapped for each frame).
static TOKENID *	token
	Active token list that holds currently assigned tokens for each tree node.
static int	totalnodenum
	Allocated number of nodes in token.
static TRELLIS_ATOM	bos
	Special token for beginning-of-sentence.
static boolean	nodes_malloced = FALSE
	Flag to check if tokens already allocated.
static TRELLIS_ATOM *	tre
	Local workarea to hold the generated trellis word.
static int	node
	Temporal work to hold the current node number on the lexicon tree.
static int	stid
	Temporal worl to specify beginning-of-word nodes on the lexicon tree.
static A_CELL *	ac
	Temporal work to hold the next states of a node.
static int	next_node2
	Temporal work to hold the next node.