lextree.h File Reference

Data structure of lexical tree. More...

#include <stdio.h>
#include <bitvec.h>
#include <s3types.h>
#include <glist.h>
#include "kbcore.h"
#include "hmm.h"
#include "lm.h"
#include "vithist.h"
#include "ascr.h"
#include "fast_algo_struct.h"
#include "dict.h"
#include "mdef.h"

Go to the source code of this file.

Classes

struct  lextree_node_t
struct  lextree_lcroot_t
struct  lextree_t

Defines

#define LEXTREE_OPERATION_SUCCESS   1
#define LEXTREE_OPERATION_FAILURE   0
#define LEXTREE_TYPE_FILLER   -1
#define LEXTREE_TYPE_UNIGRAM   0
#define LEXTREE_TYPE_BIGRAM   1
#define LEXTREE_TYPE_TRIGRAM   2
#define lextree_node_wid(n)   ((n)->wid)
#define lextree_node_prob(n)   ((n)->prob)
#define lextree_node_ssid(n)   ((n)->ssid)
#define lextree_node_rc(n)   ((n)->rc)
#define lextree_node_composite(n)   ((n)->composite)
#define lextree_node_frame(n)   ((n)->frame)
#define lextree_type(l)   ((l)->type)
#define lextree_root(l)   ((l)->root)
#define lextree_lcroot(l)   ((l)->lcroot)
#define lextree_n_lc(l)   ((l)->n_lc)
#define lextree_n_node(l)   ((l)->n_node)
#define lextree_n_alloc_node(l)   ((l)->n_alloc_node)
#define lextree_active(l)   ((l)->active)
#define lextree_next_active(l)   ((l)->next_active)
#define lextree_n_active(l)   ((l)->n_active)
#define lextree_n_next_active(l)   ((l)->n_next_active)

Functions

lextree_tlextree_init (kbcore_t *kbcore, lm_t *lm, char *lmname, int32 istreeUgProb, int32 bReport, int32 type)
lextree_tfillertree_init (kbcore_t *kbcore)
void lextree_report (lextree_t *ltree)
lextree_tlextree_build (kbcore_t *kbc, wordprob_t *wordprob, int32 n_word, s3cipid_t *lc, int32 type)
void lextree_free (lextree_t *lextree)
void lextree_utt_end (lextree_t *l, kbcore_t *kbc)
void lextree_enter (lextree_t *lextree, s3cipid_t lc, int32 frame, int32 inscore, int32 inhist, int32 thresh, kbcore_t *kbc)
void lextree_active_swap (lextree_t *lextree)
void lextree_ssid_active (lextree_t *lextree, uint8 *ssid, uint8 *comssid)
void lextree_ci_active (lextree_t *lextree, bitvec_t *ci_active)
int32 lextree_hmm_eval (lextree_t *lextree, kbcore_t *kbc, ascr_t *ascr, int32 f, FILE *fp)
int32 lextree_hmm_propagate_non_leaves (lextree_t *lextree, kbcore_t *kbc, int32 cf, int32 th, int32 pth, int32 wth, pl_t *pl)
int32 lextree_hmm_propagate_leaves (lextree_t *lextree, kbcore_t *kbc, vithist_t *vh, int32 cf, int32 wth)
void lextree_hmm_histbin (lextree_t *lextree, int32 bestscr, int32 *bin, int32 nbin, int32 bw)
void lextree_dump (lextree_t *lextree, dict_t *dict, mdef_t *mdef, FILE *fp, int32 fmt)
int32 num_lextree_links (lextree_t *ltree)

Detailed Description

Data structure of lexical tree.

A lextree can be built for a specific history (e.g., for all bigram successors of a given word or trigram successors of a word-pair in a given LM). The history provides a set of left context CIphones (if the final history word has multiple pronunciations; and there is always <sil>). A lextree is usually a set of trees, one for each distinct root model for the given set of words. Furthermore, the root node of each tree can itself actually be a SET of nodes, required by the different left contexts. If there is no history (i.e., the unigram lextree), any CIphone is a potential left-context. But this can explode the number of root nodes. So, the root nodes of the unigram lextree use COMPOSITE models (see dict2pid.h), merging different contexts into one. Similarly, the right context (at the leaves of any lextree) is always unknown. So, all leaf nodes also use composite models. Lextrees are formed by sharing as much of the HMM models as possible (based on senone-seq ID), before having to diverge. But the leaf nodes are always distinct for each word. Finally, each node has a (language model) probability, given its history. It is the max. of the LM probability of all the words reachable from that node. (Strictly speaking, it should be their sum instead of max, but practically it makes little difference.)

