PocketSphinx  5prealpha
fsg_history.h
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  * fsg_history.h -- FSG Viterbi decode history
36  *
37  * **********************************************
38  * CMU ARPA Speech Project
39  *
40  * Copyright (c) 1999 Carnegie Mellon University.
41  * ALL RIGHTS RESERVED.
42  * **********************************************
43  *
44  * HISTORY
45  *
46  * $Log: fsg_history.h,v $
47  * Revision 1.1.1.1 2006/05/23 18:45:02 dhuggins
48  * re-importation
49  *
50  * Revision 1.1 2004/07/16 00:57:12 egouvea
51  * Added Ravi's implementation of FSG support.
52  *
53  * Revision 1.7 2004/07/07 22:30:35 rkm
54  * *** empty log message ***
55  *
56  * Revision 1.6 2004/07/07 13:56:33 rkm
57  * Added reporting of (acoustic score - best senone score)/frame
58  *
59  * Revision 1.5 2004/06/25 14:49:08 rkm
60  * Optimized size of history table and speed of word transitions by maintaining only best scoring word exits at each state
61  *
62  * Revision 1.4 2004/06/23 20:32:16 rkm
63  * *** empty log message ***
64  *
65  * Revision 1.3 2004/05/27 15:16:08 rkm
66  * *** empty log message ***
67  *
68  *
69  * 25-Feb-2004 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
70  * Started, based on S3.3 version.
71  */
72 
73 
74 #ifndef __S2_FSG_HISTORY_H__
75 #define __S2_FSG_HISTORY_H__
76 
77 
78 /* SphinxBase headers. */
79 #include <sphinxbase/prim_type.h>
80 #include <sphinxbase/fsg_model.h>
81 
82 /* Local headers. */
83 #include "blkarray_list.h"
84 #include "fsg_lextree.h"
85 #include "dict.h"
86 
87 /*
88  * The Viterbi history structure. This is a tree, with the root at the
89  * FSG start state, at frame 0, with a null predecessor.
90  */
91 
92 /*
93  * A single Viterbi history entry
94  */
95 typedef struct fsg_hist_entry_s {
96  fsg_link_t *fsglink; /* Link taken result in this entry */
97  int32 score; /* Total path score at the end of this
98  transition */
99  int32 pred; /* Predecessor entry; -1 if none */
100  frame_idx_t frame; /* Ending frame for this entry */
101  int16 lc; /* Left context provided by this entry to
102  succeeding words */
103  fsg_pnode_ctxt_t rc; /* Possible right contexts to which this entry
104  applies */
106 
107 /* Access macros */
108 #define fsg_hist_entry_fsglink(v) ((v)->fsglink)
109 #define fsg_hist_entry_frame(v) ((v)->frame)
110 #define fsg_hist_entry_score(v) ((v)->score)
111 #define fsg_hist_entry_pred(v) ((v)->pred)
112 #define fsg_hist_entry_lc(v) ((v)->lc)
113 #define fsg_hist_entry_rc(v) ((v)->rc)
114 
115 
116 /*
117  * The entire tree of history entries (fsg_history_t.entries).
118  * Optimization: In a given frame, there may be several history entries, with
119  * the same left and right phonetic context, terminating in a particular state.
120  * Only the best scoring one of these needs to be saved, since everything else
121  * will be pruned according to the Viterbi algorithm. frame_entries is used
122  * temporarily in each frame to determine these best scoring entries in that
123  * frame. Only the ones not pruned are transferred to entries at the end of
124  * the frame. However, null transitions are a problem since they create
125  * entries that depend on entries created in the CURRENT frame. Hence, this
126  * pruning is done in two stages: first for the non-null transitions, and then
127  * for the null transitions alone. (This solution is sub-optimal, and can be
128  * improved with a little more work. SMOP.)
129  * Why is frame_entries a list? Each entry has a unique terminating state,
130  * and has a unique lc CIphone. But it has a SET of rc CIphones.
131  * frame_entries[s][lc] is an ordered list of entries created in the current
132  * frame, terminating in state s, and with left context lc. The list is in
133  * descending order of path score. When a new entry with (s,lc) arrives,
134  * its position in the list is determined. Then its rc set is modified by
135  * subtracting the union of the rc's of all its predecessors (i.e., better
136  * scoring entries). If the resulting rc set is empty, the entry is discarded.
137  * Otherwise, it is inserted, and the rc sets of all downstream entries in the
138  * list are updated by subtracting the new entry's rc. If any of them becomes
139  * empty, it is also discarded.
140  * As mentioned earlier, this procedure is applied in two stages, for the
141  * non-null transitions, and the null transitions, separately.
142  */
143 typedef struct fsg_history_s {
144  fsg_model_t *fsg; /* The FSG for which this object applies */
145  blkarray_list_t *entries; /* A list of history table entries; the root
146  entry is the first element of the list */
147  glist_t **frame_entries;
148  int n_ciphone;
149 } fsg_history_t;
150 
151 
152 /*
153  * One-time intialization: Allocate and return an initially empty history
154  * module.
155  */
156 fsg_history_t *fsg_history_init(fsg_model_t *fsg, dict_t *dict);
157 
158 void fsg_history_utt_start(fsg_history_t *h);
159 
160 void fsg_history_utt_end(fsg_history_t *h);
161 
162 
163 /*
164  * Create a history entry recording the completion of the given FSG
165  * transition, at the end of the given frame, with the given score, and
166  * the given predecessor history entry.
167  * The entry is initially temporary, and may be superseded by another
168  * with a higher score. The surviving entries must be transferred to
169  * the main history table, via fsg_history_end_frame().
170  */
171 void fsg_history_entry_add (fsg_history_t *h,
172  fsg_link_t *l, /* FSG transition */
173  int32 frame,
174  int32 score,
175  int32 pred,
176  int32 lc,
177  fsg_pnode_ctxt_t rc);
178 
179 /*
180  * Transfer the surviving history entries for this frame into the permanent
181  * history table. This function can be called several times during a frame.
182  * Each time, the entries surviving so far are transferred, and the temporary
183  * lists cleared. This feature is used to handle the entries due to non-null
184  * transitions and null transitions separately.
185  */
186 void fsg_history_end_frame (fsg_history_t *h);
187 
188 
189 /* Clear the hitory table */
190 void fsg_history_reset (fsg_history_t *h);
191 
192 
193 /* Return the number of valid entries in the given history table */
194 int32 fsg_history_n_entries (fsg_history_t *h);
195 
196 /*
197  * Return a ptr to the history entry for the given ID; NULL if there is no
198  * such entry.
199  */
200 fsg_hist_entry_t *fsg_history_entry_get(fsg_history_t *h, int32 id);
201 
202 
203 /*
204  * Switch the FSG associated with the given history module. Should be done
205  * when the history list is empty. If not empty, the list is cleared.
206  */
207 void fsg_history_set_fsg (fsg_history_t *h, fsg_model_t *fsg, dict_t *dict);
208 
209 /* Free the given Viterbi search history object */
210 void fsg_history_free (fsg_history_t *h);
211 
212 /* Print the entire history */
213 void fsg_history_print(fsg_history_t *h, dict_t *dict);
214 
215 #endif
Definition: fsg_history.h:95
Operations on dictionary.
a structure for a dictionary.
Definition: dict.h:76
int32 frame_idx_t
Type for frame index values.
Definition: hmm.h:64