• Main Page
  • Related Pages
  • Data Structures
  • Files
  • File List
  • Globals

src/libpocketsphinx/fsg_search.c

00001 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
00002 /* ====================================================================
00003  * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
00004  * reserved.
00005  *
00006  * Redistribution and use in source and binary forms, with or without
00007  * modification, are permitted provided that the following conditions
00008  * are met:
00009  *
00010  * 1. Redistributions of source code must retain the above copyright
00011  *    notice, this list of conditions and the following disclaimer. 
00012  *
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in
00015  *    the documentation and/or other materials provided with the
00016  *    distribution.
00017  *
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
00020  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
00021  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00022  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
00023  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00024  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
00025  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
00026  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
00027  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
00028  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
00029  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00030  *
00031  * ====================================================================
00032  *
00033  */
00034 
00035 /*
00036  * fsg_search.c -- Search structures for FSM decoding.
00037  * 
00038  * **********************************************
00039  * CMU ARPA Speech Project
00040  *
00041  * Copyright (c) 2004 Carnegie Mellon University.
00042  * ALL RIGHTS RESERVED.
00043  * **********************************************
00044  * 
00045  * HISTORY
00046  *
00047  * 18-Feb-2004  M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
00048  *              Started.
00049  */
00050 
00051 /* System headers. */
00052 #include <stdio.h>
00053 #include <string.h>
00054 #include <assert.h>
00055 
00056 /* SphinxBase headers. */
00057 #include <err.h>
00058 #include <ckd_alloc.h>
00059 #include <cmd_ln.h>
00060 
00061 /* Local headers. */
00062 #include "pocketsphinx_internal.h"
00063 #include "ps_lattice_internal.h"
00064 #include "fsg_search_internal.h"
00065 #include "fsg_history.h"
00066 #include "fsg_lextree.h"
00067 
00068 /* Turn this on for detailed debugging dump */
00069 #define __FSG_DBG__             0
00070 #define __FSG_DBG_CHAN__        0
00071 
00072 static ps_seg_t *fsg_search_seg_iter(ps_search_t *search, int32 *out_score);
00073 static ps_lattice_t *fsg_search_lattice(ps_search_t *search);
00074 static int fsg_search_prob(ps_search_t *search);
00075 
00076 static ps_searchfuncs_t fsg_funcs = {
00077     /* name: */   "fsg",
00078     /* start: */  fsg_search_start,
00079     /* step: */   fsg_search_step,
00080     /* finish: */ fsg_search_finish,
00081     /* reinit: */ fsg_search_reinit,
00082     /* free: */   fsg_search_free,
00083     /* lattice: */  fsg_search_lattice,
00084     /* hyp: */      fsg_search_hyp,
00085     /* prob: */     fsg_search_prob,
00086     /* seg_iter: */ fsg_search_seg_iter,
00087 };
00088 
00089 ps_search_t *
00090 fsg_search_init(cmd_ln_t *config,
00091                  acmod_t *acmod,
00092                  dict_t *dict)
00093 {
00094     fsg_search_t *fsgs;
00095     char const *path;
00096 
00097     fsgs = ckd_calloc(1, sizeof(*fsgs));
00098     ps_search_init(ps_search_base(fsgs), &fsg_funcs, config, acmod, dict);
00099 
00100     /* Initialize HMM context. */
00101     fsgs->hmmctx = hmm_context_init(bin_mdef_n_emit_state(acmod->mdef),
00102                                     acmod->tmat->tp, NULL, acmod->mdef->sseq);
00103 
00104     /* Intialize the search history object */
00105     fsgs->history = fsg_history_init(NULL, dict);
00106     fsgs->frame = -1;
00107 
00108     /* Initialize FSG table. */
00109     fsgs->fsgs = hash_table_new(5, FALSE);
00110 
00111     /* Get search pruning parameters */
00112     fsgs->beam_factor = 1.0f;
00113     fsgs->beam = fsgs->beam_orig
00114         = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-beam"));
00115     fsgs->pbeam = fsgs->pbeam_orig
00116         = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-pbeam"));
00117     fsgs->wbeam = fsgs->wbeam_orig
00118         = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-wbeam"));
00119 
00120     /* LM related weights/penalties */
00121     fsgs->lw = cmd_ln_float32_r(config, "-lw");
00122     fsgs->pip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-pip"))
00123                            * fsgs->lw);
00124     fsgs->wip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-wip"))
00125                            * fsgs->lw);
00126 
00127     /* Best path search (and confidence annotation)? */
00128     if (cmd_ln_boolean_r(config, "-bestpath"))
00129         fsgs->bestpath = TRUE;
00130 
00131     /* Acoustic score scale for posterior probabilities. */
00132     fsgs->ascale = 1.0f / cmd_ln_float32_r(config, "-ascale");
00133 
00134     E_INFO("FSG(beam: %d, pbeam: %d, wbeam: %d; wip: %d, pip: %d)\n",
00135            fsgs->beam_orig, fsgs->pbeam_orig, fsgs->wbeam_orig,
00136            fsgs->wip, fsgs->pip);
00137 
00138     /* Load an FSG if one was specified in config */
00139     if ((path = cmd_ln_str_r(config, "-fsg"))) {
00140         fsg_model_t *fsg;
00141 
00142         if ((fsg = fsg_model_readfile(path, acmod->lmath, fsgs->lw)) == NULL)
00143             goto error_out;
00144         if (fsg_set_add(fsgs, fsg_model_name(fsg), fsg) != fsg) {
00145             fsg_model_free(fsg);
00146             goto error_out;
00147         }
00148         if (fsg_set_select(fsgs, fsg_model_name(fsg)) == NULL)
00149             goto error_out;
00150         if (fsg_search_reinit(ps_search_base(fsgs)) < 0)
00151             goto error_out;
00152     }
00153     /* Or load a JSGF grammar */
00154     else if ((path = cmd_ln_str_r(config, "-jsgf"))) {
00155         fsg_model_t *fsg;
00156         jsgf_rule_t *rule;
00157         char const *toprule;
00158 
00159         if ((fsgs->jsgf = jsgf_parse_file(path, NULL)) == NULL)
00160             goto error_out;
00161 
00162         rule = NULL;
00163         /* Take the -toprule if specified. */
00164         if ((toprule = cmd_ln_str_r(config, "-toprule"))) {
00165             char *anglerule;
00166 
00167             anglerule = ckd_calloc(1, strlen(toprule) + 3);
00168             anglerule[0] = '<';
00169             strcat(anglerule, toprule);
00170             strcat(anglerule, ">");
00171             rule = jsgf_get_rule(fsgs->jsgf, anglerule);
00172             ckd_free(anglerule);
00173             if (rule == NULL) {
00174                 E_ERROR("Start rule %s not found\n", toprule);
00175                 goto error_out;
00176             }
00177         }
00178         /* Otherwise, take the first public rule. */
00179         else {
00180             jsgf_rule_iter_t *itor;
00181 
00182             for (itor = jsgf_rule_iter(fsgs->jsgf); itor;
00183                  itor = jsgf_rule_iter_next(itor)) {
00184                 rule = jsgf_rule_iter_rule(itor);
00185                 if (jsgf_rule_public(rule))
00186                     break;
00187             }
00188             if (rule == NULL) {
00189                 E_ERROR("No public rules found in %s\n", path);
00190                 goto error_out;
00191             }
00192         }
00193         fsg = jsgf_build_fsg(fsgs->jsgf, rule, acmod->lmath, fsgs->lw);
00194         if (fsg_set_add(fsgs, fsg_model_name(fsg), fsg) != fsg) {
00195             fsg_model_free(fsg);
00196             goto error_out;
00197         }
00198         if (fsg_set_select(fsgs, fsg_model_name(fsg)) == NULL)
00199             goto error_out;
00200         if (fsg_search_reinit(ps_search_base(fsgs)) < 0)
00201             goto error_out;
00202     }
00203 
00204     return ps_search_base(fsgs);
00205 
00206 error_out:
00207     fsg_search_free(ps_search_base(fsgs));
00208     return NULL;
00209 }
00210 
00211 void
00212 fsg_search_free(ps_search_t *search)
00213 {
00214     fsg_search_t *fsgs = (fsg_search_t *)search;
00215     hash_iter_t *itor;
00216 
00217     ps_search_deinit(search);
00218     if (fsgs->jsgf)
00219         jsgf_grammar_free(fsgs->jsgf);
00220     fsg_lextree_free(fsgs->lextree);
00221     fsg_history_reset(fsgs->history);
00222     fsg_history_set_fsg(fsgs->history, NULL, NULL);
00223     for (itor = hash_table_iter(fsgs->fsgs);
00224          itor; itor = hash_table_iter_next(itor)) {
00225         fsg_model_t *fsg = (fsg_model_t *) hash_entry_val(itor->ent);
00226         fsg_model_free(fsg);
00227     }
00228     hash_table_free(fsgs->fsgs);
00229     fsg_history_free(fsgs->history);
00230     hmm_context_free(fsgs->hmmctx);
00231     ckd_free(fsgs);
00232 }
00233 
00234 int
00235 fsg_search_reinit(ps_search_t *search)
00236 {
00237     fsg_search_t *fsgs = (fsg_search_t *)search;
00238 
00239     /* Free the old lextree */
00240     if (fsgs->lextree)
00241         fsg_lextree_free(fsgs->lextree);
00242 
00243     /* Allocate new lextree for the given FSG */
00244     fsgs->lextree = fsg_lextree_init(fsgs->fsg, ps_search_dict(fsgs),
00245                                      ps_search_acmod(fsgs)->mdef,
00246                                      fsgs->hmmctx, fsgs->wip, fsgs->pip);
00247 
00248     /* Inform the history module of the new fsg */
00249     fsg_history_set_fsg(fsgs->history, fsgs->fsg, ps_search_dict(fsgs));
00250 
00251     return 0;
00252 }
00253 
00254 
00255 static int
00256 fsg_search_add_silences(fsg_search_t *fsgs, fsg_model_t *fsg)
00257 {
00258     dict_t *dict;
00259     int32 wid;
00260     int n_sil;
00261 
00262     dict = ps_search_dict(fsgs);
00263     /*
00264      * NOTE: Unlike N-Gram search, we do not use explicit start and
00265      * end symbols.  This is because the start and end nodes are
00266      * defined in the grammar.  We do add silence/filler self-loops to
00267      * all states in order to allow for silence between words and at
00268      * the beginning and end of utterances.
00269      *
00270      * This has some implications for word graph generation, namely,
00271      * that there can (and usually will) be multiple start and end
00272      * states in the word graph.  We therefore do add explicit start
00273      * and end nodes to the graph.
00274      */
00275     /* Add silence self-loops to all states. */
00276     fsg_model_add_silence(fsg, "<sil>", -1,
00277                           cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"));
00278     n_sil = 0;
00279     /* Add self-loops for all other fillers. */
00280     for (wid = dict_to_id(dict, "<sil>") + 1; wid < dict_n_words(dict); ++wid) {
00281         char const *word = dict_word_str(dict, wid);
00282         /* FIXME: Shouldn't happen?  Also we need a better way to mark fillers. */
00283         if (0 == strcmp(word, "<s>") || 0 == strcmp(word, "</s>")) {
00284             E_ERROR("WTF, %s=%d > <sil>=%d\n", word, wid, dict_to_id(dict, "<sil>"));
00285             continue;
00286         }
00287         fsg_model_add_silence(fsg, word, -1,
00288                               cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"));
00289         ++n_sil;
00290     }
00291 
00292     return n_sil;
00293 }
00294 
00295 static int
00296 fsg_search_add_altpron(fsg_search_t *fsgs, fsg_model_t *fsg)
00297 {
00298     dict_t *dict;
00299     int n_alt;
00300     int i;
00301 
00302     dict = ps_search_dict(fsgs);
00303     /* Scan FSG's vocabulary for words that have alternate pronunciations. */
00304     n_alt = 0;
00305     for (i = 0; i < fsg_model_n_word(fsg); ++i) {
00306         char const *word;
00307         int32 wid;
00308 
00309         word = fsg_model_word_str(fsg, i);
00310         wid = dict_to_id(dict, word);
00311         if (wid != NO_WORD) {
00312             while ((wid = dict_next_alt(dict, wid)) != NO_WORD) {
00313                 fsg_model_add_alt(fsg, word, dict_word_str(dict, wid));
00314                 ++n_alt;
00315             }
00316         }
00317     }
00318 
00319     return n_alt;
00320 }
00321 
00322 fsg_model_t *
00323 fsg_set_get_fsg(fsg_search_t *fsgs, const char *name)
00324 {
00325     void *val;
00326 
00327     if (hash_table_lookup(fsgs->fsgs, name, &val) < 0)
00328         return NULL;
00329     return (fsg_model_t *)val;
00330 }
00331 
00332 fsg_model_t *
00333 fsg_set_add(fsg_search_t *fsgs, char const *name, fsg_model_t *fsg)
00334 {
00335     if (name == NULL)
00336         name = fsg_model_name(fsg);
00337 
00338     /* Add silence transitions and alternate words. */
00339     if (cmd_ln_boolean_r(ps_search_config(fsgs), "-fsgusefiller")
00340         && !fsg_model_has_sil(fsg))
00341         fsg_search_add_silences(fsgs, fsg);
00342     if (cmd_ln_boolean_r(ps_search_config(fsgs), "-fsgusealtpron")
00343         && !fsg_model_has_alt(fsg))
00344         fsg_search_add_altpron(fsgs, fsg);
00345 
00346     return (fsg_model_t *)hash_table_enter(fsgs->fsgs, name, fsg);
00347 }
00348 
00349 
00350 fsg_model_t *
00351 fsg_set_remove_byname(fsg_search_t *fsgs, char const *key)
00352 {
00353     fsg_model_t *oldfsg;
00354     void *val;
00355 
00356     /* Look for the matching FSG. */
00357     if (hash_table_lookup(fsgs->fsgs, key, &val) < 0) {
00358         E_ERROR("FSG `%s' to be deleted not found\n", key);
00359         return NULL;
00360     }
00361     oldfsg = val;
00362 
00363     /* Remove it from the FSG table. */
00364     hash_table_delete(fsgs->fsgs, key);
00365     /* If this was the currently active FSG, also delete other stuff */
00366     if (fsgs->fsg == oldfsg) {
00367         fsg_lextree_free(fsgs->lextree);
00368         fsgs->lextree = NULL;
00369         fsg_history_set_fsg(fsgs->history, NULL, NULL);
00370         fsgs->fsg = NULL;
00371     }
00372     return oldfsg;
00373 }
00374 
00375 
00376 fsg_model_t *
00377 fsg_set_remove(fsg_search_t *fsgs, fsg_model_t *fsg)
00378 {
00379     char const *key;
00380     hash_iter_t *itor;
00381 
00382     key = NULL;
00383     for (itor = hash_table_iter(fsgs->fsgs);
00384          itor; itor = hash_table_iter_next(itor)) {
00385         fsg_model_t *oldfsg;
00386 
00387         oldfsg = (fsg_model_t *) hash_entry_val(itor->ent);
00388         if (oldfsg == fsg) {
00389             key = hash_entry_key(itor->ent);
00390             hash_table_iter_free(itor);
00391             break;
00392         }
00393     }
00394     if (key == NULL) {
00395         E_WARN("FSG '%s' to be deleted not found\n", fsg_model_name(fsg));
00396         return NULL;
00397     }
00398     else
00399         return fsg_set_remove_byname(fsgs, key);
00400 }
00401 
00402 
00403 fsg_model_t *
00404 fsg_set_select(fsg_search_t *fsgs, const char *name)
00405 {
00406     fsg_model_t *fsg;
00407 
00408     fsg = fsg_set_get_fsg(fsgs, name);
00409     if (fsg == NULL) {
00410         E_ERROR("FSG '%s' not known; cannot make it current\n", name);
00411         return NULL;
00412     }
00413     fsgs->fsg = fsg;
00414     return fsg;
00415 }
00416 
00417 fsg_set_iter_t *
00418 fsg_set_iter(fsg_set_t *fsgs)
00419 {
00420     return hash_table_iter(fsgs->fsgs);
00421 }
00422 
00423 fsg_set_iter_t *
00424 fsg_set_iter_next(fsg_set_iter_t *itor)
00425 {
00426     return hash_table_iter_next(itor);
00427 }
00428 
00429 fsg_model_t *
00430 fsg_set_iter_fsg(fsg_set_iter_t *itor)
00431 {
00432     return ((fsg_model_t *)itor->ent->val);
00433 }
00434 
00435 void
00436 fsg_set_iter_free(fsg_set_iter_t *itor)
00437 {
00438     hash_table_iter_free(itor);
00439 }
00440 
00441 static void
00442 fsg_search_sen_active(fsg_search_t *fsgs)
00443 {
00444     gnode_t *gn;
00445     fsg_pnode_t *pnode;
00446     hmm_t *hmm;
00447 
00448     acmod_clear_active(ps_search_acmod(fsgs));
00449 
00450     for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
00451         pnode = (fsg_pnode_t *) gnode_ptr(gn);
00452         hmm = fsg_pnode_hmmptr(pnode);
00453         assert(hmm_frame(hmm) == fsgs->frame);
00454         acmod_activate_hmm(ps_search_acmod(fsgs), hmm);
00455     }
00456 }
00457 
00458 
00459 /*
00460  * Evaluate all the active HMMs.
00461  * (Executed once per frame.)
00462  */
00463 static void
00464 fsg_search_hmm_eval(fsg_search_t *fsgs)
00465 {
00466     gnode_t *gn;
00467     fsg_pnode_t *pnode;
00468     hmm_t *hmm;
00469     int32 bestscore;
00470     int32 n, maxhmmpf;
00471 
00472     bestscore = WORST_SCORE;
00473 
00474     if (!fsgs->pnode_active) {
00475         E_ERROR("Frame %d: No active HMM!!\n", fsgs->frame);
00476         return;
00477     }
00478 
00479     for (n = 0, gn = fsgs->pnode_active; gn; gn = gnode_next(gn), n++) {
00480         int32 score;
00481 
00482         pnode = (fsg_pnode_t *) gnode_ptr(gn);
00483         hmm = fsg_pnode_hmmptr(pnode);
00484         assert(hmm_frame(hmm) == fsgs->frame);
00485 
00486 #if __FSG_DBG__
00487         E_INFO("pnode(%08x) active @frm %5d\n", (int32) pnode,
00488                fsgs->frame);
00489         hmm_dump(hmm, stdout);
00490 #endif
00491         score = hmm_vit_eval(hmm);
00492 #if __FSG_DBG_CHAN__
00493         E_INFO("pnode(%08x) after eval @frm %5d\n",
00494                (int32) pnode, fsgs->frame);
00495         hmm_dump(hmm, stdout);
00496 #endif
00497 
00498         if (bestscore < score)
00499             bestscore = score;
00500     }
00501 
00502 #if __FSG_DBG__
00503     E_INFO("[%5d] %6d HMM; bestscr: %11d\n", fsgs->frame, n, bestscore);
00504 #endif
00505     fsgs->n_hmm_eval += n;
00506 
00507     /* Adjust beams if #active HMMs larger than absolute threshold */
00508     maxhmmpf = cmd_ln_int32_r(ps_search_config(fsgs), "-maxhmmpf");
00509     if (maxhmmpf != -1 && n > maxhmmpf) {
00510         /*
00511          * Too many HMMs active; reduce the beam factor applied to the default
00512          * beams, but not if the factor is already at a floor (0.1).
00513          */
00514         if (fsgs->beam_factor > 0.1) {        /* Hack!!  Hardwired constant 0.1 */
00515             fsgs->beam_factor *= 0.9f;        /* Hack!!  Hardwired constant 0.9 */
00516             fsgs->beam =
00517                 (int32) (fsgs->beam_orig * fsgs->beam_factor);
00518             fsgs->pbeam =
00519                 (int32) (fsgs->pbeam_orig * fsgs->beam_factor);
00520             fsgs->wbeam =
00521                 (int32) (fsgs->wbeam_orig * fsgs->beam_factor);
00522         }
00523     }
00524     else {
00525         fsgs->beam_factor = 1.0f;
00526         fsgs->beam = fsgs->beam_orig;
00527         fsgs->pbeam = fsgs->pbeam_orig;
00528         fsgs->wbeam = fsgs->wbeam_orig;
00529     }
00530 
00531     if (n > fsg_lextree_n_pnode(fsgs->lextree))
00532         E_FATAL("PANIC! Frame %d: #HMM evaluated(%d) > #PNodes(%d)\n",
00533                 fsgs->frame, n, fsg_lextree_n_pnode(fsgs->lextree));
00534 
00535     fsgs->bestscore = bestscore;
00536 }
00537 
00538 
00539 static void
00540 fsg_search_pnode_trans(fsg_search_t *fsgs, fsg_pnode_t * pnode)
00541 {
00542     fsg_pnode_t *child;
00543     hmm_t *hmm;
00544     int32 newscore, thresh, nf;
00545 
00546     assert(pnode);
00547     assert(!fsg_pnode_leaf(pnode));
00548 
00549     nf = fsgs->frame + 1;
00550     thresh = fsgs->bestscore + fsgs->beam;
00551 
00552     hmm = fsg_pnode_hmmptr(pnode);
00553 
00554     for (child = fsg_pnode_succ(pnode);
00555          child; child = fsg_pnode_sibling(child)) {
00556         newscore = hmm_out_score(hmm) + child->logs2prob;
00557 
00558         if ((newscore >= thresh) && (newscore > hmm_in_score(&child->hmm))) {
00559             /* Incoming score > pruning threshold and > target's existing score */
00560             if (hmm_frame(&child->hmm) < nf) {
00561                 /* Child node not yet activated; do so */
00562                 fsgs->pnode_active_next =
00563                     glist_add_ptr(fsgs->pnode_active_next,
00564                                   (void *) child);
00565             }
00566 
00567             hmm_enter(&child->hmm, newscore, hmm_out_history(hmm), nf);
00568         }
00569     }
00570 }
00571 
00572 
00573 static void
00574 fsg_search_pnode_exit(fsg_search_t *fsgs, fsg_pnode_t * pnode)
00575 {
00576     hmm_t *hmm;
00577     fsg_link_t *fl;
00578     int32 wid;
00579     fsg_pnode_ctxt_t ctxt;
00580 
00581     assert(pnode);
00582     assert(fsg_pnode_leaf(pnode));
00583 
00584     hmm = fsg_pnode_hmmptr(pnode);
00585     fl = fsg_pnode_fsglink(pnode);
00586     assert(fl);
00587 
00588     wid = fsg_link_wid(fl);
00589     assert(wid >= 0);
00590 
00591 #if __FSG_DBG__
00592     E_INFO("[%5d] Exit(%08x) %10d(score) %5d(pred)\n",
00593            fsgs->frame, (int32) pnode,
00594            hmm_out_score(hmm), hmm_out_history(hmm));
00595 #endif
00596 
00597     /*
00598      * Check if this is filler or single phone word; these do not model right
00599      * context (i.e., the exit score applies to all right contexts).
00600      */
00601     if (fsg_model_is_filler(fsgs->fsg, wid)
00602         /* FIXME: This might be slow due to repeated calls to dict_to_id(). */
00603         || (dict_pronlen(ps_search_dict(fsgs),
00604                          dict_to_id(ps_search_dict(fsgs),
00605                                     fsg_model_word_str(fsgs->fsg, wid))) == 1)) {
00606         /* Create a dummy context structure that applies to all right contexts */
00607         fsg_pnode_add_all_ctxt(&ctxt);
00608 
00609         /* Create history table entry for this word exit */
00610         fsg_history_entry_add(fsgs->history,
00611                               fl,
00612                               fsgs->frame,
00613                               hmm_out_score(hmm),
00614                               hmm_out_history(hmm),
00615                               pnode->ci_ext, ctxt);
00616 
00617     }
00618     else {
00619         /* Create history table entry for this word exit */
00620         fsg_history_entry_add(fsgs->history,
00621                               fl,
00622                               fsgs->frame,
00623                               hmm_out_score(hmm),
00624                               hmm_out_history(hmm),
00625                               pnode->ci_ext, pnode->ctxt);
00626     }
00627 }
00628 
00629 
00630 /*
00631  * (Beam) prune the just evaluated HMMs, determine which ones remain
00632  * active, which ones transition to successors, which ones exit and
00633  * terminate in their respective destination FSM states.
00634  * (Executed once per frame.)
00635  */
00636 static void
00637 fsg_search_hmm_prune_prop(fsg_search_t *fsgs)
00638 {
00639     gnode_t *gn;
00640     fsg_pnode_t *pnode;
00641     hmm_t *hmm;
00642     int32 thresh, word_thresh, phone_thresh;
00643 
00644     assert(fsgs->pnode_active_next == NULL);
00645 
00646     thresh = fsgs->bestscore + fsgs->beam;
00647     phone_thresh = fsgs->bestscore + fsgs->pbeam;
00648     word_thresh = fsgs->bestscore + fsgs->wbeam;
00649 
00650     for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
00651         pnode = (fsg_pnode_t *) gnode_ptr(gn);
00652         hmm = fsg_pnode_hmmptr(pnode);
00653 
00654         if (hmm_bestscore(hmm) >= thresh) {
00655             /* Keep this HMM active in the next frame */
00656             if (hmm_frame(hmm) == fsgs->frame) {
00657                 hmm_frame(hmm) = fsgs->frame + 1;
00658                 fsgs->pnode_active_next =
00659                     glist_add_ptr(fsgs->pnode_active_next,
00660                                   (void *) pnode);
00661             }
00662             else {
00663                 assert(hmm_frame(hmm) == fsgs->frame + 1);
00664             }
00665 
00666             if (!fsg_pnode_leaf(pnode)) {
00667                 if (hmm_out_score(hmm) >= phone_thresh) {
00668                     /* Transition out of this phone into its children */
00669                     fsg_search_pnode_trans(fsgs, pnode);
00670                 }
00671             }
00672             else {
00673                 if (hmm_out_score(hmm) >= word_thresh) {
00674                     /* Transition out of leaf node into destination FSG state */
00675                     fsg_search_pnode_exit(fsgs, pnode);
00676                 }
00677             }
00678         }
00679     }
00680 }
00681 
00682 
00683 /*
00684  * Propagate newly created history entries through null transitions.
00685  */
00686 static void
00687 fsg_search_null_prop(fsg_search_t *fsgs)
00688 {
00689     int32 bpidx, n_entries, thresh, newscore;
00690     fsg_hist_entry_t *hist_entry;
00691     fsg_link_t *l;
00692     int32 s, d;
00693     fsg_model_t *fsg;
00694 
00695     fsg = fsgs->fsg;
00696     thresh = fsgs->bestscore + fsgs->wbeam; /* Which beam really?? */
00697 
00698     n_entries = fsg_history_n_entries(fsgs->history);
00699 
00700     for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
00701         hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
00702 
00703         l = fsg_hist_entry_fsglink(hist_entry);
00704 
00705         /* Destination FSG state for history entry */
00706         s = l ? fsg_link_to_state(l) : fsg_model_start_state(fsg);
00707 
00708         /*
00709          * Check null transitions from d to all other states.  (Only need to
00710          * propagate one step, since FSG contains transitive closure of null
00711          * transitions.)
00712          */
00713         for (d = 0; d < fsg_model_n_state(fsg); d++) {
00714             l = fsg_model_null_trans(fsg, s, d);
00715 
00716             if (l) {            /* Propagate history entry through this null transition */
00717                 newscore =
00718                     fsg_hist_entry_score(hist_entry) +
00719                     fsg_link_logs2prob(l);
00720 
00721                 if (newscore >= thresh) {
00722                     fsg_history_entry_add(fsgs->history, l,
00723                                           fsg_hist_entry_frame(hist_entry),
00724                                           newscore,
00725                                           bpidx,
00726                                           fsg_hist_entry_lc(hist_entry),
00727                                           fsg_hist_entry_rc(hist_entry));
00728                 }
00729             }
00730         }
00731     }
00732 }
00733 
00734 
00735 /*
00736  * Perform cross-word transitions; propagate each history entry created in this
00737  * frame to lextree roots attached to the target FSG state for that entry.
00738  */
00739 static void
00740 fsg_search_word_trans(fsg_search_t *fsgs)
00741 {
00742     int32 bpidx, n_entries;
00743     fsg_hist_entry_t *hist_entry;
00744     fsg_link_t *l;
00745     int32 score, newscore, thresh, nf, d;
00746     fsg_pnode_t *root;
00747     int32 lc, rc;
00748 
00749     n_entries = fsg_history_n_entries(fsgs->history);
00750 
00751     thresh = fsgs->bestscore + fsgs->beam;
00752     nf = fsgs->frame + 1;
00753 
00754     for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
00755         hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
00756         assert(hist_entry);
00757         score = fsg_hist_entry_score(hist_entry);
00758         assert(fsgs->frame == fsg_hist_entry_frame(hist_entry));
00759 
00760         l = fsg_hist_entry_fsglink(hist_entry);
00761 
00762         /* Destination state for hist_entry */
00763         d = l ? fsg_link_to_state(l) : fsg_model_start_state(fsgs->
00764                                                                 fsg);
00765 
00766         lc = fsg_hist_entry_lc(hist_entry);
00767 
00768         /* Transition to all root nodes attached to state d */
00769         for (root = fsg_lextree_root(fsgs->lextree, d);
00770              root; root = root->sibling) {
00771             rc = root->ci_ext;
00772 
00773             if ((root->ctxt.bv[lc >> 5] & (1 << (lc & 0x001f))) &&
00774                 (hist_entry->rc.bv[rc >> 5] & (1 << (rc & 0x001f)))) {
00775                 /*
00776                  * Last CIphone of history entry is in left-context list supported by
00777                  * target root node, and
00778                  * first CIphone of target root node is in right context list supported
00779                  * by history entry;
00780                  * So the transition can go ahead (if new score is good enough).
00781                  */
00782                 newscore = score + root->logs2prob;
00783 
00784                 if ((newscore >= thresh)
00785                     && (newscore > hmm_in_score(&root->hmm))) {
00786                     if (hmm_frame(&root->hmm) < nf) {
00787                         /* Newly activated node; add to active list */
00788                         fsgs->pnode_active_next =
00789                             glist_add_ptr(fsgs->pnode_active_next,
00790                                           (void *) root);
00791 #if __FSG_DBG__
00792                         E_INFO
00793                             ("[%5d] WordTrans bpidx[%d] -> pnode[%08x] (activated)\n",
00794                              fsgs->frame, bpidx, (int32) root);
00795 #endif
00796                     }
00797                     else {
00798 #if __FSG_DBG__
00799                         E_INFO
00800                             ("[%5d] WordTrans bpidx[%d] -> pnode[%08x]\n",
00801                              fsgs->frame, bpidx, (int32) root);
00802 #endif
00803                     }
00804 
00805                     hmm_enter(&root->hmm, newscore, bpidx, nf);
00806                 }
00807             }
00808         }
00809     }
00810 }
00811 
00812 
00813 int
00814 fsg_search_step(ps_search_t *search)
00815 {
00816     fsg_search_t *fsgs = (fsg_search_t *)search;
00817     int16 const *senscr;
00818     int frame_idx, best_senid;
00819     int16 best_senscr;
00820     acmod_t *acmod = search->acmod;
00821     gnode_t *gn;
00822     fsg_pnode_t *pnode;
00823     hmm_t *hmm;
00824 
00825     /* Determine if we actually have a frame to process. */
00826     if (acmod->n_feat_frame == 0)
00827         return 0;
00828 
00829     /* Activate our HMMs for the current frame if need be. */
00830     if (!acmod->compallsen)
00831         fsg_search_sen_active(fsgs);
00832     /* Compute GMM scores for the current frame. */
00833     senscr = acmod_score(acmod, &frame_idx, &best_senscr, &best_senid);
00834     fsgs->n_sen_eval += acmod->n_senone_active;
00835     hmm_context_set_senscore(fsgs->hmmctx, senscr);
00836 
00837     /* Mark backpointer table for current frame. */
00838     fsgs->bpidx_start = fsg_history_n_entries(fsgs->history);
00839 
00840     /* Evaluate all active pnodes (HMMs) */
00841     fsg_search_hmm_eval(fsgs);
00842 
00843     /*
00844      * Prune and propagate the HMMs evaluated; create history entries for
00845      * word exits.  The words exits are tentative, and may be pruned; make
00846      * the survivors permanent via fsg_history_end_frame().
00847      */
00848     fsg_search_hmm_prune_prop(fsgs);
00849     fsg_history_end_frame(fsgs->history);
00850 
00851     /*
00852      * Propagate new history entries through any null transitions, creating
00853      * new history entries, and then make the survivors permanent.
00854      */
00855     fsg_search_null_prop(fsgs);
00856     fsg_history_end_frame(fsgs->history);
00857 
00858     /*
00859      * Perform cross-word transitions; propagate each history entry across its
00860      * terminating state to the root nodes of the lextree attached to the state.
00861      */
00862     fsg_search_word_trans(fsgs);
00863 
00864     /*
00865      * We've now come full circle, HMM and FSG states have been updated for
00866      * the next frame.
00867      * Update the active lists, deactivate any currently active HMMs that
00868      * did not survive into the next frame
00869      */
00870     for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
00871         pnode = (fsg_pnode_t *) gnode_ptr(gn);
00872         hmm = fsg_pnode_hmmptr(pnode);
00873 
00874         if (hmm_frame(hmm) == fsgs->frame) {
00875             /* This HMM NOT activated for the next frame; reset it */
00876             fsg_psubtree_pnode_deactivate(pnode);
00877         }
00878         else {
00879             assert(hmm_frame(hmm) == (fsgs->frame + 1));
00880         }
00881     }
00882 
00883     /* Free the currently active list */
00884     glist_free(fsgs->pnode_active);
00885 
00886     /* Make the next-frame active list the current one */
00887     fsgs->pnode_active = fsgs->pnode_active_next;
00888     fsgs->pnode_active_next = NULL;
00889 
00890     /* End of this frame; ready for the next */
00891     ++fsgs->frame;
00892 
00893     return 1;
00894 }
00895 
00896 
00897 /*
00898  * Set all HMMs to inactive, clear active lists, initialize FSM start
00899  * state to be the only active node.
00900  * (Executed at the start of each utterance.)
00901  */
00902 int
00903 fsg_search_start(ps_search_t *search)
00904 {
00905     fsg_search_t *fsgs = (fsg_search_t *)search;
00906     int32 silcipid;
00907     fsg_pnode_ctxt_t ctxt;
00908 
00909     /* Reset dynamic adjustment factor for beams */
00910     fsgs->beam_factor = 1.0f;
00911     fsgs->beam = fsgs->beam_orig;
00912     fsgs->pbeam = fsgs->pbeam_orig;
00913     fsgs->wbeam = fsgs->wbeam_orig;
00914 
00915     silcipid = bin_mdef_ciphone_id(ps_search_acmod(fsgs)->mdef, "SIL");
00916 
00917     /* Initialize EVERYTHING to be inactive */
00918     assert(fsgs->pnode_active == NULL);
00919     assert(fsgs->pnode_active_next == NULL);
00920 
00921     fsg_history_reset(fsgs->history);
00922     fsg_history_utt_start(fsgs->history);
00923     fsgs->final = FALSE;
00924 
00925     /* Dummy context structure that allows all right contexts to use this entry */
00926     fsg_pnode_add_all_ctxt(&ctxt);
00927 
00928     /* Create dummy history entry leading to start state */
00929     fsgs->frame = -1;
00930     fsgs->bestscore = 0;
00931     fsg_history_entry_add(fsgs->history,
00932                           NULL, -1, 0, -1, silcipid, ctxt);
00933     fsgs->bpidx_start = 0;
00934 
00935     /* Propagate dummy history entry through NULL transitions from start state */
00936     fsg_search_null_prop(fsgs);
00937 
00938     /* Perform word transitions from this dummy history entry */
00939     fsg_search_word_trans(fsgs);
00940 
00941     /* Make the next-frame active list the current one */
00942     fsgs->pnode_active = fsgs->pnode_active_next;
00943     fsgs->pnode_active_next = NULL;
00944 
00945     ++fsgs->frame;
00946 
00947     fsgs->n_hmm_eval = 0;
00948     fsgs->n_sen_eval = 0;
00949 
00950     return 0;
00951 }
00952 
00953 /*
00954  * Cleanup at the end of each utterance.
00955  */
00956 int
00957 fsg_search_finish(ps_search_t *search)
00958 {
00959     fsg_search_t *fsgs = (fsg_search_t *)search;
00960     gnode_t *gn;
00961     fsg_pnode_t *pnode;
00962     int32 n_hist;
00963 
00964     /* Deactivate all nodes in the current and next-frame active lists */
00965     for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
00966         pnode = (fsg_pnode_t *) gnode_ptr(gn);
00967         fsg_psubtree_pnode_deactivate(pnode);
00968     }
00969     for (gn = fsgs->pnode_active_next; gn; gn = gnode_next(gn)) {
00970         pnode = (fsg_pnode_t *) gnode_ptr(gn);
00971         fsg_psubtree_pnode_deactivate(pnode);
00972     }
00973 
00974     glist_free(fsgs->pnode_active);
00975     fsgs->pnode_active = NULL;
00976     glist_free(fsgs->pnode_active_next);
00977     fsgs->pnode_active_next = NULL;
00978 
00979     fsgs->final = TRUE;
00980 
00981     n_hist = fsg_history_n_entries(fsgs->history);
00982     E_INFO
00983         ("%d frames, %d HMMs (%d/fr), %d senones (%d/fr), %d history entries (%d/fr)\n\n",
00984          fsgs->frame, fsgs->n_hmm_eval,
00985          (fsgs->frame > 0) ? fsgs->n_hmm_eval / fsgs->frame : 0,
00986          fsgs->n_sen_eval,
00987          (fsgs->frame > 0) ? fsgs->n_sen_eval / fsgs->frame : 0,
00988          n_hist, (fsgs->frame > 0) ? n_hist / fsgs->frame : 0);
00989 
00990     /* Sanity check */
00991     if (fsgs->n_hmm_eval >
00992         fsg_lextree_n_pnode(fsgs->lextree) * fsgs->frame) {
00993         E_ERROR
00994             ("SANITY CHECK #HMMEval(%d) > %d (#HMMs(%d)*#frames(%d)) FAILED\n",
00995              fsgs->n_hmm_eval,
00996              fsg_lextree_n_pnode(fsgs->lextree) * fsgs->frame,
00997              fsg_lextree_n_pnode(fsgs->lextree), fsgs->frame);
00998     }
00999 
01000     return 0;
01001 }
01002 
01003 static int
01004 fsg_search_find_exit(fsg_search_t *fsgs, int frame_idx, int final, int32 *out_score)
01005 {
01006     fsg_hist_entry_t *hist_entry;
01007     fsg_model_t *fsg;
01008     int bpidx, frm, last_frm, besthist;
01009     int32 bestscore;
01010 
01011     if (frame_idx == -1)
01012         frame_idx = fsgs->frame - 1;
01013     last_frm = frm = frame_idx;
01014 
01015     /* Scan backwards to find a word exit in frame_idx. */
01016     bpidx = fsg_history_n_entries(fsgs->history) - 1;
01017     while (bpidx > 0) {
01018         hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
01019         if (fsg_hist_entry_frame(hist_entry) <= frame_idx) {
01020             frm = last_frm = fsg_hist_entry_frame(hist_entry);
01021             break;
01022         }
01023     }
01024 
01025     /* No hypothesis (yet). */
01026     if (bpidx <= 0) 
01027         return bpidx;
01028 
01029     /* Now find best word exit in this frame. */
01030     bestscore = INT_MIN;
01031     besthist = -1;
01032     fsg = fsgs->fsg;
01033     while (frm == last_frm) {
01034         fsg_link_t *fl;
01035         int32 score;
01036 
01037         fl = fsg_hist_entry_fsglink(hist_entry);
01038         score = fsg_hist_entry_score(hist_entry);
01039 
01040         if (score > bestscore) {
01041             /* Only enforce the final state constraint if this is a final hypothesis. */
01042             if ((!final)
01043                 || fsg_link_to_state(fl) == fsg_model_final_state(fsg)) {
01044                 bestscore = score;
01045                 besthist = bpidx;
01046             }
01047         }
01048 
01049         --bpidx;
01050         if (bpidx < 0)
01051             break;
01052         hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
01053         frm = fsg_hist_entry_frame(hist_entry);
01054     }
01055 
01056     /* Final state not reached. */
01057     if (besthist == -1) {
01058         E_ERROR("Final state not reached in frame %d\n", frame_idx);
01059         return -1;
01060     }
01061 
01062     /* This here's the one we want. */
01063     if (out_score)
01064         *out_score = bestscore;
01065     return besthist;
01066 }
01067 
01068 /* FIXME: Mostly duplicated with ngram_search_bestpath(). */
01069 static ps_latlink_t *
01070 fsg_search_bestpath(ps_search_t *search, int32 *out_score, int backward)
01071 {
01072     fsg_search_t *fsgs = (fsg_search_t *)search;
01073 
01074     if (search->last_link == NULL) {
01075         search->last_link = ps_lattice_bestpath(search->dag, NULL,
01076                                                 1.0, fsgs->ascale);
01077         if (search->last_link == NULL)
01078             return NULL;
01079         /* Also calculate betas so we can fill in the posterior
01080          * probability field in the segmentation. */
01081         if (search->post == 0)
01082             search->post = ps_lattice_posterior(search->dag, NULL, fsgs->ascale);
01083     }
01084     if (out_score)
01085         *out_score = search->last_link->path_scr + search->dag->final_node_ascr;
01086     return search->last_link;
01087 }
01088 
01089 char const *
01090 fsg_search_hyp(ps_search_t *search, int32 *out_score)
01091 {
01092     fsg_search_t *fsgs = (fsg_search_t *)search;
01093     char *c;
01094     size_t len;
01095     int bp, bpidx;
01096 
01097     /* Get last backpointer table index. */
01098     bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score);
01099     /* No hypothesis (yet). */
01100     if (bpidx <= 0)
01101         return NULL;
01102 
01103     /* If bestpath is enabled and the utterance is complete, then run it. */
01104     if (fsgs->bestpath && fsgs->final) {
01105         ps_lattice_t *dag;
01106         ps_latlink_t *link;
01107 
01108         if ((dag = fsg_search_lattice(search)) == NULL)
01109             return NULL;
01110         if ((link = fsg_search_bestpath(search, out_score, FALSE)) == NULL)
01111             return NULL;
01112         return ps_lattice_hyp(dag, link);
01113     }
01114 
01115     bp = bpidx;
01116     len = 0;
01117     while (bp > 0) {
01118         fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
01119         fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
01120         int32 wid;
01121 
01122         bp = fsg_hist_entry_pred(hist_entry);
01123         wid = fsg_link_wid(fl);
01124         if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
01125             continue;
01126         len += strlen(fsg_model_word_str(fsgs->fsg, wid)) + 1;
01127     }
01128 
01129     ckd_free(search->hyp_str);
01130     search->hyp_str = ckd_calloc(1, len);
01131     bp = bpidx;
01132     c = search->hyp_str + len - 1;
01133     while (bp > 0) {
01134         fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
01135         fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
01136         int32 wid;
01137 
01138         bp = fsg_hist_entry_pred(hist_entry);
01139         wid = fsg_link_wid(fl);
01140         if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
01141             continue;
01142         len = strlen(fsg_model_word_str(fsgs->fsg, wid));
01143         c -= len;
01144         memcpy(c, fsg_model_word_str(fsgs->fsg, wid), len);
01145         if (c > search->hyp_str) {
01146             --c;
01147             *c = ' ';
01148         }
01149     }
01150 
01151     return search->hyp_str;
01152 }
01153 
01154 static void
01155 fsg_seg_bp2itor(ps_seg_t *seg, fsg_hist_entry_t *hist_entry)
01156 {
01157     fsg_search_t *fsgs = (fsg_search_t *)seg->search;
01158     fsg_hist_entry_t *ph = NULL;
01159     int32 bp;
01160 
01161     if ((bp = fsg_hist_entry_pred(hist_entry)) >= 0)
01162         ph = fsg_history_entry_get(fsgs->history, bp);
01163     seg->word = fsg_model_word_str(fsgs->fsg, hist_entry->fsglink->wid);
01164     seg->ef = fsg_hist_entry_frame(hist_entry);
01165     seg->sf = ph ? fsg_hist_entry_frame(ph) + 1 : 0;
01166     /* This is kind of silly but it happens for null transitions. */
01167     if (seg->sf > seg->ef) seg->sf = seg->ef;
01168     seg->prob = 0; /* Bogus value... */
01169     /* "Language model" score = transition probability. */
01170     seg->lback = 1;
01171     seg->lscr = hist_entry->fsglink->logs2prob;
01172     if (ph) {
01173         /* FIXME: Not sure exactly how cross-word triphones are handled. */
01174         seg->ascr = hist_entry->score - ph->score - seg->lscr;
01175     }
01176     else
01177         seg->ascr = hist_entry->score - seg->lscr;
01178 }
01179 
01180 
01181 static void
01182 fsg_seg_free(ps_seg_t *seg)
01183 {
01184     fsg_seg_t *itor = (fsg_seg_t *)seg;
01185     ckd_free(itor->hist);
01186     ckd_free(itor);
01187 }
01188 
01189 static ps_seg_t *
01190 fsg_seg_next(ps_seg_t *seg)
01191 {
01192     fsg_seg_t *itor = (fsg_seg_t *)seg;
01193 
01194     if (++itor->cur == itor->n_hist) {
01195         fsg_seg_free(seg);
01196         return NULL;
01197     }
01198 
01199     fsg_seg_bp2itor(seg, itor->hist[itor->cur]);
01200     return seg;
01201 }
01202 
01203 static ps_segfuncs_t fsg_segfuncs = {
01204     /* seg_next */ fsg_seg_next,
01205     /* seg_free */ fsg_seg_free
01206 };
01207 
01208 static ps_seg_t *
01209 fsg_search_seg_iter(ps_search_t *search, int32 *out_score)
01210 {
01211     fsg_search_t *fsgs = (fsg_search_t *)search;
01212     fsg_seg_t *itor;
01213     int bp, bpidx, cur;
01214 
01215     bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score);
01216     /* No hypothesis (yet). */
01217     if (bpidx <= 0)
01218         return NULL;
01219 
01220     /* If bestpath is enabled and the utterance is complete, then run it. */
01221     if (fsgs->bestpath && fsgs->final) {
01222         ps_lattice_t *dag;
01223         ps_latlink_t *link;
01224 
01225         if ((dag = fsg_search_lattice(search)) == NULL)
01226             return NULL;
01227         if ((link = fsg_search_bestpath(search, out_score, TRUE)) == NULL)
01228             return NULL;
01229         return ps_lattice_seg_iter(dag, link, 1.0);
01230     }
01231 
01232     /* Calling this an "iterator" is a bit of a misnomer since we have
01233      * to get the entire backtrace in order to produce it.  On the
01234      * other hand, all we actually need is the bptbl IDs, and we can
01235      * allocate a fixed-size array of them. */
01236     itor = ckd_calloc(1, sizeof(*itor));
01237     itor->base.vt = &fsg_segfuncs;
01238     itor->base.search = search;
01239     itor->base.lwf = 1.0;
01240     itor->n_hist = 0;
01241     bp = bpidx;
01242     while (bp > 0) {
01243         fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
01244         bp = fsg_hist_entry_pred(hist_entry);
01245         ++itor->n_hist;
01246     }
01247     if (itor->n_hist == 0) {
01248         ckd_free(itor);
01249         return NULL;
01250     }
01251     itor->hist = ckd_calloc(itor->n_hist, sizeof(*itor->hist));
01252     cur = itor->n_hist - 1;
01253     bp = bpidx;
01254     while (bp > 0) {
01255         fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
01256         itor->hist[cur] = hist_entry;
01257         bp = fsg_hist_entry_pred(hist_entry);
01258         --cur;
01259     }
01260 
01261     /* Fill in relevant fields for first element. */
01262     fsg_seg_bp2itor((ps_seg_t *)itor, itor->hist[0]);
01263     
01264     return (ps_seg_t *)itor;
01265 }
01266 
01267 static int
01268 fsg_search_prob(ps_search_t *search)
01269 {
01270     fsg_search_t *fsgs = (fsg_search_t *)search;
01271 
01272     /* If bestpath is enabled and the utterance is complete, then run it. */
01273     if (fsgs->bestpath && fsgs->final) {
01274         ps_lattice_t *dag;
01275         ps_latlink_t *link;
01276 
01277         if ((dag = fsg_search_lattice(search)) == NULL)
01278             return 0;
01279         if ((link = fsg_search_bestpath(search, NULL, TRUE)) == NULL)
01280             return 0;
01281         return search->post;
01282     }
01283     else {
01284         /* FIXME: Give some kind of good estimate here, eventually. */
01285         return 0;
01286     }
01287 }
01288 
01289 static ps_latnode_t *
01290 new_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int ef, int32 wid, int32 ascr)
01291 {
01292     ps_latnode_t *node;
01293 
01294     for (node = dag->nodes; node; node = node->next)
01295         if (node->sf == sf && node->wid == wid)
01296             break;
01297 
01298     if (node) {
01299         /* Update end frames. */
01300         if (node->lef == -1 || node->lef < ef)
01301             node->lef = ef;
01302         if (node->fef == -1 || node->fef > ef)
01303             node->fef = ef;
01304         /* Update best link score. */
01305         if (node->info.best_exit < ascr)
01306             node->info.best_exit = ascr;
01307     }
01308     else {
01309         /* New node; link to head of list */
01310         node = listelem_malloc(dag->latnode_alloc);
01311         node->wid = wid;
01312         node->sf = sf;
01313         node->fef = node->lef = ef;
01314         node->reachable = FALSE;
01315         node->entries = NULL;
01316         node->exits = NULL;
01317         node->info.best_exit = ascr;
01318 
01319         node->next = dag->nodes;
01320         dag->nodes = node;
01321     }
01322 
01323     return node;
01324 }
01325 
01326 static ps_latnode_t *
01327 find_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int32 wid)
01328 {
01329     ps_latnode_t *node;
01330 
01331     for (node = dag->nodes; node; node = node->next)
01332         if (node->sf == sf && node->wid == wid)
01333             break;
01334     return node;
01335 }
01336 
01337 static ps_latnode_t *
01338 find_start_node(fsg_search_t *fsgs, ps_lattice_t *dag)
01339 {
01340     ps_latnode_t *node;
01341     glist_t start = NULL;
01342     int nstart = 0;
01343 
01344     /* Look for all nodes starting in frame zero with some exits. */
01345     for (node = dag->nodes; node; node = node->next) {
01346         if (node->sf == 0 && node->exits) {
01347             E_INFO("Start node %s.%d:%d:%d\n",
01348                    fsg_model_word_str(fsgs->fsg, node->wid),
01349                    node->sf, node->fef, node->lef);
01350             start = glist_add_ptr(start, node);
01351             ++nstart;
01352         }
01353     }
01354 
01355     /* If there was more than one start node candidate, then we need
01356      * to create an artificial start node with epsilon transitions to
01357      * all of them. */
01358     if (nstart == 1) {
01359         node = gnode_ptr(start);
01360     }
01361     else {
01362         gnode_t *st;
01363         int wid;
01364 
01365         wid = fsg_model_word_add(fsgs->fsg, "<s>");
01366         if (fsgs->fsg->silwords)
01367             bitvec_set(fsgs->fsg->silwords, wid);
01368         node = new_node(dag, fsgs->fsg, 0, 0, wid, 0);
01369         for (st = start; st; st = gnode_next(st))
01370             ps_lattice_link(dag, node, gnode_ptr(st), 0, 0);
01371     }
01372     glist_free(start);
01373     return node;
01374 }
01375 
01376 static ps_latnode_t *
01377 find_end_node(fsg_search_t *fsgs, ps_lattice_t *dag)
01378 {
01379     ps_latnode_t *node;
01380     glist_t end = NULL;
01381     int nend = 0;
01382 
01383     /* Look for all nodes ending in last frame with some entries. */
01384     for (node = dag->nodes; node; node = node->next) {
01385         if (node->lef == dag->n_frames - 1 && node->entries) {
01386             E_INFO("End node %s.%d:%d:%d (%d)\n",
01387                    fsg_model_word_str(fsgs->fsg, node->wid),
01388                    node->sf, node->fef, node->lef, node->info.best_exit);
01389             end = glist_add_ptr(end, node);
01390             ++nend;
01391         }
01392     }
01393 
01394     if (nend == 1) {
01395         node = gnode_ptr(end);
01396     }
01397     else if (nend == 0) {
01398         ps_latnode_t *last = NULL;
01399         int ef = 0;
01400 
01401         /* If there were no end node candidates, then just use the
01402          * node with the last exit frame. */
01403         for (node = dag->nodes; node; node = node->next) {
01404             if (node->lef > ef && node->entries) {
01405                 last = node;
01406                 ef = node->lef;
01407             }
01408         }
01409         node = last;
01410         if (node)
01411             E_INFO("End node %s.%d:%d:%d (%d)\n",
01412                    fsg_model_word_str(fsgs->fsg, node->wid),
01413                    node->sf, node->fef, node->lef, node->info.best_exit);
01414     }    
01415     else {
01416         /* If there was more than one end node candidate, then we need
01417          * to create an artificial end node with epsilon transitions
01418          * out of all of them. */
01419         gnode_t *st;
01420         int wid;
01421 
01422         wid = fsg_model_word_add(fsgs->fsg, "</s>");
01423         if (fsgs->fsg->silwords)
01424             bitvec_set(fsgs->fsg->silwords, wid);
01425         node = new_node(dag, fsgs->fsg, fsgs->frame, fsgs->frame, wid, 0);
01426         /* Use the "best" (in reality it will be the only) exit link
01427          * score from this final node as the link score. */
01428         for (st = end; st; st = gnode_next(st)) {
01429             ps_latnode_t *src = gnode_ptr(st);
01430             ps_lattice_link(dag, src, node, src->info.best_exit, fsgs->frame);
01431         }
01432     }
01433     glist_free(end);
01434     return node;
01435 }
01436 
01437 static void
01438 mark_reachable(ps_lattice_t *dag, ps_latnode_t *end)
01439 {
01440     glist_t q;
01441 
01442     /* It doesn't matter which order we do this in. */
01443     end->reachable = TRUE;
01444     q = glist_add_ptr(NULL, end);
01445     while (q) {
01446         ps_latnode_t *node = gnode_ptr(q);
01447         latlink_list_t *x;
01448 
01449         /* Pop the front of the list. */
01450         q = gnode_free(q, NULL);
01451         /* Expand all its predecessors that haven't been seen yet. */
01452         for (x = node->entries; x; x = x->next) {
01453             ps_latnode_t *next = x->link->from;
01454             if (!next->reachable) {
01455                 next->reachable = TRUE;
01456                 q = glist_add_ptr(q, next);
01457             }
01458         }
01459     }
01460 }
01461 
01470 static ps_lattice_t *
01471 fsg_search_lattice(ps_search_t *search)
01472 {
01473     fsg_search_t *fsgs;
01474     fsg_model_t *fsg;
01475     ps_latnode_t *node;
01476     ps_lattice_t *dag;
01477     int32 i, n;
01478 
01479     fsgs = (fsg_search_t *)search;
01480 
01481     /* Check to see if a lattice has previously been created over the
01482      * same number of frames, and reuse it if so. */
01483     if (search->dag && search->dag->n_frames == fsgs->frame)
01484         return search->dag;
01485 
01486     /* Nope, create a new one. */
01487     ps_lattice_free(search->dag);
01488     search->dag = NULL;
01489     dag = ps_lattice_init_search(search, fsgs->frame);
01490     fsg = fsgs->fsg;
01491 
01492     /*
01493      * Each history table entry represents a link in the word graph.
01494      * The set of nodes is determined by the number of unique
01495      * (word,start-frame) pairs in the history table.  So we will
01496      * first find all those nodes.
01497      */
01498     n = fsg_history_n_entries(fsgs->history);
01499     for (i = 0; i < n; ++i) {
01500         fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
01501         ps_latnode_t *node;
01502         int32 ascr;
01503         int sf;
01504 
01505         /* Skip null transitions. */
01506         if (fh->fsglink == NULL || fh->fsglink->wid == -1)
01507             continue;
01508 
01509         /* Find the start node of this link. */
01510         if (fh->pred) {
01511             fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
01512             /* FIXME: We include the transition score in the lattice
01513              * link score.  This is because of the practical
01514              * difficulty of obtaining it separately in bestpath or
01515              * forward-backward search, and because it is essentially
01516              * a unigram probability, so there is no need to treat it
01517              * separately from the acoustic score.  However, it's not
01518              * clear that this will actually yield correct results.*/
01519             ascr = fh->score - pfh->score;
01520             sf = pfh->frame + 1;
01521         }
01522         else {
01523             ascr = fh->score;
01524             sf = 0;
01525         }
01526 
01527         /*
01528          * Note that although scores are tied to links rather than
01529          * nodes, it's possible that there are no links out of the
01530          * destination node, and thus we need to preserve its score in
01531          * case it turns out to be utterance-final.
01532          */
01533         node = new_node(dag, fsg, sf, fh->frame, fh->fsglink->wid, ascr);
01534     }
01535 
01536     /*
01537      * Now, we will create links only to nodes that actually exist.
01538      */
01539     n = fsg_history_n_entries(fsgs->history);
01540     for (i = 0; i < n; ++i) {
01541         fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
01542         ps_latnode_t *src, *dest;
01543         int32 ascr;
01544         int sf;
01545         int j;
01546 
01547         /* Skip null transitions. */
01548         if (fh->fsglink == NULL || fh->fsglink->wid == -1)
01549             continue;
01550 
01551         /* Find the start node of this link and calculate its link score. */
01552         if (fh->pred) {
01553             fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
01554             sf = pfh->frame + 1;
01555             ascr = fh->score - pfh->score;
01556         }
01557         else {
01558             ascr = fh->score;
01559             sf = 0;
01560         }
01561         src = find_node(dag, fsg, sf, fh->fsglink->wid);
01562     
01563         /*
01564          * For each non-epsilon link following this one, look for a
01565          * matching node in the lattice and link to it.
01566          */
01567         sf = fh->frame + 1;
01568         for (j = 0; j < fsg->n_state; ++j) {
01569             gnode_t *gn;
01570 
01571             for (gn = fsg_model_trans(fsg, fh->fsglink->to_state, j); gn; gn = gnode_next(gn)) {
01572                 fsg_link_t *link = gnode_ptr(gn);
01573                 if ((dest = find_node(dag, fsg, sf, link->wid)) != NULL)
01574                     ps_lattice_link(dag, src, dest, ascr, fh->frame);
01575             }
01576 
01577             /*
01578              * Transitive closure on nulls has already been done, so we
01579              * just need to look one link forward from them.
01580              */
01581             if (fsg_model_null_trans(fsg, fh->fsglink->to_state,j)) {
01582                 gnode_t *gn2;
01583                 int k;
01584 
01585                 /* Add all non-null links out of j. */
01586                 for (k = 0; k < fsg->n_state; ++k) {
01587                     for (gn2 = fsg_model_trans(fsg, j, k); gn2; gn2 = gnode_next(gn2)) {
01588                         fsg_link_t *link = gnode_ptr(gn2);
01589                         if ((dest = find_node(dag, fsg, sf, link->wid)) != NULL)
01590                             ps_lattice_link(dag, src, dest, ascr, fh->frame);
01591                     }
01592                 }
01593             }
01594         }
01595     }
01596 
01597     /* Figure out which nodes are the start and end nodes. */
01598     if ((dag->start = find_start_node(fsgs, dag)) == NULL)
01599         goto error_out;
01600     if ((dag->end = find_end_node(fsgs, dag)) == NULL)
01601         goto error_out;
01602     E_INFO("lattice start node %s.%d end node %s.%d\n",
01603            fsg_model_word_str(fsg, dag->start->wid), dag->start->sf,
01604            fsg_model_word_str(fsg, dag->end->wid), dag->end->sf);
01605     /* FIXME: Need to calculate final_node_ascr here. */
01606 
01607     /*
01608      * Convert word IDs from FSG to dictionary.
01609      */
01610     for (node = dag->nodes; node; node = node->next) {
01611         node->wid = dict_to_id(dag->search->dict,
01612                                fsg_model_word_str(fsg, node->wid));
01613         node->basewid = dict_base_wid(dag->search->dict, node->wid);
01614     }
01615 
01616     /*
01617      * Now we are done, because the links in the graph are uniquely
01618      * defined by the history table.  However we should remove any
01619      * nodes which are not reachable from the end node of the FSG.
01620      * Everything is reachable from the start node by definition.
01621      */
01622     mark_reachable(dag, dag->end);
01623 
01624     ps_lattice_delete_unreachable(dag);
01625     {
01626         int32 silpen, fillpen;
01627 
01628         silpen = (int32)(logmath_log(fsg->lmath,
01629                                      cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"))
01630                          * fsg->lw);
01631         fillpen = (int32)(logmath_log(fsg->lmath,
01632                                       cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"))
01633                           * fsg->lw);
01634         ps_lattice_bypass_fillers(dag, silpen, fillpen);
01635     }
01636     search->dag = dag;
01637     return dag;
01638 
01639 error_out:
01640     ps_lattice_free(dag);
01641     return NULL;
01642 
01643 }

Generated on Thu Jan 27 2011 for PocketSphinx by  doxygen 1.7.1