PocketSphinx  0.6
ps_lattice.c
Go to the documentation of this file.
1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* ====================================================================
3  * Copyright (c) 2008 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  * This work was supported in part by funding from the Defense Advanced
19  * Research Projects Agency and the National Science Foundation of the
20  * United States of America, and the CMU Sphinx Speech Consortium.
21  *
22  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
23  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
24  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
26  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33  *
34  * ====================================================================
35  *
36  */
37 
42 /* System headers. */
43 #include <assert.h>
44 #include <string.h>
45 #include <math.h>
46 
47 /* SphinxBase headers. */
48 #include <sphinxbase/ckd_alloc.h>
49 #include <sphinxbase/listelem_alloc.h>
50 #include <sphinxbase/strfuncs.h>
51 #include <sphinxbase/err.h>
52 #include <sphinxbase/pio.h>
53 
54 /* Local headers. */
55 #include "pocketsphinx_internal.h"
56 #include "ps_lattice_internal.h"
57 #include "ngram_search.h"
58 #include "dict.h"
59 
60 /*
61  * Create a directed link between "from" and "to" nodes, but if a link already exists,
62  * choose one with the best ascr.
63  */
64 void
66  int32 score, int32 ef)
67 {
68  latlink_list_t *fwdlink;
69 
70  /* Look for an existing link between "from" and "to" nodes */
71  for (fwdlink = from->exits; fwdlink; fwdlink = fwdlink->next)
72  if (fwdlink->link->to == to)
73  break;
74 
75  if (fwdlink == NULL) {
76  latlink_list_t *revlink;
77  ps_latlink_t *link;
78 
79  /* No link between the two nodes; create a new one */
80  link = listelem_malloc(dag->latlink_alloc);
81  fwdlink = listelem_malloc(dag->latlink_list_alloc);
82  revlink = listelem_malloc(dag->latlink_list_alloc);
83 
84  link->from = from;
85  link->to = to;
86  link->ascr = score;
87  link->ef = ef;
88  link->best_prev = NULL;
89 
90  fwdlink->link = revlink->link = link;
91  fwdlink->next = from->exits;
92  from->exits = fwdlink;
93  revlink->next = to->entries;
94  to->entries = revlink;
95  }
96  else {
97  /* Link already exists; just retain the best ascr */
98  if (score BETTER_THAN fwdlink->link->ascr) {
99  fwdlink->link->ascr = score;
100  fwdlink->link->ef = ef;
101  }
102  }
103 }
104 
105 void
106 ps_lattice_bypass_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen)
107 {
108  ps_latnode_t *node;
109  int32 score;
110 
111  /* Bypass filler nodes */
112  for (node = dag->nodes; node; node = node->next) {
113  latlink_list_t *revlink;
114  if (node == dag->end || !dict_filler_word(dag->dict, node->basewid))
115  continue;
116 
117  /* Replace each link entering filler node with links to all its successors */
118  for (revlink = node->entries; revlink; revlink = revlink->next) {
119  latlink_list_t *forlink;
120  ps_latlink_t *rlink = revlink->link;
121 
122  score = (node->basewid == dag->silence) ? silpen : fillpen;
123  score += rlink->ascr;
124  /*
125  * Make links from predecessor of filler (from) to successors of filler.
126  * But if successor is a filler, it has already been eliminated since it
127  * appears earlier in latnode_list (see build...). So it can be skipped.
128  */
129  for (forlink = node->exits; forlink; forlink = forlink->next) {
130  ps_latlink_t *flink = forlink->link;
131  if (flink->to && rlink->from &&
132  !dict_filler_word(dag->dict, flink->to->basewid)) {
133  ps_lattice_link(dag, rlink->from, flink->to,
134  score + flink->ascr, flink->ef);
135  }
136  }
137  }
138  node->reachable = FALSE;
139  }
140 }
141 
142 static void
143 delete_node(ps_lattice_t *dag, ps_latnode_t *node)
144 {
145  latlink_list_t *x, *next_x;
146 
147  for (x = node->exits; x; x = next_x) {
148  next_x = x->next;
149  x->link->from = NULL;
150  listelem_free(dag->latlink_list_alloc, x);
151  }
152  for (x = node->entries; x; x = next_x) {
153  next_x = x->next;
154  x->link->to = NULL;
155  listelem_free(dag->latlink_list_alloc, x);
156  }
157  listelem_free(dag->latnode_alloc, node);
158 }
159 
160 
161 static void
162 remove_dangling_links(ps_lattice_t *dag, ps_latnode_t *node)
163 {
164  latlink_list_t *x, *prev_x, *next_x;
165 
166  prev_x = NULL;
167  for (x = node->exits; x; x = next_x) {
168  next_x = x->next;
169  if (x->link->to == NULL) {
170  if (prev_x)
171  prev_x->next = next_x;
172  else
173  node->exits = next_x;
174  listelem_free(dag->latlink_alloc, x->link);
175  listelem_free(dag->latlink_list_alloc, x);
176  }
177  else
178  prev_x = x;
179  }
180  prev_x = NULL;
181  for (x = node->entries; x; x = next_x) {
182  next_x = x->next;
183  if (x->link->from == NULL) {
184  if (prev_x)
185  prev_x->next = next_x;
186  else
187  node->entries = next_x;
188  listelem_free(dag->latlink_alloc, x->link);
189  listelem_free(dag->latlink_list_alloc, x);
190  }
191  else
192  prev_x = x;
193  }
194 }
195 
196 void
198 {
199  ps_latnode_t *node, *prev_node, *next_node;
200  int i;
201 
202  /* Remove unreachable nodes from the list of nodes. */
203  prev_node = NULL;
204  for (node = dag->nodes; node; node = next_node) {
205  next_node = node->next;
206  if (!node->reachable) {
207  if (prev_node)
208  prev_node->next = next_node;
209  else
210  dag->nodes = next_node;
211  /* Delete this node and NULLify links to it. */
212  delete_node(dag, node);
213  }
214  else
215  prev_node = node;
216  }
217 
218  /* Remove all links to and from unreachable nodes. */
219  i = 0;
220  for (node = dag->nodes; node; node = node->next) {
221  /* Assign sequence numbers. */
222  node->id = i++;
223 
224  /* We should obviously not encounter unreachable nodes here! */
225  assert(node->reachable);
226 
227  /* Remove all links that go nowhere. */
228  remove_dangling_links(dag, node);
229  }
230 }
231 
232 int32
233 ps_lattice_write(ps_lattice_t *dag, char const *filename)
234 {
235  FILE *fp;
236  int32 i;
237  ps_latnode_t *d, *initial, *final;
238 
239  initial = dag->start;
240  final = dag->end;
241 
242  E_INFO("Writing lattice file: %s\n", filename);
243  if ((fp = fopen(filename, "w")) == NULL) {
244  E_ERROR("Failed to open lattice file '%s' for writing: %s\n", filename, strerror(errno));
245  return -1;
246  }
247 
248  /* Stupid Sphinx-III lattice code expects 'getcwd:' here */
249  fprintf(fp, "# getcwd: /this/is/bogus\n");
250  fprintf(fp, "# -logbase %e\n", logmath_get_base(dag->lmath));
251  fprintf(fp, "#\n");
252 
253  fprintf(fp, "Frames %d\n", dag->n_frames);
254  fprintf(fp, "#\n");
255 
256  for (i = 0, d = dag->nodes; d; d = d->next, i++);
257  fprintf(fp,
258  "Nodes %d (NODEID WORD STARTFRAME FIRST-ENDFRAME LAST-ENDFRAME)\n",
259  i);
260  for (i = 0, d = dag->nodes; d; d = d->next, i++) {
261  d->id = i;
262  fprintf(fp, "%d %s %d %d %d\n",
263  i, dict_wordstr(dag->dict, d->wid),
264  d->sf, d->fef, d->lef);
265  }
266  fprintf(fp, "#\n");
267 
268  fprintf(fp, "Initial %d\nFinal %d\n", initial->id, final->id);
269  fprintf(fp, "#\n");
270 
271  /* Don't bother with this, it's not used by anything. */
272  fprintf(fp, "BestSegAscr %d (NODEID ENDFRAME ASCORE)\n",
273  0 /* #BPTable entries */ );
274  fprintf(fp, "#\n");
275 
276  fprintf(fp, "Edges (FROM-NODEID TO-NODEID ASCORE)\n");
277  for (d = dag->nodes; d; d = d->next) {
278  latlink_list_t *l;
279  for (l = d->exits; l; l = l->next) {
280  if (l->link->ascr WORSE_THAN WORST_SCORE || l->link->ascr BETTER_THAN 0)
281  continue;
282  fprintf(fp, "%d %d %d\n",
283  d->id, l->link->to->id, l->link->ascr << SENSCR_SHIFT);
284  }
285  }
286  fprintf(fp, "End\n");
287  fclose(fp);
288 
289  return 0;
290 }
291 
292 int32
293 ps_lattice_write_htk(ps_lattice_t *dag, char const *filename)
294 {
295  FILE *fp;
296  ps_latnode_t *d, *initial, *final;
297  int32 i, j, n_links, n_nodes;
298 
299  initial = dag->start;
300  final = dag->end;
301 
302  E_INFO("Writing lattice file: %s\n", filename);
303  if ((fp = fopen(filename, "w")) == NULL) {
304  E_ERROR("Failed to open lattice file '%s' for writing: %s\n", filename, strerror(errno));
305  return -1;
306  }
307 
308  for (n_links = n_nodes = 0, d = dag->nodes; d; d = d->next) {
309  latlink_list_t *l;
310  if (!d->reachable)
311  continue;
312  d->id = n_nodes;
313  for (l = d->exits; l; l = l->next) {
314  if (l->link->to == NULL || !l->link->to->reachable)
315  continue;
316  if (l->link->ascr WORSE_THAN WORST_SCORE || l->link->ascr BETTER_THAN 0)
317  continue;
318  ++n_links;
319  }
320  ++n_nodes;
321  }
322 
323  fprintf(fp, "# Lattice generated by PocketSphinx\n");
324  fprintf(fp, "#\n# Header\n#\n");
325  fprintf(fp, "VERSION=1.0\n");
326  fprintf(fp, "start=%d\n", initial->id);
327  fprintf(fp, "end=%d\n", final->id);
328  fprintf(fp, "#\n");
329 
330  fprintf(fp, "N=%d\tL=%d\n", n_nodes, n_links);
331  fprintf(fp, "#\n# Node definitions\n#\n");
332  for (i = 0, d = dag->nodes; d; d = d->next) {
333  char const *word = dict_wordstr(dag->dict, d->wid);
334  char const *c = strrchr(word, '(');
335  int altpron = 1;
336  if (!d->reachable)
337  continue;
338  if (c)
339  altpron = atoi(c + 1);
340  word = dict_basestr(dag->dict, d->wid);
341  if (d->wid == dict_startwid(dag->dict))
342  word = "!SENT_START";
343  else if (d->wid == dict_finishwid(dag->dict))
344  word = "!SENT_END";
345  else if (dict_filler_word(dag->dict, d->wid))
346  word = "!NULL";
347  fprintf(fp, "I=%d\tt=%.2f\tW=%s\tv=%d\n",
348  d->id, (double)d->sf / dag->frate,
349  word, altpron);
350  }
351  fprintf(fp, "#\n# Link definitions\n#\n");
352  for (j = 0, d = dag->nodes; d; d = d->next) {
353  latlink_list_t *l;
354  if (!d->reachable)
355  continue;
356  for (l = d->exits; l; l = l->next) {
357  if (l->link->to == NULL || !l->link->to->reachable)
358  continue;
359  if (l->link->ascr WORSE_THAN WORST_SCORE || l->link->ascr BETTER_THAN 0)
360  continue;
361  fprintf(fp, "J=%d\tS=%d\tE=%d\ta=%f\tp=%g\n", j++,
362  d->id, l->link->to->id,
363  logmath_log_to_ln(dag->lmath, l->link->ascr << SENSCR_SHIFT),
364  logmath_exp(dag->lmath, l->link->alpha + l->link->beta - dag->norm));
365  }
366  }
367  fclose(fp);
368 
369  return 0;
370 }
371 
372 /* Read parameter from a lattice file*/
373 static int
374 dag_param_read(lineiter_t *li, char *param)
375 {
376  int32 n;
377 
378  while ((li = lineiter_next(li)) != NULL) {
379  char *c;
380 
381  /* Ignore comments. */
382  if (li->buf[0] == '#')
383  continue;
384 
385  /* Find the first space. */
386  c = strchr(li->buf, ' ');
387  if (c == NULL) continue;
388 
389  /* Check that the first field equals param and that there's a number after it. */
390  if (strncmp(li->buf, param, strlen(param)) == 0
391  && sscanf(c + 1, "%d", &n) == 1)
392  return n;
393  }
394  return -1;
395 }
396 
397 /* Mark every node that has a path to the argument dagnode as "reachable". */
398 static void
399 dag_mark_reachable(ps_latnode_t * d)
400 {
401  latlink_list_t *l;
402 
403  d->reachable = 1;
404  for (l = d->entries; l; l = l->next)
405  if (l->link->from && !l->link->from->reachable)
406  dag_mark_reachable(l->link->from);
407 }
408 
409 ps_lattice_t *
411  char const *file)
412 {
413  FILE *fp;
414  int32 ispipe;
415  lineiter_t *line;
416  float64 lb;
417  float32 logratio;
418  ps_latnode_t *tail;
419  ps_latnode_t **darray;
420  ps_lattice_t *dag;
421  int i, k, n_nodes;
422  int32 pip, silpen, fillpen;
423 
424  dag = ckd_calloc(1, sizeof(*dag));
425 
426  if (ps) {
427  dag->search = ps->search;
428  dag->dict = dict_retain(ps->dict);
429  dag->lmath = logmath_retain(ps->lmath);
430  dag->frate = cmd_ln_int32_r(dag->search->config, "-frate");
431  }
432  else {
433  dag->dict = dict_init(NULL, NULL);
434  dag->lmath = logmath_init(1.0001, 0, FALSE);
435  dag->frate = 100;
436  }
437  dag->silence = dict_silwid(dag->dict);
438  dag->latnode_alloc = listelem_alloc_init(sizeof(ps_latnode_t));
439  dag->latlink_alloc = listelem_alloc_init(sizeof(ps_latlink_t));
440  dag->latlink_list_alloc = listelem_alloc_init(sizeof(latlink_list_t));
441  dag->refcount = 1;
442 
443  tail = NULL;
444  darray = NULL;
445 
446  E_INFO("Reading DAG file: %s\n", file);
447  if ((fp = fopen_compchk(file, &ispipe)) == NULL) {
448  E_ERROR("Failed to open DAG file '%s': %s\n", file, strerror(errno));
449  return NULL;
450  }
451  line = lineiter_start(fp);
452 
453  /* Read and verify logbase (ONE BIG HACK!!) */
454  if (line == NULL) {
455  E_ERROR("Premature EOF(%s)\n", file);
456  goto load_error;
457  }
458  if (strncmp(line->buf, "# getcwd: ", 10) != 0) {
459  E_ERROR("%s does not begin with '# getcwd: '\n%s", file, line->buf);
460  goto load_error;
461  }
462  if ((line = lineiter_next(line)) == NULL) {
463  E_ERROR("Premature EOF(%s)\n", file);
464  goto load_error;
465  }
466  if ((strncmp(line->buf, "# -logbase ", 11) != 0)
467  || (sscanf(line->buf + 11, "%lf", &lb) != 1)) {
468  E_WARN("%s: Cannot find -logbase in header\n", file);
469  lb = 1.0001;
470  }
471  logratio = 1.0f;
472  if (dag->lmath == NULL)
473  dag->lmath = logmath_init(lb, 0, TRUE);
474  else {
475  float32 pb = logmath_get_base(dag->lmath);
476  if (fabs(lb - pb) >= 0.0001) {
477  E_WARN("Inconsistent logbases: %f vs %f: will compensate\n", lb, pb);
478  logratio = (float32)(log(lb) / log(pb));
479  E_INFO("Lattice log ratio: %f\n", logratio);
480  }
481  }
482  /* Read Frames parameter */
483  dag->n_frames = dag_param_read(line, "Frames");
484  if (dag->n_frames <= 0) {
485  E_ERROR("Frames parameter missing or invalid\n");
486  goto load_error;
487  }
488  /* Read Nodes parameter */
489  n_nodes = dag_param_read(line, "Nodes");
490  if (n_nodes <= 0) {
491  E_ERROR("Nodes parameter missing or invalid\n");
492  goto load_error;
493  }
494 
495  /* Read nodes */
496  darray = ckd_calloc(n_nodes, sizeof(*darray));
497  for (i = 0; i < n_nodes; i++) {
498  ps_latnode_t *d;
499  int32 w;
500  int seqid, sf, fef, lef;
501  char wd[256];
502 
503  if ((line = lineiter_next(line)) == NULL) {
504  E_ERROR("Premature EOF while loading Nodes(%s)\n", file);
505  goto load_error;
506  }
507 
508  if ((k =
509  sscanf(line->buf, "%d %255s %d %d %d", &seqid, wd, &sf, &fef,
510  &lef)) != 5) {
511  E_ERROR("Cannot parse line: %s, value of count %d\n", line->buf, k);
512  goto load_error;
513  }
514 
515  w = dict_wordid(dag->dict, wd);
516  if (w < 0) {
517  if (dag->search == NULL) {
518  char *ww = ckd_salloc(wd);
519  if (dict_word2basestr(ww) != -1) {
520  if (dict_wordid(dag->dict, ww) == BAD_S3WID)
521  dict_add_word(dag->dict, ww, NULL, 0);
522  }
523  ckd_free(ww);
524  w = dict_add_word(dag->dict, wd, NULL, 0);
525  }
526  if (w < 0) {
527  E_ERROR("Unknown word in line: %s\n", line->buf);
528  goto load_error;
529  }
530  }
531 
532  if (seqid != i) {
533  E_ERROR("Seqno error: %s\n", line->buf);
534  goto load_error;
535  }
536 
537  d = listelem_malloc(dag->latnode_alloc);
538  darray[i] = d;
539  d->wid = w;
540  d->basewid = dict_basewid(dag->dict, w);
541  d->id = seqid;
542  d->sf = sf;
543  d->fef = fef;
544  d->lef = lef;
545  d->reachable = 0;
546  d->exits = d->entries = NULL;
547  d->next = NULL;
548 
549  if (!dag->nodes)
550  dag->nodes = d;
551  else
552  tail->next = d;
553  tail = d;
554  }
555 
556  /* Read initial node ID */
557  k = dag_param_read(line, "Initial");
558  if ((k < 0) || (k >= n_nodes)) {
559  E_ERROR("Initial node parameter missing or invalid\n");
560  goto load_error;
561  }
562  dag->start = darray[k];
563 
564  /* Read final node ID */
565  k = dag_param_read(line, "Final");
566  if ((k < 0) || (k >= n_nodes)) {
567  E_ERROR("Final node parameter missing or invalid\n");
568  goto load_error;
569  }
570  dag->end = darray[k];
571 
572  /* Read bestsegscore entries and ignore them. */
573  if ((k = dag_param_read(line, "BestSegAscr")) < 0) {
574  E_ERROR("BestSegAscr parameter missing\n");
575  goto load_error;
576  }
577  for (i = 0; i < k; i++) {
578  if ((line = lineiter_next(line)) == NULL) {
579  E_ERROR("Premature EOF while (%s) ignoring BestSegAscr\n",
580  line);
581  goto load_error;
582  }
583  }
584 
585  /* Read in edges. */
586  while ((line = lineiter_next(line)) != NULL) {
587  if (line->buf[0] == '#')
588  continue;
589  if (0 == strncmp(line->buf, "Edges", 5))
590  break;
591  }
592  if (line == NULL) {
593  E_ERROR("Edges missing\n");
594  goto load_error;
595  }
596  while ((line = lineiter_next(line)) != NULL) {
597  int from, to, ascr;
598  ps_latnode_t *pd, *d;
599 
600  if (sscanf(line->buf, "%d %d %d", &from, &to, &ascr) != 3)
601  break;
602  if (ascr WORSE_THAN WORST_SCORE)
603  continue;
604  pd = darray[from];
605  d = darray[to];
606  if (logratio != 1.0f)
607  ascr = (int32)(ascr * logratio);
608  ps_lattice_link(dag, pd, d, ascr, d->sf - 1);
609  }
610  if (strcmp(line->buf, "End\n") != 0) {
611  E_ERROR("Terminating 'End' missing\n");
612  goto load_error;
613  }
614  lineiter_free(line);
615  fclose_comp(fp, ispipe);
616  ckd_free(darray);
617 
618  /* Minor hack: If the final node is a filler word and not </s>,
619  * then set its base word ID to </s>, so that the language model
620  * scores won't be screwed up. */
621  if (dict_filler_word(dag->dict, dag->end->wid))
622  dag->end->basewid = dag->search
623  ? ps_search_finish_wid(dag->search)
624  : dict_wordid(dag->dict, S3_FINISH_WORD);
625 
626  /* Mark reachable from dag->end */
627  dag_mark_reachable(dag->end);
628 
629  /* Free nodes unreachable from dag->end and their links */
631 
632  if (ps) {
633  /* Build links around silence and filler words, since they do
634  * not exist in the language model. FIXME: This is
635  * potentially buggy, as we already do this before outputing
636  * lattices. */
637  pip = logmath_log(dag->lmath, cmd_ln_float32_r(ps->config, "-pip"));
638  silpen = pip + logmath_log(dag->lmath,
639  cmd_ln_float32_r(ps->config, "-silprob"));
640  fillpen = pip + logmath_log(dag->lmath,
641  cmd_ln_float32_r(ps->config, "-fillprob"));
642  ps_lattice_bypass_fillers(dag, silpen, fillpen);
643  }
644 
645  return dag;
646 
647  load_error:
648  E_ERROR("Failed to load %s\n", file);
649  lineiter_free(line);
650  if (fp) fclose_comp(fp, ispipe);
651  ckd_free(darray);
652  return NULL;
653 }
654 
655 int
657 {
658  return dag->n_frames;
659 }
660 
661 ps_lattice_t *
662 ps_lattice_init_search(ps_search_t *search, int n_frame)
663 {
664  ps_lattice_t *dag;
665 
666  dag = ckd_calloc(1, sizeof(*dag));
667  dag->search = search;
668  dag->dict = dict_retain(search->dict);
669  dag->lmath = logmath_retain(search->acmod->lmath);
670  dag->frate = cmd_ln_int32_r(dag->search->config, "-frate");
671  dag->silence = dict_silwid(dag->dict);
672  dag->n_frames = n_frame;
673  dag->latnode_alloc = listelem_alloc_init(sizeof(ps_latnode_t));
674  dag->latlink_alloc = listelem_alloc_init(sizeof(ps_latlink_t));
675  dag->latlink_list_alloc = listelem_alloc_init(sizeof(latlink_list_t));
676  dag->refcount = 1;
677  return dag;
678 }
679 
680 ps_lattice_t *
682 {
683  ++dag->refcount;
684  return dag;
685 }
686 
687 int
689 {
690  if (dag == NULL)
691  return 0;
692  if (--dag->refcount > 0)
693  return dag->refcount;
694  logmath_free(dag->lmath);
695  listelem_alloc_free(dag->latnode_alloc);
696  listelem_alloc_free(dag->latlink_alloc);
697  listelem_alloc_free(dag->latlink_list_alloc);
698  ckd_free(dag->hyp_str);
699  ckd_free(dag);
700  return 0;
701 }
702 
703 logmath_t *
705 {
706  return dag->lmath;
707 }
708 
711 {
712  return dag->nodes;
713 }
714 
717 {
718  return itor->next;
719 }
720 
721 void
723 {
724  /* Do absolutely nothing. */
725 }
726 
727 ps_latnode_t *
729 {
730  return itor;
731 }
732 
733 int
734 ps_latnode_times(ps_latnode_t *node, int16 *out_fef, int16 *out_lef)
735 {
736  if (out_fef) *out_fef = (int16)node->fef;
737  if (out_lef) *out_lef = (int16)node->lef;
738  return node->sf;
739 }
740 
741 char const *
743 {
744  return dict_wordstr(dag->dict, node->wid);
745 }
746 
747 char const *
749 {
750  return dict_wordstr(dag->dict, node->basewid);
751 }
752 
753 int32
755  ps_latlink_t **out_link)
756 {
757  latlink_list_t *links;
758  int32 bestpost = logmath_get_zero(dag->lmath);
759 
760  for (links = node->exits; links; links = links->next) {
761  int32 post = links->link->alpha + links->link->beta - dag->norm;
762  if (post > bestpost) {
763  if (out_link) *out_link = links->link;
764  bestpost = post;
765  }
766  }
767  return bestpost;
768 }
769 
772 {
773  return node->exits;
774 }
775 
778 {
779  return node->entries;
780 }
781 
784 {
785  return itor->next;
786 }
787 
788 void
790 {
791  /* Do absolutely nothing. */
792 }
793 
794 ps_latlink_t *
796 {
797  return itor->link;
798 }
799 
800 int
801 ps_latlink_times(ps_latlink_t *link, int16 *out_sf)
802 {
803  if (out_sf) {
804  if (link->from) {
805  *out_sf = link->from->sf;
806  }
807  else {
808  *out_sf = 0;
809  }
810  }
811  return link->ef;
812 }
813 
814 ps_latnode_t *
816 {
817  if (out_src) *out_src = link->from;
818  return link->to;
819 }
820 
821 char const *
823 {
824  if (link->from == NULL)
825  return NULL;
826  return dict_wordstr(dag->dict, link->from->wid);
827 }
828 
829 char const *
831 {
832  if (link->from == NULL)
833  return NULL;
834  return dict_wordstr(dag->dict, link->from->basewid);
835 }
836 
837 ps_latlink_t *
839 {
840  return link->best_prev;
841 }
842 
843 int32
844 ps_latlink_prob(ps_lattice_t *dag, ps_latlink_t *link, int32 *out_ascr)
845 {
846  int32 post = link->alpha + link->beta - dag->norm;
847  if (out_ascr) *out_ascr = link->ascr << SENSCR_SHIFT;
848  return post;
849 }
850 
851 char const *
853 {
854  ps_latlink_t *l;
855  size_t len;
856  char *c;
857 
858  /* Backtrace once to get hypothesis length. */
859  len = 0;
860  /* FIXME: There may not be a search, but actually there should be a dict. */
861  if (dict_real_word(dag->dict, link->to->basewid))
862  len += strlen(dict_wordstr(dag->dict, link->to->basewid)) + 1;
863  for (l = link; l; l = l->best_prev) {
864  if (dict_real_word(dag->dict, l->from->basewid))
865  len += strlen(dict_wordstr(dag->dict, l->from->basewid)) + 1;
866  }
867 
868  /* Backtrace again to construct hypothesis string. */
869  ckd_free(dag->hyp_str);
870  dag->hyp_str = ckd_calloc(1, len+1); /* extra one incase the hyp is empty */
871  c = dag->hyp_str + len - 1;
872  if (dict_real_word(dag->dict, link->to->basewid)) {
873  len = strlen(dict_wordstr(dag->dict, link->to->basewid));
874  c -= len;
875  memcpy(c, dict_wordstr(dag->dict, link->to->basewid), len);
876  if (c > dag->hyp_str) {
877  --c;
878  *c = ' ';
879  }
880  }
881  for (l = link; l; l = l->best_prev) {
882  if (dict_real_word(dag->dict, l->from->basewid)) {
883  len = strlen(dict_wordstr(dag->dict, l->from->basewid));
884  c -= len;
885  memcpy(c, dict_wordstr(dag->dict, l->from->basewid), len);
886  if (c > dag->hyp_str) {
887  --c;
888  *c = ' ';
889  }
890  }
891  }
892 
893  return dag->hyp_str;
894 }
895 
896 static void
897 ps_lattice_compute_lscr(ps_seg_t *seg, ps_latlink_t *link, int to)
898 {
899  ngram_model_t *lmset;
900 
901  /* Language model score is included in the link score for FSG
902  * search. FIXME: Of course, this is sort of a hack :( */
903  if (0 != strcmp(ps_search_name(seg->search), "ngram")) {
904  seg->lback = 1; /* Unigram... */
905  seg->lscr = 0;
906  return;
907  }
908 
909  lmset = ((ngram_search_t *)seg->search)->lmset;
910 
911  if (link->best_prev == NULL) {
912  if (to) /* Sentence has only two words. */
913  seg->lscr = ngram_bg_score(lmset, link->to->basewid,
914  link->from->basewid, &seg->lback)
915  >> SENSCR_SHIFT;
916  else {/* This is the start symbol, its lscr is always 0. */
917  seg->lscr = 0;
918  seg->lback = 1;
919  }
920  }
921  else {
922  /* Find the two predecessor words. */
923  if (to) {
924  seg->lscr = ngram_tg_score(lmset, link->to->basewid,
925  link->from->basewid,
926  link->best_prev->from->basewid,
927  &seg->lback) >> SENSCR_SHIFT;
928  }
929  else {
930  if (link->best_prev->best_prev)
931  seg->lscr = ngram_tg_score(lmset, link->from->basewid,
932  link->best_prev->from->basewid,
933  link->best_prev->best_prev->from->basewid,
934  &seg->lback) >> SENSCR_SHIFT;
935  else
936  seg->lscr = ngram_bg_score(lmset, link->from->basewid,
937  link->best_prev->from->basewid,
938  &seg->lback) >> SENSCR_SHIFT;
939  }
940  }
941 }
942 
943 static void
944 ps_lattice_link2itor(ps_seg_t *seg, ps_latlink_t *link, int to)
945 {
946  dag_seg_t *itor = (dag_seg_t *)seg;
947  ps_latnode_t *node;
948 
949  if (to) {
950  node = link->to;
951  seg->ef = node->lef;
952  seg->prob = 0; /* norm + beta - norm */
953  }
954  else {
955  latlink_list_t *x;
956  ps_latnode_t *n;
957  logmath_t *lmath = ps_search_acmod(seg->search)->lmath;
958 
959  node = link->from;
960  seg->ef = link->ef;
961  seg->prob = link->alpha + link->beta - itor->norm;
962  /* Sum over all exits for this word and any alternate
963  pronunciations at the same frame. */
964  for (n = node; n; n = n->alt) {
965  for (x = n->exits; x; x = x->next) {
966  if (x->link == link)
967  continue;
968  seg->prob = logmath_add(lmath, seg->prob,
969  x->link->alpha + x->link->beta - itor->norm);
970  }
971  }
972  }
973  seg->word = dict_wordstr(ps_search_dict(seg->search), node->wid);
974  seg->sf = node->sf;
975  seg->ascr = link->ascr << SENSCR_SHIFT;
976  /* Compute language model score from best predecessors. */
977  ps_lattice_compute_lscr(seg, link, to);
978 }
979 
980 static void
981 ps_lattice_seg_free(ps_seg_t *seg)
982 {
983  dag_seg_t *itor = (dag_seg_t *)seg;
984 
985  ckd_free(itor->links);
986  ckd_free(itor);
987 }
988 
989 static ps_seg_t *
990 ps_lattice_seg_next(ps_seg_t *seg)
991 {
992  dag_seg_t *itor = (dag_seg_t *)seg;
993 
994  ++itor->cur;
995  if (itor->cur == itor->n_links + 1) {
996  ps_lattice_seg_free(seg);
997  return NULL;
998  }
999  else if (itor->cur == itor->n_links) {
1000  /* Re-use the last link but with the "to" node. */
1001  ps_lattice_link2itor(seg, itor->links[itor->cur - 1], TRUE);
1002  }
1003  else {
1004  ps_lattice_link2itor(seg, itor->links[itor->cur], FALSE);
1005  }
1006 
1007  return seg;
1008 }
1009 
1010 static ps_segfuncs_t ps_lattice_segfuncs = {
1011  /* seg_next */ ps_lattice_seg_next,
1012  /* seg_free */ ps_lattice_seg_free
1013 };
1014 
1015 ps_seg_t *
1017 {
1018  dag_seg_t *itor;
1019  ps_latlink_t *l;
1020  int cur;
1021 
1022  /* Calling this an "iterator" is a bit of a misnomer since we have
1023  * to get the entire backtrace in order to produce it.
1024  */
1025  itor = ckd_calloc(1, sizeof(*itor));
1026  itor->base.vt = &ps_lattice_segfuncs;
1027  itor->base.search = dag->search;
1028  itor->base.lwf = lwf;
1029  itor->n_links = 0;
1030  itor->norm = dag->norm;
1031 
1032  for (l = link; l; l = l->best_prev) {
1033  ++itor->n_links;
1034  }
1035  if (itor->n_links == 0) {
1036  ckd_free(itor);
1037  return NULL;
1038  }
1039 
1040  itor->links = ckd_calloc(itor->n_links, sizeof(*itor->links));
1041  cur = itor->n_links - 1;
1042  for (l = link; l; l = l->best_prev) {
1043  itor->links[cur] = l;
1044  --cur;
1045  }
1046 
1047  ps_lattice_link2itor((ps_seg_t *)itor, itor->links[0], FALSE);
1048  return (ps_seg_t *)itor;
1049 }
1050 
1053 {
1054  latlink_list_t *ll;
1055 
1056  ll = listelem_malloc(dag->latlink_list_alloc);
1057  ll->link = link;
1058  ll->next = next;
1059 
1060  return ll;
1061 }
1062 
1063 void
1065 {
1066  if (dag->q_head == NULL)
1067  dag->q_head = dag->q_tail = latlink_list_new(dag, link, NULL);
1068  else {
1069  dag->q_tail->next = latlink_list_new(dag, link, NULL);
1070  dag->q_tail = dag->q_tail->next;
1071  }
1072 
1073 }
1074 
1075 ps_latlink_t *
1077 {
1078  latlink_list_t *x;
1079  ps_latlink_t *link;
1080 
1081  if (dag->q_head == NULL)
1082  return NULL;
1083  link = dag->q_head->link;
1084  x = dag->q_head->next;
1085  listelem_free(dag->latlink_list_alloc, dag->q_head);
1086  dag->q_head = x;
1087  if (dag->q_head == NULL)
1088  dag->q_tail = NULL;
1089  return link;
1090 }
1091 
1092 void
1094 {
1095  while (ps_lattice_popq(dag)) {
1096  /* Do nothing. */
1097  }
1098 }
1099 
1100 ps_latlink_t *
1102 {
1103  ps_latnode_t *node;
1104  latlink_list_t *x;
1105 
1106  /* Cancel any unfinished traversal. */
1107  ps_lattice_delq(dag);
1108 
1109  /* Initialize node fanin counts and path scores. */
1110  for (node = dag->nodes; node; node = node->next)
1111  node->info.fanin = 0;
1112  for (node = dag->nodes; node; node = node->next) {
1113  for (x = node->exits; x; x = x->next)
1114  (x->link->to->info.fanin)++;
1115  }
1116 
1117  /* Initialize agenda with all exits from start. */
1118  if (start == NULL) start = dag->start;
1119  for (x = start->exits; x; x = x->next)
1120  ps_lattice_pushq(dag, x->link);
1121 
1122  /* Pull the first edge off the queue. */
1123  return ps_lattice_traverse_next(dag, end);
1124 }
1125 
1126 ps_latlink_t *
1128 {
1129  ps_latlink_t *next;
1130 
1131  next = ps_lattice_popq(dag);
1132  if (next == NULL)
1133  return NULL;
1134 
1135  /* Decrease fanin count for destination node and expand outgoing
1136  * edges if all incoming edges have been seen. */
1137  --next->to->info.fanin;
1138  if (next->to->info.fanin == 0) {
1139  latlink_list_t *x;
1140 
1141  if (end == NULL) end = dag->end;
1142  if (next->to == end) {
1143  /* If we have traversed all links entering the end node,
1144  * clear the queue, causing future calls to this function
1145  * to return NULL. */
1146  ps_lattice_delq(dag);
1147  return next;
1148  }
1149 
1150  /* Extend all outgoing edges. */
1151  for (x = next->to->exits; x; x = x->next)
1152  ps_lattice_pushq(dag, x->link);
1153  }
1154  return next;
1155 }
1156 
1157 ps_latlink_t *
1159 {
1160  ps_latnode_t *node;
1161  latlink_list_t *x;
1162 
1163  /* Cancel any unfinished traversal. */
1164  ps_lattice_delq(dag);
1165 
1166  /* Initialize node fanout counts and path scores. */
1167  for (node = dag->nodes; node; node = node->next) {
1168  node->info.fanin = 0;
1169  for (x = node->exits; x; x = x->next)
1170  ++node->info.fanin;
1171  }
1172 
1173  /* Initialize agenda with all entries from end. */
1174  if (end == NULL) end = dag->end;
1175  for (x = end->entries; x; x = x->next)
1176  ps_lattice_pushq(dag, x->link);
1177 
1178  /* Pull the first edge off the queue. */
1179  return ps_lattice_reverse_next(dag, start);
1180 }
1181 
1182 ps_latlink_t *
1184 {
1185  ps_latlink_t *next;
1186 
1187  next = ps_lattice_popq(dag);
1188  if (next == NULL)
1189  return NULL;
1190 
1191  /* Decrease fanout count for source node and expand incoming
1192  * edges if all incoming edges have been seen. */
1193  --next->from->info.fanin;
1194  if (next->from->info.fanin == 0) {
1195  latlink_list_t *x;
1196 
1197  if (start == NULL) start = dag->start;
1198  if (next->from == start) {
1199  /* If we have traversed all links entering the start node,
1200  * clear the queue, causing future calls to this function
1201  * to return NULL. */
1202  ps_lattice_delq(dag);
1203  return next;
1204  }
1205 
1206  /* Extend all outgoing edges. */
1207  for (x = next->from->entries; x; x = x->next)
1208  ps_lattice_pushq(dag, x->link);
1209  }
1210  return next;
1211 }
1212 
1213 /*
1214  * Find the best score from dag->start to end point of any link and
1215  * use it to update links further down the path. This is like
1216  * single-source shortest path search, except that it is done over
1217  * edges rather than nodes, which allows us to do exact trigram scoring.
1218  *
1219  * Helpfully enough, we get half of the posterior probability
1220  * calculation for free that way too. (interesting research topic: is
1221  * there a reliable Viterbi analogue to word-level Forward-Backward
1222  * like there is for state-level? Or, is it just lattice density?)
1223  */
1224 ps_latlink_t *
1225 ps_lattice_bestpath(ps_lattice_t *dag, ngram_model_t *lmset,
1226  float32 lwf, float32 ascale)
1227 {
1228  ps_search_t *search;
1229  ps_latnode_t *node;
1230  ps_latlink_t *link;
1231  ps_latlink_t *bestend;
1232  latlink_list_t *x;
1233  logmath_t *lmath;
1234  int32 bestescr;
1235 
1236  search = dag->search;
1237  lmath = dag->lmath;
1238 
1239  /* Initialize path scores for all links exiting dag->start, and
1240  * set all other scores to the minimum. Also initialize alphas to
1241  * log-zero. */
1242  for (node = dag->nodes; node; node = node->next) {
1243  for (x = node->exits; x; x = x->next) {
1244  x->link->path_scr = MAX_NEG_INT32;
1245  x->link->alpha = logmath_get_zero(lmath);
1246  }
1247  }
1248  for (x = dag->start->exits; x; x = x->next) {
1249  int32 n_used;
1250 
1251  /* Ignore filler words. */
1252  if (dict_filler_word(ps_search_dict(search), x->link->to->basewid)
1253  && x->link->to != dag->end)
1254  continue;
1255 
1256  /* Best path points to dag->start, obviously. */
1257  if (lmset)
1258  x->link->path_scr = x->link->ascr +
1259  (ngram_bg_score(lmset, x->link->to->basewid,
1260  ps_search_start_wid(search), &n_used)
1261  >> SENSCR_SHIFT)
1262  * lwf;
1263  else
1264  x->link->path_scr = x->link->ascr;
1265  x->link->best_prev = NULL;
1266  /* No predecessors for start links. */
1267  x->link->alpha = 0;
1268  }
1269 
1270  /* Traverse the edges in the graph, updating path scores. */
1271  for (link = ps_lattice_traverse_edges(dag, NULL, NULL);
1272  link; link = ps_lattice_traverse_next(dag, NULL)) {
1273  int32 bprob, n_used;
1274 
1275  /* Skip filler nodes in traversal. */
1276  if (dict_filler_word(ps_search_dict(search), link->from->basewid) && link->from != dag->start)
1277  continue;
1278  if (dict_filler_word(ps_search_dict(search), link->to->basewid) && link->to != dag->end)
1279  continue;
1280 
1281  /* Sanity check, we should not be traversing edges that
1282  * weren't previously updated, otherwise nasty overflows will result. */
1283  assert(link->path_scr != MAX_NEG_INT32);
1284 
1285  /* Calculate common bigram probability for all alphas. */
1286  if (lmset)
1287  bprob = ngram_ng_prob(lmset,
1288  link->to->basewid,
1289  &link->from->basewid, 1, &n_used);
1290  else
1291  bprob = 0;
1292  /* Add in this link's acoustic score, which was a constant
1293  factor in previous computations (if any). */
1294  link->alpha += (link->ascr << SENSCR_SHIFT) * ascale;
1295 
1296  /* Update scores for all paths exiting link->to. */
1297  for (x = link->to->exits; x; x = x->next) {
1298  int32 tscore, score;
1299 
1300  /* Skip links to filler words in update. */
1301  if (dict_filler_word(ps_search_dict(search), x->link->to->basewid)
1302  && x->link->to != dag->end)
1303  continue;
1304 
1305  /* Update alpha with sum of previous alphas. */
1306  x->link->alpha = logmath_add(lmath, x->link->alpha, link->alpha + bprob);
1307  /* Calculate trigram score for bestpath. */
1308  if (lmset)
1309  tscore = (ngram_tg_score(lmset, x->link->to->basewid,
1310  link->to->basewid,
1311  link->from->basewid, &n_used) >> SENSCR_SHIFT)
1312  * lwf;
1313  else
1314  tscore = 0;
1315  /* Update link score with maximum link score. */
1316  score = link->path_scr + tscore + x->link->ascr;
1317  if (score BETTER_THAN x->link->path_scr) {
1318  x->link->path_scr = score;
1319  x->link->best_prev = link;
1320  }
1321  }
1322  }
1323 
1324  /* Find best link entering final node, and calculate normalizer
1325  * for posterior probabilities. */
1326  bestend = NULL;
1327  bestescr = MAX_NEG_INT32;
1328 
1329  /* Normalizer is the alpha for the imaginary link exiting the
1330  final node. */
1331  dag->norm = logmath_get_zero(lmath);
1332  for (x = dag->end->entries; x; x = x->next) {
1333  int32 bprob, n_used;
1334 
1335  if (dict_filler_word(ps_search_dict(search), x->link->from->basewid))
1336  continue;
1337  if (lmset)
1338  bprob = ngram_ng_prob(lmset,
1339  x->link->to->basewid,
1340  &x->link->from->basewid, 1, &n_used);
1341  else
1342  bprob = 0;
1343  dag->norm = logmath_add(lmath, dag->norm, x->link->alpha + bprob);
1344  if (x->link->path_scr BETTER_THAN bestescr) {
1345  bestescr = x->link->path_scr;
1346  bestend = x->link;
1347  }
1348  }
1349  /* FIXME: floating point... */
1350  dag->norm += (int32)(dag->final_node_ascr << SENSCR_SHIFT) * ascale;
1351 
1352  E_INFO("Normalizer P(O) = alpha(%s:%d:%d) = %d\n",
1353  dict_wordstr(dag->search->dict, dag->end->wid),
1354  dag->end->sf, dag->end->lef,
1355  dag->norm);
1356  return bestend;
1357 }
1358 
1359 static int32
1360 ps_lattice_joint(ps_lattice_t *dag, ps_latlink_t *link, float32 ascale)
1361 {
1362  ngram_model_t *lmset;
1363  int32 jprob;
1364 
1365  /* Sort of a hack... */
1366  if (dag->search && 0 == strcmp(ps_search_name(dag->search), "ngram"))
1367  lmset = ((ngram_search_t *)dag->search)->lmset;
1368  else
1369  lmset = NULL;
1370 
1371  jprob = (dag->final_node_ascr << SENSCR_SHIFT) * ascale;
1372  while (link) {
1373  if (lmset) {
1374  int lback;
1375  /* Compute unscaled language model probability. Note that
1376  this is actually not the language model probability
1377  that corresponds to this link, but that is okay,
1378  because we are just taking the sum over all links in
1379  the best path. */
1380  jprob += ngram_ng_prob(lmset, link->to->basewid,
1381  &link->from->basewid, 1, &lback);
1382  }
1383  /* If there is no language model, we assume that the language
1384  model probability (such as it is) has been included in the
1385  link score. */
1386  jprob += (link->ascr << SENSCR_SHIFT) * ascale;
1387  link = link->best_prev;
1388  }
1389 
1390  E_INFO("Joint P(O,S) = %d P(S|O) = %d\n", jprob, jprob - dag->norm);
1391  return jprob;
1392 }
1393 
1394 int32
1395 ps_lattice_posterior(ps_lattice_t *dag, ngram_model_t *lmset,
1396  float32 ascale)
1397 {
1398  ps_search_t *search;
1399  logmath_t *lmath;
1400  ps_latnode_t *node;
1401  ps_latlink_t *link;
1402  latlink_list_t *x;
1403  ps_latlink_t *bestend;
1404  int32 bestescr;
1405 
1406  search = dag->search;
1407  lmath = dag->lmath;
1408 
1409  /* Reset all betas to zero. */
1410  for (node = dag->nodes; node; node = node->next) {
1411  for (x = node->exits; x; x = x->next) {
1412  x->link->beta = logmath_get_zero(lmath);
1413  }
1414  }
1415 
1416  bestend = NULL;
1417  bestescr = MAX_NEG_INT32;
1418  /* Accumulate backward probabilities for all links. */
1419  for (link = ps_lattice_reverse_edges(dag, NULL, NULL);
1420  link; link = ps_lattice_reverse_next(dag, NULL)) {
1421  int32 bprob, n_used;
1422 
1423  /* Skip filler nodes in traversal. */
1424  if (dict_filler_word(ps_search_dict(search), link->from->basewid) && link->from != dag->start)
1425  continue;
1426  if (dict_filler_word(ps_search_dict(search), link->to->basewid) && link->to != dag->end)
1427  continue;
1428 
1429  /* Calculate LM probability. */
1430  if (lmset)
1431  bprob = ngram_ng_prob(lmset, link->to->basewid,
1432  &link->from->basewid, 1, &n_used);
1433  else
1434  bprob = 0;
1435 
1436  if (link->to == dag->end) {
1437  /* Track the best path - we will backtrace in order to
1438  calculate the unscaled joint probability for sentence
1439  posterior. */
1440  if (link->path_scr BETTER_THAN bestescr) {
1441  bestescr = link->path_scr;
1442  bestend = link;
1443  }
1444  /* Imaginary exit link from final node has beta = 1.0 */
1445  link->beta = bprob + (dag->final_node_ascr << SENSCR_SHIFT) * ascale;
1446  }
1447  else {
1448  /* Update beta from all outgoing betas. */
1449  for (x = link->to->exits; x; x = x->next) {
1450  if (dict_filler_word(ps_search_dict(search), x->link->to->basewid) && x->link->to != dag->end)
1451  continue;
1452  link->beta = logmath_add(lmath, link->beta,
1453  x->link->beta + bprob
1454  + (x->link->ascr << SENSCR_SHIFT) * ascale);
1455  }
1456  }
1457  }
1458 
1459  /* Return P(S|O) = P(O,S)/P(O) */
1460  return ps_lattice_joint(dag, bestend, ascale) - dag->norm;
1461 }
1462 
1463 int32
1465 {
1466  ps_latlink_t *link;
1467  int npruned = 0;
1468 
1469  for (link = ps_lattice_traverse_edges(dag, dag->start, dag->end);
1470  link; link = ps_lattice_traverse_next(dag, dag->end)) {
1471  link->from->reachable = FALSE;
1472  if (link->alpha + link->beta - dag->norm < beam) {
1473  latlink_list_t *x, *tmp, *next;
1474  tmp = NULL;
1475  for (x = link->from->exits; x; x = next) {
1476  next = x->next;
1477  if (x->link == link) {
1478  listelem_free(dag->latlink_list_alloc, x);
1479  }
1480  else {
1481  x->next = tmp;
1482  tmp = x;
1483  }
1484  }
1485  link->from->exits = tmp;
1486  tmp = NULL;
1487  for (x = link->to->entries; x; x = next) {
1488  next = x->next;
1489  if (x->link == link) {
1490  listelem_free(dag->latlink_list_alloc, x);
1491  }
1492  else {
1493  x->next = tmp;
1494  tmp = x;
1495  }
1496  }
1497  link->to->entries = tmp;
1498  listelem_free(dag->latlink_alloc, link);
1499  ++npruned;
1500  }
1501  }
1502  dag_mark_reachable(dag->end);
1504  return npruned;
1505 }
1506 
1507 
1508 /* Parameters to prune n-best alternatives search */
1509 #define MAX_PATHS 500 /* Max allowed active paths at any time */
1510 #define MAX_HYP_TRIES 10000
1511 
1512 /*
1513  * For each node in any path between from and end of utt, find the
1514  * best score from "from".sf to end of utt. (NOTE: Uses bigram probs;
1515  * this is an estimate of the best score from "from".) (NOTE #2: yes,
1516  * this is the "heuristic score" used in A* search)
1517  */
1518 static int32
1519 best_rem_score(ps_astar_t *nbest, ps_latnode_t * from)
1520 {
1521  ps_lattice_t *dag;
1522  latlink_list_t *x;
1523  int32 bestscore, score;
1524 
1525  dag = nbest->dag;
1526  if (from->info.rem_score <= 0)
1527  return (from->info.rem_score);
1528 
1529  /* Best score from "from" to end of utt not known; compute from successors */
1530  bestscore = WORST_SCORE;
1531  for (x = from->exits; x; x = x->next) {
1532  int32 n_used;
1533 
1534  score = best_rem_score(nbest, x->link->to);
1535  score += x->link->ascr;
1536  if (nbest->lmset)
1537  score += (ngram_bg_score(nbest->lmset, x->link->to->basewid,
1538  from->basewid, &n_used) >> SENSCR_SHIFT)
1539  * nbest->lwf;
1540  if (score BETTER_THAN bestscore)
1541  bestscore = score;
1542  }
1543  from->info.rem_score = bestscore;
1544 
1545  return bestscore;
1546 }
1547 
1548 /*
1549  * Insert newpath in sorted (by path score) list of paths. But if newpath is
1550  * too far down the list, drop it (FIXME: necessary?)
1551  * total_score = path score (newpath) + rem_score to end of utt.
1552  */
1553 static void
1554 path_insert(ps_astar_t *nbest, ps_latpath_t *newpath, int32 total_score)
1555 {
1556  ps_lattice_t *dag;
1557  ps_latpath_t *prev, *p;
1558  int32 i;
1559 
1560  dag = nbest->dag;
1561  prev = NULL;
1562  for (i = 0, p = nbest->path_list; (i < MAX_PATHS) && p; p = p->next, i++) {
1563  if ((p->score + p->node->info.rem_score) < total_score)
1564  break;
1565  prev = p;
1566  }
1567 
1568  /* newpath should be inserted between prev and p */
1569  if (i < MAX_PATHS) {
1570  /* Insert new partial hyp */
1571  newpath->next = p;
1572  if (!prev)
1573  nbest->path_list = newpath;
1574  else
1575  prev->next = newpath;
1576  if (!p)
1577  nbest->path_tail = newpath;
1578 
1579  nbest->n_path++;
1580  nbest->n_hyp_insert++;
1581  nbest->insert_depth += i;
1582  }
1583  else {
1584  /* newpath score too low; reject it and also prune paths beyond MAX_PATHS */
1585  nbest->path_tail = prev;
1586  prev->next = NULL;
1587  nbest->n_path = MAX_PATHS;
1588  listelem_free(nbest->latpath_alloc, newpath);
1589 
1590  nbest->n_hyp_reject++;
1591  for (; p; p = newpath) {
1592  newpath = p->next;
1593  listelem_free(nbest->latpath_alloc, p);
1594  nbest->n_hyp_reject++;
1595  }
1596  }
1597 }
1598 
1599 /* Find all possible extensions to given partial path */
1600 static void
1601 path_extend(ps_astar_t *nbest, ps_latpath_t * path)
1602 {
1603  latlink_list_t *x;
1604  ps_latpath_t *newpath;
1605  int32 total_score, tail_score;
1606  ps_lattice_t *dag;
1607 
1608  dag = nbest->dag;
1609 
1610  /* Consider all successors of path->node */
1611  for (x = path->node->exits; x; x = x->next) {
1612  int32 n_used;
1613 
1614  /* Skip successor if no path from it reaches the final node */
1615  if (x->link->to->info.rem_score <= WORST_SCORE)
1616  continue;
1617 
1618  /* Create path extension and compute exact score for this extension */
1619  newpath = listelem_malloc(nbest->latpath_alloc);
1620  newpath->node = x->link->to;
1621  newpath->parent = path;
1622  newpath->score = path->score + x->link->ascr;
1623  if (nbest->lmset) {
1624  if (path->parent) {
1625  newpath->score += nbest->lwf
1626  * (ngram_tg_score(nbest->lmset, newpath->node->basewid,
1627  path->node->basewid,
1628  path->parent->node->basewid, &n_used)
1629  >> SENSCR_SHIFT);
1630  }
1631  else
1632  newpath->score += nbest->lwf
1633  * (ngram_bg_score(nbest->lmset, newpath->node->basewid,
1634  path->node->basewid, &n_used)
1635  >> SENSCR_SHIFT);
1636  }
1637 
1638  /* Insert new partial path hypothesis into sorted path_list */
1639  nbest->n_hyp_tried++;
1640  total_score = newpath->score + newpath->node->info.rem_score;
1641 
1642  /* First see if hyp would be worse than the worst */
1643  if (nbest->n_path >= MAX_PATHS) {
1644  tail_score =
1645  nbest->path_tail->score
1646  + nbest->path_tail->node->info.rem_score;
1647  if (total_score < tail_score) {
1648  listelem_free(nbest->latpath_alloc, newpath);
1649  nbest->n_hyp_reject++;
1650  continue;
1651  }
1652  }
1653 
1654  path_insert(nbest, newpath, total_score);
1655  }
1656 }
1657 
1658 ps_astar_t *
1660  ngram_model_t *lmset,
1661  float32 lwf,
1662  int sf, int ef,
1663  int w1, int w2)
1664 {
1665  ps_astar_t *nbest;
1666  ps_latnode_t *node;
1667 
1668  nbest = ckd_calloc(1, sizeof(*nbest));
1669  nbest->dag = dag;
1670  nbest->lmset = lmset;
1671  nbest->lwf = lwf;
1672  nbest->sf = sf;
1673  if (ef < 0)
1674  nbest->ef = dag->n_frames + 1;
1675  else
1676  nbest->ef = ef;
1677  nbest->w1 = w1;
1678  nbest->w2 = w2;
1679  nbest->latpath_alloc = listelem_alloc_init(sizeof(ps_latpath_t));
1680 
1681  /* Initialize rem_score (A* heuristic) to default values */
1682  for (node = dag->nodes; node; node = node->next) {
1683  if (node == dag->end)
1684  node->info.rem_score = 0;
1685  else if (node->exits == NULL)
1686  node->info.rem_score = WORST_SCORE;
1687  else
1688  node->info.rem_score = 1; /* +ve => unknown value */
1689  }
1690 
1691  /* Create initial partial hypotheses list consisting of nodes starting at sf */
1692  nbest->path_list = nbest->path_tail = NULL;
1693  for (node = dag->nodes; node; node = node->next) {
1694  if (node->sf == sf) {
1695  ps_latpath_t *path;
1696  int32 n_used;
1697 
1698  best_rem_score(nbest, node);
1699  path = listelem_malloc(nbest->latpath_alloc);
1700  path->node = node;
1701  path->parent = NULL;
1702  if (nbest->lmset)
1703  path->score = nbest->lwf *
1704  (w1 < 0)
1705  ? ngram_bg_score(nbest->lmset, node->basewid, w2, &n_used)
1706  : ngram_tg_score(nbest->lmset, node->basewid, w2, w1, &n_used);
1707  else
1708  path->score = 0;
1709  path->score >>= SENSCR_SHIFT;
1710  path_insert(nbest, path, path->score + node->info.rem_score);
1711  }
1712  }
1713 
1714  return nbest;
1715 }
1716 
1717 ps_latpath_t *
1719 {
1720  ps_lattice_t *dag;
1721 
1722  dag = nbest->dag;
1723 
1724  /* Pop the top (best) partial hypothesis */
1725  while ((nbest->top = nbest->path_list) != NULL) {
1726  nbest->path_list = nbest->path_list->next;
1727  if (nbest->top == nbest->path_tail)
1728  nbest->path_tail = NULL;
1729  nbest->n_path--;
1730 
1731  /* Complete hypothesis? */
1732  if ((nbest->top->node->sf >= nbest->ef)
1733  || ((nbest->top->node == dag->end) &&
1734  (nbest->ef > dag->end->sf))) {
1735  /* FIXME: Verify that it is non-empty. Also we may want
1736  * to verify that it is actually distinct from other
1737  * paths, since often this is not the case*/
1738  return nbest->top;
1739  }
1740  else {
1741  if (nbest->top->node->fef < nbest->ef)
1742  path_extend(nbest, nbest->top);
1743  }
1744  }
1745 
1746  /* Did not find any more paths to extend. */
1747  return NULL;
1748 }
1749 
1750 char const *
1752 {
1753  ps_search_t *search;
1754  ps_latpath_t *p;
1755  size_t len;
1756  char *c;
1757  char *hyp;
1758 
1759  search = nbest->dag->search;
1760 
1761  /* Backtrace once to get hypothesis length. */
1762  len = 0;
1763  for (p = path; p; p = p->parent) {
1764  if (dict_real_word(ps_search_dict(search), p->node->basewid))
1765  len += strlen(dict_wordstr(ps_search_dict(search), p->node->basewid)) + 1;
1766  }
1767 
1768  if (len == 0) {
1769  return NULL;
1770  }
1771 
1772  /* Backtrace again to construct hypothesis string. */
1773  hyp = ckd_calloc(1, len);
1774  c = hyp + len - 1;
1775  for (p = path; p; p = p->parent) {
1776  if (dict_real_word(ps_search_dict(search), p->node->basewid)) {
1777  len = strlen(dict_wordstr(ps_search_dict(search), p->node->basewid));
1778  c -= len;
1779  memcpy(c, dict_wordstr(ps_search_dict(search), p->node->basewid), len);
1780  if (c > hyp) {
1781  --c;
1782  *c = ' ';
1783  }
1784  }
1785  }
1786 
1787  nbest->hyps = glist_add_ptr(nbest->hyps, hyp);
1788  return hyp;
1789 }
1790 
1791 static void
1792 ps_astar_node2itor(astar_seg_t *itor)
1793 {
1794  ps_seg_t *seg = (ps_seg_t *)itor;
1795  ps_latnode_t *node;
1796 
1797  assert(itor->cur < itor->n_nodes);
1798  node = itor->nodes[itor->cur];
1799  if (itor->cur == itor->n_nodes - 1)
1800  seg->ef = node->lef;
1801  else
1802  seg->ef = itor->nodes[itor->cur + 1]->sf - 1;
1803  seg->word = dict_wordstr(ps_search_dict(seg->search), node->wid);
1804  seg->sf = node->sf;
1805  seg->prob = 0; /* FIXME: implement forward-backward */
1806 }
1807 
1808 static void
1809 ps_astar_seg_free(ps_seg_t *seg)
1810 {
1811  astar_seg_t *itor = (astar_seg_t *)seg;
1812  ckd_free(itor->nodes);
1813  ckd_free(itor);
1814 }
1815 
1816 static ps_seg_t *
1817 ps_astar_seg_next(ps_seg_t *seg)
1818 {
1819  astar_seg_t *itor = (astar_seg_t *)seg;
1820 
1821  ++itor->cur;
1822  if (itor->cur == itor->n_nodes) {
1823  ps_astar_seg_free(seg);
1824  return NULL;
1825  }
1826  else {
1827  ps_astar_node2itor(itor);
1828  }
1829 
1830  return seg;
1831 }
1832 
1833 static ps_segfuncs_t ps_astar_segfuncs = {
1834  /* seg_next */ ps_astar_seg_next,
1835  /* seg_free */ ps_astar_seg_free
1836 };
1837 
1838 ps_seg_t *
1839 ps_astar_seg_iter(ps_astar_t *astar, ps_latpath_t *path, float32 lwf)
1840 {
1841  astar_seg_t *itor;
1842  ps_latpath_t *p;
1843  int cur;
1844 
1845  /* Backtrace and make an iterator, this should look familiar by now. */
1846  itor = ckd_calloc(1, sizeof(*itor));
1847  itor->base.vt = &ps_astar_segfuncs;
1848  itor->base.search = astar->dag->search;
1849  itor->base.lwf = lwf;
1850  itor->n_nodes = itor->cur = 0;
1851  for (p = path; p; p = p->parent) {
1852  ++itor->n_nodes;
1853  }
1854  itor->nodes = ckd_calloc(itor->n_nodes, sizeof(*itor->nodes));
1855  cur = itor->n_nodes - 1;
1856  for (p = path; p; p = p->parent) {
1857  itor->nodes[cur] = p->node;
1858  --cur;
1859  }
1860 
1861  ps_astar_node2itor(itor);
1862  return (ps_seg_t *)itor;
1863 }
1864 
1865 void
1867 {
1868  gnode_t *gn;
1869 
1870  /* Free all hyps. */
1871  for (gn = nbest->hyps; gn; gn = gnode_next(gn)) {
1872  ckd_free(gnode_ptr(gn));
1873  }
1874  glist_free(nbest->hyps);
1875  /* Free all paths. */
1876  listelem_alloc_free(nbest->latpath_alloc);
1877  /* Free the Henge. */
1878  ckd_free(nbest);
1879 }