Classes | Defines | Functions

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)    ((l)->active)
#define lextree_lcroot (   l)    ((l)->lcroot)
#define lextree_n_active (   l)    ((l)->n_active)
#define lextree_n_alloc_node (   l)    ((l)->n_alloc_node)
#define lextree_n_lc (   l)    ((l)->n_lc)
#define lextree_n_next_active (   l)    ((l)->n_next_active)
#define lextree_n_node (   l)    ((l)->n_node)
#define lextree_next_active (   l)    ((l)->next_active)
#define lextree_node_composite (   n)    ((n)->composite)
#define lextree_node_frame (   n)    ((n)->frame)
#define lextree_node_prob (   n)    ((n)->prob)
#define lextree_node_rc (   n)    ((n)->rc)
#define lextree_node_ssid (   n)    ((n)->ssid)
#define lextree_node_wid (   n)    ((n)->wid)
#define LEXTREE_OPERATION_FAILURE   0
#define LEXTREE_OPERATION_SUCCESS   1
#define lextree_root (   l)    ((l)->root)
#define lextree_type (   l)    ((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:
kbcoreIn: 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:
lextreeThe 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:
kbcIn: All the necessary knowledge bases
wordprobIn: Words in the tree and their (LM) probabilities
n_wordIn: Size of the wordprob[] array
lcIn: BAD_S3CIPID terminated array of left context CIphones, or NULL if no specific left context
typeIn: 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:
lextreeIn: Lextree being traversed
ci_activeIn/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:
lextreeIn: A lexical tree
dictIn: a dictionary
mdefIn: a model definition
fpA file pointer
fmtfmt=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:
lextreeIn/Out: Lextree being entered
lcIn: Left-context if any (can be BAD_S3CIPID)
frameIn: Frame from which being activated (for the next)
inscoreIn: Incoming score
inhistIn: Incoming history
threshIn: Pruning threshold; incoming scores below this threshold will not enter successfully
kbcIn: 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:
lextreeIn/Out: Lextree with HMMs to be evaluated
kbcIn:
ascrIn: Senone scores (primary and composite)
fIn: Frame in which being invoked
fpIn: 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:
lextreeIn: Its active HMM bestscores are used
bestscrIn: Overall bestscore in current frame
binIn/Out: The histogram bins; caller allocates this array
nbinIn: Size of bin[]
bwIn: 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:
lextreeIn/Out: Propagate scores across HMMs in this lextree
kbcIn: Core knowledge bases
vhIn/Out: Viterbi history structure to be updated with word exits
cfIn: Current frame index
wthIn: 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:
lextreeIn/Out: Propagate scores across HMMs in this lextree
kbcIn: Core knowledge bases
cfIn: Current frame index.
thIn: General (HMM survival) pruning thresh
pthIn: Phone transition pruning threshold
wthIn: Word exit pruning threshold
plIn: 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:
kbcoreIn: Initialized kbcore
lmIn: LM, to decide which set of word list is used
lmnameIn: LM name
istreeUgProbIn: Decide whether LM factoring is used or not
bReportIn: Whether to report the progress so far.
typeIn: 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:
ltreeIn: 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:
lextreeIn: lextree->active is scanned
ssidIn/Out: ssid[s] is set to non-0 if senone sequence ID s is active
comssidIn/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:
ltreeIn: A lexical tree