summaryrefslogtreecommitdiffstats
path: root/media/pocketsphinx/src/fsg_search.c
diff options
context:
space:
mode:
authorMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
committerMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
commit5f8de423f190bbb79a62f804151bc24824fa32d8 (patch)
tree10027f336435511475e392454359edea8e25895d /media/pocketsphinx/src/fsg_search.c
parent49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff)
downloadUXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip
Add m-esr52 at 52.6.0
Diffstat (limited to 'media/pocketsphinx/src/fsg_search.c')
-rw-r--r--media/pocketsphinx/src/fsg_search.c1550
1 files changed, 1550 insertions, 0 deletions
diff --git a/media/pocketsphinx/src/fsg_search.c b/media/pocketsphinx/src/fsg_search.c
new file mode 100644
index 000000000..f24a0fb83
--- /dev/null
+++ b/media/pocketsphinx/src/fsg_search.c
@@ -0,0 +1,1550 @@
+/* -*- 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;
+
+}
+