fsg_search.c
/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
* Copyright (c) 1999-2004 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 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.
*
* ====================================================================
*
*/
/*
* fsg_search.c -- Search structures for FSM decoding.
*
* **********************************************
* CMU ARPA Speech Project
*
* Copyright (c) 2004 Carnegie Mellon University.
* ALL RIGHTS RESERVED.
* **********************************************
*
* HISTORY
*
* 18-Feb-2004 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
* Started.
*/
/* System headers. */
#include <stdio.h>
#include <string.h>
#include <assert.h>
/* SphinxBase headers. */
#include <sphinxbase/err.h>
#include <sphinxbase/ckd_alloc.h>
#include <sphinxbase/strfuncs.h>
#include <sphinxbase/cmd_ln.h>
/* Local headers. */
#include "pocketsphinx_internal.h"
#include "ps_lattice_internal.h"
#include "fsg_search_internal.h"
#include "fsg_history.h"
#include "fsg_lextree.h"
/* Turn this on for detailed debugging dump */
#define __FSG_DBG__ 0
#define __FSG_DBG_CHAN__ 0
static ps_seg_t *fsg_search_seg_iter(ps_search_t *search);
static ps_lattice_t *fsg_search_lattice(ps_search_t *search);
static int fsg_search_prob(ps_search_t *search);
static ps_searchfuncs_t fsg_funcs = {
/* start: */ fsg_search_start,
/* step: */ fsg_search_step,
/* finish: */ fsg_search_finish,
/* reinit: */ fsg_search_reinit,
/* free: */ fsg_search_free,
/* lattice: */ fsg_search_lattice,
/* hyp: */ fsg_search_hyp,
/* prob: */ fsg_search_prob,
/* seg_iter: */ fsg_search_seg_iter,
};
static int
fsg_search_add_silences(fsg_search_t *fsgs, fsg_model_t *fsg)
{
dict_t *dict;
int32 wid;
int n_sil;
dict = ps_search_dict(fsgs);
/*
* NOTE: Unlike N-Gram search, we do not use explicit start and
* end symbols. This is because the start and end nodes are
* defined in the grammar. We do add silence/filler self-loops to
* all states in order to allow for silence between words and at
* the beginning and end of utterances.
*
* This has some implications for word graph generation, namely,
* that there can (and usually will) be multiple start and end
* states in the word graph. We therefore do add explicit start
* and end nodes to the graph.
*/
/* Add silence self-loops to all states. */
fsg_model_add_silence(fsg, "<sil>", -1,
cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"));
n_sil = 0;
/* Add self-loops for all other fillers. */
for (wid = dict_filler_start(dict); wid < dict_filler_end(dict); ++wid) {
char const *word = dict_wordstr(dict, wid);
if (wid == dict_startwid(dict) || wid == dict_finishwid(dict))
continue;
fsg_model_add_silence(fsg, word, -1,
cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"));
++n_sil;
}
return n_sil;
}
/* Scans the dictionary and check if all words are present. */
static int
fsg_search_check_dict(fsg_search_t *fsgs, fsg_model_t *fsg)
{
dict_t *dict;
int i;
dict = ps_search_dict(fsgs);
for (i = 0; i < fsg_model_n_word(fsg); ++i) {
char const *word;
int32 wid;
word = fsg_model_word_str(fsg, i);
wid = dict_wordid(dict, word);
if (wid == BAD_S3WID) {
E_ERROR("The word '%s' is missing in the dictionary\n", word);
return FALSE;
}
}
return TRUE;
}
static int
fsg_search_add_altpron(fsg_search_t *fsgs, fsg_model_t *fsg)
{
dict_t *dict;
int n_alt, n_word;
int i;
dict = ps_search_dict(fsgs);
/* Scan FSG's vocabulary for words that have alternate pronunciations. */
n_alt = 0;
n_word = fsg_model_n_word(fsg);
for (i = 0; i < n_word; ++i) {
char const *word;
int32 wid;
word = fsg_model_word_str(fsg, i);
wid = dict_wordid(dict, word);
if (wid != BAD_S3WID) {
while ((wid = dict_nextalt(dict, wid)) != BAD_S3WID) {
n_alt += fsg_model_add_alt(fsg, word, dict_wordstr(dict, wid));
}
}
}
E_INFO("Added %d alternate word transitions\n", n_alt);
return n_alt;
}
ps_search_t *
fsg_search_init(const char *name,
fsg_model_t *fsg,
cmd_ln_t *config,
acmod_t *acmod,
dict_t *dict,
dict2pid_t *d2p)
{
fsg_search_t *fsgs = ckd_calloc(1, sizeof(*fsgs));
ps_search_init(ps_search_base(fsgs), &fsg_funcs, PS_SEARCH_TYPE_FSG, name, config, acmod, dict, d2p);
fsgs->fsg = fsg_model_retain(fsg);
/* Initialize HMM context. */
fsgs->hmmctx = hmm_context_init(bin_mdef_n_emit_state(acmod->mdef),
acmod->tmat->tp, NULL, acmod->mdef->sseq);
if (fsgs->hmmctx == NULL) {
ps_search_free(ps_search_base(fsgs));
return NULL;
}
/* Intialize the search history object */
fsgs->history = fsg_history_init(NULL, dict);
fsgs->frame = -1;
/* Get search pruning parameters */
fsgs->beam_factor = 1.0f;
fsgs->beam = fsgs->beam_orig
= (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-beam"))
>> SENSCR_SHIFT;
fsgs->pbeam = fsgs->pbeam_orig
= (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-pbeam"))
>> SENSCR_SHIFT;
fsgs->wbeam = fsgs->wbeam_orig
= (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-wbeam"))
>> SENSCR_SHIFT;
/* LM related weights/penalties */
fsgs->lw = cmd_ln_float32_r(config, "-lw");
fsgs->pip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-pip"))
* fsgs->lw)
>> SENSCR_SHIFT;
fsgs->wip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-wip"))
* fsgs->lw)
>> SENSCR_SHIFT;
/* Acoustic score scale for posterior probabilities. */
fsgs->ascale = 1.0 / cmd_ln_float32_r(config, "-ascale");
E_INFO("FSG(beam: %d, pbeam: %d, wbeam: %d; wip: %d, pip: %d)\n",
fsgs->beam_orig, fsgs->pbeam_orig, fsgs->wbeam_orig,
fsgs->wip, fsgs->pip);
if (!fsg_search_check_dict(fsgs, fsg)) {
fsg_search_free(ps_search_base(fsgs));
return NULL;
}
if (cmd_ln_boolean_r(config, "-fsgusefiller") &&
!fsg_model_has_sil(fsg))
fsg_search_add_silences(fsgs, fsg);
if (cmd_ln_boolean_r(config, "-fsgusealtpron") &&
!fsg_model_has_alt(fsg))
fsg_search_add_altpron(fsgs, fsg);
if (fsg_search_reinit(ps_search_base(fsgs),
ps_search_dict(fsgs),
ps_search_dict2pid(fsgs)) < 0)
{
ps_search_free(ps_search_base(fsgs));
return NULL;
}
ptmr_init(&fsgs->perf);
return ps_search_base(fsgs);
}
void
fsg_search_free(ps_search_t *search)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
double n_speech = (double)fsgs->n_tot_frame
/ cmd_ln_int32_r(ps_search_config(fsgs), "-frate");
E_INFO("TOTAL fsg %.2f CPU %.3f xRT\n",
fsgs->perf.t_tot_cpu,
fsgs->perf.t_tot_cpu / n_speech);
E_INFO("TOTAL fsg %.2f wall %.3f xRT\n",
fsgs->perf.t_tot_elapsed,
fsgs->perf.t_tot_elapsed / n_speech);
ps_search_base_free(search);
fsg_lextree_free(fsgs->lextree);
if (fsgs->history) {
fsg_history_reset(fsgs->history);
fsg_history_set_fsg(fsgs->history, NULL, NULL);
fsg_history_free(fsgs->history);
}
hmm_context_free(fsgs->hmmctx);
fsg_model_free(fsgs->fsg);
ckd_free(fsgs);
}
int
fsg_search_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
/* Free the old lextree */
if (fsgs->lextree)
fsg_lextree_free(fsgs->lextree);
/* Free old dict2pid, dict */
ps_search_base_reinit(search, dict, d2p);
/* Update the number of words (not used by this module though). */
search->n_words = dict_size(dict);
/* Allocate new lextree for the given FSG */
fsgs->lextree = fsg_lextree_init(fsgs->fsg, dict, d2p,
ps_search_acmod(fsgs)->mdef,
fsgs->hmmctx, fsgs->wip, fsgs->pip);
/* Inform the history module of the new fsg */
fsg_history_set_fsg(fsgs->history, fsgs->fsg, dict);
return 0;
}
static void
fsg_search_sen_active(fsg_search_t *fsgs)
{
gnode_t *gn;
fsg_pnode_t *pnode;
hmm_t *hmm;
acmod_clear_active(ps_search_acmod(fsgs));
for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
pnode = (fsg_pnode_t *) gnode_ptr(gn);
hmm = fsg_pnode_hmmptr(pnode);
assert(hmm_frame(hmm) == fsgs->frame);
acmod_activate_hmm(ps_search_acmod(fsgs), hmm);
}
}
/*
* Evaluate all the active HMMs.
* (Executed once per frame.)
*/
static void
fsg_search_hmm_eval(fsg_search_t *fsgs)
{
gnode_t *gn;
fsg_pnode_t *pnode;
hmm_t *hmm;
int32 bestscore;
int32 n, maxhmmpf;
bestscore = WORST_SCORE;
if (!fsgs->pnode_active) {
E_ERROR("Frame %d: No active HMM!!\n", fsgs->frame);
return;
}
for (n = 0, gn = fsgs->pnode_active; gn; gn = gnode_next(gn), n++) {
int32 score;
pnode = (fsg_pnode_t *) gnode_ptr(gn);
hmm = fsg_pnode_hmmptr(pnode);
assert(hmm_frame(hmm) == fsgs->frame);
#if __FSG_DBG__
E_INFO("pnode(%08x) active @frm %5d\n", (int32) pnode,
fsgs->frame);
hmm_dump(hmm, stdout);
#endif
score = hmm_vit_eval(hmm);
#if __FSG_DBG_CHAN__
E_INFO("pnode(%08x) after eval @frm %5d\n",
(int32) pnode, fsgs->frame);
hmm_dump(hmm, stdout);
#endif
if (score BETTER_THAN bestscore)
bestscore = score;
}
#if __FSG_DBG__
E_INFO("[%5d] %6d HMM; bestscr: %11d\n", fsgs->frame, n, bestscore);
#endif
fsgs->n_hmm_eval += n;
/* Adjust beams if #active HMMs larger than absolute threshold */
maxhmmpf = cmd_ln_int32_r(ps_search_config(fsgs), "-maxhmmpf");
if (maxhmmpf != -1 && n > maxhmmpf) {
/*
* Too many HMMs active; reduce the beam factor applied to the default
* beams, but not if the factor is already at a floor (0.1).
*/
if (fsgs->beam_factor > 0.1) { /* Hack!! Hardwired constant 0.1 */
fsgs->beam_factor *= 0.9f; /* Hack!! Hardwired constant 0.9 */
fsgs->beam =
(int32) (fsgs->beam_orig * fsgs->beam_factor);
fsgs->pbeam =
(int32) (fsgs->pbeam_orig * fsgs->beam_factor);
fsgs->wbeam =
(int32) (fsgs->wbeam_orig * fsgs->beam_factor);
}
}
else {
fsgs->beam_factor = 1.0f;
fsgs->beam = fsgs->beam_orig;
fsgs->pbeam = fsgs->pbeam_orig;
fsgs->wbeam = fsgs->wbeam_orig;
}
if (n > fsg_lextree_n_pnode(fsgs->lextree))
E_FATAL("PANIC! Frame %d: #HMM evaluated(%d) > #PNodes(%d)\n",
fsgs->frame, n, fsg_lextree_n_pnode(fsgs->lextree));
fsgs->bestscore = bestscore;
}
static void
fsg_search_pnode_trans(fsg_search_t *fsgs, fsg_pnode_t * pnode)
{
fsg_pnode_t *child;
hmm_t *hmm;
int32 newscore, thresh, nf;
assert(pnode);
assert(!fsg_pnode_leaf(pnode));
nf = fsgs->frame + 1;
thresh = fsgs->bestscore + fsgs->beam;
hmm = fsg_pnode_hmmptr(pnode);
for (child = fsg_pnode_succ(pnode);
child; child = fsg_pnode_sibling(child)) {
newscore = hmm_out_score(hmm) + child->logs2prob;
if ((newscore BETTER_THAN thresh)
&& (newscore BETTER_THAN hmm_in_score(&child->hmm))) {
/* Incoming score > pruning threshold and > target's existing score */
if (hmm_frame(&child->hmm) < nf) {
/* Child node not yet activated; do so */
fsgs->pnode_active_next =
glist_add_ptr(fsgs->pnode_active_next,
(void *) child);
}
hmm_enter(&child->hmm, newscore, hmm_out_history(hmm), nf);
}
}
}
static void
fsg_search_pnode_exit(fsg_search_t *fsgs, fsg_pnode_t * pnode)
{
hmm_t *hmm;
fsg_link_t *fl;
int32 wid;
fsg_pnode_ctxt_t ctxt;
assert(pnode);
assert(fsg_pnode_leaf(pnode));
hmm = fsg_pnode_hmmptr(pnode);
fl = fsg_pnode_fsglink(pnode);
assert(fl);
wid = fsg_link_wid(fl);
assert(wid >= 0);
#if __FSG_DBG__
E_INFO("[%5d] Exit(%08x) %10d(score) %5d(pred)\n",
fsgs->frame, (int32) pnode,
hmm_out_score(hmm), hmm_out_history(hmm));
#endif
/*
* Check if this is filler or single phone word; these do not model right
* context (i.e., the exit score applies to all right contexts).
*/
if (fsg_model_is_filler(fsgs->fsg, wid)
/* FIXME: This might be slow due to repeated calls to dict_to_id(). */
|| (dict_is_single_phone(ps_search_dict(fsgs),
dict_wordid(ps_search_dict(fsgs),
fsg_model_word_str(fsgs->fsg, wid))))) {
/* Create a dummy context structure that applies to all right contexts */
fsg_pnode_add_all_ctxt(&ctxt);
/* Create history table entry for this word exit */
fsg_history_entry_add(fsgs->history,
fl,
fsgs->frame,
hmm_out_score(hmm),
hmm_out_history(hmm),
pnode->ci_ext, ctxt);
}
else {
/* Create history table entry for this word exit */
fsg_history_entry_add(fsgs->history,
fl,
fsgs->frame,
hmm_out_score(hmm),
hmm_out_history(hmm),
pnode->ci_ext, pnode->ctxt);
}
}
/*
* (Beam) prune the just evaluated HMMs, determine which ones remain
* active, which ones transition to successors, which ones exit and
* terminate in their respective destination FSM states.
* (Executed once per frame.)
*/
static void
fsg_search_hmm_prune_prop(fsg_search_t *fsgs)
{
gnode_t *gn;
fsg_pnode_t *pnode;
hmm_t *hmm;
int32 thresh, word_thresh, phone_thresh;
assert(fsgs->pnode_active_next == NULL);
thresh = fsgs->bestscore + fsgs->beam;
phone_thresh = fsgs->bestscore + fsgs->pbeam;
word_thresh = fsgs->bestscore + fsgs->wbeam;
for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
pnode = (fsg_pnode_t *) gnode_ptr(gn);
hmm = fsg_pnode_hmmptr(pnode);
if (hmm_bestscore(hmm) >= thresh) {
/* Keep this HMM active in the next frame */
if (hmm_frame(hmm) == fsgs->frame) {
hmm_frame(hmm) = fsgs->frame + 1;
fsgs->pnode_active_next =
glist_add_ptr(fsgs->pnode_active_next,
(void *) pnode);
}
else {
assert(hmm_frame(hmm) == fsgs->frame + 1);
}
if (!fsg_pnode_leaf(pnode)) {
if (hmm_out_score(hmm) >= phone_thresh) {
/* Transition out of this phone into its children */
fsg_search_pnode_trans(fsgs, pnode);
}
}
else {
if (hmm_out_score(hmm) >= word_thresh) {
/* Transition out of leaf node into destination FSG state */
fsg_search_pnode_exit(fsgs, pnode);
}
}
}
}
}
/*
* Propagate newly created history entries through null transitions.
*/
static void
fsg_search_null_prop(fsg_search_t *fsgs)
{
int32 bpidx, n_entries, thresh, newscore;
fsg_hist_entry_t *hist_entry;
fsg_link_t *l;
int32 s;
fsg_model_t *fsg;
fsg = fsgs->fsg;
thresh = fsgs->bestscore + fsgs->wbeam; /* Which beam really?? */
n_entries = fsg_history_n_entries(fsgs->history);
for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
fsg_arciter_t *itor;
hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
l = fsg_hist_entry_fsglink(hist_entry);
/* Destination FSG state for history entry */
s = l ? fsg_link_to_state(l) : fsg_model_start_state(fsg);
/*
* Check null transitions from d to all other states. (Only need to
* propagate one step, since FSG contains transitive closure of null
* transitions.)
*/
/* Add all links from from_state to dst */
for (itor = fsg_model_arcs(fsg, s); itor;
itor = fsg_arciter_next(itor)) {
fsg_link_t *l = fsg_arciter_get(itor);
/* FIXME: Need to deal with tag transitions somehow. */
if (fsg_link_wid(l) != -1)
continue;
newscore =
fsg_hist_entry_score(hist_entry) +
(fsg_link_logs2prob(l) >> SENSCR_SHIFT);
if (newscore >= thresh) {
fsg_history_entry_add(fsgs->history, l,
fsg_hist_entry_frame(hist_entry),
newscore,
bpidx,
fsg_hist_entry_lc(hist_entry),
fsg_hist_entry_rc(hist_entry));
}
}
}
}
/*
* Perform cross-word transitions; propagate each history entry created in this
* frame to lextree roots attached to the target FSG state for that entry.
*/
static void
fsg_search_word_trans(fsg_search_t *fsgs)
{
int32 bpidx, n_entries;
fsg_hist_entry_t *hist_entry;
fsg_link_t *l;
int32 score, newscore, thresh, nf, d;
fsg_pnode_t *root;
int32 lc, rc;
n_entries = fsg_history_n_entries(fsgs->history);
thresh = fsgs->bestscore + fsgs->beam;
nf = fsgs->frame + 1;
for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
assert(hist_entry);
score = fsg_hist_entry_score(hist_entry);
assert(fsgs->frame == fsg_hist_entry_frame(hist_entry));
l = fsg_hist_entry_fsglink(hist_entry);
/* Destination state for hist_entry */
d = l ? fsg_link_to_state(l) : fsg_model_start_state(fsgs->
fsg);
lc = fsg_hist_entry_lc(hist_entry);
/* Transition to all root nodes attached to state d */
for (root = fsg_lextree_root(fsgs->lextree, d);
root; root = root->sibling) {
rc = root->ci_ext;
if ((root->ctxt.bv[lc >> 5] & (1 << (lc & 0x001f))) &&
(hist_entry->rc.bv[rc >> 5] & (1 << (rc & 0x001f)))) {
/*
* Last CIphone of history entry is in left-context list supported by
* target root node, and
* first CIphone of target root node is in right context list supported
* by history entry;
* So the transition can go ahead (if new score is good enough).
*/
newscore = score + root->logs2prob;
if ((newscore BETTER_THAN thresh)
&& (newscore BETTER_THAN hmm_in_score(&root->hmm))) {
if (hmm_frame(&root->hmm) < nf) {
/* Newly activated node; add to active list */
fsgs->pnode_active_next =
glist_add_ptr(fsgs->pnode_active_next,
(void *) root);
#if __FSG_DBG__
E_INFO
("[%5d] WordTrans bpidx[%d] -> pnode[%08x] (activated)\n",
fsgs->frame, bpidx, (int32) root);
#endif
}
else {
#if __FSG_DBG__
E_INFO
("[%5d] WordTrans bpidx[%d] -> pnode[%08x]\n",
fsgs->frame, bpidx, (int32) root);
#endif
}
hmm_enter(&root->hmm, newscore, bpidx, nf);
}
}
}
}
}
int
fsg_search_step(ps_search_t *search, int frame_idx)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
int16 const *senscr;
acmod_t *acmod = search->acmod;
gnode_t *gn;
fsg_pnode_t *pnode;
hmm_t *hmm;
/* Activate our HMMs for the current frame if need be. */
if (!acmod->compallsen)
fsg_search_sen_active(fsgs);
/* Compute GMM scores for the current frame. */
senscr = acmod_score(acmod, &frame_idx);
fsgs->n_sen_eval += acmod->n_senone_active;
hmm_context_set_senscore(fsgs->hmmctx, senscr);
/* Mark backpointer table for current frame. */
fsgs->bpidx_start = fsg_history_n_entries(fsgs->history);
/* Evaluate all active pnodes (HMMs) */
fsg_search_hmm_eval(fsgs);
/*
* Prune and propagate the HMMs evaluated; create history entries for
* word exits. The words exits are tentative, and may be pruned; make
* the survivors permanent via fsg_history_end_frame().
*/
fsg_search_hmm_prune_prop(fsgs);
fsg_history_end_frame(fsgs->history);
/*
* Propagate new history entries through any null transitions, creating
* new history entries, and then make the survivors permanent.
*/
fsg_search_null_prop(fsgs);
fsg_history_end_frame(fsgs->history);
/*
* Perform cross-word transitions; propagate each history entry across its
* terminating state to the root nodes of the lextree attached to the state.
*/
fsg_search_word_trans(fsgs);
/*
* We've now come full circle, HMM and FSG states have been updated for
* the next frame.
* Update the active lists, deactivate any currently active HMMs that
* did not survive into the next frame
*/
for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
pnode = (fsg_pnode_t *) gnode_ptr(gn);
hmm = fsg_pnode_hmmptr(pnode);
if (hmm_frame(hmm) == fsgs->frame) {
/* This HMM NOT activated for the next frame; reset it */
fsg_psubtree_pnode_deactivate(pnode);
}
else {
assert(hmm_frame(hmm) == (fsgs->frame + 1));
}
}
/* Free the currently active list */
glist_free(fsgs->pnode_active);
/* Make the next-frame active list the current one */
fsgs->pnode_active = fsgs->pnode_active_next;
fsgs->pnode_active_next = NULL;
/* End of this frame; ready for the next */
++fsgs->frame;
return 1;
}
/*
* Set all HMMs to inactive, clear active lists, initialize FSM start
* state to be the only active node.
* (Executed at the start of each utterance.)
*/
int
fsg_search_start(ps_search_t *search)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
int32 silcipid;
fsg_pnode_ctxt_t ctxt;
/* Reset dynamic adjustment factor for beams */
fsgs->beam_factor = 1.0f;
fsgs->beam = fsgs->beam_orig;
fsgs->pbeam = fsgs->pbeam_orig;
fsgs->wbeam = fsgs->wbeam_orig;
silcipid = bin_mdef_ciphone_id(ps_search_acmod(fsgs)->mdef, "SIL");
/* Initialize EVERYTHING to be inactive */
assert(fsgs->pnode_active == NULL);
assert(fsgs->pnode_active_next == NULL);
fsg_history_reset(fsgs->history);
fsg_history_utt_start(fsgs->history);
fsgs->final = FALSE;
/* Dummy context structure that allows all right contexts to use this entry */
fsg_pnode_add_all_ctxt(&ctxt);
/* Create dummy history entry leading to start state */
fsgs->frame = -1;
fsgs->bestscore = 0;
fsg_history_entry_add(fsgs->history,
NULL, -1, 0, -1, silcipid, ctxt);
fsgs->bpidx_start = 0;
/* Propagate dummy history entry through NULL transitions from start state */
fsg_search_null_prop(fsgs);
/* Perform word transitions from this dummy history entry */
fsg_search_word_trans(fsgs);
/* Make the next-frame active list the current one */
fsgs->pnode_active = fsgs->pnode_active_next;
fsgs->pnode_active_next = NULL;
++fsgs->frame;
fsgs->n_hmm_eval = 0;
fsgs->n_sen_eval = 0;
ptmr_reset(&fsgs->perf);
ptmr_start(&fsgs->perf);
return 0;
}
/*
* Cleanup at the end of each utterance.
*/
int
fsg_search_finish(ps_search_t *search)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
gnode_t *gn;
fsg_pnode_t *pnode;
int32 n_hist, cf;
/* Deactivate all nodes in the current and next-frame active lists */
for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
pnode = (fsg_pnode_t *) gnode_ptr(gn);
fsg_psubtree_pnode_deactivate(pnode);
}
for (gn = fsgs->pnode_active_next; gn; gn = gnode_next(gn)) {
pnode = (fsg_pnode_t *) gnode_ptr(gn);
fsg_psubtree_pnode_deactivate(pnode);
}
glist_free(fsgs->pnode_active);
fsgs->pnode_active = NULL;
glist_free(fsgs->pnode_active_next);
fsgs->pnode_active_next = NULL;
fsgs->final = TRUE;
n_hist = fsg_history_n_entries(fsgs->history);
fsgs->n_tot_frame += fsgs->frame;
E_INFO
("%d frames, %d HMMs (%d/fr), %d senones (%d/fr), %d history entries (%d/fr)\n\n",
fsgs->frame, fsgs->n_hmm_eval,
(fsgs->frame > 0) ? fsgs->n_hmm_eval / fsgs->frame : 0,
fsgs->n_sen_eval,
(fsgs->frame > 0) ? fsgs->n_sen_eval / fsgs->frame : 0,
n_hist, (fsgs->frame > 0) ? n_hist / fsgs->frame : 0);
/* Print out some statistics. */
ptmr_stop(&fsgs->perf);
/* This is the number of frames processed. */
cf = ps_search_acmod(fsgs)->output_frame;
if (cf > 0) {
double n_speech = (double) (cf + 1)
/ cmd_ln_int32_r(ps_search_config(fsgs), "-frate");
E_INFO("fsg %.2f CPU %.3f xRT\n",
fsgs->perf.t_cpu, fsgs->perf.t_cpu / n_speech);
E_INFO("fsg %.2f wall %.3f xRT\n",
fsgs->perf.t_elapsed, fsgs->perf.t_elapsed / n_speech);
}
return 0;
}
static int
fsg_search_find_exit(fsg_search_t *fsgs, int frame_idx, int final, int32 *out_score)
{
fsg_hist_entry_t *hist_entry = NULL;
fsg_model_t *fsg;
int bpidx, frm, last_frm, besthist;
int32 bestscore;
if (frame_idx == -1)
frame_idx = fsgs->frame - 1;
last_frm = frm = frame_idx;
/* Scan backwards to find a word exit in frame_idx. */
bpidx = fsg_history_n_entries(fsgs->history) - 1;
while (bpidx > 0) {
hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
if (fsg_hist_entry_frame(hist_entry) <= frame_idx) {
frm = last_frm = fsg_hist_entry_frame(hist_entry);
break;
}
bpidx--;
}
/* No hypothesis (yet). */
if (bpidx <= 0)
return bpidx;
/* Now find best word exit in this frame. */
bestscore = INT_MIN;
besthist = -1;
fsg = fsgs->fsg;
while (frm == last_frm) {
fsg_link_t *fl;
int32 score;
fl = fsg_hist_entry_fsglink(hist_entry);
score = fsg_hist_entry_score(hist_entry);
if (fl == NULL)
break;
/* Prefer final hypothesis */
if (score == bestscore && fsg_link_to_state(fl) == fsg_model_final_state(fsg)) {
besthist = bpidx;
} else if (score BETTER_THAN bestscore) {
/* Only enforce the final state constraint if this is a final hypothesis. */
if ((!final)
|| fsg_link_to_state(fl) == fsg_model_final_state(fsg)) {
bestscore = score;
besthist = bpidx;
}
}
--bpidx;
if (bpidx < 0)
break;
hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
frm = fsg_hist_entry_frame(hist_entry);
}
/* Final state not reached. */
if (besthist == -1) {
E_ERROR("Final result does not match the grammar in frame %d\n", frame_idx);
return -1;
}
/* This here's the one we want. */
if (out_score)
*out_score = bestscore;
return besthist;
}
/* FIXME: Mostly duplicated with ngram_search_bestpath(). */
static ps_latlink_t *
fsg_search_bestpath(ps_search_t *search, int32 *out_score, int backward)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
if (search->last_link == NULL) {
search->last_link = ps_lattice_bestpath(search->dag, NULL,
1.0, fsgs->ascale);
if (search->last_link == NULL)
return NULL;
/* Also calculate betas so we can fill in the posterior
* probability field in the segmentation. */
if (search->post == 0)
search->post = ps_lattice_posterior(search->dag, NULL, fsgs->ascale);
}
if (out_score)
*out_score = search->last_link->path_scr + search->dag->final_node_ascr;
return search->last_link;
}
char const *
fsg_search_hyp(ps_search_t *search, int32 *out_score)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
dict_t *dict = ps_search_dict(search);
char *c;
size_t len;
int bp, bpidx;
/* Get last backpointer table index. */
bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score);
/* No hypothesis (yet). */
if (bpidx <= 0) {
return NULL;
}
/* If bestpath is enabled and the utterance is complete, then run it. */
if (fsgs->bestpath && fsgs->final) {
ps_lattice_t *dag;
ps_latlink_t *link;
if ((dag = fsg_search_lattice(search)) == NULL) {
E_WARN("Failed to obtain the lattice while bestpath enabled\n");
return NULL;
}
if ((link = fsg_search_bestpath(search, out_score, FALSE)) == NULL) {
E_WARN("Failed to find the bestpath in a lattice\n");
return NULL;
}
return ps_lattice_hyp(dag, link);
}
bp = bpidx;
len = 0;
while (bp > 0) {
fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
char const *baseword;
int32 wid;
bp = fsg_hist_entry_pred(hist_entry);
wid = fsg_link_wid(fl);
if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
continue;
baseword = dict_basestr(dict,
dict_wordid(dict,
fsg_model_word_str(fsgs->fsg, wid)));
len += strlen(baseword) + 1;
}
ckd_free(search->hyp_str);
if (len == 0) {
search->hyp_str = NULL;
return search->hyp_str;
}
search->hyp_str = ckd_calloc(1, len);
bp = bpidx;
c = search->hyp_str + len - 1;
while (bp > 0) {
fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
char const *baseword;
int32 wid;
bp = fsg_hist_entry_pred(hist_entry);
wid = fsg_link_wid(fl);
if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
continue;
baseword = dict_basestr(dict,
dict_wordid(dict,
fsg_model_word_str(fsgs->fsg, wid)));
len = strlen(baseword);
c -= len;
memcpy(c, baseword, len);
if (c > search->hyp_str) {
--c;
*c = ' ';
}
}
return search->hyp_str;
}
static void
fsg_seg_bp2itor(ps_seg_t *seg, fsg_hist_entry_t *hist_entry)
{
fsg_search_t *fsgs = (fsg_search_t *)seg->search;
fsg_hist_entry_t *ph = NULL;
int32 bp;
if ((bp = fsg_hist_entry_pred(hist_entry)) >= 0)
ph = fsg_history_entry_get(fsgs->history, bp);
seg->word = fsg_model_word_str(fsgs->fsg, hist_entry->fsglink->wid);
seg->ef = fsg_hist_entry_frame(hist_entry);
seg->sf = ph ? fsg_hist_entry_frame(ph) + 1 : 0;
/* This is kind of silly but it happens for null transitions. */
if (seg->sf > seg->ef) seg->sf = seg->ef;
seg->prob = 0; /* Bogus value... */
/* "Language model" score = transition probability. */
seg->lback = 1;
seg->lscr = fsg_link_logs2prob(hist_entry->fsglink) >> SENSCR_SHIFT;
if (ph) {
/* FIXME: Not sure exactly how cross-word triphones are handled. */
seg->ascr = hist_entry->score - ph->score - seg->lscr;
}
else
seg->ascr = hist_entry->score - seg->lscr;
}
static void
fsg_seg_free(ps_seg_t *seg)
{
fsg_seg_t *itor = (fsg_seg_t *)seg;
ckd_free(itor->hist);
ckd_free(itor);
}
static ps_seg_t *
fsg_seg_next(ps_seg_t *seg)
{
fsg_seg_t *itor = (fsg_seg_t *)seg;
if (++itor->cur == itor->n_hist) {
fsg_seg_free(seg);
return NULL;
}
fsg_seg_bp2itor(seg, itor->hist[itor->cur]);
return seg;
}
static ps_segfuncs_t fsg_segfuncs = {
/* seg_next */ fsg_seg_next,
/* seg_free */ fsg_seg_free
};
static ps_seg_t *
fsg_search_seg_iter(ps_search_t *search)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
fsg_seg_t *itor;
int32 out_score;
int bp, bpidx, cur;
bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, &out_score);
/* No hypothesis (yet). */
if (bpidx <= 0)
return NULL;
/* If bestpath is enabled and the utterance is complete, then run it. */
if (fsgs->bestpath && fsgs->final) {
ps_lattice_t *dag;
ps_latlink_t *link;
if ((dag = fsg_search_lattice(search)) == NULL)
return NULL;
if ((link = fsg_search_bestpath(search, &out_score, TRUE)) == NULL)
return NULL;
return ps_lattice_seg_iter(dag, link, 1.0);
}
/* Calling this an "iterator" is a bit of a misnomer since we have
* to get the entire backtrace in order to produce it. On the
* other hand, all we actually need is the bptbl IDs, and we can
* allocate a fixed-size array of them. */
itor = ckd_calloc(1, sizeof(*itor));
itor->base.vt = &fsg_segfuncs;
itor->base.search = search;
itor->base.lwf = 1.0;
itor->n_hist = 0;
bp = bpidx;
while (bp > 0) {
fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
bp = fsg_hist_entry_pred(hist_entry);
++itor->n_hist;
}
if (itor->n_hist == 0) {
ckd_free(itor);
return NULL;
}
itor->hist = ckd_calloc(itor->n_hist, sizeof(*itor->hist));
cur = itor->n_hist - 1;
bp = bpidx;
while (bp > 0) {
fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
itor->hist[cur] = hist_entry;
bp = fsg_hist_entry_pred(hist_entry);
--cur;
}
/* Fill in relevant fields for first element. */
fsg_seg_bp2itor((ps_seg_t *)itor, itor->hist[0]);
return (ps_seg_t *)itor;
}
static int
fsg_search_prob(ps_search_t *search)
{
fsg_search_t *fsgs = (fsg_search_t *)search;
/* If bestpath is enabled and the utterance is complete, then run it. */
if (fsgs->bestpath && fsgs->final) {
ps_lattice_t *dag;
ps_latlink_t *link;
if ((dag = fsg_search_lattice(search)) == NULL)
return 0;
if ((link = fsg_search_bestpath(search, NULL, TRUE)) == NULL)
return 0;
return search->post;
}
else {
/* FIXME: Give some kind of good estimate here, eventually. */
return 0;
}
}
static ps_latnode_t *
find_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int32 wid, int32 node_id)
{
ps_latnode_t *node;
for (node = dag->nodes; node; node = node->next)
if ((node->sf == sf) && (node->wid == wid) && (node->node_id == node_id))
break;
return node;
}
static ps_latnode_t *
new_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int ef, int32 wid, int32 node_id, int32 ascr)
{
ps_latnode_t *node;
node = find_node(dag, fsg, sf, wid, node_id);
if (node) {
/* Update end frames. */
if (node->lef == -1 || node->lef < ef)
node->lef = ef;
if (node->fef == -1 || node->fef > ef)
node->fef = ef;
/* Update best link score. */
if (ascr BETTER_THAN node->info.best_exit)
node->info.best_exit = ascr;
}
else {
/* New node; link to head of list */
node = listelem_malloc(dag->latnode_alloc);
node->wid = wid;
node->sf = sf;
node->fef = node->lef = ef;
node->reachable = FALSE;
node->entries = NULL;
node->exits = NULL;
node->info.best_exit = ascr;
node->node_id = node_id;
node->next = dag->nodes;
dag->nodes = node;
++dag->n_nodes;
}
return node;
}
static ps_latnode_t *
find_start_node(fsg_search_t *fsgs, ps_lattice_t *dag)
{
ps_latnode_t *node;
glist_t start = NULL;
int nstart = 0;
/* Look for all nodes starting in frame zero with some exits. */
for (node = dag->nodes; node; node = node->next) {
if (node->sf == 0 && node->exits) {
E_INFO("Start node %s.%d:%d:%d\n",
fsg_model_word_str(fsgs->fsg, node->wid),
node->sf, node->fef, node->lef);
start = glist_add_ptr(start, node);
++nstart;
}
}
/* If there was more than one start node candidate, then we need
* to create an artificial start node with epsilon transitions to
* all of them. */
if (nstart == 1) {
node = gnode_ptr(start);
}
else {
gnode_t *st;
int wid;
wid = fsg_model_word_add(fsgs->fsg, "<s>");
if (fsgs->fsg->silwords)
bitvec_set(fsgs->fsg->silwords, wid);
node = new_node(dag, fsgs->fsg, 0, 0, wid, -1, 0);
for (st = start; st; st = gnode_next(st))
ps_lattice_link(dag, node, gnode_ptr(st), 0, 0);
}
glist_free(start);
return node;
}
static ps_latnode_t *
find_end_node(fsg_search_t *fsgs, ps_lattice_t *dag)
{
ps_latnode_t *node;
glist_t end = NULL;
int nend = 0;
/* Look for all nodes ending in last frame with some entries. */
for (node = dag->nodes; node; node = node->next) {
if (node->lef == dag->n_frames - 1 && node->entries) {
E_INFO("End node %s.%d:%d:%d (%d)\n",
fsg_model_word_str(fsgs->fsg, node->wid),
node->sf, node->fef, node->lef, node->info.best_exit);
end = glist_add_ptr(end, node);
++nend;
}
}
if (nend == 1) {
node = gnode_ptr(end);
}
else if (nend == 0) {
ps_latnode_t *last = NULL;
int ef = 0;
/* If there were no end node candidates, then just use the
* node with the last exit frame. */
for (node = dag->nodes; node; node = node->next) {
if (node->lef > ef && node->entries) {
last = node;
ef = node->lef;
}
}
node = last;
if (node)
E_INFO("End node %s.%d:%d:%d (%d)\n",
fsg_model_word_str(fsgs->fsg, node->wid),
node->sf, node->fef, node->lef, node->info.best_exit);
}
else {
/* If there was more than one end node candidate, then we need
* to create an artificial end node with epsilon transitions
* out of all of them. */
gnode_t *st;
int wid;
wid = fsg_model_word_add(fsgs->fsg, "</s>");
if (fsgs->fsg->silwords)
bitvec_set(fsgs->fsg->silwords, wid);
node = new_node(dag, fsgs->fsg, fsgs->frame, fsgs->frame, wid, -1, 0);
/* Use the "best" (in reality it will be the only) exit link
* score from this final node as the link score. */
for (st = end; st; st = gnode_next(st)) {
ps_latnode_t *src = gnode_ptr(st);
ps_lattice_link(dag, src, node, src->info.best_exit, fsgs->frame);
}
}
glist_free(end);
return node;
}
static void
mark_reachable(ps_lattice_t *dag, ps_latnode_t *end)
{
glist_t q;
/* It doesn't matter which order we do this in. */
end->reachable = TRUE;
q = glist_add_ptr(NULL, end);
while (q) {
ps_latnode_t *node = gnode_ptr(q);
latlink_list_t *x;
/* Pop the front of the list. */
q = gnode_free(q, NULL);
/* Expand all its predecessors that haven't been seen yet. */
for (x = node->entries; x; x = x->next) {
ps_latnode_t *next = x->link->from;
if (!next->reachable) {
next->reachable = TRUE;
q = glist_add_ptr(q, next);
}
}
}
}
static ps_lattice_t *
fsg_search_lattice(ps_search_t *search)
{
fsg_search_t *fsgs;
fsg_model_t *fsg;
ps_latnode_t *node;
ps_lattice_t *dag;
int32 i, n;
fsgs = (fsg_search_t *)search;
/* Check to see if a lattice has previously been created over the
* same number of frames, and reuse it if so. */
if (search->dag && search->dag->n_frames == fsgs->frame)
return search->dag;
/* Nope, create a new one. */
ps_lattice_free(search->dag);
search->dag = NULL;
dag = ps_lattice_init_search(search, fsgs->frame);
fsg = fsgs->fsg;
/*
* Each history table entry represents a link in the word graph.
* The set of nodes is determined by the number of unique
* (word,start-frame) pairs in the history table. So we will
* first find all those nodes.
*/
n = fsg_history_n_entries(fsgs->history);
for (i = 0; i < n; ++i) {
fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
int32 ascr;
int sf;
/* Skip null transitions. */
if (fh->fsglink == NULL || fh->fsglink->wid == -1)
continue;
/* Find the start node of this link. */
if (fh->pred) {
fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
/* FIXME: We include the transition score in the lattice
* link score. This is because of the practical
* difficulty of obtaining it separately in bestpath or
* forward-backward search, and because it is essentially
* a unigram probability, so there is no need to treat it
* separately from the acoustic score. However, it's not
* clear that this will actually yield correct results.*/
ascr = fh->score - pfh->score;
sf = pfh->frame + 1;
}
else {
ascr = fh->score;
sf = 0;
}
/*
* Note that although scores are tied to links rather than
* nodes, it's possible that there are no links out of the
* destination node, and thus we need to preserve its score in
* case it turns out to be utterance-final.
*/
new_node(dag, fsg, sf, fh->frame, fh->fsglink->wid, fsg_link_to_state(fh->fsglink), ascr);
}
/*
* Now, we will create links only to nodes that actually exist.
*/
n = fsg_history_n_entries(fsgs->history);
for (i = 0; i < n; ++i) {
fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
fsg_arciter_t *itor;
ps_latnode_t *src, *dest;
int32 ascr;
int sf;
/* Skip null transitions. */
if (fh->fsglink == NULL || fh->fsglink->wid == -1)
continue;
/* Find the start node of this link and calculate its link score. */
if (fh->pred) {
fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
sf = pfh->frame + 1;
ascr = fh->score - pfh->score;
}
else {
ascr = fh->score;
sf = 0;
}
src = find_node(dag, fsg, sf, fh->fsglink->wid, fsg_link_to_state(fh->fsglink));
sf = fh->frame + 1;
for (itor = fsg_model_arcs(fsg, fsg_link_to_state(fh->fsglink));
itor; itor = fsg_arciter_next(itor)) {
fsg_link_t *link = fsg_arciter_get(itor);
/* FIXME: Need to figure out what to do about tag transitions. */
if (link->wid >= 0) {
/*
* For each non-epsilon link following this one, look for a
* matching node in the lattice and link to it.
*/
if ((dest = find_node(dag, fsg, sf, link->wid, fsg_link_to_state(link))) != NULL)
ps_lattice_link(dag, src, dest, ascr, fh->frame);
}
else {
/*
* Transitive closure on nulls has already been done, so we
* just need to look one link forward from them.
*/
fsg_arciter_t *itor2;
/* Add all non-null links out of j. */
for (itor2 = fsg_model_arcs(fsg, fsg_link_to_state(link));
itor2; itor2 = fsg_arciter_next(itor2)) {
fsg_link_t *link = fsg_arciter_get(itor2);
if (link->wid == -1)
continue;
if ((dest = find_node(dag, fsg, sf, link->wid, fsg_link_to_state(link))) != NULL) {
ps_lattice_link(dag, src, dest, ascr, fh->frame);
}
}
}
}
}
/* Figure out which nodes are the start and end nodes. */
if ((dag->start = find_start_node(fsgs, dag)) == NULL) {
E_WARN("Failed to find the start node\n");
goto error_out;
}
if ((dag->end = find_end_node(fsgs, dag)) == NULL) {
E_WARN("Failed to find the end node\n");
goto error_out;
}
E_INFO("lattice start node %s.%d end node %s.%d\n",
fsg_model_word_str(fsg, dag->start->wid), dag->start->sf,
fsg_model_word_str(fsg, dag->end->wid), dag->end->sf);
/* FIXME: Need to calculate final_node_ascr here. */
/*
* Convert word IDs from FSG to dictionary.
*/
for (node = dag->nodes; node; node = node->next) {
node->wid = dict_wordid(dag->search->dict,
fsg_model_word_str(fsg, node->wid));
node->basewid = dict_basewid(dag->search->dict, node->wid);
}
/*
* Now we are done, because the links in the graph are uniquely
* defined by the history table. However we should remove any
* nodes which are not reachable from the end node of the FSG.
* Everything is reachable from the start node by definition.
*/
mark_reachable(dag, dag->end);
ps_lattice_delete_unreachable(dag);
{
int32 silpen, fillpen;
silpen = (int32)(logmath_log(fsg->lmath,
cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"))
* fsg->lw)
>> SENSCR_SHIFT;
fillpen = (int32)(logmath_log(fsg->lmath,
cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"))
* fsg->lw)
>> SENSCR_SHIFT;
ps_lattice_penalize_fillers(dag, silpen, fillpen);
}
search->dag = dag;
return dag;
error_out:
ps_lattice_free(dag);
return NULL;
}
ps_latnode_s::wid
int32 wid
Dictionary word id.
Definition: ps_lattice_internal.h:115
SENSCR_SHIFT
#define SENSCR_SHIFT
Shift count for senone scores.
Definition: hmm.h:73
ps_search_init
void ps_search_init(ps_search_t *search, ps_searchfuncs_t *vt, const char *type, const char *name, cmd_ln_t *config, acmod_t *acmod, dict_t *dict, dict2pid_t *d2p)
Initialize base structure.
Definition: pocketsphinx.c:1371
ps_search_s::dag
ps_lattice_t * dag
Current hypothesis word graph.
Definition: pocketsphinx_internal.h:110
ps_lattice_link
POCKETSPHINX_EXPORT void ps_lattice_link(ps_lattice_t *dag, ps_latnode_t *from, ps_latnode_t *to, int32 score, int32 ef)
Create a directed link between "from" and "to" nodes, but if a link already exists,...
Definition: ps_lattice.c:65
ps_seg_s::sf
frame_idx_t sf
Start frame.
Definition: pocketsphinx_internal.h:182
fsg_pnode_ctxt_t
Definition: fsg_lextree.h:60
fsg_search_s::frame
frame_idx_t frame
Current frame.
Definition: fsg_search_internal.h:90
fsg_search_s::history
struct fsg_history_s * history
For storing the Viterbi search history.
Definition: fsg_search_internal.h:76
fsg_search_s::wbeam
int32 wbeam
Effective beams after applying beam_factor.
Definition: fsg_search_internal.h:87
fsg_lextree_free
void fsg_lextree_free(fsg_lextree_t *lextree)
Free lextrees for an FSG.
Definition: fsg_lextree.c:286
hmm_context_init
hmm_context_t * hmm_context_init(int32 n_emit_state, uint8 **const *tp, int16 const *senscore, uint16 *const *sseq)
Create an HMM context.
Definition: hmm.c:56
pocketsphinx_internal.h
fsg_search_s::pnode_active_next
glist_t pnode_active_next
Those activated for the next frame.
Definition: fsg_search_internal.h:79
ps_latnode_s::exits
latlink_list_t * exits
Links out of this node.
Definition: ps_lattice_internal.h:129
ps_seg_s::vt
ps_segfuncs_t * vt
V-table of seg methods.
Definition: pocketsphinx_internal.h:179
ps_search_s
Base structure for search module.
Definition: pocketsphinx_internal.h:98
acmod_score
const int16 * acmod_score(acmod_t *acmod, int *inout_frame_idx)
Score one frame of data.
Definition: acmod.c:1106
ps_search_s::n_words
int32 n_words
Number of words known to search (may be less than in the dictionary)
Definition: pocketsphinx_internal.h:113
hmm_dump
void hmm_dump(hmm_t *h, FILE *fp)
For debugging, dump the whole HMM out.
Definition: hmm.c:116
ps_lattice_s::search
ps_search_t * search
Search (if generated by search).
Definition: ps_lattice_internal.h:65
ps_seg_s
Base structure for hypothesis segmentation iterator.
Definition: pocketsphinx_internal.h:178
ps_latlink_s::from
struct ps_latnode_s * from
From node.
Definition: ps_lattice_internal.h:97
bin_mdef_s::sseq
uint16 ** sseq
Unique senone sequences (2D array built at load time)
Definition: bin_mdef.h:134
ps_latnode_s::next
struct ps_latnode_s * next
Next node in DAG (no ordering implied)
Definition: ps_lattice_internal.h:133
ps_lattice_bestpath
POCKETSPHINX_EXPORT ps_latlink_t * ps_lattice_bestpath(ps_lattice_t *dag, ngram_model_t *lmset, float32 lwf, float32 ascale)
Do N-Gram based best-path search on a word graph.
Definition: ps_lattice.c:1215
fsg_search_s::lextree
struct fsg_lextree_s * lextree
Lextree structure for the currently active FSG.
Definition: fsg_search_internal.h:74
fsg_pnode_add_all_ctxt
void fsg_pnode_add_all_ctxt(fsg_pnode_ctxt_t *ctxt)
Set all flags on in the given context bitvector.
Definition: fsg_lextree.c:327
fsg_seg_s::hist
fsg_hist_entry_t ** hist
Sequence of history entries.
Definition: fsg_search_internal.h:60
ps_latnode_s::entries
latlink_list_t * entries
Links into this node.
Definition: ps_lattice_internal.h:130
ps_search_base_reinit
void ps_search_base_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p)
Re-initialize base structure with new dictionary.
Definition: pocketsphinx.c:1415
fsg_search_s::pnode_active
glist_t pnode_active
Those active in this frame.
Definition: fsg_search_internal.h:78
latlink_list_s
Linked list of DAG link pointers.
Definition: ps_lattice_internal.h:53
BAD_S3WID
#define BAD_S3WID
Dictionary word id.
Definition: s3types.h:90
ps_lattice_s::final_node_ascr
int32 final_node_ascr
Acoustic score of implicit link exiting final node.
Definition: ps_lattice_internal.h:76
fsg_search_s::final
uint8 final
Decoding is finished for this utterance.
Definition: fsg_search_internal.h:91
ps_seg_s::word
const char * word
Word string (pointer into dictionary hash)
Definition: pocketsphinx_internal.h:181
fsg_hist_entry_s
Definition: fsg_history.h:95
acmod_activate_hmm
void acmod_activate_hmm(acmod_t *acmod, hmm_t *hmm)
Activate senones associated with an HMM.
Definition: acmod.c:1213
fsg_search_s::bpidx_start
int32 bpidx_start
First history entry index this frame.
Definition: fsg_search_internal.h:97
ps_search_s::post
int32 post
Utterance posterior probability.
Definition: pocketsphinx_internal.h:112
dict2pid_t
Building composite triphone (as well as word internal triphones) with the dictionary.
Definition: dict2pid.h:84
ps_seg_s::lscr
int32 lscr
Language model score.
Definition: pocketsphinx_internal.h:185
acmod_s::mdef
bin_mdef_t * mdef
Model definition.
Definition: acmod.h:159
ps_latlink_s
Links between DAG nodes.
Definition: ps_lattice_internal.h:96
ps_lattice_hyp
const char * ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link)
Get hypothesis string after bestpath search.
Definition: ps_lattice.c:830
fsg_search_s::hmmctx
hmm_context_t * hmmctx
HMM context.
Definition: fsg_search_internal.h:71
ps_lattice_s::latnode_alloc
listelem_alloc_t * latnode_alloc
Node allocator for this DAG.
Definition: ps_lattice_internal.h:80
fsg_seg_s::base
ps_seg_t base
Base structure.
Definition: fsg_search_internal.h:59
ps_seg_s::search
ps_search_t * search
Search object from whence this came.
Definition: pocketsphinx_internal.h:180
ps_lattice_penalize_fillers
void ps_lattice_penalize_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen)
Insert penalty for fillers.
Definition: ps_lattice.c:106
ps_lattice_internal.h
hmm_enter
void hmm_enter(hmm_t *h, int32 score, int32 histid, int frame)
Enter an HMM with the given path score and history ID.
Definition: hmm.c:201
ps_latnode_s::reachable
int16 reachable
From.
Definition: ps_lattice_internal.h:121
ps_search_s::hyp_str
char * hyp_str
Current hypothesis string.
Definition: pocketsphinx_internal.h:109
ps_seg_s::prob
int32 prob
Log posterior probability.
Definition: pocketsphinx_internal.h:186
bin_mdef_ciphone_id
int bin_mdef_ciphone_id(bin_mdef_t *m, const char *ciphone)
Context-independent phone lookup.
Definition: bin_mdef.c:690
ps_lattice_posterior
POCKETSPHINX_EXPORT int32 ps_lattice_posterior(ps_lattice_t *dag, ngram_model_t *lmset, float32 ascale)
Calculate link posterior probabilities on a word graph.
Definition: ps_lattice.c:1446
fsg_search_s::beam_orig
int32 beam_orig
Global pruning threshold.
Definition: fsg_search_internal.h:81
fsg_search_s::ascale
float32 ascale
Acoustic score scale for posterior probabilities.
Definition: fsg_search_internal.h:94
ps_latnode_s::basewid
int32 basewid
Dictionary base word id.
Definition: ps_lattice_internal.h:116
ps_seg_s::ef
frame_idx_t ef
End frame.
Definition: pocketsphinx_internal.h:183
ps_lattice_s::n_frames
frame_idx_t n_frames
Number of frames for this utterance.
Definition: ps_lattice_internal.h:74
fsg_psubtree_pnode_deactivate
void fsg_psubtree_pnode_deactivate(fsg_pnode_t *pnode)
Mark the given pnode as inactive (for search).
Definition: fsg_lextree.c:831
ps_lattice_init_search
ps_lattice_t * ps_lattice_init_search(ps_search_t *search, int n_frame)
Construct an empty word graph with reference to a search structure.
Definition: ps_lattice.c:639
dict_size
#define dict_size(d)
Packaged macro access to dictionary members.
Definition: dict.h:151
ps_lattice_seg_iter
ps_seg_t * ps_lattice_seg_iter(ps_lattice_t *dag, ps_latlink_t *link, float32 lwf)
Get hypothesis segmentation iterator after bestpath search.
Definition: ps_lattice.c:1006
ps_lattice_s::end
ps_latnode_t * end
Ending node.
Definition: ps_lattice_internal.h:72
hmm_t
An individual HMM among the HMM search space.
tmat_t::tp
uint8 *** tp
The transition matrices; kept in the same scale as acoustic scores; tp[tmatid][from-state][to-state].
Definition: tmat.h:56
ps_lattice_s::start
ps_latnode_t * start
Starting node.
Definition: ps_lattice_internal.h:71
fsg_search_s::n_sen_eval
int32 n_sen_eval
Total senones evaluated this utt.
Definition: fsg_search_internal.h:102
acmod_s::compallsen
uint8 compallsen
Compute all senones?
Definition: acmod.h:188
ps_search_base_free
void ps_search_base_free(ps_search_t *search)
Free search.
Definition: pocketsphinx.c:1402
ps_latnode_s
DAG nodes.
Definition: ps_lattice_internal.h:113
ps_latnode_s::lef
int32 lef
Last end frame.
Definition: ps_lattice_internal.h:119
ps_searchfuncs_s
V-table for search algorithm.
Definition: pocketsphinx_internal.h:82
ps_search_s::last_link
ps_latlink_t * last_link
Final link in best path.
Definition: pocketsphinx_internal.h:111
fsg_seg_s::n_hist
int16 n_hist
Number of history entries.
Definition: fsg_search_internal.h:61
fsg_lextree_init
fsg_lextree_t * fsg_lextree_init(fsg_model_t *fsg, dict_t *dict, dict2pid_t *d2p, bin_mdef_t *mdef, hmm_context_t *ctx, int32 wip, int32 pip)
Create, initialize, and return a new phonetic lextree for the given FSG.
Definition: fsg_lextree.c:215
fsg_search_s::pbeam_orig
int32 pbeam_orig
Pruning threshold for phone transition.
Definition: fsg_search_internal.h:82
ps_seg_s::ascr
int32 ascr
Acoustic score.
Definition: pocketsphinx_internal.h:184
ps_latnode_s::best_exit
int32 best_exit
Best exit score (used for final nodes only)
Definition: ps_lattice_internal.h:127
ps_lattice_s
Word graph structure used in bestpath/nbest search.
Definition: ps_lattice_internal.h:61
fsg_seg_s
Segmentation "iterator" for FSG history.
Definition: fsg_search_internal.h:58
fsg_search_s::wbeam_orig
int32 wbeam_orig
Pruning threshold for word exit.
Definition: fsg_search_internal.h:83
ps_lattice_s::nodes
ps_latnode_t * nodes
List of all nodes.
Definition: ps_lattice_internal.h:70
fsg_search_s::fsg
fsg_model_t * fsg
FSG model.
Definition: fsg_search_internal.h:73
ps_seg_s::lback
int32 lback
Language model backoff.
Definition: pocketsphinx_internal.h:189
ps_lattice_delete_unreachable
void ps_lattice_delete_unreachable(ps_lattice_t *dag)
Remove nodes marked as unreachable.
Definition: ps_lattice.c:174
acmod_s::lmath
logmath_t * lmath
Log-math computation.
Definition: acmod.h:151
hmm_context_set_senscore
#define hmm_context_set_senscore(ctx, senscr)
Change the senone score array for a context.
Definition: hmm.h:227
dict_t
a structure for a dictionary.
Definition: dict.h:76
hmm_context_free
void hmm_context_free(hmm_context_t *ctx)
Free an HMM context.
Definition: hmm.c:80
fsg_search_s::beam_factor
float32 beam_factor
Dynamic/adaptive factor (<=1) applied to above beams to determine actual effective beams.
Definition: fsg_search_internal.h:84
ps_search_s::dict
dict_t * dict
Pronunciation dictionary.
Definition: pocketsphinx_internal.h:107
ps_latnode_s::fef
int32 fef
First end frame.
Definition: ps_lattice_internal.h:118
fsg_search_s::bestscore
int32 bestscore
For beam pruning.
Definition: fsg_search_internal.h:96
ps_lattice_s::n_nodes
int32 n_nodes
Number of nodes in this lattice.
Definition: ps_lattice_internal.h:75
ps_lattice_free
POCKETSPHINX_EXPORT int ps_lattice_free(ps_lattice_t *dag)
Free a lattice.
Definition: ps_lattice.c:665
dict_wordid
POCKETSPHINX_EXPORT s3wid_t dict_wordid(dict_t *d, const char *word)
Return word id for given word string if present.
Definition: dict.c:399
hmm_vit_eval
int32 hmm_vit_eval(hmm_t *hmm)
Viterbi evaluation of given HMM.
Definition: hmm.c:789
acmod_clear_active
void acmod_clear_active(acmod_t *acmod)
Clear set of active senones.
Definition: acmod.c:1197
fsg_pnode_s
Definition: fsg_lextree.h:79
fsg_seg_s::cur
int16 cur
Current position in hist.
Definition: fsg_search_internal.h:62
BETTER_THAN
#define BETTER_THAN
Is one score better than another?
Definition: hmm.h:95
acmod_s::n_senone_active
int n_senone_active
Number of active GMMs.
Definition: acmod.h:169
acmod_s
Acoustic model structure.
Definition: acmod.h:148
ps_latlink_s::path_scr
int32 path_scr
Best path score from root of DAG.
Definition: ps_lattice_internal.h:101
fsg_search_s
Implementation of FSG search (and "FSG set") structure.
Definition: fsg_search_internal.h:68
ps_segfuncs_s
Definition: pocketsphinx_internal.h:170
ps_latnode_s::sf
frame_idx_t sf
Start frame.
Definition: ps_lattice_internal.h:120
fsg_search_s::n_hmm_eval
int32 n_hmm_eval
Total HMMs evaluated this utt.
Definition: fsg_search_internal.h:101
ps_seg_s::lwf
float32 lwf
Language weight factor (for second-pass searches)
Definition: pocketsphinx_internal.h:191
acmod_s::tmat
tmat_t * tmat
Transition matrices.
Definition: acmod.h:160
ps_latnode_s::node_id
int32 node_id
Node from fsg model, used to map lattice back to model.
Definition: ps_lattice_internal.h:122
fsg_search_s::bestpath
uint8 bestpath
Whether to run bestpath search and confidence annotation at end.
Definition: fsg_search_internal.h:92
ps_search_s::acmod
acmod_t * acmod
Acoustic model.
Definition: pocketsphinx_internal.h:106
fsg_search_s::wip
int32 wip
Language weights.
Definition: fsg_search_internal.h:88
WORST_SCORE
#define WORST_SCORE
Large "bad" score.
Definition: hmm.h:84
fsg_search_s::perf
ptmr_t perf
Performance counter.
Definition: fsg_search_internal.h:104