PocketSphinx  0.6
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) {
77  if (dict)
78  h->n_ciphone = bin_mdef_n_ciphone(dict->mdef);
79  h->frame_entries =
80  (glist_t **) ckd_calloc_2d(fsg_model_n_state(fsg),
81  bin_mdef_n_ciphone(dict->mdef),
82  sizeof(**h->frame_entries));
83  }
84  else {
85  h->frame_entries = NULL;
86  }
87 
88  return h;
89 }
90 
91 void
92 fsg_history_free(fsg_history_t *h)
93 {
94  int32 s, lc, ns, np;
95  gnode_t *gn;
96 
97  if (h->fsg) {
98  ns = fsg_model_n_state(h->fsg);
99  np = h->n_ciphone;
100 
101  for (s = 0; s < ns; s++) {
102  for (lc = 0; lc < np; lc++) {
103  for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
104  ckd_free(gnode_ptr(gn));
105  }
106  glist_free(h->frame_entries[s][lc]);
107  }
108  }
109  }
110  ckd_free_2d(h->frame_entries);
111  blkarray_list_free(h->entries);
112  ckd_free(h);
113 }
114 
115 
116 void
117 fsg_history_set_fsg(fsg_history_t *h, fsg_model_t *fsg, dict_t *dict)
118 {
119  if (blkarray_list_n_valid(h->entries) != 0) {
120  E_WARN("Switching FSG while history not empty; history cleared\n");
121  blkarray_list_reset(h->entries);
122  }
123 
124  if (h->frame_entries)
125  ckd_free_2d((void **) h->frame_entries);
126  h->frame_entries = NULL;
127  h->fsg = fsg;
128 
129  if (fsg) {
130  if (dict)
131  h->n_ciphone = bin_mdef_n_ciphone(dict->mdef);
132  h->frame_entries =
133  (glist_t **) ckd_calloc_2d(fsg_model_n_state(fsg),
134  bin_mdef_n_ciphone(dict->mdef),
135  sizeof(glist_t));
136  }
137 }
138 
139 
140 void
141 fsg_history_entry_add(fsg_history_t * h,
142  fsg_link_t * link,
143  int32 frame, int32 score, int32 pred,
144  int32 lc, fsg_pnode_ctxt_t rc)
145 {
146  fsg_hist_entry_t *entry, *new_entry;
147  int32 s;
148  gnode_t *gn, *prev_gn;
149 
150  /* Skip the optimization for the initial dummy entries; always enter them */
151  if (frame < 0) {
152  new_entry =
153  (fsg_hist_entry_t *) ckd_calloc(1, sizeof(fsg_hist_entry_t));
154  new_entry->fsglink = link;
155  new_entry->frame = frame;
156  new_entry->score = score;
157  new_entry->pred = pred;
158  new_entry->lc = lc;
159  new_entry->rc = rc;
160 
161  blkarray_list_append(h->entries, (void *) new_entry);
162  return;
163  }
164 
165  s = fsg_link_to_state(link);
166 
167  /* Locate where this entry should be inserted in frame_entries[s][lc] */
168  prev_gn = NULL;
169  for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
170  entry = (fsg_hist_entry_t *) gnode_ptr(gn);
171 
172  if (score BETTER_THAN entry->score)
173  break; /* Found where to insert new entry */
174 
175  /* Existing entry score not worse than new score */
176  if (FSG_PNODE_CTXT_SUB(&rc, &(entry->rc)) == 0)
177  return; /* rc set reduced to 0; new entry can be ignored */
178 
179  prev_gn = gn;
180  }
181 
182  /* Create new entry after prev_gn (if prev_gn is NULL, at head) */
183  new_entry =
184  (fsg_hist_entry_t *) ckd_calloc(1, sizeof(fsg_hist_entry_t));
185  new_entry->fsglink = link;
186  new_entry->frame = frame;
187  new_entry->score = score;
188  new_entry->pred = pred;
189  new_entry->lc = lc;
190  new_entry->rc = rc; /* Note: rc set must be non-empty at this point */
191 
192  if (!prev_gn) {
193  h->frame_entries[s][lc] = glist_add_ptr(h->frame_entries[s][lc],
194  (void *) new_entry);
195  prev_gn = h->frame_entries[s][lc];
196  }
197  else
198  prev_gn = glist_insert_ptr(prev_gn, (void *) new_entry);
199 
200  /*
201  * Update the rc set of all the remaining entries in the list. At this
202  * point, gn is the entry, if any, immediately following new entry.
203  */
204  while (gn) {
205  entry = (fsg_hist_entry_t *) gnode_ptr(gn);
206 
207  if (FSG_PNODE_CTXT_SUB(&(entry->rc), &rc) == 0) {
208  /* rc set of entry reduced to 0; can prune this entry */
209  ckd_free((void *) entry);
210  gn = gnode_free(gn, prev_gn);
211  }
212  else {
213  prev_gn = gn;
214  gn = gnode_next(gn);
215  }
216  }
217 }
218 
219 
220 /*
221  * Transfer the surviving history entries for this frame into the permanent
222  * history table.
223  */
224 void
225 fsg_history_end_frame(fsg_history_t * h)
226 {
227  int32 s, lc, ns, np;
228  gnode_t *gn;
229  fsg_hist_entry_t *entry;
230 
231  ns = fsg_model_n_state(h->fsg);
232  np = h->n_ciphone;
233 
234  for (s = 0; s < ns; s++) {
235  for (lc = 0; lc < np; lc++) {
236  for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
237  entry = (fsg_hist_entry_t *) gnode_ptr(gn);
238  blkarray_list_append(h->entries, (void *) entry);
239  }
240 
241  glist_free(h->frame_entries[s][lc]);
242  h->frame_entries[s][lc] = NULL;
243  }
244  }
245 }
246 
247 
249 fsg_history_entry_get(fsg_history_t * h, int32 id)
250 {
251  blkarray_list_t *entries;
252  int32 r, c;
253 
254  entries = h->entries;
255 
256  if (id >= blkarray_list_n_valid(entries))
257  return NULL;
258 
259  r = id / blkarray_list_blksize(entries);
260  c = id - (r * blkarray_list_blksize(entries));
261 
262  return ((fsg_hist_entry_t *) blkarray_list_ptr(entries, r, c));
263 }
264 
265 
266 void
267 fsg_history_reset(fsg_history_t * h)
268 {
269  blkarray_list_reset(h->entries);
270 }
271 
272 
273 int32
274 fsg_history_n_entries(fsg_history_t * h)
275 {
276  return (blkarray_list_n_valid(h->entries));
277 }
278 
279 void
280 fsg_history_utt_start(fsg_history_t * h)
281 {
282  int32 s, lc, ns, np;
283 
284  assert(blkarray_list_n_valid(h->entries) == 0);
285  assert(h->frame_entries);
286 
287  ns = fsg_model_n_state(h->fsg);
288  np = h->n_ciphone;
289 
290  for (s = 0; s < ns; s++) {
291  for (lc = 0; lc < np; lc++) {
292  assert(h->frame_entries[s][lc] == NULL);
293  }
294  }
295 }
296 
297 void
298 fsg_history_utt_end(fsg_history_t * h)
299 {
300 }