diff options
Diffstat (limited to 'media/pocketsphinx/src/fsg_search.c')
| -rw-r--r-- | media/pocketsphinx/src/fsg_search.c | 1550 |
1 files changed, 0 insertions, 1550 deletions
diff --git a/media/pocketsphinx/src/fsg_search.c b/media/pocketsphinx/src/fsg_search.c deleted file mode 100644 index f24a0fb83..000000000 --- a/media/pocketsphinx/src/fsg_search.c +++ /dev/null @@ -1,1550 +0,0 @@ -/* -*- 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" -#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, "<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_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, "<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); - } - } - } -} - -/** - * 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; - -} - |