diff options
Diffstat (limited to 'media/pocketsphinx/src/ngram_search.c')
| -rw-r--r-- | media/pocketsphinx/src/ngram_search.c | 1409 |
1 files changed, 1409 insertions, 0 deletions
diff --git a/media/pocketsphinx/src/ngram_search.c b/media/pocketsphinx/src/ngram_search.c new file mode 100644 index 000000000..47e488c3a --- /dev/null +++ b/media/pocketsphinx/src/ngram_search.c @@ -0,0 +1,1409 @@ +/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */ +/* ==================================================================== + * Copyright (c) 2008 Carnegie Mellon University. All rights + * reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * This work was supported in part by funding from the Defense Advanced + * Research Projects Agency and the National Science Foundation of the + * United States of America, and the CMU Sphinx Speech Consortium. + * + * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND + * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY + * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * ==================================================================== + * + */ + +/** + * @file ngram_search.c N-Gram based multi-pass search ("FBS") + */ + +/* System headers. */ +#include <string.h> +#include <assert.h> + +/* SphinxBase headers. */ +#include <sphinxbase/ckd_alloc.h> +#include <sphinxbase/listelem_alloc.h> +#include <sphinxbase/err.h> + +/* Local headers. */ +#include "pocketsphinx_internal.h" +#include "ps_lattice_internal.h" +#include "ngram_search.h" +#include "ngram_search_fwdtree.h" +#include "ngram_search_fwdflat.h" + +static int ngram_search_start(ps_search_t *search); +static int ngram_search_step(ps_search_t *search, int frame_idx); +static int ngram_search_finish(ps_search_t *search); +static int ngram_search_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p); +static char const *ngram_search_hyp(ps_search_t *search, int32 *out_score, int32 *out_is_final); +static int32 ngram_search_prob(ps_search_t *search); +static ps_seg_t *ngram_search_seg_iter(ps_search_t *search, int32 *out_score); + +static ps_searchfuncs_t ngram_funcs = { + /* name: */ "ngram", + /* start: */ ngram_search_start, + /* step: */ ngram_search_step, + /* finish: */ ngram_search_finish, + /* reinit: */ ngram_search_reinit, + /* free: */ ngram_search_free, + /* lattice: */ ngram_search_lattice, + /* hyp: */ ngram_search_hyp, + /* prob: */ ngram_search_prob, + /* seg_iter: */ ngram_search_seg_iter, +}; + +static ngram_model_t *default_lm; + +static void +ngram_search_update_widmap(ngram_search_t *ngs) +{ + char const **words; + int32 i, n_words; + + /* It's okay to include fillers since they won't be in the LM */ + n_words = ps_search_n_words(ngs); + words = (char const**)ckd_calloc(n_words, sizeof(*words)); + /* This will include alternates, again, that's okay since they aren't in the LM */ + for (i = 0; i < n_words; ++i) + words[i] = dict_wordstr(ps_search_dict(ngs), i); + ngram_model_set_map_words(ngs->lmset, words, n_words); + ckd_free(words); +} + +static void +ngram_search_calc_beams(ngram_search_t *ngs) +{ + cmd_ln_t *config; + acmod_t *acmod; + + config = ps_search_config(ngs); + acmod = ps_search_acmod(ngs); + + /* Log beam widths. */ + ngs->beam = logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-beam"))>>SENSCR_SHIFT; + ngs->wbeam = logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-wbeam"))>>SENSCR_SHIFT; + ngs->pbeam = logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-pbeam"))>>SENSCR_SHIFT; + ngs->lpbeam = logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-lpbeam"))>>SENSCR_SHIFT; + ngs->lponlybeam = logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-lponlybeam"))>>SENSCR_SHIFT; + ngs->fwdflatbeam = logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-fwdflatbeam"))>>SENSCR_SHIFT; + ngs->fwdflatwbeam = logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-fwdflatwbeam"))>>SENSCR_SHIFT; + + /* Absolute pruning parameters. */ + ngs->maxwpf = cmd_ln_int32_r(config, "-maxwpf"); + ngs->maxhmmpf = cmd_ln_int32_r(config, "-maxhmmpf"); + + /* Various penalties which may or may not be useful. */ + ngs->wip = logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-wip")) >>SENSCR_SHIFT; + ngs->nwpen = logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-nwpen")) >>SENSCR_SHIFT; + ngs->pip = logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-pip")) >>SENSCR_SHIFT; + ngs->silpen = ngs->pip + + (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-silprob"))>>SENSCR_SHIFT); + ngs->fillpen = ngs->pip + + (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-fillprob"))>>SENSCR_SHIFT); + + /* Language weight ratios for fwdflat and bestpath search. */ + ngs->fwdflat_fwdtree_lw_ratio = + cmd_ln_float32_r(config, "-fwdflatlw") + / cmd_ln_float32_r(config, "-lw"); + ngs->bestpath_fwdtree_lw_ratio = + cmd_ln_float32_r(config, "-bestpathlw") + / cmd_ln_float32_r(config, "-lw"); + + /* Acoustic score scale for posterior probabilities. */ + ngs->ascale = 1.0 / cmd_ln_float32_r(config, "-ascale"); +} + +ps_search_t * +ngram_search_init(ngram_model_t *lm, + cmd_ln_t *config, + acmod_t *acmod, + dict_t *dict, + dict2pid_t *d2p) +{ + ngram_search_t *ngs; + static char *lmname = "default"; + + /* Make the acmod's feature buffer growable if we are doing two-pass + * search. */ + acmod_set_grow(acmod, cmd_ln_boolean_r(config, "-fwdflat") && + cmd_ln_boolean_r(config, "-fwdtree")); + + ngs = ckd_calloc(1, sizeof(*ngs)); + ps_search_init(&ngs->base, &ngram_funcs, config, acmod, dict, d2p); + ngs->hmmctx = hmm_context_init(bin_mdef_n_emit_state(acmod->mdef), + acmod->tmat->tp, NULL, acmod->mdef->sseq); + if (ngs->hmmctx == NULL) { + ps_search_free(ps_search_base(ngs)); + return NULL; + } + ngs->chan_alloc = listelem_alloc_init(sizeof(chan_t)); + ngs->root_chan_alloc = listelem_alloc_init(sizeof(root_chan_t)); + ngs->latnode_alloc = listelem_alloc_init(sizeof(ps_latnode_t)); + + /* Calculate various beam widths and such. */ + ngram_search_calc_beams(ngs); + + /* Allocate a billion different tables for stuff. */ + ngs->word_chan = ckd_calloc(dict_size(dict), + sizeof(*ngs->word_chan)); + ngs->word_lat_idx = ckd_calloc(dict_size(dict), + sizeof(*ngs->word_lat_idx)); + ngs->word_active = bitvec_alloc(dict_size(dict)); + ngs->last_ltrans = ckd_calloc(dict_size(dict), + sizeof(*ngs->last_ltrans)); + + /* FIXME: All these structures need to be made dynamic with + * garbage collection. */ + ngs->bp_table_size = cmd_ln_int32_r(config, "-latsize"); + ngs->bp_table = ckd_calloc(ngs->bp_table_size, + sizeof(*ngs->bp_table)); + /* FIXME: This thing is frickin' huge. */ + ngs->bscore_stack_size = ngs->bp_table_size * 20; + ngs->bscore_stack = ckd_calloc(ngs->bscore_stack_size, + sizeof(*ngs->bscore_stack)); + ngs->n_frame_alloc = 256; + ngs->bp_table_idx = ckd_calloc(ngs->n_frame_alloc + 1, + sizeof(*ngs->bp_table_idx)); + ++ngs->bp_table_idx; /* Make bptableidx[-1] valid */ + + /* Allocate active word list array */ + ngs->active_word_list = ckd_calloc_2d(2, dict_size(dict), + sizeof(**ngs->active_word_list)); + + ngs->lmset = ngram_model_set_init(config, &lm, &lmname, NULL, 1); + if (!ngs->lmset) + goto error_out; + + if (ngram_wid(ngs->lmset, S3_FINISH_WORD) == + ngram_unknown_wid(ngs->lmset)) + { + E_ERROR("Language model/set does not contain </s>, " + "recognition will fail\n"); + goto error_out; + } + + /* Create word mappings. */ + ngram_search_update_widmap(ngs); + + /* Initialize fwdtree, fwdflat, bestpath modules if necessary. */ + if (cmd_ln_boolean_r(config, "-fwdtree")) { + ngram_fwdtree_init(ngs); + ngs->fwdtree = TRUE; + ngs->fwdtree_perf.name = "fwdtree"; + ptmr_init(&ngs->fwdtree_perf); + } + if (cmd_ln_boolean_r(config, "-fwdflat")) { + ngram_fwdflat_init(ngs); + ngs->fwdflat = TRUE; + ngs->fwdflat_perf.name = "fwdflat"; + ptmr_init(&ngs->fwdflat_perf); + } + if (cmd_ln_boolean_r(config, "-bestpath")) { + ngs->bestpath = TRUE; + ngs->bestpath_perf.name = "bestpath"; + ptmr_init(&ngs->bestpath_perf); + } + + return (ps_search_t *)ngs; + +error_out: + ngram_search_free((ps_search_t *)ngs); + return NULL; +} + +static int +ngram_search_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + int old_n_words; + int rv = 0; + + /* Update the number of words. */ + old_n_words = search->n_words; + if (old_n_words != dict_size(dict)) { + search->n_words = dict_size(dict); + /* Reallocate these temporary arrays. */ + ckd_free(ngs->word_lat_idx); + ckd_free(ngs->word_active); + ckd_free(ngs->last_ltrans); + ckd_free_2d(ngs->active_word_list); + ngs->word_lat_idx = ckd_calloc(search->n_words, sizeof(*ngs->word_lat_idx)); + ngs->word_active = bitvec_alloc(search->n_words); + ngs->last_ltrans = ckd_calloc(search->n_words, sizeof(*ngs->last_ltrans)); + ngs->active_word_list + = ckd_calloc_2d(2, search->n_words, + sizeof(**ngs->active_word_list)); + } + + /* Free old dict2pid, dict */ + ps_search_base_reinit(search, dict, d2p); + + if (ngs->lmset == NULL) + return 0; + + /* Update beam widths. */ + ngram_search_calc_beams(ngs); + + /* Update word mappings. */ + ngram_search_update_widmap(ngs); + + /* Now rebuild lextrees. */ + if (ngs->fwdtree) { + if ((rv = ngram_fwdtree_reinit(ngs)) < 0) + return rv; + } + if (ngs->fwdflat) { + if ((rv = ngram_fwdflat_reinit(ngs)) < 0) + return rv; + } + + return rv; +} + +void +ngram_search_free(ps_search_t *search) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + ps_search_deinit(search); + if (ngs->fwdtree) + ngram_fwdtree_deinit(ngs); + if (ngs->fwdflat) + ngram_fwdflat_deinit(ngs); + if (ngs->bestpath) { + double n_speech = (double)ngs->n_tot_frame + / cmd_ln_int32_r(ps_search_config(ngs), "-frate"); + + E_INFO("TOTAL bestpath %.2f CPU %.3f xRT\n", + ngs->bestpath_perf.t_tot_cpu, + ngs->bestpath_perf.t_tot_cpu / n_speech); + E_INFO("TOTAL bestpath %.2f wall %.3f xRT\n", + ngs->bestpath_perf.t_tot_elapsed, + ngs->bestpath_perf.t_tot_elapsed / n_speech); + } + + hmm_context_free(ngs->hmmctx); + listelem_alloc_free(ngs->chan_alloc); + listelem_alloc_free(ngs->root_chan_alloc); + listelem_alloc_free(ngs->latnode_alloc); + ngram_model_free(ngs->lmset); + + ckd_free(ngs->word_chan); + ckd_free(ngs->word_lat_idx); + bitvec_free(ngs->word_active); + ckd_free(ngs->bp_table); + ckd_free(ngs->bscore_stack); + if (ngs->bp_table_idx != NULL) + ckd_free(ngs->bp_table_idx - 1); + ckd_free_2d(ngs->active_word_list); + ckd_free(ngs->last_ltrans); + ckd_free(ngs); +} + +int +ngram_search_mark_bptable(ngram_search_t *ngs, int frame_idx) +{ + if (frame_idx >= ngs->n_frame_alloc) { + ngs->n_frame_alloc *= 2; + ngs->bp_table_idx = ckd_realloc(ngs->bp_table_idx - 1, + (ngs->n_frame_alloc + 1) + * sizeof(*ngs->bp_table_idx)); + if (ngs->frm_wordlist) { + ngs->frm_wordlist = ckd_realloc(ngs->frm_wordlist, + ngs->n_frame_alloc + * sizeof(*ngs->frm_wordlist)); + } + ++ngs->bp_table_idx; /* Make bptableidx[-1] valid */ + } + ngs->bp_table_idx[frame_idx] = ngs->bpidx; + return ngs->bpidx; +} + +static void +set_real_wid(ngram_search_t *ngs, int32 bp) +{ + bptbl_t *ent, *prev; + + assert(bp != NO_BP); + ent = ngs->bp_table + bp; + if (ent->bp == NO_BP) + prev = NULL; + else + prev = ngs->bp_table + ent->bp; + + /* Propagate lm state for fillers, rotate it for words. */ + if (dict_filler_word(ps_search_dict(ngs), ent->wid)) { + if (prev != NULL) { + ent->real_wid = prev->real_wid; + ent->prev_real_wid = prev->prev_real_wid; + } + else { + ent->real_wid = dict_basewid(ps_search_dict(ngs), + ent->wid); + ent->prev_real_wid = BAD_S3WID; + } + } + else { + ent->real_wid = dict_basewid(ps_search_dict(ngs), ent->wid); + if (prev != NULL) + ent->prev_real_wid = prev->real_wid; + else + ent->prev_real_wid = BAD_S3WID; + } +} + +#define NGRAM_HISTORY_LONG_WORD 2000 /* 20s */ + +void +ngram_search_save_bp(ngram_search_t *ngs, int frame_idx, + int32 w, int32 score, int32 path, int32 rc) +{ + int32 bp; + + /* Look for an existing exit for this word in this frame. The + * only reason one would exist is from a different right context + * triphone, but of course that happens quite frequently. */ + bp = ngs->word_lat_idx[w]; + if (bp != NO_BP) { + + if (frame_idx - ngs->bp_table[path].frame > NGRAM_HISTORY_LONG_WORD) { + E_WARN("Word '%s' survived for %d frames, potential overpruning\n", dict_wordstr(ps_search_dict(ngs), w), + frame_idx - ngs->bp_table[path].frame); + } + + /* Keep only the best scoring one, we will reconstruct the + * others from the right context scores - usually the history + * is not lost. */ + if (ngs->bp_table[bp].score WORSE_THAN score) { + assert(path != bp); /* Pathological. */ + if (ngs->bp_table[bp].bp != path) { + int32 bplh[2], newlh[2]; + /* But, sometimes, the history *is* lost. If we wanted to + * do exact language model scoring we'd have to preserve + * these alternate histories. */ + E_DEBUG(2,("Updating path history %d => %d frame %d\n", + ngs->bp_table[bp].bp, path, frame_idx)); + bplh[0] = ngs->bp_table[bp].bp == -1 + ? -1 : ngs->bp_table[ngs->bp_table[bp].bp].prev_real_wid; + bplh[1] = ngs->bp_table[bp].bp == -1 + ? -1 : ngs->bp_table[ngs->bp_table[bp].bp].real_wid; + newlh[0] = path == -1 + ? -1 : ngs->bp_table[path].prev_real_wid; + newlh[1] = path == -1 + ? -1 : ngs->bp_table[path].real_wid; + /* Actually it's worth checking how often the actual + * language model state changes. */ + if (bplh[0] != newlh[0] || bplh[1] != newlh[1]) { + /* It's fairly rare that the actual language model + * state changes, but it does happen some + * times. */ + E_DEBUG(1, ("Updating language model state %s,%s => %s,%s frame %d\n", + dict_wordstr(ps_search_dict(ngs), bplh[0]), + dict_wordstr(ps_search_dict(ngs), bplh[1]), + dict_wordstr(ps_search_dict(ngs), newlh[0]), + dict_wordstr(ps_search_dict(ngs), newlh[1]), + frame_idx)); + set_real_wid(ngs, bp); + } + ngs->bp_table[bp].bp = path; + } + ngs->bp_table[bp].score = score; + } + /* But do keep track of scores for all right contexts, since + * we need them to determine the starting path scores for any + * successors of this word exit. */ + if (ngs->bp_table[bp].s_idx != -1) + ngs->bscore_stack[ngs->bp_table[bp].s_idx + rc] = score; + } + else { + int32 i, rcsize; + bptbl_t *be; + + /* This might happen if recognition fails. */ + if (ngs->bpidx == NO_BP) { + E_ERROR("No entries in backpointer table!"); + return; + } + + /* Expand the backpointer tables if necessary. */ + if (ngs->bpidx >= ngs->bp_table_size) { + ngs->bp_table_size *= 2; + ngs->bp_table = ckd_realloc(ngs->bp_table, + ngs->bp_table_size + * sizeof(*ngs->bp_table)); + E_INFO("Resized backpointer table to %d entries\n", ngs->bp_table_size); + } + if (ngs->bss_head >= ngs->bscore_stack_size + - bin_mdef_n_ciphone(ps_search_acmod(ngs)->mdef)) { + ngs->bscore_stack_size *= 2; + ngs->bscore_stack = ckd_realloc(ngs->bscore_stack, + ngs->bscore_stack_size + * sizeof(*ngs->bscore_stack)); + E_INFO("Resized score stack to %d entries\n", ngs->bscore_stack_size); + } + + ngs->word_lat_idx[w] = ngs->bpidx; + be = &(ngs->bp_table[ngs->bpidx]); + be->wid = w; + be->frame = frame_idx; + be->bp = path; + be->score = score; + be->s_idx = ngs->bss_head; + be->valid = TRUE; + assert(path != ngs->bpidx); + + /* DICT2PID */ + /* Get diphone ID for final phone and number of ssids corresponding to it. */ + be->last_phone = dict_last_phone(ps_search_dict(ngs),w); + if (dict_is_single_phone(ps_search_dict(ngs), w)) { + be->last2_phone = -1; + be->s_idx = -1; + rcsize = 0; + } + else { + be->last2_phone = dict_second_last_phone(ps_search_dict(ngs),w); + rcsize = dict2pid_rssid(ps_search_dict2pid(ngs), + be->last_phone, be->last2_phone)->n_ssid; + } + /* Allocate some space on the bscore_stack for all of these triphones. */ + for (i = 0; i < rcsize; ++i) + ngs->bscore_stack[ngs->bss_head + i] = WORST_SCORE; + if (rcsize) + ngs->bscore_stack[ngs->bss_head + rc] = score; + set_real_wid(ngs, ngs->bpidx); + + ngs->bpidx++; + ngs->bss_head += rcsize; + } +} + +int +ngram_search_find_exit(ngram_search_t *ngs, int frame_idx, int32 *out_best_score, int32 *out_is_final) +{ + /* End of backpointers for this frame. */ + int end_bpidx; + int best_exit, bp; + int32 best_score; + + /* No hypothesis means no exit node! */ + if (ngs->n_frame == 0) + return NO_BP; + + if (frame_idx == -1 || frame_idx >= ngs->n_frame) + frame_idx = ngs->n_frame - 1; + end_bpidx = ngs->bp_table_idx[frame_idx]; + + best_score = WORST_SCORE; + best_exit = NO_BP; + + /* Scan back to find a frame with some backpointers in it. */ + while (frame_idx >= 0 && ngs->bp_table_idx[frame_idx] == end_bpidx) + --frame_idx; + /* This is NOT an error, it just means there is no hypothesis yet. */ + if (frame_idx < 0) + return NO_BP; + + /* Now find the entry for </s> OR the best scoring entry. */ + assert(end_bpidx < ngs->bp_table_size); + for (bp = ngs->bp_table_idx[frame_idx]; bp < end_bpidx; ++bp) { + if (ngs->bp_table[bp].wid == ps_search_finish_wid(ngs) + || ngs->bp_table[bp].score BETTER_THAN best_score) { + best_score = ngs->bp_table[bp].score; + best_exit = bp; + } + if (ngs->bp_table[bp].wid == ps_search_finish_wid(ngs)) + break; + } + + if (out_best_score) { + *out_best_score = best_score; + } + if (out_is_final) { + *out_is_final = (ngs->bp_table[bp].wid == ps_search_finish_wid(ngs)); + } + return best_exit; +} + +char const * +ngram_search_bp_hyp(ngram_search_t *ngs, int bpidx) +{ + ps_search_t *base = ps_search_base(ngs); + char *c; + size_t len; + int bp; + + if (bpidx == NO_BP) + return NULL; + + bp = bpidx; + len = 0; + while (bp != NO_BP) { + bptbl_t *be = &ngs->bp_table[bp]; + bp = be->bp; + if (dict_real_word(ps_search_dict(ngs), be->wid)) + len += strlen(dict_basestr(ps_search_dict(ngs), be->wid)) + 1; + } + + ckd_free(base->hyp_str); + if (len == 0) { + base->hyp_str = NULL; + return base->hyp_str; + } + base->hyp_str = ckd_calloc(1, len); + + bp = bpidx; + c = base->hyp_str + len - 1; + while (bp != NO_BP) { + bptbl_t *be = &ngs->bp_table[bp]; + size_t len; + + bp = be->bp; + if (dict_real_word(ps_search_dict(ngs), be->wid)) { + len = strlen(dict_basestr(ps_search_dict(ngs), be->wid)); + c -= len; + memcpy(c, dict_basestr(ps_search_dict(ngs), be->wid), len); + if (c > base->hyp_str) { + --c; + *c = ' '; + } + } + } + + return base->hyp_str; +} + +void +ngram_search_alloc_all_rc(ngram_search_t *ngs, int32 w) +{ + chan_t *hmm, *thmm; + xwdssid_t *rssid; + int32 i, tmatid, ciphone; + + /* DICT2PID */ + /* Get pointer to array of triphones for final diphone. */ + assert(!dict_is_single_phone(ps_search_dict(ngs), w)); + ciphone = dict_last_phone(ps_search_dict(ngs),w); + rssid = dict2pid_rssid(ps_search_dict2pid(ngs), + ciphone, + dict_second_last_phone(ps_search_dict(ngs),w)); + tmatid = bin_mdef_pid2tmatid(ps_search_acmod(ngs)->mdef, ciphone); + hmm = ngs->word_chan[w]; + if ((hmm == NULL) || (hmm_nonmpx_ssid(&hmm->hmm) != rssid->ssid[0])) { + hmm = listelem_malloc(ngs->chan_alloc); + hmm->next = ngs->word_chan[w]; + ngs->word_chan[w] = hmm; + + hmm->info.rc_id = 0; + hmm->ciphone = ciphone; + hmm_init(ngs->hmmctx, &hmm->hmm, FALSE, rssid->ssid[0], tmatid); + E_DEBUG(3,("allocated rc_id 0 ssid %d ciphone %d lc %d word %s\n", + rssid->ssid[0], hmm->ciphone, + dict_second_last_phone(ps_search_dict(ngs),w), + dict_wordstr(ps_search_dict(ngs),w))); + } + for (i = 1; i < rssid->n_ssid; ++i) { + if ((hmm->next == NULL) || (hmm_nonmpx_ssid(&hmm->next->hmm) != rssid->ssid[i])) { + thmm = listelem_malloc(ngs->chan_alloc); + thmm->next = hmm->next; + hmm->next = thmm; + hmm = thmm; + + hmm->info.rc_id = i; + hmm->ciphone = ciphone; + hmm_init(ngs->hmmctx, &hmm->hmm, FALSE, rssid->ssid[i], tmatid); + E_DEBUG(3,("allocated rc_id %d ssid %d ciphone %d lc %d word %s\n", + i, rssid->ssid[i], hmm->ciphone, + dict_second_last_phone(ps_search_dict(ngs),w), + dict_wordstr(ps_search_dict(ngs),w))); + } + else + hmm = hmm->next; + } +} + +void +ngram_search_free_all_rc(ngram_search_t *ngs, int32 w) +{ + chan_t *hmm, *thmm; + + for (hmm = ngs->word_chan[w]; hmm; hmm = thmm) { + thmm = hmm->next; + hmm_deinit(&hmm->hmm); + listelem_free(ngs->chan_alloc, hmm); + } + ngs->word_chan[w] = NULL; +} + +int32 +ngram_search_exit_score(ngram_search_t *ngs, bptbl_t *pbe, int rcphone) +{ + /* DICT2PID */ + /* Get the mapping from right context phone ID to index in the + * right context table and the bscore_stack. */ + if (pbe->last2_phone == -1) { + /* No right context for single phone predecessor words. */ + return pbe->score; + } + else { + xwdssid_t *rssid; + /* Find the index for the last diphone of the previous word + + * the first phone of the current word. */ + rssid = dict2pid_rssid(ps_search_dict2pid(ngs), + pbe->last_phone, pbe->last2_phone); + /* This may be WORST_SCORE, which means that there was no exit + * with rcphone as right context. */ + return ngs->bscore_stack[pbe->s_idx + rssid->cimap[rcphone]]; + } +} + +/* + * Compute acoustic and LM scores for a BPTable entry (segment). + */ +void +ngram_compute_seg_score(ngram_search_t *ngs, bptbl_t *be, float32 lwf, + int32 *out_ascr, int32 *out_lscr) +{ + bptbl_t *pbe; + int32 start_score; + + /* Start of utterance. */ + if (be->bp == NO_BP) { + *out_ascr = be->score; + *out_lscr = 0; + return; + } + + /* Otherwise, calculate lscr and ascr. */ + pbe = ngs->bp_table + be->bp; + start_score = ngram_search_exit_score(ngs, pbe, + dict_first_phone(ps_search_dict(ngs),be->wid)); + assert(start_score BETTER_THAN WORST_SCORE); + + /* FIXME: These result in positive acoustic scores when filler + words have non-filler pronunciations. That whole business + is still pretty much broken but at least it doesn't + segfault. */ + if (be->wid == ps_search_silence_wid(ngs)) { + *out_lscr = ngs->silpen; + } + else if (dict_filler_word(ps_search_dict(ngs), be->wid)) { + *out_lscr = ngs->fillpen; + } + else { + int32 n_used; + *out_lscr = ngram_tg_score(ngs->lmset, + be->real_wid, + pbe->real_wid, + pbe->prev_real_wid, + &n_used)>>SENSCR_SHIFT; + *out_lscr = *out_lscr * lwf; + } + *out_ascr = be->score - start_score - *out_lscr; +} + +static int +ngram_search_start(ps_search_t *search) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + ngs->done = FALSE; + ngram_model_flush(ngs->lmset); + if (ngs->fwdtree) + ngram_fwdtree_start(ngs); + else if (ngs->fwdflat) + ngram_fwdflat_start(ngs); + else + return -1; + return 0; +} + +static int +ngram_search_step(ps_search_t *search, int frame_idx) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + if (ngs->fwdtree) + return ngram_fwdtree_search(ngs, frame_idx); + else if (ngs->fwdflat) + return ngram_fwdflat_search(ngs, frame_idx); + else + return -1; +} + +void +dump_bptable(ngram_search_t *ngs) +{ + int i; + E_INFO("Backpointer table (%d entries):\n", ngs->bpidx); + for (i = 0; i < ngs->bpidx; ++i) { + bptbl_t *bpe = ngs->bp_table + i; + int j, rcsize; + + E_INFO_NOFN("%-5d %-10s start %-3d end %-3d score %-8d bp %-3d real_wid %-5d prev_real_wid %-5d", + i, dict_wordstr(ps_search_dict(ngs), bpe->wid), + (bpe->bp == -1 + ? 0 : ngs->bp_table[bpe->bp].frame + 1), + bpe->frame, bpe->score, bpe->bp, + bpe->real_wid, bpe->prev_real_wid); + + if (bpe->last2_phone == -1) + rcsize = 0; + else + rcsize = dict2pid_rssid(ps_search_dict2pid(ngs), + bpe->last_phone, bpe->last2_phone)->n_ssid; + if (rcsize) { + E_INFOCONT("\tbss"); + for (j = 0; j < rcsize; ++j) + if (ngs->bscore_stack[bpe->s_idx + j] != WORST_SCORE) + E_INFOCONT(" %d", bpe->score - ngs->bscore_stack[bpe->s_idx + j]); + } + E_INFOCONT("\n"); + } +} + +static int +ngram_search_finish(ps_search_t *search) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + ngs->n_tot_frame += ngs->n_frame; + if (ngs->fwdtree) { + ngram_fwdtree_finish(ngs); + /* dump_bptable(ngs); */ + + /* Now do fwdflat search in its entirety, if requested. */ + if (ngs->fwdflat) { + int i; + /* Rewind the acoustic model. */ + if (acmod_rewind(ps_search_acmod(ngs)) < 0) + return -1; + /* Now redo search. */ + ngram_fwdflat_start(ngs); + i = 0; + while (ps_search_acmod(ngs)->n_feat_frame > 0) { + int nfr; + if ((nfr = ngram_fwdflat_search(ngs, i)) < 0) + return nfr; + acmod_advance(ps_search_acmod(ngs)); + ++i; + } + ngram_fwdflat_finish(ngs); + /* And now, we should have a result... */ + /* dump_bptable(ngs); */ + } + } + else if (ngs->fwdflat) { + ngram_fwdflat_finish(ngs); + } + + /* Mark the current utterance as done. */ + ngs->done = TRUE; + return 0; +} + +static ps_latlink_t * +ngram_search_bestpath(ps_search_t *search, int32 *out_score, int backward) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + if (search->last_link == NULL) { + search->last_link = ps_lattice_bestpath(search->dag, ngs->lmset, + ngs->bestpath_fwdtree_lw_ratio, + ngs->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, ngs->lmset, + ngs->ascale); + } + if (out_score) + *out_score = search->last_link->path_scr + search->dag->final_node_ascr; + return search->last_link; +} + +static char const * +ngram_search_hyp(ps_search_t *search, int32 *out_score, int32 *out_is_final) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + /* Only do bestpath search if the utterance is complete. */ + if (ngs->bestpath && ngs->done) { + ps_lattice_t *dag; + ps_latlink_t *link; + char const *hyp; + double n_speech; + + ptmr_reset(&ngs->bestpath_perf); + ptmr_start(&ngs->bestpath_perf); + if ((dag = ngram_search_lattice(search)) == NULL) + return NULL; + if ((link = ngram_search_bestpath(search, out_score, FALSE)) == NULL) + return NULL; + hyp = ps_lattice_hyp(dag, link); + ptmr_stop(&ngs->bestpath_perf); + n_speech = (double)dag->n_frames + / cmd_ln_int32_r(ps_search_config(ngs), "-frate"); + E_INFO("bestpath %.2f CPU %.3f xRT\n", + ngs->bestpath_perf.t_cpu, + ngs->bestpath_perf.t_cpu / n_speech); + E_INFO("bestpath %.2f wall %.3f xRT\n", + ngs->bestpath_perf.t_elapsed, + ngs->bestpath_perf.t_elapsed / n_speech); + return hyp; + } + else { + int32 bpidx; + + /* fwdtree and fwdflat use same backpointer table. */ + bpidx = ngram_search_find_exit(ngs, -1, out_score, out_is_final); + if (bpidx != NO_BP) + return ngram_search_bp_hyp(ngs, bpidx); + } + + return NULL; +} + +static void +ngram_search_bp2itor(ps_seg_t *seg, int bp) +{ + ngram_search_t *ngs = (ngram_search_t *)seg->search; + bptbl_t *be, *pbe; + + be = &ngs->bp_table[bp]; + pbe = be->bp == -1 ? NULL : &ngs->bp_table[be->bp]; + seg->word = dict_wordstr(ps_search_dict(ngs), be->wid); + seg->ef = be->frame; + seg->sf = pbe ? pbe->frame + 1 : 0; + seg->prob = 0; /* Bogus value... */ + /* Compute acoustic and LM scores for this segment. */ + if (pbe == NULL) { + seg->ascr = be->score; + seg->lscr = 0; + seg->lback = 0; + } + else { + int32 start_score; + + /* Find ending path score of previous word. */ + start_score = ngram_search_exit_score(ngs, pbe, + dict_first_phone(ps_search_dict(ngs), be->wid)); + assert(start_score BETTER_THAN WORST_SCORE); + if (be->wid == ps_search_silence_wid(ngs)) { + seg->lscr = ngs->silpen; + } + else if (dict_filler_word(ps_search_dict(ngs), be->wid)) { + seg->lscr = ngs->fillpen; + } + else { + seg->lscr = ngram_tg_score(ngs->lmset, + be->real_wid, + pbe->real_wid, + pbe->prev_real_wid, + &seg->lback)>>SENSCR_SHIFT; + seg->lscr = (int32)(seg->lscr * seg->lwf); + } + seg->ascr = be->score - start_score - seg->lscr; + } +} + +static void +ngram_bp_seg_free(ps_seg_t *seg) +{ + bptbl_seg_t *itor = (bptbl_seg_t *)seg; + + ckd_free(itor->bpidx); + ckd_free(itor); +} + +static ps_seg_t * +ngram_bp_seg_next(ps_seg_t *seg) +{ + bptbl_seg_t *itor = (bptbl_seg_t *)seg; + + if (++itor->cur == itor->n_bpidx) { + ngram_bp_seg_free(seg); + return NULL; + } + + ngram_search_bp2itor(seg, itor->bpidx[itor->cur]); + return seg; +} + +static ps_segfuncs_t ngram_bp_segfuncs = { + /* seg_next */ ngram_bp_seg_next, + /* seg_free */ ngram_bp_seg_free +}; + +static ps_seg_t * +ngram_search_bp_iter(ngram_search_t *ngs, int bpidx, float32 lwf) +{ + bptbl_seg_t *itor; + int bp, cur; + + /* 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 = &ngram_bp_segfuncs; + itor->base.search = ps_search_base(ngs); + itor->base.lwf = lwf; + itor->n_bpidx = 0; + bp = bpidx; + while (bp != NO_BP) { + bptbl_t *be = &ngs->bp_table[bp]; + bp = be->bp; + ++itor->n_bpidx; + } + if (itor->n_bpidx == 0) { + ckd_free(itor); + return NULL; + } + itor->bpidx = ckd_calloc(itor->n_bpidx, sizeof(*itor->bpidx)); + cur = itor->n_bpidx - 1; + bp = bpidx; + while (bp != NO_BP) { + bptbl_t *be = &ngs->bp_table[bp]; + itor->bpidx[cur] = bp; + bp = be->bp; + --cur; + } + + /* Fill in relevant fields for first element. */ + ngram_search_bp2itor((ps_seg_t *)itor, itor->bpidx[0]); + + return (ps_seg_t *)itor; +} + +static ps_seg_t * +ngram_search_seg_iter(ps_search_t *search, int32 *out_score) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + /* Only do bestpath search if the utterance is done. */ + if (ngs->bestpath && ngs->done) { + ps_lattice_t *dag; + ps_latlink_t *link; + double n_speech; + ps_seg_t *itor; + + ptmr_reset(&ngs->bestpath_perf); + ptmr_start(&ngs->bestpath_perf); + if ((dag = ngram_search_lattice(search)) == NULL) + return NULL; + if ((link = ngram_search_bestpath(search, out_score, TRUE)) == NULL) + return NULL; + itor = ps_lattice_seg_iter(dag, link, + ngs->bestpath_fwdtree_lw_ratio); + ptmr_stop(&ngs->bestpath_perf); + n_speech = (double)dag->n_frames + / cmd_ln_int32_r(ps_search_config(ngs), "-frate"); + E_INFO("bestpath %.2f CPU %.3f xRT\n", + ngs->bestpath_perf.t_cpu, + ngs->bestpath_perf.t_cpu / n_speech); + E_INFO("bestpath %.2f wall %.3f xRT\n", + ngs->bestpath_perf.t_elapsed, + ngs->bestpath_perf.t_elapsed / n_speech); + return itor; + } + else { + int32 bpidx; + + /* fwdtree and fwdflat use same backpointer table. */ + bpidx = ngram_search_find_exit(ngs, -1, out_score, NULL); + return ngram_search_bp_iter(ngs, bpidx, + /* but different language weights... */ + (ngs->done && ngs->fwdflat) + ? ngs->fwdflat_fwdtree_lw_ratio : 1.0); + } + + return NULL; +} + +static int32 +ngram_search_prob(ps_search_t *search) +{ + ngram_search_t *ngs = (ngram_search_t *)search; + + /* Only do bestpath search if the utterance is done. */ + if (ngs->bestpath && ngs->done) { + ps_lattice_t *dag; + ps_latlink_t *link; + + if ((dag = ngram_search_lattice(search)) == NULL) + return 0; + if ((link = ngram_search_bestpath(search, NULL, TRUE)) == NULL) + return 0; + return search->post; + } + else { + /* FIXME: Give some kind of good estimate here, eventually. */ + return 0; + } +} + +static void +create_dag_nodes(ngram_search_t *ngs, ps_lattice_t *dag) +{ + bptbl_t *bp_ptr; + int32 i; + + for (i = 0, bp_ptr = ngs->bp_table; i < ngs->bpidx; ++i, ++bp_ptr) { + int32 sf, ef, wid; + ps_latnode_t *node; + + /* Skip invalid backpointers (these result from -maxwpf pruning) */ + if (!bp_ptr->valid) + continue; + + sf = (bp_ptr->bp < 0) ? 0 : ngs->bp_table[bp_ptr->bp].frame + 1; + ef = bp_ptr->frame; + wid = bp_ptr->wid; + + assert(ef < dag->n_frames); + /* Skip non-final </s> entries. */ + if ((wid == ps_search_finish_wid(ngs)) && (ef < dag->n_frames - 1)) + continue; + + /* Skip if word not in LM */ + if ((!dict_filler_word(ps_search_dict(ngs), wid)) + && (!ngram_model_set_known_wid(ngs->lmset, + dict_basewid(ps_search_dict(ngs), wid)))) + continue; + + /* See if bptbl entry <wid,sf> already in lattice */ + for (node = dag->nodes; node; node = node->next) { + if ((node->wid == wid) && (node->sf == sf)) + break; + } + + /* For the moment, store bptbl indices in node.{fef,lef} */ + if (node) + node->lef = i; + else { + /* New node; link to head of list */ + node = listelem_malloc(dag->latnode_alloc); + node->wid = wid; + node->sf = sf; /* This is a frame index. */ + node->fef = node->lef = i; /* These are backpointer indices (argh) */ + node->reachable = FALSE; + node->entries = NULL; + node->exits = NULL; + + /* NOTE: This creates the list of nodes in reverse + * topological order, i.e. a node always precedes its + * antecedents in this list. */ + node->next = dag->nodes; + dag->nodes = node; + ++dag->n_nodes; + } + } +} + +static ps_latnode_t * +find_start_node(ngram_search_t *ngs, ps_lattice_t *dag) +{ + ps_latnode_t *node; + + /* Find start node <s>.0 */ + for (node = dag->nodes; node; node = node->next) { + if ((node->wid == ps_search_start_wid(ngs)) && (node->sf == 0)) + break; + } + if (!node) { + /* This is probably impossible. */ + E_ERROR("Couldn't find <s> in first frame\n"); + return NULL; + } + return node; +} + +static ps_latnode_t * +find_end_node(ngram_search_t *ngs, ps_lattice_t *dag, float32 lwf) +{ + ps_latnode_t *node; + int32 ef, bestbp, bp, bestscore; + + /* Find final node </s>.last_frame; nothing can follow this node */ + for (node = dag->nodes; node; node = node->next) { + int32 lef = ngs->bp_table[node->lef].frame; + if ((node->wid == ps_search_finish_wid(ngs)) + && (lef == dag->n_frames - 1)) + break; + } + if (node != NULL) + return node; + + /* It is quite likely that no </s> exited in the last frame. So, + * find the node corresponding to the best exit. */ + /* Find the last frame containing a word exit. */ + for (ef = dag->n_frames - 1; + ef >= 0 && ngs->bp_table_idx[ef] == ngs->bpidx; + --ef); + if (ef < 0) { + E_ERROR("Empty backpointer table: can not build DAG.\n"); + return NULL; + } + + /* Find best word exit in that frame. */ + bestscore = WORST_SCORE; + bestbp = NO_BP; + for (bp = ngs->bp_table_idx[ef]; bp < ngs->bp_table_idx[ef + 1]; ++bp) { + int32 n_used, l_scr, wid, prev_wid; + wid = ngs->bp_table[bp].real_wid; + prev_wid = ngs->bp_table[bp].prev_real_wid; + /* Always prefer </s>, of which there will only be one per frame. */ + if (wid == ps_search_finish_wid(ngs)) { + bestbp = bp; + break; + } + l_scr = ngram_tg_score(ngs->lmset, ps_search_finish_wid(ngs), + wid, prev_wid, &n_used) >>SENSCR_SHIFT; + l_scr = l_scr * lwf; + if (ngs->bp_table[bp].score + l_scr BETTER_THAN bestscore) { + bestscore = ngs->bp_table[bp].score + l_scr; + bestbp = bp; + } + } + if (bestbp == NO_BP) { + E_ERROR("No word exits found in last frame (%d), assuming no recognition\n", ef); + return NULL; + } + E_INFO("</s> not found in last frame, using %s.%d instead\n", + dict_basestr(ps_search_dict(ngs), ngs->bp_table[bestbp].wid), ef); + + /* Now find the node that corresponds to it. */ + for (node = dag->nodes; node; node = node->next) { + if (node->lef == bestbp) + return node; + } + + /* FIXME: This seems to happen a lot! */ + E_ERROR("Failed to find DAG node corresponding to %s\n", + dict_basestr(ps_search_dict(ngs), ngs->bp_table[bestbp].wid)); + return NULL; +} + +/* + * Build lattice from bptable. + */ +ps_lattice_t * +ngram_search_lattice(ps_search_t *search) +{ + int32 i, score, ascr, lscr; + ps_latnode_t *node, *from, *to; + ngram_search_t *ngs; + ps_lattice_t *dag; + int min_endfr, nlink; + float lwf; + + ngs = (ngram_search_t *)search; + min_endfr = cmd_ln_int32_r(ps_search_config(search), "-min_endfr"); + + /* If the best score is WORST_SCORE or worse, there is no way to + * make a lattice. */ + if (ngs->best_score == WORST_SCORE || ngs->best_score WORSE_THAN WORST_SCORE) + return NULL; + + /* 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 == ngs->n_frame) + return search->dag; + + /* Nope, create a new one. */ + ps_lattice_free(search->dag); + search->dag = NULL; + dag = ps_lattice_init_search(search, ngs->n_frame); + /* Compute these such that they agree with the fwdtree language weight. */ + lwf = ngs->fwdflat ? ngs->fwdflat_fwdtree_lw_ratio : 1.0; + create_dag_nodes(ngs, dag); + if ((dag->start = find_start_node(ngs, dag)) == NULL) + goto error_out; + if ((dag->end = find_end_node(ngs, dag, ngs->bestpath_fwdtree_lw_ratio)) == NULL) + goto error_out; + E_INFO("lattice start node %s.%d end node %s.%d\n", + dict_wordstr(search->dict, dag->start->wid), dag->start->sf, + dict_wordstr(search->dict, dag->end->wid), dag->end->sf); + + ngram_compute_seg_score(ngs, ngs->bp_table + dag->end->lef, lwf, + &dag->final_node_ascr, &lscr); + + /* + * At this point, dag->nodes is ordered such that nodes earlier in + * the list can follow (in time) those later in the list, but not + * vice versa (see above - also note that adjacency is purely + * determined by time which is why we can make this claim). Now + * create precedence links and simultanesously mark all nodes that + * can reach dag->end. (All nodes are reached from dag->start + * simply by definition - they were created that way). + * + * Note that this also means that any nodes before dag->end in the + * list can be discarded, meaning that dag->end will always be + * equal to dag->nodes (FIXME: except when loading from a file but + * we can fix that...) + */ + i = 0; + while (dag->nodes && dag->nodes != dag->end) { + ps_latnode_t *next = dag->nodes->next; + listelem_free(dag->latnode_alloc, dag->nodes); + dag->nodes = next; + ++i; + } + E_INFO("Eliminated %d nodes before end node\n", i); + dag->end->reachable = TRUE; + nlink = 0; + for (to = dag->end; to; to = to->next) { + int fef, lef; + + /* Skip if not reachable; it will never be reachable from dag->end */ + if (!to->reachable) + continue; + + /* Prune nodes with too few endpoints - heuristic + borrowed from Sphinx3 */ + fef = ngs->bp_table[to->fef].frame; + lef = ngs->bp_table[to->lef].frame; + if (to != dag->end && lef - fef < min_endfr) { + to->reachable = FALSE; + continue; + } + + /* Find predecessors of to : from->fef+1 <= to->sf <= from->lef+1 */ + for (from = to->next; from; from = from->next) { + bptbl_t *from_bpe; + + fef = ngs->bp_table[from->fef].frame; + lef = ngs->bp_table[from->lef].frame; + + if ((to->sf <= fef) || (to->sf > lef + 1)) + continue; + if (lef - fef < min_endfr) { + assert(!from->reachable); + continue; + } + + /* Find bptable entry for "from" that exactly precedes "to" */ + i = from->fef; + from_bpe = ngs->bp_table + i; + for (; i <= from->lef; i++, from_bpe++) { + if (from_bpe->wid != from->wid) + continue; + if (from_bpe->frame >= to->sf - 1) + break; + } + + if ((i > from->lef) || (from_bpe->frame != to->sf - 1)) + continue; + + /* Find acoustic score from.sf->to.sf-1 with right context = to */ + /* This gives us from_bpe's best acoustic score. */ + ngram_compute_seg_score(ngs, from_bpe, lwf, + &ascr, &lscr); + /* Now find the exact path score for from->to, including + * the appropriate final triphone. In fact this might not + * exist. */ + score = ngram_search_exit_score(ngs, from_bpe, + dict_first_phone(ps_search_dict(ngs), to->wid)); + /* Does not exist. Can't create a link here. */ + if (score == WORST_SCORE) + continue; + /* Adjust the arc score to match the correct triphone. */ + else + score = ascr + (score - from_bpe->score); + if (score BETTER_THAN 0) { + /* Scores must be negative, or Bad Things will happen. + In general, they are, except in corner cases + involving filler words. We don't want to throw any + links away so we'll keep these, but with some + arbitrarily improbable but recognizable score. */ + ps_lattice_link(dag, from, to, -424242, from_bpe->frame); + ++nlink; + from->reachable = TRUE; + } + else if (score BETTER_THAN WORST_SCORE) { + ps_lattice_link(dag, from, to, score, from_bpe->frame); + ++nlink; + from->reachable = TRUE; + } + } + } + + /* There must be at least one path between dag->start and dag->end */ + if (!dag->start->reachable) { + E_ERROR("End node of lattice isolated; unreachable\n"); + goto error_out; + } + + for (node = dag->nodes; node; node = node->next) { + /* Change node->{fef,lef} from bptbl indices to frames. */ + node->fef = ngs->bp_table[node->fef].frame; + node->lef = ngs->bp_table[node->lef].frame; + /* Find base wid for nodes. */ + node->basewid = dict_basewid(search->dict, node->wid); + } + + /* Link nodes with alternate pronunciations at the same timepoint. */ + for (node = dag->nodes; node; node = node->next) { + ps_latnode_t *alt; + /* Scan forward to find the next alternate, then stop. */ + for (alt = node->next; alt && alt->sf == node->sf; alt = alt->next) { + if (alt->basewid == node->basewid) { + alt->alt = node->alt; + node->alt = alt; + break; + } + } + } + E_INFO("Lattice has %d nodes, %d links\n", dag->n_nodes, nlink); + + /* Minor hack: If the final node is a filler word and not </s>, + * then set its base word ID to </s>, so that the language model + * scores won't be screwed up. */ + if (dict_filler_word(ps_search_dict(ngs), dag->end->wid)) + dag->end->basewid = ps_search_finish_wid(ngs); + + /* Free nodes unreachable from dag->end and their links */ + ps_lattice_delete_unreachable(dag); + + /* Add silprob and fillprob to corresponding links */ + ps_lattice_penalize_fillers(dag, ngs->silpen, ngs->fillpen); + + search->dag = dag; + return dag; + +error_out: + ps_lattice_free(dag); + return NULL; +} + +void ngram_search_set_lm(ngram_model_t *lm) +{ + default_lm = ngram_model_retain(lm); +} + |