/* -*- 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 #include #include /* SphinxBase headers. */ #include #include #include #include /* Local headers. */ #include "pocketsphinx_internal.h" #include "ps_lattice_internal.h" #include "fsg_search_internal.h" #include "fsg_history.h" #include "fsg_lextree.h" #include "dict.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, int32 *out_score); 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 = { /* name: */ "fsg", /* 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, "", -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_WARN("The word '%s' is missing in the dictionary. Trying to create new phoneme \n", word); if (!dict->ngram_g2p_model) { E_ERROR("NO dict->ngram_g2p_model. Aborting.."); return FALSE; } int new_wid = dict_add_g2p_word(dict, word); if (new_wid > 0){ /* Now we also have to add it to dict2pid. */ dict2pid_add_word(ps_search_dict2pid(fsgs), new_wid); } else { E_ERROR("Exiting... \n"); 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(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, 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; } return ps_search_base(fsgs); } void fsg_search_free(ps_search_t *search) { fsg_search_t *fsgs = (fsg_search_t *)search; ps_search_deinit(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; 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; /* 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); 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); return 0; } static int fsg_search_find_exit(fsg_search_t *fsgs, int frame_idx, int final, int32 *out_score, int32* out_is_final) { fsg_hist_entry_t *hist_entry = NULL; fsg_model_t *fsg; int bpidx, frm, last_frm, besthist; int32 bestscore; if (out_is_final) *out_is_final = FALSE; 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; if (out_is_final) { fsg_link_t *fl; hist_entry = fsg_history_entry_get(fsgs->history, besthist); fl = fsg_hist_entry_fsglink(hist_entry); *out_is_final = (fsg_link_to_state(fl) == fsg_model_final_state(fsg)); } 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, int32 *out_is_final) { 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, out_is_final); /* 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, int32 *out_score) { fsg_search_t *fsgs = (fsg_search_t *)search; fsg_seg_t *itor; int bp, bpidx, cur; bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score, NULL); /* 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, ""); 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, ""); 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); } } } } /** * Generate a lattice from FSG search results. * * One might think that this is simply a matter of adding acoustic * scores to the FSG's edges. However, one would be wrong. The * crucial difference here is that the word lattice is acyclic, and it * also contains timing information. */ 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; }