ngram_search.c
Go to the documentation of this file.
/* -*- 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.
*
* ====================================================================
*
*/
/* 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);
static int32 ngram_search_prob(ps_search_t *search);
static ps_seg_t *ngram_search_seg_iter(ps_search_t *search);
static ps_searchfuncs_t ngram_funcs = {
/* 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(const char *name,
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, PS_SEARCH_TYPE_NGRAM, name, 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;
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);
}
ps_search_base_free(search);
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)
{
/* 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;
}
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)
{
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);
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)
{
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, NULL, 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, 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);
}
ps_latnode_s::wid
int32 wid
Dictionary word id.
Definition: ps_lattice_internal.h:115
SENSCR_SHIFT
#define SENSCR_SHIFT
Shift count for senone scores.
Definition: hmm.h:73
bptbl_s::bp
int32 bp
Back Pointer.
Definition: ngram_search.h:114
bptbl_seg_s::n_bpidx
int16 n_bpidx
Number of backpointer IDs.
Definition: ngram_search.h:129
ngram_fwdtree_reinit
int ngram_fwdtree_reinit(ngram_search_t *ngs)
Rebuild search structures for updated language models.
Definition: ngram_search_fwdtree.c:451
ps_search_init
void ps_search_init(ps_search_t *search, ps_searchfuncs_t *vt, const char *type, const char *name, cmd_ln_t *config, acmod_t *acmod, dict_t *dict, dict2pid_t *d2p)
Initialize base structure.
Definition: pocketsphinx.c:1371
ngram_search_s::hmmctx
hmm_context_t * hmmctx
HMM context.
Definition: ngram_search.h:200
xwdssid_t::cimap
s3cipid_t * cimap
Index into ssid[] above for each ci phone.
Definition: dict2pid.h:75
ps_search_s::dag
ps_lattice_t * dag
Current hypothesis word graph.
Definition: pocketsphinx_internal.h:110
ps_lattice_link
POCKETSPHINX_EXPORT void ps_lattice_link(ps_lattice_t *dag, ps_latnode_t *from, ps_latnode_t *to, int32 score, int32 ef)
Create a directed link between "from" and "to" nodes, but if a link already exists,...
Definition: ps_lattice.c:65
ngram_search_s::chan_alloc
listelem_alloc_t * chan_alloc
For chan_t.
Definition: ngram_search.h:211
ngram_search_set_lm
void ngram_search_set_lm(ngram_model_t *lm)
Sets the global language model.
Definition: ngram_search.c:1403
ngram_search_s::ascale
float32 ascale
Acoustic score scale for posterior probabilities.
Definition: ngram_search.h:333
xwdssid_t::ssid
s3ssid_t * ssid
Senone Sequence ID list for all context ciphones.
Definition: dict2pid.h:74
ps_seg_s::sf
frame_idx_t sf
Start frame.
Definition: pocketsphinx_internal.h:182
ps_latnode_s::alt
struct ps_latnode_s * alt
Node with alternate pronunciation for this word.
Definition: ps_lattice_internal.h:132
ngram_fwdtree_start
void ngram_fwdtree_start(ngram_search_t *ngs)
Start fwdtree decoding for an utterance.
Definition: ngram_search_fwdtree.c:471
hmm_context_init
hmm_context_t * hmm_context_init(int32 n_emit_state, uint8 **const *tp, int16 const *senscore, uint16 *const *sseq)
Create an HMM context.
Definition: hmm.c:56
pocketsphinx_internal.h
ps_latnode_s::exits
latlink_list_t * exits
Links out of this node.
Definition: ps_lattice_internal.h:129
ps_seg_s::vt
ps_segfuncs_t * vt
V-table of seg methods.
Definition: pocketsphinx_internal.h:179
chan_s::rc_id
int32 rc_id
right-context id for last phone of words
Definition: ngram_search.h:79
ps_search_s
Base structure for search module.
Definition: pocketsphinx_internal.h:98
ps_search_s::n_words
int32 n_words
Number of words known to search (may be less than in the dictionary)
Definition: pocketsphinx_internal.h:113
ps_seg_s
Base structure for hypothesis segmentation iterator.
Definition: pocketsphinx_internal.h:178
bin_mdef_s::sseq
uint16 ** sseq
Unique senone sequences (2D array built at load time)
Definition: bin_mdef.h:134
dict2pid_rssid
#define dict2pid_rssid(d, ci, lc)
Access macros; not designed for arbitrary use.
Definition: dict2pid.h:115
ps_latnode_s::next
struct ps_latnode_s * next
Next node in DAG (no ordering implied)
Definition: ps_lattice_internal.h:133
ps_lattice_bestpath
POCKETSPHINX_EXPORT ps_latlink_t * ps_lattice_bestpath(ps_lattice_t *dag, ngram_model_t *lmset, float32 lwf, float32 ascale)
Do N-Gram based best-path search on a word graph.
Definition: ps_lattice.c:1215
ngram_search_find_exit
int ngram_search_find_exit(ngram_search_t *ngs, int frame_idx, int32 *out_best_score)
Find the best word exit for the current frame in the backpointer table.
Definition: ngram_search.c:506
ngram_search_alloc_all_rc
void ngram_search_alloc_all_rc(ngram_search_t *ngs, int32 w)
Allocate last phone channels for all possible right contexts for word w.
Definition: ngram_search.c:598
ngram_fwdflat_deinit
void ngram_fwdflat_deinit(ngram_search_t *ngs)
Release memory associated with fwdflat decoding.
Definition: ngram_search_fwdflat.c:169
ps_latnode_s::entries
latlink_list_t * entries
Links into this node.
Definition: ps_lattice_internal.h:130
ps_search_base_reinit
void ps_search_base_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p)
Re-initialize base structure with new dictionary.
Definition: pocketsphinx.c:1415
ngram_fwdtree_search
int ngram_fwdtree_search(ngram_search_t *ngs, int frame_idx)
Search one frame forward in an utterance.
Definition: ngram_search_fwdtree.c:1455
ngram_search_s::active_word_list
int32 ** active_word_list
Array of active multi-phone words for current and next frame.
Definition: ngram_search.h:287
BAD_S3WID
#define BAD_S3WID
Dictionary word id.
Definition: s3types.h:90
ps_lattice_s::final_node_ascr
int32 final_node_ascr
Acoustic score of implicit link exiting final node.
Definition: ps_lattice_internal.h:76
xwdssid_t::n_ssid
int32 n_ssid
#Unique ssid in above, compressed ssid list
Definition: dict2pid.h:76
bptbl_s::frame
frame_idx_t frame
start or end frame
Definition: ngram_search.h:110
bptbl_seg_s::base
ps_seg_t base
Base structure.
Definition: ngram_search.h:127
WORSE_THAN
#define WORSE_THAN
Is one score worse than another?
Definition: hmm.h:100
ngram_search_fwdtree.h
root_chan_s
Lexical tree node data type for the first phone (root) of each dynamic HMM tree structure.
Definition: ngram_search.h:90
ps_seg_s::word
const char * word
Word string (pointer into dictionary hash)
Definition: pocketsphinx_internal.h:181
ngram_search_s::word_active
bitvec_t * word_active
array of active flags for all words.
Definition: ngram_search.h:247
ngram_search_exit_score
int32 ngram_search_exit_score(ngram_search_t *ngs, bptbl_t *pbe, int rcphone)
Get the exit score for a backpointer entry with a given right context.
Definition: ngram_search.c:660
hmm_deinit
void hmm_deinit(hmm_t *hmm)
Free an HMM structure, releasing internal data (but not the HMM structure itself).
Definition: hmm.c:111
ps_search_s::post
int32 post
Utterance posterior probability.
Definition: pocketsphinx_internal.h:112
bptbl_s::real_wid
int32 real_wid
wid of this or latest predecessor real word
Definition: ngram_search.h:117
dict2pid_t
Building composite triphone (as well as word internal triphones) with the dictionary.
Definition: dict2pid.h:84
dict_filler_word
int dict_filler_word(dict_t *d, s3wid_t w)
Return 1 if w is a filler word, 0 if not.
Definition: dict.c:413
ps_seg_s::lscr
int32 lscr
Language model score.
Definition: pocketsphinx_internal.h:185
acmod_s::mdef
bin_mdef_t * mdef
Model definition.
Definition: acmod.h:159
ps_latlink_s
Links between DAG nodes.
Definition: ps_lattice_internal.h:96
ps_lattice_hyp
const char * ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link)
Get hypothesis string after bestpath search.
Definition: ps_lattice.c:830
ps_lattice_s::latnode_alloc
listelem_alloc_t * latnode_alloc
Node allocator for this DAG.
Definition: ps_lattice_internal.h:80
ngram_search_lattice
ps_lattice_t * ngram_search_lattice(ps_search_t *search)
Construct a word lattice from the current hypothesis.
Definition: ngram_search.c:1215
ngram_search_mark_bptable
int ngram_search_mark_bptable(ngram_search_t *ngs, int frame_idx)
Record the current frame's index in the backpointer table.
Definition: ngram_search.c:329
ngram_search_save_bp
void ngram_search_save_bp(ngram_search_t *ngs, int frame_idx, int32 w, int32 score, int32 path, int32 rc)
Enter a word in the backpointer table.
Definition: ngram_search.c:383
ps_seg_s::search
ps_search_t * search
Search object from whence this came.
Definition: pocketsphinx_internal.h:180
ps_lattice_penalize_fillers
void ps_lattice_penalize_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen)
Insert penalty for fillers.
Definition: ps_lattice.c:106
chan_s::ciphone
int32 ciphone
ciphone for this node
Definition: ngram_search.h:73
hmm_init
void hmm_init(hmm_context_t *ctx, hmm_t *hmm, int mpx, int ssid, int tmatid)
Populate a previously-allocated HMM structure, allocating internal data.
Definition: hmm.c:89
ps_lattice_internal.h
ps_latnode_s::reachable
int16 reachable
From.
Definition: ps_lattice_internal.h:121
ps_search_s::hyp_str
char * hyp_str
Current hypothesis string.
Definition: pocketsphinx_internal.h:109
ps_seg_s::prob
int32 prob
Log posterior probability.
Definition: pocketsphinx_internal.h:186
ngram_search_s::best_score
int32 best_score
Best Viterbi path score.
Definition: ngram_search.h:325
bptbl_seg_s
Segmentation "iterator" for backpointer table results.
Definition: ngram_search.h:126
ps_lattice_posterior
POCKETSPHINX_EXPORT int32 ps_lattice_posterior(ps_lattice_t *dag, ngram_model_t *lmset, float32 ascale)
Calculate link posterior probabilities on a word graph.
Definition: ps_lattice.c:1446
ps_latnode_s::basewid
int32 basewid
Dictionary base word id.
Definition: ps_lattice_internal.h:116
ps_seg_s::ef
frame_idx_t ef
End frame.
Definition: pocketsphinx_internal.h:183
ngram_fwdflat_init
void ngram_fwdflat_init(ngram_search_t *ngs)
Initialize N-Gram search for fwdflat decoding.
Definition: ngram_search_fwdflat.c:145
ps_lattice_s::n_frames
frame_idx_t n_frames
Number of frames for this utterance.
Definition: ps_lattice_internal.h:74
ps_lattice_init_search
ps_lattice_t * ps_lattice_init_search(ps_search_t *search, int n_frame)
Construct an empty word graph with reference to a search structure.
Definition: ps_lattice.c:639
dict_size
#define dict_size(d)
Packaged macro access to dictionary members.
Definition: dict.h:151
ps_lattice_seg_iter
ps_seg_t * ps_lattice_seg_iter(ps_lattice_t *dag, ps_latlink_t *link, float32 lwf)
Get hypothesis segmentation iterator after bestpath search.
Definition: ps_lattice.c:1006
ps_lattice_s::end
ps_latnode_t * end
Ending node.
Definition: ps_lattice_internal.h:72
tmat_t::tp
uint8 *** tp
The transition matrices; kept in the same scale as acoustic scores; tp[tmatid][from-state][to-state].
Definition: tmat.h:56
ps_lattice_s::start
ps_latnode_t * start
Starting node.
Definition: ps_lattice_internal.h:71
ngram_fwdtree_finish
void ngram_fwdtree_finish(ngram_search_t *ngs)
Finish fwdtree decoding for an utterance.
Definition: ngram_search_fwdtree.c:1499
bptbl_s::score
int32 score
Score (best among all right contexts)
Definition: ngram_search.h:115
acmod_set_grow
int acmod_set_grow(acmod_t *acmod, int grow_feat)
Set memory allocation policy for utterance processing.
Definition: acmod.c:410
ngram_fwdflat_finish
void ngram_fwdflat_finish(ngram_search_t *ngs)
Finish fwdflat decoding for an utterance.
Definition: ngram_search_fwdflat.c:929
ngram_search_s::latnode_alloc
listelem_alloc_t * latnode_alloc
For latnode_t.
Definition: ngram_search.h:213
bptbl_s::last_phone
int16 last_phone
last phone of this word
Definition: ngram_search.h:119
ngram_search_s::n_frame
int32 n_frame
Number of frames actually present.
Definition: ngram_search.h:308
ngram_search_s::frm_wordlist
ps_latnode_t ** frm_wordlist
List of active words in each frame.
Definition: ngram_search.h:316
bptbl_s
Back pointer table (forward pass lattice; actually a tree)
Definition: ngram_search.h:109
ngram_fwdflat_reinit
int ngram_fwdflat_reinit(ngram_search_t *ngs)
Rebuild search structures for updated language models.
Definition: ngram_search_fwdflat.c:192
ps_search_base_free
void ps_search_base_free(ps_search_t *search)
Free search.
Definition: pocketsphinx.c:1402
chan_s::next
struct chan_s * next
first descendant of this channel; or, in the case of the last phone of a word, the next alternative r...
Definition: ngram_search.h:68
bptbl_seg_s::cur
int16 cur
Current position in bpidx.
Definition: ngram_search.h:130
ngram_search_free_all_rc
void ngram_search_free_all_rc(ngram_search_t *ngs, int32 w)
Allocate last phone channels for all possible right contexts for word w.
Definition: ngram_search.c:647
ps_latnode_s
DAG nodes.
Definition: ps_lattice_internal.h:113
ps_latnode_s::lef
int32 lef
Last end frame.
Definition: ps_lattice_internal.h:119
ps_searchfuncs_s
V-table for search algorithm.
Definition: pocketsphinx_internal.h:82
ps_search_s::last_link
ps_latlink_t * last_link
Final link in best path.
Definition: pocketsphinx_internal.h:111
ps_seg_s::ascr
int32 ascr
Acoustic score.
Definition: pocketsphinx_internal.h:184
xwdssid_t
cross word triphone model structure
Definition: dict2pid.h:73
ngram_search_free
void ngram_search_free(ps_search_t *search)
Finalize the N-Gram search module.
Definition: ngram_search.c:289
bptbl_seg_s::bpidx
int32 * bpidx
Sequence of backpointer IDs.
Definition: ngram_search.h:128
ps_lattice_s
Word graph structure used in bestpath/nbest search.
Definition: ps_lattice_internal.h:61
ngram_search_s::root_chan_alloc
listelem_alloc_t * root_chan_alloc
For root_chan_t.
Definition: ngram_search.h:212
chan_s
Lexical tree node data type.
Definition: ngram_search.h:64
ps_lattice_s::nodes
ps_latnode_t * nodes
List of all nodes.
Definition: ps_lattice_internal.h:70
ps_seg_s::lback
int32 lback
Language model backoff.
Definition: pocketsphinx_internal.h:189
ngram_search_s
N-Gram search module structure.
Definition: ngram_search.h:197
ngram_fwdtree_deinit
void ngram_fwdtree_deinit(ngram_search_t *ngs)
Release memory associated with fwdtree decoding.
Definition: ngram_search_fwdtree.c:422
ps_lattice_delete_unreachable
void ps_lattice_delete_unreachable(ps_lattice_t *dag)
Remove nodes marked as unreachable.
Definition: ps_lattice.c:174
acmod_s::lmath
logmath_t * lmath
Log-math computation.
Definition: acmod.h:151
ngram_fwdtree_init
void ngram_fwdtree_init(ngram_search_t *ngs)
Initialize N-Gram search for fwdtree decoding.
Definition: ngram_search_fwdtree.c:381
acmod_advance
int acmod_advance(acmod_t *acmod)
Advance the frame index.
Definition: acmod.c:899
dict_t
a structure for a dictionary.
Definition: dict.h:76
hmm_context_free
void hmm_context_free(hmm_context_t *ctx)
Free an HMM context.
Definition: hmm.c:80
ngram_fwdflat_start
void ngram_fwdflat_start(ngram_search_t *ngs)
Start fwdflat decoding for an utterance.
Definition: ngram_search_fwdflat.c:374
bptbl_s::wid
int32 wid
Word index.
Definition: ngram_search.h:113
ps_search_s::dict
dict_t * dict
Pronunciation dictionary.
Definition: pocketsphinx_internal.h:107
ps_latnode_s::fef
int32 fef
First end frame.
Definition: ps_lattice_internal.h:118
bptbl_s::prev_real_wid
int32 prev_real_wid
wid of second-last real word
Definition: ngram_search.h:118
ngram_fwdflat_search
int ngram_fwdflat_search(ngram_search_t *ngs, int frame_idx)
Search one frame forward in an utterance.
Definition: ngram_search_fwdflat.c:816
ps_lattice_s::n_nodes
int32 n_nodes
Number of nodes in this lattice.
Definition: ps_lattice_internal.h:75
ngram_search_init
ps_search_t * ngram_search_init(const char *name, ngram_model_t *lm, cmd_ln_t *config, acmod_t *acmod, dict_t *dict, dict2pid_t *d2p)
Initialize the N-Gram search module.
Definition: ngram_search.c:140
chan_s::hmm
hmm_t hmm
Basic HMM structure.
Definition: ngram_search.h:65
ngram_search_fwdflat.h
ps_lattice_free
POCKETSPHINX_EXPORT int ps_lattice_free(ps_lattice_t *dag)
Free a lattice.
Definition: ps_lattice.c:665
dict_real_word
POCKETSPHINX_EXPORT int dict_real_word(dict_t *d, s3wid_t w)
Test if w is a "real" word, i.e.
Definition: dict.c:427
BETTER_THAN
#define BETTER_THAN
Is one score better than another?
Definition: hmm.h:95
bptbl_s::s_idx
int32 s_idx
Start of BScoreStack for various right contexts.
Definition: ngram_search.h:116
acmod_rewind
int acmod_rewind(acmod_t *acmod)
Rewind the current utterance, allowing it to be rescored.
Definition: acmod.c:877
ngram_search_s::word_chan
chan_t ** word_chan
Channels associated with a given word (only used for right contexts, single-phone words in fwdtree se...
Definition: ngram_search.h:246
acmod_s
Acoustic model structure.
Definition: acmod.h:148
ngram_search.h
ps_latlink_s::path_scr
int32 path_scr
Best path score from root of DAG.
Definition: ps_lattice_internal.h:101
ps_segfuncs_s
Definition: pocketsphinx_internal.h:170
ps_latnode_s::sf
frame_idx_t sf
Start frame.
Definition: ps_lattice_internal.h:120
ngram_search_s::lmset
ngram_model_t * lmset
Set of language models.
Definition: ngram_search.h:199
ps_seg_s::lwf
float32 lwf
Language weight factor (for second-pass searches)
Definition: pocketsphinx_internal.h:191
acmod_s::tmat
tmat_t * tmat
Transition matrices.
Definition: acmod.h:160
bptbl_s::valid
uint8 valid
For absolute pruning.
Definition: ngram_search.h:111
bptbl_s::last2_phone
int16 last2_phone
next-to-last phone of this word
Definition: ngram_search.h:120
ngram_search_bp_hyp
const char * ngram_search_bp_hyp(ngram_search_t *ngs, int bpidx)
Backtrace from a given backpointer index to obtain a word hypothesis.
Definition: ngram_search.c:550
WORST_SCORE
#define WORST_SCORE
Large "bad" score.
Definition: hmm.h:84
ngram_search_s::n_frame_alloc
int32 n_frame_alloc
Number of frames allocated in bp_table_idx and friends.
Definition: ngram_search.h:307