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
68fsg_history_init(fsg_model_t * fsg, dict_t *dict)
69{
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
90void
91fsg_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
115void
116fsg_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
138void
139fsg_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 */
222void
223fsg_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
247fsg_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
253void
254fsg_history_reset(fsg_history_t * h)
255{
256 blkarray_list_reset(h->entries);
257}
258
259
260int32
261fsg_history_n_entries(fsg_history_t * h)
262{
263 return (blkarray_list_n_valid(h->entries));
264}
265
266void
267fsg_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
284void
285fsg_history_utt_end(fsg_history_t * h)
286{
287}
288
289void
290fsg_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}
#define BETTER_THAN
Is one score better than another?
Definition: hmm.h:95
a structure for a dictionary.
Definition: dict.h:76
bin_mdef_t * mdef
Model definition used for phone IDs; NULL if none used.
Definition: dict.h:78
Definition: fsg_history.h:95