PocketSphinx  0.6
src/libpocketsphinx/fsg_history.c
00001 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
00002 /* ====================================================================
00003  * Copyright (c) 1999-2004 Carnegie Mellon University.  All rights
00004  * reserved.
00005  *
00006  * Redistribution and use in source and binary forms, with or without
00007  * modification, are permitted provided that the following conditions
00008  * are met:
00009  *
00010  * 1. Redistributions of source code must retain the above copyright
00011  *    notice, this list of conditions and the following disclaimer. 
00012  *
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in
00015  *    the documentation and/or other materials provided with the
00016  *    distribution.
00017  *
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 
00020  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 
00021  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00022  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
00023  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00024  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
00025  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
00026  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
00027  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
00028  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
00029  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00030  *
00031  * ====================================================================
00032  *
00033  */
00034 
00035 /*
00036  * fsg_history.c -- FSG Viterbi decode history
00037  * 
00038  * **********************************************
00039  * CMU ARPA Speech Project
00040  *
00041  * Copyright (c) 1999 Carnegie Mellon University.
00042  * ALL RIGHTS RESERVED.
00043  * **********************************************
00044  * 
00045  * HISTORY
00046  * 
00047  * 25-Feb-2004  M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
00048  *              Started..
00049  */
00050 
00051 /* System headers. */
00052 #include <assert.h>
00053 
00054 /* SphinxBase headers. */
00055 #include <sphinxbase/prim_type.h>
00056 #include <sphinxbase/err.h>
00057 #include <sphinxbase/ckd_alloc.h>
00058 
00059 /* Local headers. */
00060 #include "fsg_search_internal.h"
00061 #include "fsg_history.h"
00062 
00063 
00064 #define __FSG_DBG__     0
00065 
00066 
00067 fsg_history_t *
00068 fsg_history_init(fsg_model_t * fsg, dict_t *dict)
00069 {
00070     fsg_history_t *h;
00071 
00072     h = (fsg_history_t *) ckd_calloc(1, sizeof(fsg_history_t));
00073     h->fsg = fsg;
00074     h->entries = blkarray_list_init();
00075 
00076     if (fsg) {
00077         if (dict)
00078             h->n_ciphone = bin_mdef_n_ciphone(dict->mdef);
00079         h->frame_entries =
00080             (glist_t **) ckd_calloc_2d(fsg_model_n_state(fsg),
00081                                        bin_mdef_n_ciphone(dict->mdef),
00082                                        sizeof(**h->frame_entries));
00083     }
00084     else {
00085         h->frame_entries = NULL;
00086     }
00087 
00088     return h;
00089 }
00090 
00091 void
00092 fsg_history_free(fsg_history_t *h)
00093 {
00094     int32 s, lc, ns, np;
00095     gnode_t *gn;
00096 
00097     if (h->fsg) {
00098         ns = fsg_model_n_state(h->fsg);
00099         np = h->n_ciphone;
00100 
00101         for (s = 0; s < ns; s++) {
00102             for (lc = 0; lc < np; lc++) {
00103                 for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
00104                     ckd_free(gnode_ptr(gn));
00105                 }
00106                 glist_free(h->frame_entries[s][lc]);
00107             }
00108         }
00109     }
00110     ckd_free_2d(h->frame_entries);
00111     blkarray_list_free(h->entries);
00112     ckd_free(h);
00113 }
00114 
00115 
00116 void
00117 fsg_history_set_fsg(fsg_history_t *h, fsg_model_t *fsg, dict_t *dict)
00118 {
00119     if (blkarray_list_n_valid(h->entries) != 0) {
00120         E_WARN("Switching FSG while history not empty; history cleared\n");
00121         blkarray_list_reset(h->entries);
00122     }
00123 
00124     if (h->frame_entries)
00125         ckd_free_2d((void **) h->frame_entries);
00126     h->frame_entries = NULL;
00127     h->fsg = fsg;
00128 
00129     if (fsg) {
00130         if (dict)
00131             h->n_ciphone = bin_mdef_n_ciphone(dict->mdef);
00132         h->frame_entries =
00133             (glist_t **) ckd_calloc_2d(fsg_model_n_state(fsg),
00134                                        bin_mdef_n_ciphone(dict->mdef),
00135                                        sizeof(glist_t));
00136     }
00137 }
00138 
00139 
00140 void
00141 fsg_history_entry_add(fsg_history_t * h,
00142                       fsg_link_t * link,
00143                       int32 frame, int32 score, int32 pred,
00144                       int32 lc, fsg_pnode_ctxt_t rc)
00145 {
00146     fsg_hist_entry_t *entry, *new_entry;
00147     int32 s;
00148     gnode_t *gn, *prev_gn;
00149 
00150     /* Skip the optimization for the initial dummy entries; always enter them */
00151     if (frame < 0) {
00152         new_entry =
00153             (fsg_hist_entry_t *) ckd_calloc(1, sizeof(fsg_hist_entry_t));
00154         new_entry->fsglink = link;
00155         new_entry->frame = frame;
00156         new_entry->score = score;
00157         new_entry->pred = pred;
00158         new_entry->lc = lc;
00159         new_entry->rc = rc;
00160 
00161         blkarray_list_append(h->entries, (void *) new_entry);
00162         return;
00163     }
00164 
00165     s = fsg_link_to_state(link);
00166 
00167     /* Locate where this entry should be inserted in frame_entries[s][lc] */
00168     prev_gn = NULL;
00169     for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
00170         entry = (fsg_hist_entry_t *) gnode_ptr(gn);
00171 
00172         if (score BETTER_THAN entry->score)
00173             break;              /* Found where to insert new entry */
00174 
00175         /* Existing entry score not worse than new score */
00176         if (FSG_PNODE_CTXT_SUB(&rc, &(entry->rc)) == 0)
00177             return;             /* rc set reduced to 0; new entry can be ignored */
00178 
00179         prev_gn = gn;
00180     }
00181 
00182     /* Create new entry after prev_gn (if prev_gn is NULL, at head) */
00183     new_entry =
00184         (fsg_hist_entry_t *) ckd_calloc(1, sizeof(fsg_hist_entry_t));
00185     new_entry->fsglink = link;
00186     new_entry->frame = frame;
00187     new_entry->score = score;
00188     new_entry->pred = pred;
00189     new_entry->lc = lc;
00190     new_entry->rc = rc;         /* Note: rc set must be non-empty at this point */
00191 
00192     if (!prev_gn) {
00193         h->frame_entries[s][lc] = glist_add_ptr(h->frame_entries[s][lc],
00194                                                 (void *) new_entry);
00195         prev_gn = h->frame_entries[s][lc];
00196     }
00197     else
00198         prev_gn = glist_insert_ptr(prev_gn, (void *) new_entry);
00199 
00200     /*
00201      * Update the rc set of all the remaining entries in the list.  At this
00202      * point, gn is the entry, if any, immediately following new entry.
00203      */
00204     while (gn) {
00205         entry = (fsg_hist_entry_t *) gnode_ptr(gn);
00206 
00207         if (FSG_PNODE_CTXT_SUB(&(entry->rc), &rc) == 0) {
00208             /* rc set of entry reduced to 0; can prune this entry */
00209             ckd_free((void *) entry);
00210             gn = gnode_free(gn, prev_gn);
00211         }
00212         else {
00213             prev_gn = gn;
00214             gn = gnode_next(gn);
00215         }
00216     }
00217 }
00218 
00219 
00220 /*
00221  * Transfer the surviving history entries for this frame into the permanent
00222  * history table.
00223  */
00224 void
00225 fsg_history_end_frame(fsg_history_t * h)
00226 {
00227     int32 s, lc, ns, np;
00228     gnode_t *gn;
00229     fsg_hist_entry_t *entry;
00230 
00231     ns = fsg_model_n_state(h->fsg);
00232     np = h->n_ciphone;
00233 
00234     for (s = 0; s < ns; s++) {
00235         for (lc = 0; lc < np; lc++) {
00236             for (gn = h->frame_entries[s][lc]; gn; gn = gnode_next(gn)) {
00237                 entry = (fsg_hist_entry_t *) gnode_ptr(gn);
00238                 blkarray_list_append(h->entries, (void *) entry);
00239             }
00240 
00241             glist_free(h->frame_entries[s][lc]);
00242             h->frame_entries[s][lc] = NULL;
00243         }
00244     }
00245 }
00246 
00247 
00248 fsg_hist_entry_t *
00249 fsg_history_entry_get(fsg_history_t * h, int32 id)
00250 {
00251     blkarray_list_t *entries;
00252     int32 r, c;
00253 
00254     entries = h->entries;
00255 
00256     if (id >= blkarray_list_n_valid(entries))
00257         return NULL;
00258 
00259     r = id / blkarray_list_blksize(entries);
00260     c = id - (r * blkarray_list_blksize(entries));
00261 
00262     return ((fsg_hist_entry_t *) blkarray_list_ptr(entries, r, c));
00263 }
00264 
00265 
00266 void
00267 fsg_history_reset(fsg_history_t * h)
00268 {
00269     blkarray_list_reset(h->entries);
00270 }
00271 
00272 
00273 int32
00274 fsg_history_n_entries(fsg_history_t * h)
00275 {
00276     return (blkarray_list_n_valid(h->entries));
00277 }
00278 
00279 void
00280 fsg_history_utt_start(fsg_history_t * h)
00281 {
00282     int32 s, lc, ns, np;
00283 
00284     assert(blkarray_list_n_valid(h->entries) == 0);
00285     assert(h->frame_entries);
00286 
00287     ns = fsg_model_n_state(h->fsg);
00288     np = h->n_ciphone;
00289 
00290     for (s = 0; s < ns; s++) {
00291         for (lc = 0; lc < np; lc++) {
00292             assert(h->frame_entries[s][lc] == NULL);
00293         }
00294     }
00295 }
00296 
00297 void
00298 fsg_history_utt_end(fsg_history_t * h)
00299 {
00300 }