PocketSphinx  5prealpha
fsg_history.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_history.c -- FSG Viterbi decode history
37  *
38  * **********************************************
39  * CMU ARPA Speech Project
40  *
41  * Copyright (c) 1999 Carnegie Mellon University.
42  * ALL RIGHTS RESERVED.
43  * **********************************************
44  *
45  * HISTORY
46  *
47  * 25-Feb-2004 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
48  * Started..
49  */
50 
51 /* System headers. */
52 #include <assert.h>
53 
54 /* SphinxBase headers. */
55 #include <sphinxbase/prim_type.h>
56 #include <sphinxbase/err.h>
57 #include <sphinxbase/ckd_alloc.h>
58 
59 /* Local headers. */
60 #include "fsg_search_internal.h"
61 #include "fsg_history.h"
62 
63 
64 #define __FSG_DBG__ 0
65 
66 
68 fsg_history_init(fsg_model_t * fsg, dict_t *dict)
69 {
70  fsg_history_t *h;
71 
72  h = (fsg_history_t *) ckd_calloc(1, sizeof(fsg_history_t));
73  h->fsg = fsg;
74  h->entries = blkarray_list_init();
75 
76  if (fsg && dict) {
77  h->n_ciphone = bin_mdef_n_ciphone(dict->mdef);
78  h->frame_entries =
79  (glist_t **) ckd_calloc_2d(fsg_model_n_state(fsg),
80  bin_mdef_n_ciphone(dict->mdef),
81  sizeof(**h->frame_entries));
82  }
83  else {
84  h->frame_entries = NULL;
85  }
86 
87  return h;
88 }
89 
90 void
91 fsg_history_free(fsg_history_t *h)
92 {
93  int32 s, lc, ns, np;
94  gnode_t *gn;
95 
96  if (h->fsg) {
97  ns = fsg_model_n_state(h->fsg);
98  np = h->n_ciphone;
99 
100  for (s = 0; s < ns; s++) {
101  for (lc = 0; lc < np; lc++) {
102  for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
103  ckd_free(gnode_ptr(gn));
104  }
105  glist_free(h->frame_entries[s][lc]);
106  }
107  }
108  }
109  ckd_free_2d(h->frame_entries);
110  blkarray_list_free(h->entries);
111  ckd_free(h);
112 }
113 
114 
115 void
116 fsg_history_set_fsg(fsg_history_t *h, fsg_model_t *fsg, dict_t *dict)
117 {
118  if (blkarray_list_n_valid(h->entries) != 0) {
119  E_WARN("Switching FSG while history not empty; history cleared\n");
120  blkarray_list_reset(h->entries);
121  }
122 
123  if (h->frame_entries)
124  ckd_free_2d((void **) h->frame_entries);
125  h->frame_entries = NULL;
126  h->fsg = fsg;
127 
128  if (fsg && dict) {
129  h->n_ciphone = bin_mdef_n_ciphone(dict->mdef);
130  h->frame_entries =
131  (glist_t **) ckd_calloc_2d(fsg_model_n_state(fsg),
132  bin_mdef_n_ciphone(dict->mdef),
133  sizeof(glist_t));
134  }
135 }
136 
137 
138 void
139 fsg_history_entry_add(fsg_history_t * h,
140  fsg_link_t * link,
141  int32 frame, int32 score, int32 pred,
142  int32 lc, fsg_pnode_ctxt_t rc)
143 {
144  fsg_hist_entry_t *entry, *new_entry;
145  int32 s;
146  gnode_t *gn, *prev_gn;
147 
148  /* Skip the optimization for the initial dummy entries; always enter them */
149  if (frame < 0) {
150  new_entry =
151  (fsg_hist_entry_t *) ckd_calloc(1, sizeof(fsg_hist_entry_t));
152  new_entry->fsglink = link;
153  new_entry->frame = frame;
154  new_entry->score = score;
155  new_entry->pred = pred;
156  new_entry->lc = lc;
157  new_entry->rc = rc;
158 
159  blkarray_list_append(h->entries, (void *) new_entry);
160  return;
161  }
162 
163  s = fsg_link_to_state(link);
164 
165  /* Locate where this entry should be inserted in frame_entries[s][lc] */
166  prev_gn = NULL;
167  for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
168  entry = (fsg_hist_entry_t *) gnode_ptr(gn);
169 
170  if (score BETTER_THAN entry->score)
171  break; /* Found where to insert new entry */
172 
173  /* Existing entry score not worse than new score */
174  if (FSG_PNODE_CTXT_SUB(&rc, &(entry->rc)) == 0)
175  return; /* rc set reduced to 0; new entry can be ignored */
176 
177  prev_gn = gn;
178  }
179 
180  /* Create new entry after prev_gn (if prev_gn is NULL, at head) */
181  new_entry =
182  (fsg_hist_entry_t *) ckd_calloc(1, sizeof(fsg_hist_entry_t));
183  new_entry->fsglink = link;
184  new_entry->frame = frame;
185  new_entry->score = score;
186  new_entry->pred = pred;
187  new_entry->lc = lc;
188  new_entry->rc = rc; /* Note: rc set must be non-empty at this point */
189 
190  if (!prev_gn) {
191  h->frame_entries[s][lc] = glist_add_ptr(h->frame_entries[s][lc],
192  (void *) new_entry);
193  prev_gn = h->frame_entries[s][lc];
194  }
195  else
196  prev_gn = glist_insert_ptr(prev_gn, (void *) new_entry);
197 
198  /*
199  * Update the rc set of all the remaining entries in the list. At this
200  * point, gn is the entry, if any, immediately following new entry.
201  */
202  while (gn) {
203  entry = (fsg_hist_entry_t *) gnode_ptr(gn);
204 
205  if (FSG_PNODE_CTXT_SUB(&(entry->rc), &rc) == 0) {
206  /* rc set of entry reduced to 0; can prune this entry */
207  ckd_free((void *) entry);
208  gn = gnode_free(gn, prev_gn);
209  }
210  else {
211  prev_gn = gn;
212  gn = gnode_next(gn);
213  }
214  }
215 }
216 
217 
218 /*
219  * Transfer the surviving history entries for this frame into the permanent
220  * history table.
221  */
222 void
223 fsg_history_end_frame(fsg_history_t * h)
224 {
225  int32 s, lc, ns, np;
226  gnode_t *gn;
227  fsg_hist_entry_t *entry;
228 
229  ns = fsg_model_n_state(h->fsg);
230  np = h->n_ciphone;
231 
232  for (s = 0; s < ns; s++) {
233  for (lc = 0; lc < np; lc++) {
234  for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
235  entry = (fsg_hist_entry_t *) gnode_ptr(gn);
236  blkarray_list_append(h->entries, (void *) entry);
237  }
238 
239  glist_free(h->frame_entries[s][lc]);
240  h->frame_entries[s][lc] = NULL;
241  }
242  }
243 }
244 
245 
247 fsg_history_entry_get(fsg_history_t * h, int32 id)
248 {
249  return ((fsg_hist_entry_t *) blkarray_list_get(h->entries, id));
250 }
251 
252 
253 void
254 fsg_history_reset(fsg_history_t * h)
255 {
256  blkarray_list_reset(h->entries);
257 }
258 
259 
260 int32
261 fsg_history_n_entries(fsg_history_t * h)
262 {
263  return (blkarray_list_n_valid(h->entries));
264 }
265 
266 void
267 fsg_history_utt_start(fsg_history_t * h)
268 {
269  int32 s, lc, ns, np;
270 
271  assert(blkarray_list_n_valid(h->entries) == 0);
272  assert(h->frame_entries);
273 
274  ns = fsg_model_n_state(h->fsg);
275  np = h->n_ciphone;
276 
277  for (s = 0; s < ns; s++) {
278  for (lc = 0; lc < np; lc++) {
279  assert(h->frame_entries[s][lc] == NULL);
280  }
281  }
282 }
283 
284 void
285 fsg_history_utt_end(fsg_history_t * h)
286 {
287 }
288 
289 void
290 fsg_history_print(fsg_history_t *h, dict_t *dict)
291 {
292  int bpidx, bp;
293 
294  for (bpidx = 0; bpidx < blkarray_list_n_valid(h->entries); bpidx++) {
295  bp = bpidx;
296  printf("History entry: ");
297  while (bp > 0) {
298  fsg_hist_entry_t *hist_entry = fsg_history_entry_get(h, bp);
299  fsg_link_t *fl = fsg_hist_entry_fsglink(hist_entry);
300  char const *baseword;
301  int32 wid;
302  bp = fsg_hist_entry_pred(hist_entry);
303  wid = fsg_link_wid(fl);
304 
305  if (fl == NULL)
306  continue;
307 
308  baseword = fsg_model_word_str(h->fsg, wid);
309 
310  printf("%s(%d->%d:%d) ", baseword,
311  fsg_link_from_state(hist_entry->fsglink),
312  fsg_link_to_state(hist_entry->fsglink),
313  hist_entry->frame);
314  }
315  printf("\n");
316  }
317 }
Definition: fsg_history.h:95
a structure for a dictionary.
Definition: dict.h:76
#define BETTER_THAN
Is one score better than another?
Definition: hmm.h:95
bin_mdef_t * mdef
Model definition used for phone IDs; NULL if none used.
Definition: dict.h:78