ngram_search.h
Go to the documentation of this file.
/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
* Copyright (c) 2008 Carnegie Mellon University. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* This work was supported in part by funding from the Defense Advanced
* Research Projects Agency and the National Science Foundation of the
* United States of America, and the CMU Sphinx Speech Consortium.
*
* THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
* ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
* NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* ====================================================================
*
*/
#ifndef __NGRAM_SEARCH_H__
#define __NGRAM_SEARCH_H__
/* SphinxBase headers. */
#include <sphinxbase/cmd_ln.h>
#include <sphinxbase/logmath.h>
#include <sphinxbase/ngram_model.h>
#include <sphinxbase/listelem_alloc.h>
#include <sphinxbase/err.h>
/* Local headers. */
#include "pocketsphinx_internal.h"
#include "hmm.h"
typedef struct chan_s {
hmm_t hmm;
struct chan_s *next;
struct chan_s *alt;
int32 ciphone;
union {
int32 penult_phn_wid;
int32 rc_id;
} info;
} chan_t;
typedef struct root_chan_s {
hmm_t hmm;
chan_t *next;
int32 penult_phn_wid;
int32 this_phn_wid;
int16 ciphone;
int16 ci2phone;
} root_chan_t;
typedef struct bptbl_s {
frame_idx_t frame;
uint8 valid;
uint8 refcnt;
int32 wid;
int32 bp;
int32 score;
int32 s_idx;
int32 real_wid;
int32 prev_real_wid;
int16 last_phone;
int16 last2_phone;
} bptbl_t;
typedef struct bptbl_seg_s {
ps_seg_t base;
int32 *bpidx;
int16 n_bpidx;
int16 cur;
} bptbl_seg_t;
/*
* Candidates words for entering their last phones. Cleared and rebuilt in each
* frame.
* NOTE: candidates can only be multi-phone, real dictionary words.
*/
typedef struct lastphn_cand_s {
int32 wid;
int32 score;
int32 bp;
int32 next; /* next candidate starting at the same frame */
} lastphn_cand_t;
/*
* Since the same instance of a word (i.e., <word,start-frame>) reaches its last
* phone several times, we can compute its best BP and LM transition score info
* just the first time and cache it for future occurrences. Structure for such
* a cache.
*/
typedef struct {
int32 sf; /* Start frame */
int32 dscr; /* Delta-score upon entering last phone */
int32 bp; /* Best BP */
} last_ltrans_t;
#define CAND_SF_ALLOCSIZE 32
typedef struct {
int32 bp_ef;
int32 cand;
} cand_sf_t;
/*
* Structure for reorganizing the BP table entries in the current frame according
* to distinct right context ci-phones. Each entry contains the best BP entry for
* a given right context. Each successor word will pick up the correct entry based
* on its first ci-phone.
*/
typedef struct bestbp_rc_s {
int32 score;
int32 path; /* BP table index corresponding to this entry */
int32 lc; /* right most ci-phone of above BP entry word */
} bestbp_rc_t;
#define NO_BP -1
typedef struct ngram_search_stats_s {
int32 n_phone_eval;
int32 n_root_chan_eval;
int32 n_nonroot_chan_eval;
int32 n_last_chan_eval;
int32 n_word_lastchan_eval;
int32 n_lastphn_cand_utt;
int32 n_fwdflat_chan;
int32 n_fwdflat_words;
int32 n_fwdflat_word_transition;
int32 n_senone_active_utt;
} ngram_search_stats_t;
struct ngram_search_s {
ps_search_t base;
ngram_model_t *lmset;
hmm_context_t *hmmctx;
/* Flags to quickly indicate which passes are enabled. */
uint8 fwdtree;
uint8 fwdflat;
uint8 bestpath;
/* State of procesing. */
uint8 done;
/* Allocators */
listelem_alloc_t *chan_alloc;
listelem_alloc_t *root_chan_alloc;
listelem_alloc_t *latnode_alloc;
root_chan_t *root_chan;
int32 n_root_chan_alloc;
int32 n_root_chan;
int32 n_nonroot_chan;
int32 max_nonroot_chan;
root_chan_t *rhmm_1ph;
chan_t **word_chan;
bitvec_t *word_active;
int32 *homophone_set;
int32 *single_phone_wid;
int32 n_1ph_words;
int32 n_1ph_LMwords;
chan_t ***active_chan_list;
int32 n_active_chan[2];
int32 **active_word_list;
int32 n_active_word[2];
/*
* FIXME: Document all of these bits.
*/
lastphn_cand_t *lastphn_cand;
int32 n_lastphn_cand;
last_ltrans_t *last_ltrans; /* one per word */
int32 cand_sf_alloc;
cand_sf_t *cand_sf;
bestbp_rc_t *bestbp_rc;
bptbl_t *bp_table; /* Forward pass lattice */
int32 bpidx; /* First free BPTable entry */
int32 bp_table_size;
int32 *bscore_stack; /* Score stack for all possible right contexts */
int32 bss_head; /* First free BScoreStack entry */
int32 bscore_stack_size;
int32 n_frame_alloc;
int32 n_frame;
int32 *bp_table_idx; /* First BPTable entry for each frame */
int32 *word_lat_idx; /* BPTable index for any word in current frame;
cleared before each frame */
/*
* Flat lexicon (2nd pass) search stuff.
*/
ps_latnode_t **frm_wordlist;
int32 *fwdflat_wordlist;
bitvec_t *expand_word_flag;
int32 *expand_word_list;
int32 n_expand_words;
int32 min_ef_width;
int32 max_sf_win;
float32 fwdflat_fwdtree_lw_ratio;
int32 best_score;
int32 last_phone_best_score;
int32 renormalized;
/*
* DAG (3rd pass) search stuff.
*/
float32 bestpath_fwdtree_lw_ratio;
float32 ascale;
ngram_search_stats_t st;
ptmr_t fwdtree_perf;
ptmr_t fwdflat_perf;
ptmr_t bestpath_perf;
int32 n_tot_frame;
/* A collection of beam widths. */
int32 beam;
int32 dynamic_beam;
int32 pbeam;
int32 wbeam;
int32 lpbeam;
int32 lponlybeam;
int32 fwdflatbeam;
int32 fwdflatwbeam;
int32 fillpen;
int32 silpen;
int32 wip;
int32 nwpen;
int32 pip;
int32 maxwpf;
int32 maxhmmpf;
};
typedef struct ngram_search_s ngram_search_t;
ps_search_t *ngram_search_init(const char *name,
ngram_model_t *lm,
cmd_ln_t *config,
acmod_t *acmod,
dict_t *dict,
dict2pid_t *d2p);
void ngram_search_free(ps_search_t *ngs);
int ngram_search_mark_bptable(ngram_search_t *ngs, int frame_idx);
void ngram_search_save_bp(ngram_search_t *ngs, int frame_idx, int32 w,
int32 score, int32 path, int32 rc);
void ngram_search_alloc_all_rc(ngram_search_t *ngs, int32 w);
void ngram_search_free_all_rc(ngram_search_t *ngs, int32 w);
int ngram_search_find_exit(ngram_search_t *ngs, int frame_idx, int32 *out_best_score, int32 *out_is_final);
char const *ngram_search_bp_hyp(ngram_search_t *ngs, int bpidx);
void ngram_compute_seg_scores(ngram_search_t *ngs, float32 lwf);
ps_lattice_t *ngram_search_lattice(ps_search_t *search);
int32 ngram_search_exit_score(ngram_search_t *ngs, bptbl_t *pbe, int rcphone);
void ngram_search_set_lm(ngram_model_t *lm);
#endif /* __NGRAM_SEARCH_H__ */
chan_s::hmm
hmm_t hmm
Basic HMM structure.
Definition: ngram_search.h:65
pocketsphinx_internal.h
Internal implementation of PocketSphinx decoder.
ngram_search_s::n_frame_alloc
int32 n_frame_alloc
Number of frames allocated in bp_table_idx and friends.
Definition: ngram_search.h:307
bptbl_s::wid
int32 wid
Word index.
Definition: ngram_search.h:113
chan_t
struct chan_s chan_t
Lexical tree node data type.
ngram_search_find_exit
int ngram_search_find_exit(ngram_search_t *ngs, int frame_idx, int32 *out_best_score, int32 *out_is_final)
Find the best word exit for the current frame in the backpointer table.
Definition: ngram_search.c:506
ps_search_s
Base structure for search module.
Definition: pocketsphinx_internal.h:98
ngram_search_lattice
ps_lattice_t * ngram_search_lattice(ps_search_t *search)
Construct a word lattice from the current hypothesis.
Definition: ngram_search.c:1218
ngram_search_s::n_nonroot_chan
int32 n_nonroot_chan
Number of valid non-root channels.
Definition: ngram_search.h:234
ngram_search_set_lm
void ngram_search_set_lm(ngram_model_t *lm)
Sets the global language model.
Definition: ngram_search.c:1406
root_chan_s::next
chan_t * next
first descendant of this channel
Definition: ngram_search.h:94
ngram_search_s::chan_alloc
listelem_alloc_t * chan_alloc
For chan_t.
Definition: ngram_search.h:211
hmm_t
An individual HMM among the HMM search space.
bptbl_s::frame
frame_idx_t frame
start or end frame
Definition: ngram_search.h:110
root_chan_t
struct root_chan_s root_chan_t
Lexical tree node data type for the first phone (root) of each dynamic HMM tree structure.
ngram_search_s::hmmctx
hmm_context_t * hmmctx
HMM context.
Definition: ngram_search.h:200
bptbl_s::last2_phone
int16 last2_phone
next-to-last phone of this word
Definition: ngram_search.h:120
ngram_search_free_all_rc
void ngram_search_free_all_rc(ngram_search_t *ngs, int32 w)
Allocate last phone channels for all possible right contexts for word w.
Definition: ngram_search.c:650
ngram_search_s::word_active
bitvec_t * word_active
array of active flags for all words.
Definition: ngram_search.h:247
bptbl_seg_t
struct bptbl_seg_s bptbl_seg_t
Segmentation "iterator" for backpointer table results.
ngram_search_save_bp
void ngram_search_save_bp(ngram_search_t *ngs, int frame_idx, int32 w, int32 score, int32 path, int32 rc)
Enter a word in the backpointer table.
Definition: ngram_search.c:383
ngram_search_alloc_all_rc
void ngram_search_alloc_all_rc(ngram_search_t *ngs, int32 w)
Allocate last phone channels for all possible right contexts for word w.
Definition: ngram_search.c:601
hmm.h
Implementation of HMM base structure.
cand_sf_t
Definition: ngram_search.h:158
root_chan_s::ciphone
int16 ciphone
first ciphone of this node; all words rooted at this node begin with this ciphone ...
Definition: ngram_search.h:100
ngram_search_s::active_word_list
int32 ** active_word_list
Array of active multi-phone words for current and next frame.
Definition: ngram_search.h:287
chan_s::next
struct chan_s * next
first descendant of this channel; or, in the case of the last phone of a word, the next alternative r...
Definition: ngram_search.h:68
ngram_search_stats_s
Various statistics for profiling.
Definition: ngram_search.h:180
ngram_search_s::single_phone_wid
int32 * single_phone_wid
list of single-phone word ids
Definition: ngram_search.h:264
ngram_search_s::n_root_chan_alloc
int32 n_root_chan_alloc
Number of root_chan allocated.
Definition: ngram_search.h:232
root_chan_s::ci2phone
int16 ci2phone
second ciphone of this node; one root HMM for each unique right context
Definition: ngram_search.h:102
bptbl_s::bp
int32 bp
Back Pointer.
Definition: ngram_search.h:114
chan_s::penult_phn_wid
int32 penult_phn_wid
list of words whose last phone follows this one; this field indicates the first of the list; the rest...
Definition: ngram_search.h:75
last_ltrans_t
Definition: ngram_search.h:151
chan_s::rc_id
int32 rc_id
right-context id for last phone of words
Definition: ngram_search.h:79
ngram_search_s
N-Gram search module structure.
Definition: ngram_search.h:197
ngram_search_mark_bptable
int ngram_search_mark_bptable(ngram_search_t *ngs, int frame_idx)
Record the current frame&#39;s index in the backpointer table.
Definition: ngram_search.c:329
ngram_search_s::max_nonroot_chan
int32 max_nonroot_chan
Maximum possible number of non-root channels.
Definition: ngram_search.h:235
ngram_search_s::last_phone_best_score
int32 last_phone_best_score
Best Viterbi path score for last phone.
Definition: ngram_search.h:326
bptbl_s::real_wid
int32 real_wid
wid of this or latest predecessor real word
Definition: ngram_search.h:117
ngram_search_s::rhmm_1ph
root_chan_t * rhmm_1ph
Root HMMs for single-phone words.
Definition: ngram_search.h:236
ngram_search_free
void ngram_search_free(ps_search_t *ngs)
Finalize the N-Gram search module.
Definition: ngram_search.c:289
bptbl_s::prev_real_wid
int32 prev_real_wid
wid of second-last real word
Definition: ngram_search.h:118
ngram_search_s::latnode_alloc
listelem_alloc_t * latnode_alloc
For latnode_t.
Definition: ngram_search.h:213
hmm_context_t
Shared information between a set of HMMs.
bptbl_seg_s
Segmentation "iterator" for backpointer table results.
Definition: ngram_search.h:126
bptbl_s::refcnt
uint8 refcnt
Reference count (number of successors)
Definition: ngram_search.h:112
ngram_search_s::frm_wordlist
ps_latnode_t ** frm_wordlist
List of active words in each frame.
Definition: ngram_search.h:316
ps_latnode_s
DAG nodes.
Definition: ps_lattice_internal.h:113
root_chan_s
Lexical tree node data type for the first phone (root) of each dynamic HMM tree structure.
Definition: ngram_search.h:90
chan_s
Lexical tree node data type.
Definition: ngram_search.h:64
root_chan_s::hmm
hmm_t hmm
Basic HMM structure.
Definition: ngram_search.h:91
root_chan_s::this_phn_wid
int32 this_phn_wid
list of words consisting of this single phone; actually the first of the list, like penult_phn_wid; -...
Definition: ngram_search.h:97
ngram_search_bp_hyp
char const * ngram_search_bp_hyp(ngram_search_t *ngs, int bpidx)
Backtrace from a given backpointer index to obtain a word hypothesis.
Definition: ngram_search.c:553
bptbl_seg_s::cur
int16 cur
Current position in bpidx.
Definition: ngram_search.h:130
ngram_search_s::active_chan_list
chan_t *** active_chan_list
Array of active channels for current and next frame.
Definition: ngram_search.h:275
dict_t
a structure for a dictionary.
Definition: dict.h:76
chan_s::alt
struct chan_s * alt
sibling; i.e., next descendant of parent HMM
Definition: ngram_search.h:71
ps_lattice_s
Word graph structure used in bestpath/nbest search.
Definition: ps_lattice_internal.h:61
bptbl_t
struct bptbl_s bptbl_t
Back pointer table (forward pass lattice; actually a tree)
bptbl_seg_s::n_bpidx
int16 n_bpidx
Number of backpointer IDs.
Definition: ngram_search.h:129
ngram_search_s::best_score
int32 best_score
Best Viterbi path score.
Definition: ngram_search.h:325
bptbl_s
Back pointer table (forward pass lattice; actually a tree)
Definition: ngram_search.h:109
ngram_search_s::n_1ph_LMwords
int32 n_1ph_LMwords
Number single phone dict words also in LM; these come first in single_phone_wid.
Definition: ngram_search.h:266
ngram_compute_seg_scores
void ngram_compute_seg_scores(ngram_search_t *ngs, float32 lwf)
Compute language and acoustic scores for backpointer table entries.
ngram_search_s::root_chan
root_chan_t * root_chan
Search structure of HMM instances.
Definition: ngram_search.h:231
ngram_search_init
ps_search_t * ngram_search_init(const char *name, ngram_model_t *lm, cmd_ln_t *config, acmod_t *acmod, dict_t *dict, dict2pid_t *d2p)
Initialize the N-Gram search module.
Definition: ngram_search.c:140
ngram_search_exit_score
int32 ngram_search_exit_score(ngram_search_t *ngs, bptbl_t *pbe, int rcphone)
Get the exit score for a backpointer entry with a given right context.
Definition: ngram_search.c:663
bptbl_s::s_idx
int32 s_idx
Start of BScoreStack for various right contexts.
Definition: ngram_search.h:116
frame_idx_t
int32 frame_idx_t
Type for frame index values.
Definition: hmm.h:64
ngram_search_s::n_frame
int32 n_frame
Number of frames actually present.
Definition: ngram_search.h:308
ngram_search_s::lmset
ngram_model_t * lmset
Set of language models.
Definition: ngram_search.h:199
bptbl_s::valid
uint8 valid
For absolute pruning.
Definition: ngram_search.h:111
ngram_search_s::n_1ph_words
int32 n_1ph_words
Number single phone words in dict (total)
Definition: ngram_search.h:265
ngram_search_s::root_chan_alloc
listelem_alloc_t * root_chan_alloc
For root_chan_t.
Definition: ngram_search.h:212
chan_s::ciphone
int32 ciphone
ciphone for this node
Definition: ngram_search.h:73
bptbl_seg_s::bpidx
int32 * bpidx
Sequence of backpointer IDs.
Definition: ngram_search.h:128
ngram_search_s::st
ngram_search_stats_t st
Various statistics for profiling.
Definition: ngram_search.h:335
ngram_search_s::word_chan
chan_t ** word_chan
Channels associated with a given word (only used for right contexts, single-phone words in fwdtree se...
Definition: ngram_search.h:246
ngram_search_s::fwdflat_wordlist
int32 * fwdflat_wordlist
List of active word IDs for utterance.
Definition: ngram_search.h:317
bptbl_s::score
int32 score
Score (best among all right contexts)
Definition: ngram_search.h:115
bestbp_rc_s
Definition: ngram_search.h:169
ngram_search_s::n_root_chan
int32 n_root_chan
Number of valid root_chan.
Definition: ngram_search.h:233
ps_seg_s
Base structure for hypothesis segmentation iterator.
Definition: pocketsphinx_internal.h:178
ngram_search_s::homophone_set
int32 * homophone_set
Each node in the HMM tree structure may point to a set of words whose last phone would follow that no...
Definition: ngram_search.h:263
bptbl_seg_s::base
ps_seg_t base
Base structure.
Definition: ngram_search.h:127
ngram_search_s::ascale
float32 ascale
Acoustic score scale for posterior probabilities.
Definition: ngram_search.h:333
acmod_s
Acoustic model structure.
Definition: acmod.h:148
dict2pid_t
Building composite triphone (as well as word internal triphones) with the dictionary.
Definition: dict2pid.h:84
lastphn_cand_s
Definition: ngram_search.h:138
ngram_search_stats_t
struct ngram_search_stats_s ngram_search_stats_t
Various statistics for profiling.
bptbl_s::last_phone
int16 last_phone
last phone of this word
Definition: ngram_search.h:119