ARCHAN : Two weaknesses of the code, 1, when full triphone is expanded, the code loop for all CI index. This is because dict2pid, unlike ctxt_table, doesn't provide a list of triphones 2, for all active node, the code has iterate two times. Rather than once, because of separation of prop_non_leaves and prop_leaves.


Define Documentation

#define lextree_active (  )     ((l)->active)
#define lextree_lcroot (  )     ((l)->lcroot)
#define lextree_n_active (  )     ((l)->n_active)
#define lextree_n_alloc_node (  )     ((l)->n_alloc_node)
#define lextree_n_lc (  )     ((l)->n_lc)
#define lextree_n_next_active (  )     ((l)->n_next_active)
#define lextree_n_node (  )     ((l)->n_node)
#define lextree_next_active (  )     ((l)->next_active)
#define lextree_node_composite (  )     ((n)->composite)
#define lextree_node_frame (  )     ((n)->frame)
#define lextree_node_prob (  )     ((n)->prob)
#define lextree_node_rc (  )     ((n)->rc)
#define lextree_node_ssid (  )     ((n)->ssid)
#define lextree_node_wid (  )     ((n)->wid)
#define LEXTREE_OPERATION_FAILURE   0
#define LEXTREE_OPERATION_SUCCESS   1
#define lextree_root (  )     ((l)->root)
#define lextree_type (  )     ((l)->type)
#define LEXTREE_TYPE_BIGRAM   1
#define LEXTREE_TYPE_FILLER   -1
#define LEXTREE_TYPE_TRIGRAM   2
#define LEXTREE_TYPE_UNIGRAM   0

Function Documentation

lextree_t* fillertree_init ( kbcore_t kbcore  ) 

Initialize a filler tree.

Parameters:
kbcore In: Initialized kbcore
void lextree_active_swap ( lextree_t lextree  ) 

