Data structure of lexical tree. More...
#include <stdio.h>#include <bitvec.h>#include <ngram_model.h>#include <glist.h>#include "s3types.h"#include "hmm.h"#include "tmat.h"#include "vithist.h"#include "s3dict.h"#include "bin_mdef.h"#include "fillpen.h"Go to the source code of this file.
Data Structures | |
| struct | lextree_node_t |
| struct | lextree_lcroot_t |
| struct | lextree_t |
| struct | wordprob_t |
| Generic structure that could be used at any n-gram level. More... | |
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_t * | lextree_init (bin_mdef_t *mdef, tmat_t *tmat, s3dict_t *dict, dict2pid_t *dict2pid, fillpen_t *fp, ngram_model_t *lm, const char *lmname, int32 istreeUgProb, int32 bReport, int32 type) |
| Initialize a lexical tree, also factor language model score through out the tree. | |
| lextree_t * | fillertree_init (bin_mdef_t *mdef, tmat_t *tmat, s3dict_t *dict, dict2pid_t *dict2pid, fillpen_t *fillpen) |
| Initialize a filler tree. | |
| void | lextree_report (lextree_t *ltree) |
| Report the lextree data structure. | |
| void | lextree_free (lextree_t *lextree) |
| void | lextree_utt_end (lextree_t *l) |
| Reset the entire lextree (to the inactive state). | |
| void | lextree_enter (lextree_t *lextree, s3cipid_t lc, int32 frame, int32 inscore, int32 inhist, int32 thresh) |
| Enter root nodes of lextree for given left-context, with given incoming score/history. | |
| void | lextree_active_swap (lextree_t *lextree) |
| Swap the active and next_active lists of the given lextree. | |
| void | lextree_ssid_active (lextree_t *lextree, bitvec_t *ssid, bitvec_t *comssid) |
| Marks the active ssid and composite ssids in the given lextree. | |
| void | lextree_ci_active (lextree_t *lextree, bitvec_t *ci_active) |
| For each active lextree node, mark the corresponding CI phone as active. | |
| int32 | lextree_hmm_eval (lextree_t *lextree, int16 *senscr, int16 *comsen, int32 f, FILE *fp) |
| Evaluate the active HMMs in the given lextree, using the current frame senone scores. | |
| int32 | lextree_hmm_propagate_non_leaves (lextree_t *lextree, int32 cf, int32 th, int32 pth, int32 wth) |
| Propagate the non-leaves nodes of HMMs in the given lextree through to the start of the next frame. | |
| int32 | lextree_hmm_propagate_leaves (lextree_t *lextree, 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. | |
| 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. | |
| void | lextree_dump (lextree_t *lextree, FILE *fp, int32 fmt) |
| For debugging, dump the whole lexical tree. | |
| int32 | num_lextree_links (lextree_t *ltree) |
| Utility function that count the number of links. | |
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.
Definition in file lextree.h.
| 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.)
| lextree | The lexical tree |
Definition at line 1266 of file lextree.c.
References lextree_t::active, lextree_t::n_active, lextree_t::n_next_active, and lextree_t::next_active.
| void lextree_ci_active | ( | lextree_t * | lextree, | |
| bitvec_t * | ci_active | |||
| ) |
For each active lextree node, mark the corresponding CI phone as active.
| lextree | In: Lextree being traversed | |
| ci_active | In/Out: Active/inactive flag for ciphones |
Definition at line 951 of file lextree.c.
References lextree_t::active, lextree_node_t::ci, and lextree_t::n_active.
| void lextree_dump | ( | lextree_t * | lextree, | |
| FILE * | fp, | |||
| int32 | fmt | |||
| ) |
For debugging, dump the whole lexical tree.
| lextree | In: A lexical tree | |
| fp | A file pointer | |
| fmt | fmt=1, Ravi's format, fmt=2, Dot's format |
Definition at line 1069 of file lextree.c.
References lextree_node_t::ci, lextree_t::dict, lextree_t::lcroot, lextree_t::mdef, lextree_t::n_lc, and lextree_t::root.
| void lextree_enter | ( | lextree_t * | lextree, | |
| s3cipid_t | lc, | |||
| int32 | frame, | |||
| int32 | inscore, | |||
| int32 | inhist, | |||
| int32 | thresh | |||
| ) |
Enter root nodes of lextree for given left-context, with given incoming score/history.
| 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 |
Definition at line 1141 of file lextree.c.
References lextree_node_t::children, lextree_node_t::ci, lextree_t::dict, lextree_t::dict2pid, dict2pid_is_composite, get_rc_nssid(), lextree_node_t::hmm, lextree_t::lcroot, dict2pid_t::lrssid, lextree_t::mdef, lextree_t::n_lc, lextree_t::n_next_active, lextree_t::next_active, lextree_node_t::prob, lextree_t::root, xwdssid_t::ssid, lextree_t::tmat, and lextree_node_t::wid.
| int32 lextree_hmm_eval | ( | lextree_t * | lextree, | |
| int16 * | senscr, | |||
| int16 * | comsen, | |||
| 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.
| lextree | In/Out: Lextree with HMMs to be evaluated | |
| senscr | In: Primary senone scores | |
| comsen | In: Composite senone scores | |
| f | In: Frame in which being invoked | |
| fp | In: If not-NULL, dump HMM state (for debugging) |
Definition at line 1279 of file lextree.c.
References lextree_t::active, lextree_t::best, lextree_t::comctx, lextree_t::ctx, lextree_t::dict2pid, lextree_node_t::hmm, hmm_context_set_senscore, lextree_t::mdef, lextree_t::n_active, lextree_node_t::ssid, lextree_t::wbest, and lextree_node_t::wid.
| 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.
| 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 |
Definition at line 1339 of file lextree.c.
References lextree_t::active, BAD_S3SSID, lextree_node_t::hmm, lextree_t::n_active, lextree_node_t::ssid, and lextree_node_t::wid.
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.
| lextree | In/Out: Propagate scores across HMMs in this lextree | |
| vh | In/Out: Viterbi history structure to be updated with word exits | |
| cf | In: Current frame index | |
| wth | In: Word exit pruning threshold |
Definition at line 1575 of file lextree.c.
References lextree_t::active, BAD_S3CIPID, BAD_S3SSID, lextree_t::dict, lextree_t::dict2pid, dict2pid_is_composite, lextree_t::fp, lextree_node_t::hmm, lextree_t::lm, lextree_t::n_active, lextree_node_t::prob, lextree_node_t::rc, lextree_node_t::ssid, lextree_t::type, and lextree_node_t::wid.
| int32 lextree_hmm_propagate_non_leaves | ( | lextree_t * | lextree, | |
| int32 | cf, | |||
| int32 | th, | |||
| int32 | pth, | |||
| int32 | wth | |||
| ) |
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.
| lextree | In/Out: Propagate scores across HMMs in this lextree | |
| cf | In: Current frame index. | |
| th | In: General (HMM survival) pruning thresh | |
| pth | In: Phone transition pruning threshold | |
| wth | In: Word exit pruning threshold |
Definition at line 1390 of file lextree.c.
References lextree_t::active, BAD_S3CIPID, BAD_S3SSID, lextree_node_t::children, lextree_node_t::ci, lextree_t::dict, lextree_t::dict2pid, dict2pid_is_composite, get_rc_nssid(), lextree_node_t::hmm, lextree_t::mdef, lextree_t::n_active, lextree_t::n_alloc_node, lextree_t::n_next_active, xwdssid_t::n_ssid, lextree_t::next_active, lextree_node_t::prob, lextree_node_t::rc, dict2pid_t::rssid, xwdssid_t::ssid, lextree_node_t::ssid, lextree_t::tmat, and lextree_node_t::wid.
| lextree_t* lextree_init | ( | bin_mdef_t * | mdef, | |
| tmat_t * | tmat, | |||
| s3dict_t * | dict, | |||
| dict2pid_t * | dict2pid, | |||
| fillpen_t * | fp, | |||
| ngram_model_t * | lm, | |||
| const 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.
| 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 |
Definition at line 246 of file lextree.c.
References BAD_S3CIPID, lextree_t::dict, lextree_t::dict2pid, lextree_t::fp, lextree_t::lm, lextree_t::mdef, lextree_t::prev_word, wordprob_t::prob, lextree_t::tmat, and wordprob_t::wid.
| void lextree_report | ( | lextree_t * | ltree | ) |
Report the lextree data structure.
| ltree | In: Report a lexical tree |
Definition at line 360 of file lextree.c.
References lextree_t::n_lc, lextree_t::n_node, lextree_t::prev_word, lextree_t::root, and lextree_t::type.
| void lextree_ssid_active | ( | lextree_t * | lextree, | |
| bitvec_t * | ssid, | |||
| bitvec_t * | 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.
| 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 |
Definition at line 966 of file lextree.c.
References lextree_t::active, lextree_node_t::composite, lextree_t::n_active, and lextree_node_t::ssid.
| void lextree_utt_end | ( | lextree_t * | l | ) |
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.
Definition at line 992 of file lextree.c.
References lextree_t::active, lextree_t::dict2pid, dict2pid_is_composite, lextree_t::n_active, lextree_t::n_next_active, and lextree_t::prev_word.
| int32 num_lextree_links | ( | lextree_t * | ltree | ) |
Utility function that count the number of links.
| ltree | In: A lexical tree |
Definition at line 406 of file lextree.c.
References lextree_t::root.
1.6.1