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.
static LOGPROB	tmpprob
	Temporal work for computing LM likelihood.
static LOGPROB *	iwparray
	Temporal pointer to hold inter-word cache array.
static LOGPROB	wordend_best_score
	Best score of word-end nodes.
static int	wordend_best_node
	Node id of the best wordend nodes.
static TRELLIS_ATOM *	wordend_best_tre
	Trellis word corresponds to above.
static WORD_ID	wordend_best_last_cword
	Last context-aware word of above.
static int	isoid
	Temporal work to hold isolated 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.3

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 167 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 211 of file beam.c. Referenced by bt_current_max(), and print_1pass_result().

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 306 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 416 of file beam.c. Referenced by get_back_trellis_proceed().

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 464 of file beam.c. Referenced by get_back_trellis_proceed().

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 556 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 579 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 598 of file beam.c. Referenced by finalize_1st_pass().

static void clear_tlist (  int  tt  )  [static]

Reset the token space. Parameters: tt  [in] work area id (0 or 1) Definition at line 623 of file beam.c. Referenced by get_back_trellis_proceed().

static void clear_tokens (  int  tt  )  [static]

Clear the active token list. Parameters: tt  [in] work area id of previous frame (0 or 1) Definition at line 641 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 663 of file beam.c. Referenced by get_back_trellis_proceed(), and 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 705 of file beam.c. Referenced by get_back_trellis_proceed(), and 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 750 of file beam.c. Referenced by get_back_trellis_proceed(), and 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 849 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 913 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 983 of file beam.c. Referenced by get_back_trellis_init(), and get_back_trellis_proceed().

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 1247 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 1445 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 1576 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 2317 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 2399 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 2600 of file beam.c. Referenced by main_recognition_loop().

---