Swap the active and next_active lists of the given lextree. (Usually done at the end of each frame: from the current active list, we've built the next_active list for the next frame, and finally need to make the latter the current active list.)

Parameters:
lextree The lexical tree
lextree_t* lextree_build ( kbcore_t kbc,
wordprob_t wordprob,
int32  n_word,
s3cipid_t lc,
int32  type 
)

Build a lexical tree for the set of words specified in wordprob[] (with their associated LM probabilities). wordprob[] must contain EXACTLY the set of words for which the lextree is to be built, i.e, including alternatives and excluding OOVs. Return value: Pointer to lextree_t structure representing entire lextree.

Parameters:
kbc In: All the necessary knowledge bases
wordprob In: Words in the tree and their (LM) probabilities
n_word In: Size of the wordprob[] array
lc In: BAD_S3CIPID terminated array of left context CIphones, or NULL if no specific left context
type In: Type of lextree
void lextree_ci_active ( lextree_t lextree,
bitvec_t *  ci_active 
)

For each active lextree node, mark the corresponding CI phone as active.

Parameters:
lextree In: Lextree being traversed
ci_active In/Out: Active/inactive flag for ciphones
void lextree_dump ( lextree_t lextree,
dict_t dict,
mdef_t mdef,
FILE *  fp,
int32  fmt 
)

For debugging, dump the whole lexical tree

Parameters:
lextree In: A lexical tree
dict In: a dictionary
mdef In: a model definition
fp A file pointer
fmt fmt=1, Ravi's format, fmt=2, Dot's format
void lextree_enter ( lextree_t lextree,
s3cipid_t  lc,
int32  frame,
int32  inscore,
int32  inhist,
int32  thresh,
kbcore_t kbc 
)

Enter root nodes of lextree for given left-context, with given incoming score/history.

Parameters:
lextree In/Out: Lextree being entered
lc In: Left-context if any (can be BAD_S3CIPID)
frame In: Frame from which being activated (for the next)
inscore In: Incoming score
inhist In: Incoming history
thresh In: Pruning threshold; incoming scores below this threshold will not enter successfully
kbc In: a kbcore, that provided stuffs such as dict and dict2pid
void lextree_free ( lextree_t lextree  ) 
int32 lextree_hmm_eval ( lextree_t lextree,
kbcore_t kbc,
ascr_t ascr,
int32  f,
FILE *  fp 
)

Evaluate the active HMMs in the given lextree, using the current frame senone scores. Return value: The best HMM state score as a result. Note that the current

Parameters:
lextree In/Out: Lextree with HMMs to be evaluated
kbc In:
ascr In: Senone scores (primary and composite)
f In: Frame in which being invoked
fp In: If not-NULL, dump HMM state (for debugging)
void lextree_hmm_histbin ( lextree_t lextree,
int32  bestscr,
int32 *  bin,
int32  nbin,
int32  bw 
)

In order to use histogram pruning, get a histogram of the bestscore of each active HMM in the given lextree. For a given HMM, its bin is determined by: (bestscr - hmm->bestscore) / bw. Invoked right after all active HMMs are evaluated.

Parameters:
lextree In: Its active HMM bestscores are used
bestscr In: Overall bestscore in current frame
bin In/Out: The histogram bins; caller allocates this array
nbin In: Size of bin[]
bw In: Bin width; i.e., score range per bin
int32 lextree_hmm_propagate_leaves ( lextree_t lextree,
kbcore_t kbc,
vithist_t vh,
int32  cf,
int32  wth 
)

Propagate the leaves nodes of HMMs in the given lextree through to the start of the next frame. Called after HMM state scores have been updated. Propagates HMM exit scores through to successor HMM entry states. It should be called right after lextree_hmm_propagate_leaves.

Returns:
SRCH_FAILURE if it failed, SRCH_SUCCESS if it succeeded.
Parameters:
lextree In/Out: Propagate scores across HMMs in this lextree
kbc In: Core knowledge bases
vh In/Out: Viterbi history structure to be updated with word exits
cf In: Current frame index
wth In: Word exit pruning threshold
int32 lextree_hmm_propagate_non_leaves ( lextree_t lextree,
kbcore_t kbc,
int32  cf,
int32  th,
int32  pth,
int32  wth,
pl_t pl 
)

Propagate the non-leaves nodes of HMMs in the given lextree through to the start of the next frame. Called after HMM state scores have been updated. Marks those with "good" scores as active for the next frame.

There is a difference between this part of the code in the composite mode or not in the composite mode. When in composite mode, the code will propagate the leaf node as if it is just a simple node. In that case, composite senone-sequence index will be used.

(Warning! Grandpa is the true daddy! ) In the case when full triphone is expanded, the code will propagate to all possible contexts expansion which is stored in the "children" list of the leaf nodes. Notice, conceptually the list of all possible contexts should be the children of the parent of the leave nodes rather than the children of the leave node. However, physically, the expansion was part of the children list. So, there will be subtle difference in propagation.

Returns:
SRCH_FAILURE if it failed, SRCH_SUCCESS if it succeeded.
Parameters:
lextree In/Out: Propagate scores across HMMs in this lextree
kbc In: Core knowledge bases
cf In: Current frame index.
th In: General (HMM survival) pruning thresh
pth In: Phone transition pruning threshold
wth In: Word exit pruning threshold
pl In: Phoneme lookahead struct
lextree_t* lextree_init ( kbcore_t kbcore,
lm_t lm,
char *  lmname,
int32  istreeUgProb,
int32  bReport,
int32  type 
)

Initialize a lexical tree, also factor language model score through out the tree. Currently only unigram look-ahead is supported.

Parameters:
kbcore In: Initialized kbcore
lm In: LM, to decide which set of word list is used
lmname In: LM name
istreeUgProb In: Decide whether LM factoring is used or not
bReport In: Whether to report the progress so far.
type In: Type of the lexical tree, 0: unigram lextree, 1: 2g, 2: 3g lextree
void lextree_report ( lextree_t ltree  ) 

Report the lextree data structure.

Parameters:
ltree In: Report a lexical tree
void lextree_ssid_active ( lextree_t lextree,
uint8 *  ssid,
uint8 *  comssid 
)

Marks the active ssid and composite ssids in the given lextree. Caller must allocate ssid[] and comssid[]. Caller also responsible for clearing them before calling this function.

Parameters:
lextree In: lextree->active is scanned
ssid In/Out: ssid[s] is set to non-0 if senone sequence ID s is active
comssid In/Out: comssid[s] is set to non-0 if composite senone sequence ID s is active
void lextree_utt_end ( lextree_t l,
kbcore_t kbc 
)

Reset the entire lextree (to the inactive state). I.e., mark each HMM node as inactive, (with lextree_node_t.frame = -1), and the active list size to 0.

int32 num_lextree_links ( lextree_t ltree  ) 

Utility function that count the number of links

Parameters:
ltree In: A lexical tree

Generated on 7 Mar 2010 by  doxygen 1.6.1