PocketSphinx  0.6
fsg_search.c
1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* ====================================================================
3  * Copyright (c) 1999-2004 Carnegie Mellon University. All rights
4  * reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  *
18  *
19  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
20  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
23  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  *
31  * ====================================================================
32  *
33  */
34 
35 /*
36  * fsg_search.c -- Search structures for FSM decoding.
37  *
38  * **********************************************
39  * CMU ARPA Speech Project
40  *
41  * Copyright (c) 2004 Carnegie Mellon University.
42  * ALL RIGHTS RESERVED.
43  * **********************************************
44  *
45  * HISTORY
46  *
47  * 18-Feb-2004 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon
48  * Started.
49  */
50 
51 /* System headers. */
52 #include <stdio.h>
53 #include <string.h>
54 #include <assert.h>
55 
56 /* SphinxBase headers. */
57 #include <sphinxbase/err.h>
58 #include <sphinxbase/ckd_alloc.h>
59 #include <sphinxbase/strfuncs.h>
60 #include <sphinxbase/cmd_ln.h>
61 
62 /* Local headers. */
63 #include "pocketsphinx_internal.h"
64 #include "ps_lattice_internal.h"
65 #include "fsg_search_internal.h"
66 #include "fsg_history.h"
67 #include "fsg_lextree.h"
68 
69 /* Turn this on for detailed debugging dump */
70 #define __FSG_DBG__ 0
71 #define __FSG_DBG_CHAN__ 0
72 
73 static ps_seg_t *fsg_search_seg_iter(ps_search_t *search, int32 *out_score);
74 static ps_lattice_t *fsg_search_lattice(ps_search_t *search);
75 static int fsg_search_prob(ps_search_t *search);
76 
77 static ps_searchfuncs_t fsg_funcs = {
78  /* name: */ "fsg",
79  /* start: */ fsg_search_start,
80  /* step: */ fsg_search_step,
81  /* finish: */ fsg_search_finish,
82  /* reinit: */ fsg_search_reinit,
83  /* free: */ fsg_search_free,
84  /* lattice: */ fsg_search_lattice,
85  /* hyp: */ fsg_search_hyp,
86  /* prob: */ fsg_search_prob,
87  /* seg_iter: */ fsg_search_seg_iter,
88 };
89 
91 fsg_search_init(cmd_ln_t *config,
92  acmod_t *acmod,
93  dict_t *dict,
94  dict2pid_t *d2p)
95 {
96  fsg_search_t *fsgs;
97  char const *path;
98 
99  fsgs = ckd_calloc(1, sizeof(*fsgs));
100  ps_search_init(ps_search_base(fsgs), &fsg_funcs, config, acmod, dict, d2p);
101 
102  /* Initialize HMM context. */
103  fsgs->hmmctx = hmm_context_init(bin_mdef_n_emit_state(acmod->mdef),
104  acmod->tmat->tp, NULL, acmod->mdef->sseq);
105  if (fsgs->hmmctx == NULL) {
106  ps_search_free(ps_search_base(fsgs));
107  return NULL;
108  }
109 
110  /* Intialize the search history object */
111  fsgs->history = fsg_history_init(NULL, dict);
112  fsgs->frame = -1;
113 
114  /* Initialize FSG table. */
115  fsgs->fsgs = hash_table_new(5, HASH_CASE_YES);
116 
117  /* Get search pruning parameters */
118  fsgs->beam_factor = 1.0f;
119  fsgs->beam = fsgs->beam_orig
120  = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-beam"))
121  >> SENSCR_SHIFT;
122  fsgs->pbeam = fsgs->pbeam_orig
123  = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-pbeam"))
124  >> SENSCR_SHIFT;
125  fsgs->wbeam = fsgs->wbeam_orig
126  = (int32) logmath_log(acmod->lmath, cmd_ln_float64_r(config, "-wbeam"))
127  >> SENSCR_SHIFT;
128 
129  /* LM related weights/penalties */
130  fsgs->lw = cmd_ln_float32_r(config, "-lw");
131  fsgs->pip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-pip"))
132  * fsgs->lw)
133  >> SENSCR_SHIFT;
134  fsgs->wip = (int32) (logmath_log(acmod->lmath, cmd_ln_float32_r(config, "-wip"))
135  * fsgs->lw)
136  >> SENSCR_SHIFT;
137 
138  /* Best path search (and confidence annotation)? */
139  if (cmd_ln_boolean_r(config, "-bestpath"))
140  fsgs->bestpath = TRUE;
141 
142  /* Acoustic score scale for posterior probabilities. */
143  fsgs->ascale = 1.0 / cmd_ln_float32_r(config, "-ascale");
144 
145  E_INFO("FSG(beam: %d, pbeam: %d, wbeam: %d; wip: %d, pip: %d)\n",
146  fsgs->beam_orig, fsgs->pbeam_orig, fsgs->wbeam_orig,
147  fsgs->wip, fsgs->pip);
148 
149  /* Load an FSG if one was specified in config */
150  if ((path = cmd_ln_str_r(config, "-fsg"))) {
151  fsg_model_t *fsg;
152 
153  if ((fsg = fsg_model_readfile(path, acmod->lmath, fsgs->lw)) == NULL)
154  goto error_out;
155  if (fsg_set_add(fsgs, fsg_model_name(fsg), fsg) != fsg) {
156  fsg_model_free(fsg);
157  goto error_out;
158  }
159  if (fsg_set_select(fsgs, fsg_model_name(fsg)) == NULL)
160  goto error_out;
161  if (fsg_search_reinit(ps_search_base(fsgs),
162  ps_search_dict(fsgs),
163  ps_search_dict2pid(fsgs)) < 0)
164  goto error_out;
165  }
166  /* Or load a JSGF grammar */
167  else if ((path = cmd_ln_str_r(config, "-jsgf"))) {
168  fsg_model_t *fsg;
169  jsgf_rule_t *rule;
170  char const *toprule;
171 
172  if ((fsgs->jsgf = jsgf_parse_file(path, NULL)) == NULL)
173  goto error_out;
174 
175  rule = NULL;
176  /* Take the -toprule if specified. */
177  if ((toprule = cmd_ln_str_r(config, "-toprule"))) {
178  char *anglerule;
179  anglerule = string_join("<", toprule, ">", NULL);
180  rule = jsgf_get_rule(fsgs->jsgf, anglerule);
181  ckd_free(anglerule);
182  if (rule == NULL) {
183  E_ERROR("Start rule %s not found\n", toprule);
184  goto error_out;
185  }
186  }
187  /* Otherwise, take the first public rule. */
188  else {
189  jsgf_rule_iter_t *itor;
190 
191  for (itor = jsgf_rule_iter(fsgs->jsgf); itor;
192  itor = jsgf_rule_iter_next(itor)) {
193  rule = jsgf_rule_iter_rule(itor);
194  if (jsgf_rule_public(rule)) {
195  jsgf_rule_iter_free(itor);
196  break;
197  }
198  }
199  if (rule == NULL) {
200  E_ERROR("No public rules found in %s\n", path);
201  goto error_out;
202  }
203  }
204  fsg = jsgf_build_fsg(fsgs->jsgf, rule, acmod->lmath, fsgs->lw);
205  if (fsg_set_add(fsgs, fsg_model_name(fsg), fsg) != fsg) {
206  fsg_model_free(fsg);
207  goto error_out;
208  }
209  if (fsg_set_select(fsgs, fsg_model_name(fsg)) == NULL)
210  goto error_out;
211  if (fsg_search_reinit(ps_search_base(fsgs),
212  ps_search_dict(fsgs),
213  ps_search_dict2pid(fsgs)) < 0)
214  goto error_out;
215  }
216 
217  return ps_search_base(fsgs);
218 
219 error_out:
220  fsg_search_free(ps_search_base(fsgs));
221  return NULL;
222 }
223 
224 void
225 fsg_search_free(ps_search_t *search)
226 {
227  fsg_search_t *fsgs = (fsg_search_t *)search;
228  hash_iter_t *itor;
229 
230  ps_search_deinit(search);
231  if (fsgs->jsgf)
232  jsgf_grammar_free(fsgs->jsgf);
233  fsg_lextree_free(fsgs->lextree);
234  if (fsgs->history) {
235  fsg_history_reset(fsgs->history);
236  fsg_history_set_fsg(fsgs->history, NULL, NULL);
237  fsg_history_free(fsgs->history);
238  }
239  if (fsgs->fsgs) {
240  for (itor = hash_table_iter(fsgs->fsgs);
241  itor; itor = hash_table_iter_next(itor)) {
242  fsg_model_t *fsg = (fsg_model_t *) hash_entry_val(itor->ent);
243  fsg_model_free(fsg);
244  }
245  hash_table_free(fsgs->fsgs);
246  }
247  hmm_context_free(fsgs->hmmctx);
248  ckd_free(fsgs);
249 }
250 
251 int
252 fsg_search_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p)
253 {
254  fsg_search_t *fsgs = (fsg_search_t *)search;
255 
256  /* Free the old lextree */
257  if (fsgs->lextree)
258  fsg_lextree_free(fsgs->lextree);
259 
260  /* Free old dict2pid, dict */
261  ps_search_base_reinit(search, dict, d2p);
262 
263  /* Nothing to update */
264  if (fsgs->fsg == NULL)
265  return 0;
266 
267  /* Update the number of words (not used by this module though). */
268  search->n_words = dict_size(dict);
269 
270  /* Allocate new lextree for the given FSG */
271  fsgs->lextree = fsg_lextree_init(fsgs->fsg, dict, d2p,
272  ps_search_acmod(fsgs)->mdef,
273  fsgs->hmmctx, fsgs->wip, fsgs->pip);
274 
275  /* Inform the history module of the new fsg */
276  fsg_history_set_fsg(fsgs->history, fsgs->fsg, dict);
277 
278  return 0;
279 }
280 
281 
282 static int
283 fsg_search_add_silences(fsg_search_t *fsgs, fsg_model_t *fsg)
284 {
285  dict_t *dict;
286  int32 wid;
287  int n_sil;
288 
289  dict = ps_search_dict(fsgs);
290  /*
291  * NOTE: Unlike N-Gram search, we do not use explicit start and
292  * end symbols. This is because the start and end nodes are
293  * defined in the grammar. We do add silence/filler self-loops to
294  * all states in order to allow for silence between words and at
295  * the beginning and end of utterances.
296  *
297  * This has some implications for word graph generation, namely,
298  * that there can (and usually will) be multiple start and end
299  * states in the word graph. We therefore do add explicit start
300  * and end nodes to the graph.
301  */
302  /* Add silence self-loops to all states. */
303  fsg_model_add_silence(fsg, "<sil>", -1,
304  cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"));
305  n_sil = 0;
306  /* Add self-loops for all other fillers. */
307  for (wid = dict_filler_start(dict); wid < dict_filler_end(dict); ++wid) {
308  char const *word = dict_wordstr(dict, wid);
309  if (wid == dict_startwid(dict) || wid == dict_finishwid(dict))
310  continue;
311  fsg_model_add_silence(fsg, word, -1,
312  cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"));
313  ++n_sil;
314  }
315 
316  return n_sil;
317 }
318 
319 /* Scans the dictionary and check if all words are present. */
320 static int
321 fsg_search_check_dict(fsg_search_t *fsgs, fsg_model_t *fsg)
322 {
323  dict_t *dict;
324  int i;
325 
326  dict = ps_search_dict(fsgs);
327  for (i = 0; i < fsg_model_n_word(fsg); ++i) {
328  char const *word;
329  int32 wid;
330 
331  word = fsg_model_word_str(fsg, i);
332  wid = dict_wordid(dict, word);
333  if (wid == BAD_S3WID) {
334  E_ERROR("The word '%s' is missing in the dictionary\n", word);
335  return FALSE;
336  }
337  }
338 
339  return TRUE;
340 }
341 
342 static int
343 fsg_search_add_altpron(fsg_search_t *fsgs, fsg_model_t *fsg)
344 {
345  dict_t *dict;
346  int n_alt, n_word;
347  int i;
348 
349  dict = ps_search_dict(fsgs);
350  /* Scan FSG's vocabulary for words that have alternate pronunciations. */
351  n_alt = 0;
352  n_word = fsg_model_n_word(fsg);
353  for (i = 0; i < n_word; ++i) {
354  char const *word;
355  int32 wid;
356 
357  word = fsg_model_word_str(fsg, i);
358  wid = dict_wordid(dict, word);
359  if (wid != BAD_S3WID) {
360  while ((wid = dict_nextalt(dict, wid)) != BAD_S3WID) {
361  n_alt += fsg_model_add_alt(fsg, word, dict_wordstr(dict, wid));
362  }
363  }
364  }
365 
366  E_INFO("Added %d alternate word transitions\n", n_alt);
367  return n_alt;
368 }
369 
370 fsg_model_t *
371 fsg_set_get_fsg(fsg_search_t *fsgs, const char *name)
372 {
373  void *val;
374 
375  if (hash_table_lookup(fsgs->fsgs, name, &val) < 0)
376  return NULL;
377  return (fsg_model_t *)val;
378 }
379 
380 fsg_model_t *
381 fsg_set_add(fsg_search_t *fsgs, char const *name, fsg_model_t *fsg)
382 {
383  if (name == NULL)
384  name = fsg_model_name(fsg);
385 
386  if (!fsg_search_check_dict(fsgs, fsg))
387  return NULL;
388 
389  /* Add silence transitions and alternate words. */
390  if (cmd_ln_boolean_r(ps_search_config(fsgs), "-fsgusefiller")
391  && !fsg_model_has_sil(fsg))
392  fsg_search_add_silences(fsgs, fsg);
393  if (cmd_ln_boolean_r(ps_search_config(fsgs), "-fsgusealtpron")
394  && !fsg_model_has_alt(fsg))
395  fsg_search_add_altpron(fsgs, fsg);
396 
397  return (fsg_model_t *)hash_table_enter(fsgs->fsgs, name, fsg);
398 }
399 
400 
401 fsg_model_t *
402 fsg_set_remove_byname(fsg_search_t *fsgs, char const *key)
403 {
404  fsg_model_t *oldfsg;
405  void *val;
406 
407  /* Look for the matching FSG. */
408  if (hash_table_lookup(fsgs->fsgs, key, &val) < 0) {
409  E_ERROR("FSG `%s' to be deleted not found\n", key);
410  return NULL;
411  }
412  oldfsg = val;
413 
414  /* Remove it from the FSG table. */
415  hash_table_delete(fsgs->fsgs, key);
416  /* If this was the currently active FSG, also delete other stuff */
417  if (fsgs->fsg == oldfsg) {
418  fsg_lextree_free(fsgs->lextree);
419  fsgs->lextree = NULL;
420  fsg_history_set_fsg(fsgs->history, NULL, NULL);
421  fsgs->fsg = NULL;
422  }
423  return oldfsg;
424 }
425 
426 
427 fsg_model_t *
428 fsg_set_remove(fsg_search_t *fsgs, fsg_model_t *fsg)
429 {
430  char const *key;
431  hash_iter_t *itor;
432 
433  key = NULL;
434  for (itor = hash_table_iter(fsgs->fsgs);
435  itor; itor = hash_table_iter_next(itor)) {
436  fsg_model_t *oldfsg;
437 
438  oldfsg = (fsg_model_t *) hash_entry_val(itor->ent);
439  if (oldfsg == fsg) {
440  key = hash_entry_key(itor->ent);
441  hash_table_iter_free(itor);
442  break;
443  }
444  }
445  if (key == NULL) {
446  E_WARN("FSG '%s' to be deleted not found\n", fsg_model_name(fsg));
447  return NULL;
448  }
449  else
450  return fsg_set_remove_byname(fsgs, key);
451 }
452 
453 
454 fsg_model_t *
455 fsg_set_select(fsg_search_t *fsgs, const char *name)
456 {
457  fsg_model_t *fsg;
458 
459  fsg = fsg_set_get_fsg(fsgs, name);
460  if (fsg == NULL) {
461  E_ERROR("FSG '%s' not known; cannot make it current\n", name);
462  return NULL;
463  }
464  fsgs->fsg = fsg;
465  return fsg;
466 }
467 
470 {
471  return hash_table_iter(fsgs->fsgs);
472 }
473 
476 {
477  return hash_table_iter_next(itor);
478 }
479 
480 fsg_model_t *
482 {
483  return ((fsg_model_t *)itor->ent->val);
484 }
485 
486 void
488 {
489  hash_table_iter_free(itor);
490 }
491 
492 static void
493 fsg_search_sen_active(fsg_search_t *fsgs)
494 {
495  gnode_t *gn;
496  fsg_pnode_t *pnode;
497  hmm_t *hmm;
498 
499  acmod_clear_active(ps_search_acmod(fsgs));
500 
501  for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
502  pnode = (fsg_pnode_t *) gnode_ptr(gn);
503  hmm = fsg_pnode_hmmptr(pnode);
504  assert(hmm_frame(hmm) == fsgs->frame);
505  acmod_activate_hmm(ps_search_acmod(fsgs), hmm);
506  }
507 }
508 
509 
510 /*
511  * Evaluate all the active HMMs.
512  * (Executed once per frame.)
513  */
514 static void
515 fsg_search_hmm_eval(fsg_search_t *fsgs)
516 {
517  gnode_t *gn;
518  fsg_pnode_t *pnode;
519  hmm_t *hmm;
520  int32 bestscore;
521  int32 n, maxhmmpf;
522 
523  bestscore = WORST_SCORE;
524 
525  if (!fsgs->pnode_active) {
526  E_ERROR("Frame %d: No active HMM!!\n", fsgs->frame);
527  return;
528  }
529 
530  for (n = 0, gn = fsgs->pnode_active; gn; gn = gnode_next(gn), n++) {
531  int32 score;
532 
533  pnode = (fsg_pnode_t *) gnode_ptr(gn);
534  hmm = fsg_pnode_hmmptr(pnode);
535  assert(hmm_frame(hmm) == fsgs->frame);
536 
537 #if __FSG_DBG__
538  E_INFO("pnode(%08x) active @frm %5d\n", (int32) pnode,
539  fsgs->frame);
540  hmm_dump(hmm, stdout);
541 #endif
542  score = hmm_vit_eval(hmm);
543 #if __FSG_DBG_CHAN__
544  E_INFO("pnode(%08x) after eval @frm %5d\n",
545  (int32) pnode, fsgs->frame);
546  hmm_dump(hmm, stdout);
547 #endif
548 
549  if (score BETTER_THAN bestscore)
550  bestscore = score;
551  }
552 
553 #if __FSG_DBG__
554  E_INFO("[%5d] %6d HMM; bestscr: %11d\n", fsgs->frame, n, bestscore);
555 #endif
556  fsgs->n_hmm_eval += n;
557 
558  /* Adjust beams if #active HMMs larger than absolute threshold */
559  maxhmmpf = cmd_ln_int32_r(ps_search_config(fsgs), "-maxhmmpf");
560  if (maxhmmpf != -1 && n > maxhmmpf) {
561  /*
562  * Too many HMMs active; reduce the beam factor applied to the default
563  * beams, but not if the factor is already at a floor (0.1).
564  */
565  if (fsgs->beam_factor > 0.1) { /* Hack!! Hardwired constant 0.1 */
566  fsgs->beam_factor *= 0.9f; /* Hack!! Hardwired constant 0.9 */
567  fsgs->beam =
568  (int32) (fsgs->beam_orig * fsgs->beam_factor);
569  fsgs->pbeam =
570  (int32) (fsgs->pbeam_orig * fsgs->beam_factor);
571  fsgs->wbeam =
572  (int32) (fsgs->wbeam_orig * fsgs->beam_factor);
573  }
574  }
575  else {
576  fsgs->beam_factor = 1.0f;
577  fsgs->beam = fsgs->beam_orig;
578  fsgs->pbeam = fsgs->pbeam_orig;
579  fsgs->wbeam = fsgs->wbeam_orig;
580  }
581 
582  if (n > fsg_lextree_n_pnode(fsgs->lextree))
583  E_FATAL("PANIC! Frame %d: #HMM evaluated(%d) > #PNodes(%d)\n",
584  fsgs->frame, n, fsg_lextree_n_pnode(fsgs->lextree));
585 
586  fsgs->bestscore = bestscore;
587 }
588 
589 
590 static void
591 fsg_search_pnode_trans(fsg_search_t *fsgs, fsg_pnode_t * pnode)
592 {
593  fsg_pnode_t *child;
594  hmm_t *hmm;
595  int32 newscore, thresh, nf;
596 
597  assert(pnode);
598  assert(!fsg_pnode_leaf(pnode));
599 
600  nf = fsgs->frame + 1;
601  thresh = fsgs->bestscore + fsgs->beam;
602 
603  hmm = fsg_pnode_hmmptr(pnode);
604 
605  for (child = fsg_pnode_succ(pnode);
606  child; child = fsg_pnode_sibling(child)) {
607  newscore = hmm_out_score(hmm) + child->logs2prob;
608 
609  if ((newscore BETTER_THAN thresh)
610  && (newscore BETTER_THAN hmm_in_score(&child->hmm))) {
611  /* Incoming score > pruning threshold and > target's existing score */
612  if (hmm_frame(&child->hmm) < nf) {
613  /* Child node not yet activated; do so */
614  fsgs->pnode_active_next =
615  glist_add_ptr(fsgs->pnode_active_next,
616  (void *) child);
617  }
618 
619  hmm_enter(&child->hmm, newscore, hmm_out_history(hmm), nf);
620  }
621  }
622 }
623 
624 
625 static void
626 fsg_search_pnode_exit(fsg_search_t *fsgs, fsg_pnode_t * pnode)
627 {
628  hmm_t *hmm;
629  fsg_link_t *fl;
630  int32 wid;
631  fsg_pnode_ctxt_t ctxt;
632 
633  assert(pnode);
634  assert(fsg_pnode_leaf(pnode));
635 
636  hmm = fsg_pnode_hmmptr(pnode);
637  fl = fsg_pnode_fsglink(pnode);
638  assert(fl);
639 
640  wid = fsg_link_wid(fl);
641  assert(wid >= 0);
642 
643 #if __FSG_DBG__
644  E_INFO("[%5d] Exit(%08x) %10d(score) %5d(pred)\n",
645  fsgs->frame, (int32) pnode,
646  hmm_out_score(hmm), hmm_out_history(hmm));
647 #endif
648 
649  /*
650  * Check if this is filler or single phone word; these do not model right
651  * context (i.e., the exit score applies to all right contexts).
652  */
653  if (fsg_model_is_filler(fsgs->fsg, wid)
654  /* FIXME: This might be slow due to repeated calls to dict_to_id(). */
655  || (dict_is_single_phone(ps_search_dict(fsgs),
656  dict_wordid(ps_search_dict(fsgs),
657  fsg_model_word_str(fsgs->fsg, wid))))) {
658  /* Create a dummy context structure that applies to all right contexts */
659  fsg_pnode_add_all_ctxt(&ctxt);
660 
661  /* Create history table entry for this word exit */
662  fsg_history_entry_add(fsgs->history,
663  fl,
664  fsgs->frame,
665  hmm_out_score(hmm),
666  hmm_out_history(hmm),
667  pnode->ci_ext, ctxt);
668 
669  }
670  else {
671  /* Create history table entry for this word exit */
672  fsg_history_entry_add(fsgs->history,
673  fl,
674  fsgs->frame,
675  hmm_out_score(hmm),
676  hmm_out_history(hmm),
677  pnode->ci_ext, pnode->ctxt);
678  }
679 }
680 
681 
682 /*
683  * (Beam) prune the just evaluated HMMs, determine which ones remain
684  * active, which ones transition to successors, which ones exit and
685  * terminate in their respective destination FSM states.
686  * (Executed once per frame.)
687  */
688 static void
689 fsg_search_hmm_prune_prop(fsg_search_t *fsgs)
690 {
691  gnode_t *gn;
692  fsg_pnode_t *pnode;
693  hmm_t *hmm;
694  int32 thresh, word_thresh, phone_thresh;
695 
696  assert(fsgs->pnode_active_next == NULL);
697 
698  thresh = fsgs->bestscore + fsgs->beam;
699  phone_thresh = fsgs->bestscore + fsgs->pbeam;
700  word_thresh = fsgs->bestscore + fsgs->wbeam;
701 
702  for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
703  pnode = (fsg_pnode_t *) gnode_ptr(gn);
704  hmm = fsg_pnode_hmmptr(pnode);
705 
706  if (hmm_bestscore(hmm) >= thresh) {
707  /* Keep this HMM active in the next frame */
708  if (hmm_frame(hmm) == fsgs->frame) {
709  hmm_frame(hmm) = fsgs->frame + 1;
710  fsgs->pnode_active_next =
711  glist_add_ptr(fsgs->pnode_active_next,
712  (void *) pnode);
713  }
714  else {
715  assert(hmm_frame(hmm) == fsgs->frame + 1);
716  }
717 
718  if (!fsg_pnode_leaf(pnode)) {
719  if (hmm_out_score(hmm) >= phone_thresh) {
720  /* Transition out of this phone into its children */
721  fsg_search_pnode_trans(fsgs, pnode);
722  }
723  }
724  else {
725  if (hmm_out_score(hmm) >= word_thresh) {
726  /* Transition out of leaf node into destination FSG state */
727  fsg_search_pnode_exit(fsgs, pnode);
728  }
729  }
730  }
731  }
732 }
733 
734 
735 /*
736  * Propagate newly created history entries through null transitions.
737  */
738 static void
739 fsg_search_null_prop(fsg_search_t *fsgs)
740 {
741  int32 bpidx, n_entries, thresh, newscore;
742  fsg_hist_entry_t *hist_entry;
743  fsg_link_t *l;
744  int32 s;
745  fsg_model_t *fsg;
746 
747  fsg = fsgs->fsg;
748  thresh = fsgs->bestscore + fsgs->wbeam; /* Which beam really?? */
749 
750  n_entries = fsg_history_n_entries(fsgs->history);
751 
752  for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
753  fsg_arciter_t *itor;
754  hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
755 
756  l = fsg_hist_entry_fsglink(hist_entry);
757 
758  /* Destination FSG state for history entry */
759  s = l ? fsg_link_to_state(l) : fsg_model_start_state(fsg);
760 
761  /*
762  * Check null transitions from d to all other states. (Only need to
763  * propagate one step, since FSG contains transitive closure of null
764  * transitions.)
765  */
766  /* Add all links from from_state to dst */
767  for (itor = fsg_model_arcs(fsg, s); itor;
768  itor = fsg_arciter_next(itor)) {
769  fsg_link_t *l = fsg_arciter_get(itor);
770 
771  /* FIXME: Need to deal with tag transitions somehow. */
772  if (fsg_link_wid(l) != -1)
773  continue;
774  newscore =
775  fsg_hist_entry_score(hist_entry) +
776  (fsg_link_logs2prob(l) >> SENSCR_SHIFT);
777 
778  if (newscore >= thresh) {
779  fsg_history_entry_add(fsgs->history, l,
780  fsg_hist_entry_frame(hist_entry),
781  newscore,
782  bpidx,
783  fsg_hist_entry_lc(hist_entry),
784  fsg_hist_entry_rc(hist_entry));
785  }
786  }
787  }
788 }
789 
790 
791 /*
792  * Perform cross-word transitions; propagate each history entry created in this
793  * frame to lextree roots attached to the target FSG state for that entry.
794  */
795 static void
796 fsg_search_word_trans(fsg_search_t *fsgs)
797 {
798  int32 bpidx, n_entries;
799  fsg_hist_entry_t *hist_entry;
800  fsg_link_t *l;
801  int32 score, newscore, thresh, nf, d;
802  fsg_pnode_t *root;
803  int32 lc, rc;
804 
805  n_entries = fsg_history_n_entries(fsgs->history);
806 
807  thresh = fsgs->bestscore + fsgs->beam;
808  nf = fsgs->frame + 1;
809 
810  for (bpidx = fsgs->bpidx_start; bpidx < n_entries; bpidx++) {
811  hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
812  assert(hist_entry);
813  score = fsg_hist_entry_score(hist_entry);
814  assert(fsgs->frame == fsg_hist_entry_frame(hist_entry));
815 
816  l = fsg_hist_entry_fsglink(hist_entry);
817 
818  /* Destination state for hist_entry */
819  d = l ? fsg_link_to_state(l) : fsg_model_start_state(fsgs->
820  fsg);
821 
822  lc = fsg_hist_entry_lc(hist_entry);
823 
824  /* Transition to all root nodes attached to state d */
825  for (root = fsg_lextree_root(fsgs->lextree, d);
826  root; root = root->sibling) {
827  rc = root->ci_ext;
828 
829  if ((root->ctxt.bv[lc >> 5] & (1 << (lc & 0x001f))) &&
830  (hist_entry->rc.bv[rc >> 5] & (1 << (rc & 0x001f)))) {
831  /*
832  * Last CIphone of history entry is in left-context list supported by
833  * target root node, and
834  * first CIphone of target root node is in right context list supported
835  * by history entry;
836  * So the transition can go ahead (if new score is good enough).
837  */
838  newscore = score + root->logs2prob;
839 
840  if ((newscore BETTER_THAN thresh)
841  && (newscore BETTER_THAN hmm_in_score(&root->hmm))) {
842  if (hmm_frame(&root->hmm) < nf) {
843  /* Newly activated node; add to active list */
844  fsgs->pnode_active_next =
845  glist_add_ptr(fsgs->pnode_active_next,
846  (void *) root);
847 #if __FSG_DBG__
848  E_INFO
849  ("[%5d] WordTrans bpidx[%d] -> pnode[%08x] (activated)\n",
850  fsgs->frame, bpidx, (int32) root);
851 #endif
852  }
853  else {
854 #if __FSG_DBG__
855  E_INFO
856  ("[%5d] WordTrans bpidx[%d] -> pnode[%08x]\n",
857  fsgs->frame, bpidx, (int32) root);
858 #endif
859  }
860 
861  hmm_enter(&root->hmm, newscore, bpidx, nf);
862  }
863  }
864  }
865  }
866 }
867 
868 
869 int
870 fsg_search_step(ps_search_t *search, int frame_idx)
871 {
872  fsg_search_t *fsgs = (fsg_search_t *)search;
873  int16 const *senscr;
874  acmod_t *acmod = search->acmod;
875  gnode_t *gn;
876  fsg_pnode_t *pnode;
877  hmm_t *hmm;
878 
879  /* Activate our HMMs for the current frame if need be. */
880  if (!acmod->compallsen)
881  fsg_search_sen_active(fsgs);
882  /* Compute GMM scores for the current frame. */
883  senscr = acmod_score(acmod, &frame_idx);
884  fsgs->n_sen_eval += acmod->n_senone_active;
885  hmm_context_set_senscore(fsgs->hmmctx, senscr);
886 
887  /* Mark backpointer table for current frame. */
888  fsgs->bpidx_start = fsg_history_n_entries(fsgs->history);
889 
890  /* Evaluate all active pnodes (HMMs) */
891  fsg_search_hmm_eval(fsgs);
892 
893  /*
894  * Prune and propagate the HMMs evaluated; create history entries for
895  * word exits. The words exits are tentative, and may be pruned; make
896  * the survivors permanent via fsg_history_end_frame().
897  */
898  fsg_search_hmm_prune_prop(fsgs);
899  fsg_history_end_frame(fsgs->history);
900 
901  /*
902  * Propagate new history entries through any null transitions, creating
903  * new history entries, and then make the survivors permanent.
904  */
905  fsg_search_null_prop(fsgs);
906  fsg_history_end_frame(fsgs->history);
907 
908  /*
909  * Perform cross-word transitions; propagate each history entry across its
910  * terminating state to the root nodes of the lextree attached to the state.
911  */
912  fsg_search_word_trans(fsgs);
913 
914  /*
915  * We've now come full circle, HMM and FSG states have been updated for
916  * the next frame.
917  * Update the active lists, deactivate any currently active HMMs that
918  * did not survive into the next frame
919  */
920  for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
921  pnode = (fsg_pnode_t *) gnode_ptr(gn);
922  hmm = fsg_pnode_hmmptr(pnode);
923 
924  if (hmm_frame(hmm) == fsgs->frame) {
925  /* This HMM NOT activated for the next frame; reset it */
927  }
928  else {
929  assert(hmm_frame(hmm) == (fsgs->frame + 1));
930  }
931  }
932 
933  /* Free the currently active list */
934  glist_free(fsgs->pnode_active);
935 
936  /* Make the next-frame active list the current one */
937  fsgs->pnode_active = fsgs->pnode_active_next;
938  fsgs->pnode_active_next = NULL;
939 
940  /* End of this frame; ready for the next */
941  ++fsgs->frame;
942 
943  return 1;
944 }
945 
946 
947 /*
948  * Set all HMMs to inactive, clear active lists, initialize FSM start
949  * state to be the only active node.
950  * (Executed at the start of each utterance.)
951  */
952 int
953 fsg_search_start(ps_search_t *search)
954 {
955  fsg_search_t *fsgs = (fsg_search_t *)search;
956  int32 silcipid;
957  fsg_pnode_ctxt_t ctxt;
958 
959  /* Reset dynamic adjustment factor for beams */
960  fsgs->beam_factor = 1.0f;
961  fsgs->beam = fsgs->beam_orig;
962  fsgs->pbeam = fsgs->pbeam_orig;
963  fsgs->wbeam = fsgs->wbeam_orig;
964 
965  silcipid = bin_mdef_ciphone_id(ps_search_acmod(fsgs)->mdef, "SIL");
966 
967  /* Initialize EVERYTHING to be inactive */
968  assert(fsgs->pnode_active == NULL);
969  assert(fsgs->pnode_active_next == NULL);
970 
971  fsg_history_reset(fsgs->history);
972  fsg_history_utt_start(fsgs->history);
973  fsgs->final = FALSE;
974 
975  /* Dummy context structure that allows all right contexts to use this entry */
976  fsg_pnode_add_all_ctxt(&ctxt);
977 
978  /* Create dummy history entry leading to start state */
979  fsgs->frame = -1;
980  fsgs->bestscore = 0;
981  fsg_history_entry_add(fsgs->history,
982  NULL, -1, 0, -1, silcipid, ctxt);
983  fsgs->bpidx_start = 0;
984 
985  /* Propagate dummy history entry through NULL transitions from start state */
986  fsg_search_null_prop(fsgs);
987 
988  /* Perform word transitions from this dummy history entry */
989  fsg_search_word_trans(fsgs);
990 
991  /* Make the next-frame active list the current one */
992  fsgs->pnode_active = fsgs->pnode_active_next;
993  fsgs->pnode_active_next = NULL;
994 
995  ++fsgs->frame;
996 
997  fsgs->n_hmm_eval = 0;
998  fsgs->n_sen_eval = 0;
999 
1000  return 0;
1001 }
1002 
1003 /*
1004  * Cleanup at the end of each utterance.
1005  */
1006 int
1007 fsg_search_finish(ps_search_t *search)
1008 {
1009  fsg_search_t *fsgs = (fsg_search_t *)search;
1010  gnode_t *gn;
1011  fsg_pnode_t *pnode;
1012  int32 n_hist;
1013 
1014  /* Deactivate all nodes in the current and next-frame active lists */
1015  for (gn = fsgs->pnode_active; gn; gn = gnode_next(gn)) {
1016  pnode = (fsg_pnode_t *) gnode_ptr(gn);
1018  }
1019  for (gn = fsgs->pnode_active_next; gn; gn = gnode_next(gn)) {
1020  pnode = (fsg_pnode_t *) gnode_ptr(gn);
1022  }
1023 
1024  glist_free(fsgs->pnode_active);
1025  fsgs->pnode_active = NULL;
1026  glist_free(fsgs->pnode_active_next);
1027  fsgs->pnode_active_next = NULL;
1028 
1029  fsgs->final = TRUE;
1030 
1031  n_hist = fsg_history_n_entries(fsgs->history);
1032  E_INFO
1033  ("%d frames, %d HMMs (%d/fr), %d senones (%d/fr), %d history entries (%d/fr)\n\n",
1034  fsgs->frame, fsgs->n_hmm_eval,
1035  (fsgs->frame > 0) ? fsgs->n_hmm_eval / fsgs->frame : 0,
1036  fsgs->n_sen_eval,
1037  (fsgs->frame > 0) ? fsgs->n_sen_eval / fsgs->frame : 0,
1038  n_hist, (fsgs->frame > 0) ? n_hist / fsgs->frame : 0);
1039 
1040  return 0;
1041 }
1042 
1043 static int
1044 fsg_search_find_exit(fsg_search_t *fsgs, int frame_idx, int final, int32 *out_score, int32* out_is_final)
1045 {
1046  fsg_hist_entry_t *hist_entry;
1047  fsg_model_t *fsg;
1048  int bpidx, frm, last_frm, besthist;
1049  int32 bestscore;
1050 
1051  if (frame_idx == -1)
1052  frame_idx = fsgs->frame - 1;
1053  last_frm = frm = frame_idx;
1054 
1055  /* Scan backwards to find a word exit in frame_idx. */
1056  bpidx = fsg_history_n_entries(fsgs->history) - 1;
1057  while (bpidx > 0) {
1058  hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
1059  if (fsg_hist_entry_frame(hist_entry) <= frame_idx) {
1060  frm = last_frm = fsg_hist_entry_frame(hist_entry);
1061  break;
1062  }
1063  }
1064 
1065  /* No hypothesis (yet). */
1066  if (bpidx <= 0)
1067  return bpidx;
1068 
1069  /* Now find best word exit in this frame. */
1070  bestscore = INT_MIN;
1071  besthist = -1;
1072  fsg = fsgs->fsg;
1073  while (frm == last_frm) {
1074  fsg_link_t *fl;
1075  int32 score;
1076 
1077  fl = fsg_hist_entry_fsglink(hist_entry);
1078  score = fsg_hist_entry_score(hist_entry);
1079 
1080  if (fl == NULL)
1081  break;
1082 
1083  /* Prefer final hypothesis */
1084  if (score == bestscore && fsg_link_to_state(fl) == fsg_model_final_state(fsg)) {
1085  besthist = bpidx;
1086  } else if (score BETTER_THAN bestscore) {
1087  /* Only enforce the final state constraint if this is a final hypothesis. */
1088  if ((!final)
1089  || fsg_link_to_state(fl) == fsg_model_final_state(fsg)) {
1090  bestscore = score;
1091  besthist = bpidx;
1092  }
1093  }
1094 
1095  --bpidx;
1096  if (bpidx < 0)
1097  break;
1098  hist_entry = fsg_history_entry_get(fsgs->history, bpidx);
1099  frm = fsg_hist_entry_frame(hist_entry);
1100  }
1101 
1102  /* Final state not reached. */
1103  if (besthist == -1) {
1104  E_ERROR("Final result does not match the grammar in frame %d\n", frame_idx);
1105  return -1;
1106  }
1107 
1108  /* This here's the one we want. */
1109  if (out_score)
1110  *out_score = bestscore;
1111  if (out_is_final) {
1112  fsg_link_t *fl;
1113  hist_entry = fsg_history_entry_get(fsgs->history, besthist);
1114  fl = fsg_hist_entry_fsglink(hist_entry);
1115  *out_is_final = (fsg_link_to_state(fl) == fsg_model_final_state(fsg));
1116  }
1117  return besthist;
1118 }
1119 
1120 /* FIXME: Mostly duplicated with ngram_search_bestpath(). */
1121 static ps_latlink_t *
1122 fsg_search_bestpath(ps_search_t *search, int32 *out_score, int backward)
1123 {
1124  fsg_search_t *fsgs = (fsg_search_t *)search;
1125 
1126  if (search->last_link == NULL) {
1127  search->last_link = ps_lattice_bestpath(search->dag, NULL,
1128  1.0, fsgs->ascale);
1129  if (search->last_link == NULL)
1130  return NULL;
1131  /* Also calculate betas so we can fill in the posterior
1132  * probability field in the segmentation. */
1133  if (search->post == 0)
1134  search->post = ps_lattice_posterior(search->dag, NULL, fsgs->ascale);
1135  }
1136  if (out_score)
1137  *out_score = search->last_link->path_scr + search->dag->final_node_ascr;
1138  return search->last_link;
1139 }
1140 
1141 char const *
1142 fsg_search_hyp(ps_search_t *search, int32 *out_score, int32 *out_is_final)
1143 {
1144  fsg_search_t *fsgs = (fsg_search_t *)search;
1145  dict_t *dict = ps_search_dict(search);
1146  char *c;
1147  size_t len;
1148  int bp, bpidx;
1149 
1150  /* Get last backpointer table index. */
1151  bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score, out_is_final);
1152  /* No hypothesis (yet). */
1153  if (bpidx <= 0)
1154  return NULL;
1155 
1156  /* If bestpath is enabled and the utterance is complete, then run it. */
1157  if (fsgs->bestpath && fsgs->final) {
1158  ps_lattice_t *dag;
1159  ps_latlink_t *link;
1160 
1161  if ((dag = fsg_search_lattice(search)) == NULL) {
1162  E_WARN("Failed to obtain the lattice while bestpath enabled\n");
1163  return NULL;
1164  }
1165  if ((link = fsg_search_bestpath(search, out_score, FALSE)) == NULL) {
1166  E_WARN("Failed to find the bestpath in a lattice\n");
1167  return NULL;
1168  }
1169  return ps_lattice_hyp(dag, link);
1170  }
1171 
1172  bp = bpidx;
1173  len = 0;
1174  while (bp > 0) {
1175  fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
1176  fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
1177  char const *baseword;
1178  int32 wid;
1179 
1180  bp = fsg_hist_entry_pred(hist_entry);
1181  wid = fsg_link_wid(fl);
1182  if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
1183  continue;
1184  baseword = dict_basestr(dict,
1185  dict_wordid(dict,
1186  fsg_model_word_str(fsgs->fsg, wid)));
1187  len += strlen(baseword) + 1;
1188  }
1189 
1190  ckd_free(search->hyp_str);
1191  if (len == 0) {
1192  search->hyp_str = NULL;
1193  return search->hyp_str;
1194  }
1195  search->hyp_str = ckd_calloc(1, len);
1196 
1197  bp = bpidx;
1198  c = search->hyp_str + len - 1;
1199  while (bp > 0) {
1200  fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
1201  fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
1202  char const *baseword;
1203  int32 wid;
1204 
1205  bp = fsg_hist_entry_pred(hist_entry);
1206  wid = fsg_link_wid(fl);
1207  if (wid < 0 || fsg_model_is_filler(fsgs->fsg, wid))
1208  continue;
1209  baseword = dict_basestr(dict,
1210  dict_wordid(dict,
1211  fsg_model_word_str(fsgs->fsg, wid)));
1212  len = strlen(baseword);
1213  c -= len;
1214  memcpy(c, baseword, len);
1215  if (c > search->hyp_str) {
1216  --c;
1217  *c = ' ';
1218  }
1219  }
1220 
1221  return search->hyp_str;
1222 }
1223 
1224 static void
1225 fsg_seg_bp2itor(ps_seg_t *seg, fsg_hist_entry_t *hist_entry)
1226 {
1227  fsg_search_t *fsgs = (fsg_search_t *)seg->search;
1228  fsg_hist_entry_t *ph = NULL;
1229  int32 bp;
1230 
1231  if ((bp = fsg_hist_entry_pred(hist_entry)) >= 0)
1232  ph = fsg_history_entry_get(fsgs->history, bp);
1233  seg->word = fsg_model_word_str(fsgs->fsg, hist_entry->fsglink->wid);
1234  seg->ef = fsg_hist_entry_frame(hist_entry);
1235  seg->sf = ph ? fsg_hist_entry_frame(ph) + 1 : 0;
1236  /* This is kind of silly but it happens for null transitions. */
1237  if (seg->sf > seg->ef) seg->sf = seg->ef;
1238  seg->prob = 0; /* Bogus value... */
1239  /* "Language model" score = transition probability. */
1240  seg->lback = 1;
1241  seg->lscr = hist_entry->fsglink->logs2prob;
1242  if (ph) {
1243  /* FIXME: Not sure exactly how cross-word triphones are handled. */
1244  seg->ascr = hist_entry->score - ph->score - seg->lscr;
1245  }
1246  else
1247  seg->ascr = hist_entry->score - seg->lscr;
1248 }
1249 
1250 
1251 static void
1252 fsg_seg_free(ps_seg_t *seg)
1253 {
1254  fsg_seg_t *itor = (fsg_seg_t *)seg;
1255  ckd_free(itor->hist);
1256  ckd_free(itor);
1257 }
1258 
1259 static ps_seg_t *
1260 fsg_seg_next(ps_seg_t *seg)
1261 {
1262  fsg_seg_t *itor = (fsg_seg_t *)seg;
1263 
1264  if (++itor->cur == itor->n_hist) {
1265  fsg_seg_free(seg);
1266  return NULL;
1267  }
1268 
1269  fsg_seg_bp2itor(seg, itor->hist[itor->cur]);
1270  return seg;
1271 }
1272 
1273 static ps_segfuncs_t fsg_segfuncs = {
1274  /* seg_next */ fsg_seg_next,
1275  /* seg_free */ fsg_seg_free
1276 };
1277 
1278 static ps_seg_t *
1279 fsg_search_seg_iter(ps_search_t *search, int32 *out_score)
1280 {
1281  fsg_search_t *fsgs = (fsg_search_t *)search;
1282  fsg_seg_t *itor;
1283  int bp, bpidx, cur;
1284 
1285  bpidx = fsg_search_find_exit(fsgs, fsgs->frame, fsgs->final, out_score, NULL);
1286  /* No hypothesis (yet). */
1287  if (bpidx <= 0)
1288  return NULL;
1289 
1290  /* If bestpath is enabled and the utterance is complete, then run it. */
1291  if (fsgs->bestpath && fsgs->final) {
1292  ps_lattice_t *dag;
1293  ps_latlink_t *link;
1294 
1295  if ((dag = fsg_search_lattice(search)) == NULL)
1296  return NULL;
1297  if ((link = fsg_search_bestpath(search, out_score, TRUE)) == NULL)
1298  return NULL;
1299  return ps_lattice_seg_iter(dag, link, 1.0);
1300  }
1301 
1302  /* Calling this an "iterator" is a bit of a misnomer since we have
1303  * to get the entire backtrace in order to produce it. On the
1304  * other hand, all we actually need is the bptbl IDs, and we can
1305  * allocate a fixed-size array of them. */
1306  itor = ckd_calloc(1, sizeof(*itor));
1307  itor->base.vt = &fsg_segfuncs;
1308  itor->base.search = search;
1309  itor->base.lwf = 1.0;
1310  itor->n_hist = 0;
1311  bp = bpidx;
1312  while (bp > 0) {
1313  fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
1314  bp = fsg_hist_entry_pred(hist_entry);
1315  ++itor->n_hist;
1316  }
1317  if (itor->n_hist == 0) {
1318  ckd_free(itor);
1319  return NULL;
1320  }
1321  itor->hist = ckd_calloc(itor->n_hist, sizeof(*itor->hist));
1322  cur = itor->n_hist - 1;
1323  bp = bpidx;
1324  while (bp > 0) {
1325  fsg_hist_entry_t *hist_entry = fsg_history_entry_get(fsgs->history, bp);
1326  itor->hist[cur] = hist_entry;
1327  bp = fsg_hist_entry_pred(hist_entry);
1328  --cur;
1329  }
1330 
1331  /* Fill in relevant fields for first element. */
1332  fsg_seg_bp2itor((ps_seg_t *)itor, itor->hist[0]);
1333 
1334  return (ps_seg_t *)itor;
1335 }
1336 
1337 static int
1338 fsg_search_prob(ps_search_t *search)
1339 {
1340  fsg_search_t *fsgs = (fsg_search_t *)search;
1341 
1342  /* If bestpath is enabled and the utterance is complete, then run it. */
1343  if (fsgs->bestpath && fsgs->final) {
1344  ps_lattice_t *dag;
1345  ps_latlink_t *link;
1346 
1347  if ((dag = fsg_search_lattice(search)) == NULL)
1348  return 0;
1349  if ((link = fsg_search_bestpath(search, NULL, TRUE)) == NULL)
1350  return 0;
1351  return search->post;
1352  }
1353  else {
1354  /* FIXME: Give some kind of good estimate here, eventually. */
1355  return 0;
1356  }
1357 }
1358 
1359 static ps_latnode_t *
1360 find_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int32 wid, int32 node_id)
1361 {
1362  ps_latnode_t *node;
1363 
1364  for (node = dag->nodes; node; node = node->next)
1365  if ((node->sf == sf) && (node->wid == wid) && (node->node_id == node_id))
1366  break;
1367  return node;
1368 }
1369 
1370 static ps_latnode_t *
1371 new_node(ps_lattice_t *dag, fsg_model_t *fsg, int sf, int ef, int32 wid, int32 node_id, int32 ascr)
1372 {
1373  ps_latnode_t *node;
1374 
1375  node = find_node(dag, fsg, sf, wid, node_id);
1376 
1377  if (node) {
1378  /* Update end frames. */
1379  if (node->lef == -1 || node->lef < ef)
1380  node->lef = ef;
1381  if (node->fef == -1 || node->fef > ef)
1382  node->fef = ef;
1383  /* Update best link score. */
1384  if (ascr BETTER_THAN node->info.best_exit)
1385  node->info.best_exit = ascr;
1386  }
1387  else {
1388  /* New node; link to head of list */
1389  node = listelem_malloc(dag->latnode_alloc);
1390  node->wid = wid;
1391  node->sf = sf;
1392  node->fef = node->lef = ef;
1393  node->reachable = FALSE;
1394  node->entries = NULL;
1395  node->exits = NULL;
1396  node->info.best_exit = ascr;
1397  node->node_id = node_id;
1398 
1399  node->next = dag->nodes;
1400  dag->nodes = node;
1401  ++dag->n_nodes;
1402  }
1403 
1404  return node;
1405 }
1406 
1407 static ps_latnode_t *
1408 find_start_node(fsg_search_t *fsgs, ps_lattice_t *dag)
1409 {
1410  ps_latnode_t *node;
1411  glist_t start = NULL;
1412  int nstart = 0;
1413 
1414  /* Look for all nodes starting in frame zero with some exits. */
1415  for (node = dag->nodes; node; node = node->next) {
1416  if (node->sf == 0 && node->exits) {
1417  E_INFO("Start node %s.%d:%d:%d\n",
1418  fsg_model_word_str(fsgs->fsg, node->wid),
1419  node->sf, node->fef, node->lef);
1420  start = glist_add_ptr(start, node);
1421  ++nstart;
1422  }
1423  }
1424 
1425  /* If there was more than one start node candidate, then we need
1426  * to create an artificial start node with epsilon transitions to
1427  * all of them. */
1428  if (nstart == 1) {
1429  node = gnode_ptr(start);
1430  }
1431  else {
1432  gnode_t *st;
1433  int wid;
1434 
1435  wid = fsg_model_word_add(fsgs->fsg, "<s>");
1436  if (fsgs->fsg->silwords)
1437  bitvec_set(fsgs->fsg->silwords, wid);
1438  node = new_node(dag, fsgs->fsg, 0, 0, wid, -1, 0);
1439  for (st = start; st; st = gnode_next(st))
1440  ps_lattice_link(dag, node, gnode_ptr(st), 0, 0);
1441  }
1442  glist_free(start);
1443  return node;
1444 }
1445 
1446 static ps_latnode_t *
1447 find_end_node(fsg_search_t *fsgs, ps_lattice_t *dag)
1448 {
1449  ps_latnode_t *node;
1450  glist_t end = NULL;
1451  int nend = 0;
1452 
1453  /* Look for all nodes ending in last frame with some entries. */
1454  for (node = dag->nodes; node; node = node->next) {
1455  if (node->lef == dag->n_frames - 1 && node->entries) {
1456  E_INFO("End node %s.%d:%d:%d (%d)\n",
1457  fsg_model_word_str(fsgs->fsg, node->wid),
1458  node->sf, node->fef, node->lef, node->info.best_exit);
1459  end = glist_add_ptr(end, node);
1460  ++nend;
1461  }
1462  }
1463 
1464  if (nend == 1) {
1465  node = gnode_ptr(end);
1466  }
1467  else if (nend == 0) {
1468  ps_latnode_t *last = NULL;
1469  int ef = 0;
1470 
1471  /* If there were no end node candidates, then just use the
1472  * node with the last exit frame. */
1473  for (node = dag->nodes; node; node = node->next) {
1474  if (node->lef > ef && node->entries) {
1475  last = node;
1476  ef = node->lef;
1477  }
1478  }
1479  node = last;
1480  if (node)
1481  E_INFO("End node %s.%d:%d:%d (%d)\n",
1482  fsg_model_word_str(fsgs->fsg, node->wid),
1483  node->sf, node->fef, node->lef, node->info.best_exit);
1484  }
1485  else {
1486  /* If there was more than one end node candidate, then we need
1487  * to create an artificial end node with epsilon transitions
1488  * out of all of them. */
1489  gnode_t *st;
1490  int wid;
1491  wid = fsg_model_word_add(fsgs->fsg, "</s>");
1492  if (fsgs->fsg->silwords)
1493  bitvec_set(fsgs->fsg->silwords, wid);
1494  node = new_node(dag, fsgs->fsg, fsgs->frame, fsgs->frame, wid, -1, 0);
1495  /* Use the "best" (in reality it will be the only) exit link
1496  * score from this final node as the link score. */
1497  for (st = end; st; st = gnode_next(st)) {
1498  ps_latnode_t *src = gnode_ptr(st);
1499  ps_lattice_link(dag, src, node, src->info.best_exit, fsgs->frame);
1500  }
1501  }
1502  glist_free(end);
1503  return node;
1504 }
1505 
1506 static void
1507 mark_reachable(ps_lattice_t *dag, ps_latnode_t *end)
1508 {
1509  glist_t q;
1510 
1511  /* It doesn't matter which order we do this in. */
1512  end->reachable = TRUE;
1513  q = glist_add_ptr(NULL, end);
1514  while (q) {
1515  ps_latnode_t *node = gnode_ptr(q);
1516  latlink_list_t *x;
1517 
1518  /* Pop the front of the list. */
1519  q = gnode_free(q, NULL);
1520  /* Expand all its predecessors that haven't been seen yet. */
1521  for (x = node->entries; x; x = x->next) {
1522  ps_latnode_t *next = x->link->from;
1523  if (!next->reachable) {
1524  next->reachable = TRUE;
1525  q = glist_add_ptr(q, next);
1526  }
1527  }
1528  }
1529 }
1530 
1539 static ps_lattice_t *
1540 fsg_search_lattice(ps_search_t *search)
1541 {
1542  fsg_search_t *fsgs;
1543  fsg_model_t *fsg;
1544  ps_latnode_t *node;
1545  ps_lattice_t *dag;
1546  int32 i, n;
1547 
1548  fsgs = (fsg_search_t *)search;
1549 
1550  /* Check to see if a lattice has previously been created over the
1551  * same number of frames, and reuse it if so. */
1552  if (search->dag && search->dag->n_frames == fsgs->frame)
1553  return search->dag;
1554 
1555  /* Nope, create a new one. */
1556  ps_lattice_free(search->dag);
1557  search->dag = NULL;
1558  dag = ps_lattice_init_search(search, fsgs->frame);
1559  fsg = fsgs->fsg;
1560 
1561  /*
1562  * Each history table entry represents a link in the word graph.
1563  * The set of nodes is determined by the number of unique
1564  * (word,start-frame) pairs in the history table. So we will
1565  * first find all those nodes.
1566  */
1567  n = fsg_history_n_entries(fsgs->history);
1568  for (i = 0; i < n; ++i) {
1569  fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
1570  int32 ascr;
1571  int sf;
1572 
1573  /* Skip null transitions. */
1574  if (fh->fsglink == NULL || fh->fsglink->wid == -1)
1575  continue;
1576 
1577  /* Find the start node of this link. */
1578  if (fh->pred) {
1579  fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
1580  /* FIXME: We include the transition score in the lattice
1581  * link score. This is because of the practical
1582  * difficulty of obtaining it separately in bestpath or
1583  * forward-backward search, and because it is essentially
1584  * a unigram probability, so there is no need to treat it
1585  * separately from the acoustic score. However, it's not
1586  * clear that this will actually yield correct results.*/
1587  ascr = fh->score - pfh->score;
1588  sf = pfh->frame + 1;
1589  }
1590  else {
1591  ascr = fh->score;
1592  sf = 0;
1593  }
1594 
1595  /*
1596  * Note that although scores are tied to links rather than
1597  * nodes, it's possible that there are no links out of the
1598  * destination node, and thus we need to preserve its score in
1599  * case it turns out to be utterance-final.
1600  */
1601  new_node(dag, fsg, sf, fh->frame, fh->fsglink->wid, fsg_link_to_state(fh->fsglink), ascr);
1602  }
1603 
1604  /*
1605  * Now, we will create links only to nodes that actually exist.
1606  */
1607  n = fsg_history_n_entries(fsgs->history);
1608  for (i = 0; i < n; ++i) {
1609  fsg_hist_entry_t *fh = fsg_history_entry_get(fsgs->history, i);
1610  fsg_arciter_t *itor;
1611  ps_latnode_t *src, *dest;
1612  int32 ascr;
1613  int sf;
1614 
1615  /* Skip null transitions. */
1616  if (fh->fsglink == NULL || fh->fsglink->wid == -1)
1617  continue;
1618 
1619  /* Find the start node of this link and calculate its link score. */
1620  if (fh->pred) {
1621  fsg_hist_entry_t *pfh = fsg_history_entry_get(fsgs->history, fh->pred);
1622  sf = pfh->frame + 1;
1623  ascr = fh->score - pfh->score;
1624  }
1625  else {
1626  ascr = fh->score;
1627  sf = 0;
1628  }
1629  src = find_node(dag, fsg, sf, fh->fsglink->wid, fsg_link_to_state(fh->fsglink));
1630  sf = fh->frame + 1;
1631 
1632  for (itor = fsg_model_arcs(fsg, fsg_link_to_state(fh->fsglink));
1633  itor; itor = fsg_arciter_next(itor)) {
1634  fsg_link_t *link = fsg_arciter_get(itor);
1635 
1636  /* FIXME: Need to figure out what to do about tag transitions. */
1637  if (link->wid >= 0) {
1638  /*
1639  * For each non-epsilon link following this one, look for a
1640  * matching node in the lattice and link to it.
1641  */
1642  if ((dest = find_node(dag, fsg, sf, link->wid, fsg_link_to_state(link))) != NULL)
1643  ps_lattice_link(dag, src, dest, ascr, fh->frame);
1644  }
1645  else {
1646  /*
1647  * Transitive closure on nulls has already been done, so we
1648  * just need to look one link forward from them.
1649  */
1650  fsg_arciter_t *itor2;
1651 
1652  /* Add all non-null links out of j. */
1653  for (itor2 = fsg_model_arcs(fsg, fsg_link_to_state(link));
1654  itor2; itor2 = fsg_arciter_next(itor2)) {
1655  fsg_link_t *link = fsg_arciter_get(itor2);
1656 
1657  if (link->wid == -1)
1658  continue;
1659 
1660  if ((dest = find_node(dag, fsg, sf, link->wid, fsg_link_to_state(link))) != NULL) {
1661  ps_lattice_link(dag, src, dest, ascr, fh->frame);
1662  }
1663  }
1664  }
1665  }
1666  }
1667 
1668 
1669  /* Figure out which nodes are the start and end nodes. */
1670  if ((dag->start = find_start_node(fsgs, dag)) == NULL) {
1671  E_WARN("Failed to find the start node\n");
1672  goto error_out;
1673  }
1674  if ((dag->end = find_end_node(fsgs, dag)) == NULL) {
1675  E_WARN("Failed to find the end node\n");
1676  goto error_out;
1677  }
1678 
1679 
1680  E_INFO("lattice start node %s.%d end node %s.%d\n",
1681  fsg_model_word_str(fsg, dag->start->wid), dag->start->sf,
1682  fsg_model_word_str(fsg, dag->end->wid), dag->end->sf);
1683  /* FIXME: Need to calculate final_node_ascr here. */
1684 
1685  /*
1686  * Convert word IDs from FSG to dictionary.
1687  */
1688  for (node = dag->nodes; node; node = node->next) {
1689  node->wid = dict_wordid(dag->search->dict,
1690  fsg_model_word_str(fsg, node->wid));
1691  node->basewid = dict_basewid(dag->search->dict, node->wid);
1692  }
1693 
1694  /*
1695  * Now we are done, because the links in the graph are uniquely
1696  * defined by the history table. However we should remove any
1697  * nodes which are not reachable from the end node of the FSG.
1698  * Everything is reachable from the start node by definition.
1699  */
1700  mark_reachable(dag, dag->end);
1701 
1703  {
1704  int32 silpen, fillpen;
1705 
1706  silpen = (int32)(logmath_log(fsg->lmath,
1707  cmd_ln_float32_r(ps_search_config(fsgs), "-silprob"))
1708  * fsg->lw)
1709  >> SENSCR_SHIFT;
1710  fillpen = (int32)(logmath_log(fsg->lmath,
1711  cmd_ln_float32_r(ps_search_config(fsgs), "-fillprob"))
1712  * fsg->lw)
1713  >> SENSCR_SHIFT;
1714  ps_lattice_bypass_fillers(dag, silpen, fillpen);
1715  }
1716  search->dag = dag;
1717 
1718  return dag;
1719 
1720 
1721 error_out:
1722  ps_lattice_free(dag);
1723  return NULL;
1724 
1725 }
void fsg_lextree_free(fsg_lextree_t *lextree)
Free lextrees for an FSG.
Definition: fsg_lextree.c:284
glist_t pnode_active_next
Those activated for the next frame.
Implementation of FSG search (and "FSG set") structure.
Internal implementation of PocketSphinx decoder.
int16 reachable
From.
POCKETSPHINX_EXPORT fsg_model_t * fsg_set_select(fsg_set_t *fsgs, const char *name)
Switch to a new FSG (identified by its string name).
Definition: fsg_search.c:455
Base structure for search module.
POCKETSPHINX_EXPORT fsg_set_iter_t * fsg_set_iter_next(fsg_set_iter_t *itor)
Advance an iterator to the next grammar in the set.
Definition: fsg_search.c:475
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:1029
int16 cur
Current position in hist.
Definition: fsg_history.h:95
POCKETSPHINX_EXPORT s3wid_t dict_wordid(dict_t *d, const char *word)
Return word id for given word string if present.
Definition: dict.c:382
int32 lef
Last end frame.
fsg_model_t * fsg
Currently active FSG; NULL if none.
int32 wbeam_orig
Pruning threshold for word exit.
void fsg_pnode_add_all_ctxt(fsg_pnode_ctxt_t *ctxt)
Set all flags on in the given context bitvector.
Definition: fsg_lextree.c:326
void ps_search_base_reinit(ps_search_t *search, dict_t *dict, dict2pid_t *d2p)
Re-initialize base structure with new dictionary.
int n_senone_active
Number of active GMMs.
Definition: acmod.h:169
acmod_t * acmod
Acoustic model.
Segmentation "iterator" for FSG history.
ps_seg_t base
Base structure.
An individual HMM among the HMM search space.
float32 beam_factor
Dynamic/adaptive factor (<=1) applied to above beams to determine actual effective beams...
ps_latnode_t * start
Starting node.
uint8 *** tp
The transition matrices; kept in the same scale as acoustic scores; tp[tmatid][from-state][to-state]...
Definition: tmat.h:110
ps_segfuncs_t * vt
V-table of seg methods.
logmath_t * lmath
Log-math computation.
Definition: acmod.h:151
hash_iter_t fsg_set_iter_t
Iterator over finite-state grammars.
Definition: fsg_set.h:64
int bin_mdef_ciphone_id(bin_mdef_t *m, const char *ciphone)
Context-independent phone lookup.
Definition: bin_mdef.c:692
struct fsg_history_s * history
For storing the Viterbi search history.
uint16 ** sseq
Unique senone sequences (2D array built at load time)
Definition: bin_mdef.h:137
int32 lscr
Language model score.
int32 n_words
Number of words known to search (may be less than in the dictionary)
int32 wbeam
Effective beams after applying beam_factor.
void acmod_activate_hmm(acmod_t *acmod, hmm_t *hmm)
Activate senones associated with an HMM.
Definition: acmod.c:1191
float32 ascale
Acoustic score scale for posterior probabilities.
ps_search_t * search
Search (if generated by search).
#define BAD_S3WID
Dictionary word id.
Definition: s3types.h:136
frame_idx_t n_frames
Number of frames for this utterance.
POCKETSPHINX_EXPORT fsg_model_t * fsg_set_remove(fsg_set_t *fsgs, fsg_model_t *wfsg)
Delete the given FSG from the known collection.
Definition: fsg_search.c:428
POCKETSPHINX_EXPORT fsg_model_t * fsg_set_add(fsg_set_t *fsgs, char const *name, fsg_model_t *wfsg)
Add the given FSG to the collection of FSGs known to this search object.
Definition: fsg_search.c:381
jsgf_t * jsgf
Active JSGF grammar file.
Word graph search implementation.
int32 n_hmm_eval
Total HMMs evaluated this utt.
ps_latnode_t * nodes
List of all nodes.
void ps_search_init(ps_search_t *search, ps_searchfuncs_t *vt, cmd_ln_t *config, acmod_t *acmod, dict_t *dict, dict2pid_t *d2p)
Initialize base structure.
listelem_alloc_t * latnode_alloc
Node allocator for this DAG.
int32 wip
Language weights.
int32 best_exit
Best exit score (used for final nodes only)
hash_table_t * fsgs
Table of all FSGs loaded.
int16 n_nodes
Number of nodes in this lattice.
int32 prob
Log posterior probability.
latlink_list_t * entries
Links into this node.
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:1408
hmm_context_t * hmmctx
HMM context.
char const * word
Word string (pointer into dictionary hash)
ps_search_t * search
Search object from whence this came.
int32 final_node_ascr
Acoustic score of implicit link exiting final node.
fsg_hist_entry_t ** hist
Sequence of history entries.
int32 hmm_vit_eval(hmm_t *hmm)
Viterbi evaluation of given HMM.
Definition: hmm.c:789
void fsg_psubtree_pnode_deactivate(fsg_pnode_t *pnode)
Mark the given pnode as inactive (for search).
Definition: fsg_lextree.c:831
uint8 compallsen
Compute all senones?
Definition: acmod.h:183
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
void ps_lattice_delete_unreachable(ps_lattice_t *dag)
Remove nodes marked as unreachable.
Definition: ps_lattice.c:197
ps_latnode_t * end
Ending node.
frame_idx_t sf
Start frame.
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:1238
int32 beam_orig
Global pruning threshold.
POCKETSPHINX_EXPORT fsg_set_iter_t * fsg_set_iter(fsg_set_t *fsgs)
Get an iterator over all finite-state grammars in a set.
Definition: fsg_search.c:469
latlink_list_t * exits
Links out of this node.
#define WORST_SCORE
Large "bad" score.
Definition: hmm.h:88
tmat_t * tmat
Transition matrices.
Definition: acmod.h:160
frame_idx_t ef
End frame.
int32 ascr
Acoustic score.
void hmm_enter(hmm_t *h, int32 score, int32 histid, int frame)
Enter an HMM with the given path score and history ID.
Definition: hmm.c:201
void acmod_clear_active(acmod_t *acmod)
Clear set of active senones.
Definition: acmod.c:1175
int32 wid
Dictionary word id.
int32 node_id
Node from fsg model, used to map lattice back to model.
int32 pbeam_orig
Pruning threshold for phone transition.
#define hmm_context_set_senscore(ctx, senscr)
Change the senone score array for a context.
Definition: hmm.h:231
void hmm_dump(hmm_t *h, FILE *fp)
For debugging, dump the whole HMM out.
Definition: hmm.c:116
uint8 final
Decoding is finished for this utterance.
#define SENSCR_SHIFT
Shift count for senone scores.
Definition: hmm.h:77
POCKETSPHINX_EXPORT fsg_model_t * fsg_set_remove_byname(fsg_set_t *fsgs, char const *name)
Like fsg_set_del_fsg(), but identifies the FSG by its name.
Definition: fsg_search.c:402
a structure for a dictionary.
Definition: dict.h:79
char const * ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link)
Get hypothesis string after bestpath search.
Definition: ps_lattice.c:853
Word graph structure used in bestpath/nbest search.
int32 bestscore
For beam pruning.
int32 bpidx_start
First history entry index this frame.
POCKETSPHINX_EXPORT fsg_model_t * fsg_set_iter_fsg(fsg_set_iter_t *itor)
Get the current rule in an FSG iterator.
Definition: fsg_search.c:481
POCKETSPHINX_EXPORT fsg_model_t * fsg_set_get_fsg(fsg_set_t *fsgs, char const *name)
Lookup the FSG associated with the given name.
Definition: fsg_search.c:371
int32 post
Utterance posterior probability.
char * hyp_str
Current hypothesis string.
fsg_lextree_t * fsg_lextree_init(fsg_model_t *fsg, dict_t *dict, dict2pid_t *d2p, bin_mdef_t *mdef, hmm_context_t *ctx, int32 wip, int32 pip)
Create, initialize, and return a new phonetic lextree for the given FSG.
Definition: fsg_lextree.c:213
#define BETTER_THAN
Is one score better than another?
Definition: hmm.h:99
dict_t * dict
Pronunciation dictionary.
int32 fef
First end frame.
uint8 bestpath
Whether to run bestpath search and confidence annotation at end.
int32 lback
Language model backoff.
int32 n_sen_eval
Total senones evaluated this utt.
int32 basewid
Dictionary base word id.
glist_t pnode_active
Those active in this frame.
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:662
void hmm_context_free(hmm_context_t *ctx)
Free an HMM context.
Definition: hmm.c:80
int16 n_hist
Number of history entries.
bin_mdef_t * mdef
Model definition.
Definition: acmod.h:159
ps_latlink_t * last_link
Final link in best path.
struct ps_latnode_s * next
Next node in DAG (no ordering implied)
void ps_lattice_bypass_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen)
Bypass filler words.
Definition: ps_lattice.c:106
V-table for search algorithm.
frame_idx_t frame
Current frame.
ps_lattice_t * dag
Current hypothesis word graph.
Base structure for hypothesis segmentation iterator.
struct fsg_lextree_s * lextree
Lextree structure for the currently active FSG.
#define dict_size(d)
Packaged macro access to dictionary members.
Definition: dict.h:154
POCKETSPHINX_EXPORT int ps_lattice_free(ps_lattice_t *dag)
Free a lattice.
Definition: ps_lattice.c:688
Acoustic model structure.
Definition: acmod.h:148
float32 lwf
Language weight factor (for second-pass searches)
Building composite triphone (as well as word internal triphones) with the dictionary.
Definition: dict2pid.h:148
void ps_search_deinit(ps_search_t *search)
De-initialize base structure.
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, choose one with the best link_scr.
Definition: ps_lattice.c:65
frame_idx_t sf
Start frame.
int16 const * acmod_score(acmod_t *acmod, int *inout_frame_idx)
Score one frame of data.
Definition: acmod.c:1088
POCKETSPHINX_EXPORT void fsg_set_iter_free(fsg_set_iter_t *itor)
Free an FSG iterator (if the end hasn&#39;t been reached).
Definition: fsg_search.c:487