fsg_history.h
Go to the documentation of this file.
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$
47  * Revision 1.1 2006/04/05 20:27:30 dhdfu
48  * A Great Reorganzation of header files and executables
49  *
50  * Revision 1.2 2006/02/23 05:10:18 arthchan2003
51  * Merged from branch SPHINX3_5_2_RCI_IRII_BRANCH: Adaptation of Sphinx 2's FSG search into Sphinx 3
52  *
53  * Revision 1.1.2.5 2005/07/24 19:34:46 arthchan2003
54  * Removed search_hyp_t, used srch_hyp_t instead
55  *
56  * Revision 1.1.2.4 2005/07/24 01:34:54 arthchan2003
57  * Mode 2 is basically running. Still need to fix function such as resulting and build the correct utterance ID
58  *
59  * Revision 1.1.2.3 2005/07/13 18:39:47 arthchan2003
60  * (For Fun) Remove the hmm_t hack. Consider each s2 global functions one-by-one and replace them by sphinx 3's macro. There are 8 minor HACKs where functions need to be removed temporarily. Also, there are three major hacks. 1, there are no concept of "phone" in sphinx3 dict_t, there is only ciphone. That is to say we need to build it ourselves. 2, sphinx2 dict_t will be a bunch of left and right context tables. This is currently bypass. 3, the fsg routine is using fsg_hmm_t which is just a duplication of CHAN_T in sphinx2, I will guess using hmm_evaluate should be a good replacement. But I haven't figure it out yet.
61  *
62  * Revision 1.1.2.2 2005/06/28 07:01:20 arthchan2003
63  * General fix of fsg routines to make a prototype of fsg_init and fsg_read. Not completed. The number of empty functions in fsg_search is now decreased from 35 to 30.
64  *
65  * Revision 1.1.2.1 2005/06/27 05:26:29 arthchan2003
66  * Sphinx 2 fsg mainpulation routines. Compiled with faked functions. Currently fended off from users.
67  *
68  * Revision 1.1 2004/07/16 00:57:12 egouvea
69  * Added Ravi's implementation of FSG support.
70  *
71  * Revision 1.7 2004/07/07 22:30:35 rkm
72  * *** empty log message ***
73  *
74  * Revision 1.6 2004/07/07 13:56:33 rkm
75  * Added reporting of (acoustic score - best senone score)/frame
76  *
77  * Revision 1.5 2004/06/25 14:49:08 rkm
78  * Optimized size of history table and speed of word transitions by maintaining only best scoring word exits at each state
79  *
80  * Revision 1.4 2004/06/23 20:32:16 rkm
81  * *** empty log message ***
82  *
83  * Revision 1.3 2004/05/27 15:16:08 rkm
84  * *** empty log message ***
85  *
86  *
87  * 25-Feb-2004 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
88  * Started, based on S3.3 version.
89  */
90 
91 
92 #ifndef __S2_FSG_HISTORY_H__
93 #define __S2_FSG_HISTORY_H__
94 
95 
96 #include <stdio.h>
97 
98 #include <glist.h>
99 #include <s3types.h>
100 #include <blkarray_list.h>
101 #include <fsg_psubtree.h>
102 #include <word_fsg.h>
103 #include <search.h>
104 #include <dict.h>
105 
106 
107 #ifdef __cplusplus
108 extern "C" {
109 #endif
110 #if 0
111 /* Fool Emacs. */
112 }
113 #endif
114 
115 /*
116  * The Viterbi history structure. This is a tree, with the root at the
117  * FSG start state, at frame 0, with a null predecessor.
118  */
119 
120 /*
121  * A single Viterbi history entry
122  */
123 typedef struct fsg_hist_entry_s {
124  word_fsglink_t *fsglink; /* Link taken result in this entry */
125  int32 frame; /* Ending frame for this entry */
126  int32 score; /* Total path score at the end of this
127  transition */
128  int32 pred; /* Predecessor entry; -1 if none */
129  int32 lc; /* Left context provided by this entry to
130  succeeding words */
131  fsg_pnode_ctxt_t rc; /* Possible right contexts to which this entry
132  applies */
134 
135 /* Access macros */
136 #define fsg_hist_entry_fsglink(v) ((v)->fsglink)
137 #define fsg_hist_entry_frame(v) ((v)->frame)
138 #define fsg_hist_entry_score(v) ((v)->score)
139 #define fsg_hist_entry_pred(v) ((v)->pred)
140 #define fsg_hist_entry_lc(v) ((v)->lc)
141 #define fsg_hist_entry_rc(v) ((v)->rc)
142 
143 
144 /*
145  * The entire tree of history entries (fsg_history_t.entries).
146  * Optimization: In a given frame, there may be several history entries, with
147  * the same left and right phonetic context, terminating in a particular state.
148  * Only the best scoring one of these needs to be saved, since everything else
149  * will be pruned according to the Viterbi algorithm. frame_entries is used
150  * temporarily in each frame to determine these best scoring entries in that
151  * frame. Only the ones not pruned are transferred to entries at the end of
152  * the frame. However, null transitions are a problem since they create
153  * entries that depend on entries created in the CURRENT frame. Hence, this
154  * pruning is done in two stages: first for the non-null transitions, and then
155  * for the null transitions alone. (This solution is sub-optimal, and can be
156  * improved with a little more work. SMOP.)
157  * Why is frame_entries a list? Each entry has a unique terminating state,
158  * and has a unique lc CIphone. But it has a SET of rc CIphones.
159  * frame_entries[s][lc] is an ordered list of entries created in the current
160  * frame, terminating in state s, and with left context lc. The list is in
161  * descending order of path score. When a new entry with (s,lc) arrives,
162  * its position in the list is determined. Then its rc set is modified by
163  * subtracting the union of the rc's of all its predecessors (i.e., better
164  * scoring entries). If the resulting rc set is empty, the entry is discarded.
165  * Otherwise, it is inserted, and the rc sets of all downstream entries in the
166  * list are updated by subtracting the new entry's rc. If any of them becomes
167  * empty, it is also discarded.
168  * As mentioned earlier, this procedure is applied in two stages, for the
169  * non-null transitions, and the null transitions, separately.
170  */
171 typedef struct fsg_history_s {
172  word_fsg_t *fsg; /* The FSG for which this object applies */
173  blkarray_list_t *entries; /* A list of history table entries; the root
174  entry is the first element of the list */
175  glist_t **frame_entries;
176 
177  /*Added by Arthur at 20050627*/
178  int32 n_ciphone;
179 } fsg_history_t;
180 
181 
182 /*
183  * One-time intialization: Allocate and return an initially empty history
184  * module.
185  */
186 fsg_history_t *fsg_history_init (word_fsg_t *fsg,int32 n_ciphone);
187 
189 
191 
192 
194 
195 
196 /*
197  * Create a history entry recording the completion of the given FSG
198  * transition, at the end of the given frame, with the given score, and
199  * the given predecessor history entry.
200  * The entry is initially temporary, and may be superseded by another
201  * with a higher score. The surviving entries must be transferred to
202  * the main history table, via fsg_history_end_frame().
203  */
205  word_fsglink_t *, /* FSG transition */
206  int32 frame,
207  int32 score,
208  int32 pred,
209  int32 lc,
211 
212 /*
213  * Transfer the surviving history entries for this frame into the permanent
214  * history table. This function can be called several times during a frame.
215  * Each time, the entries surviving so far are transferred, and the temporary
216  * lists cleared. This feature is used to handle the entries due to non-null
217  * transitions and null transitions separately.
218  */
220 
221 
222 /* Clear the hitory table */
224 
225 
226 /* Return the number of valid entries in the given history table */
228 
229 
230 /*
231  * Viterbi backtrace.
232  */
234 
235 
236 /*
237  * Dump the Viterbi history data to the given file (mainly for debugging).
238  */
239 void fsg_history_dump (fsg_history_t *vh, char const *uttid, FILE *fp, dict_t *dict);
240 
241 
242 /*
243  * Return a ptr to the history entry for the given ID; NULL if there is no
244  * such entry.
245  */
247 
248 
249 /*
250  * Switch the FSG associated with the given history module. Should be done
251  * when the history list is empty. If not empty, the list is cleared.
252  */
254 
255 
256 /* Free the given Viterbi search history object */
258 
259 
260 /*
261  * Extract and fill out a srch_hyp_t structure from the given history entry
262  * (index). Caller must allocate hyp.
263  * Note: Must not be called with index <= 0.
264  * Note: (hyp->wid < 0) iff the entry corresponds to a null transition.
265  * Note: hyp->{conf,latden,phone_perp} have dummy values filled in.
266  * Note: hyp->next is unaffected.
267  * Return value: -1 if index <= 0 (error; hyp is not filled in);
268  * the return value is +ve if it is a valid, real (non-dummy) entry.
269  */
270 int32 fsg_history_entry_hyp_extract (fsg_history_t *h, int32 index,
271  srch_hyp_t *hyp, dict_t *dict);
272 
273 #ifdef __cplusplus
274 }
275 #endif
276 
277 
278 #endif
void fsg_history_end_frame(fsg_history_t *)
void fsg_history_utt_start(fsg_history_t *)
Definition: fsg_psubtree.h:138
fsg_pnode_ctxt_t rc
Definition: fsg_history.h:131
a hypothesis structure
glist_t ** frame_entries
Definition: fsg_history.h:175
Definition: fsg_history.h:123
The temporary header file for sphinx 3 functions.
void fsg_history_utt_end(fsg_history_t *)
Definition: blkarray_list.h:90
int32 n_ciphone
Definition: fsg_history.h:178
Definition: word_fsg.h:187
void fsg_history_entry_add(fsg_history_t *, word_fsglink_t *, int32 frame, int32 score, int32 pred, int32 lc, fsg_pnode_ctxt_t rc)
Operations on dictionary.
blkarray_list_t * entries
Definition: fsg_history.h:173
struct fsg_hist_entry_s fsg_hist_entry_t
word_fsglink_t * fsglink
Definition: fsg_history.h:124
word_fsg_t * fsg
Definition: fsg_history.h:172
int32 fsg_history_entry_hyp_extract(fsg_history_t *h, int32 index, srch_hyp_t *hyp, dict_t *dict)
int32 frame
Definition: fsg_history.h:125
void fsg_history_dump(fsg_history_t *vh, char const *uttid, FILE *fp, dict_t *dict)
Size definition of semantically units. Common for both s3 and s3.X decoder.
Definition: fsg_history.h:171
a structure for a dictionary.
Definition: dict.h:146
int32 score
Definition: fsg_history.h:126
glist_t fsg_history_backtrace(fsg_history_t *)
int32 pred
Definition: fsg_history.h:128
void fsg_history_set_fsg(fsg_history_t *, word_fsg_t *)
int32 fsg_history_n_entries(fsg_history_t *h)
fsg_hist_entry_t * fsg_history_entry_get(fsg_history_t *, int32 id)
fsg_history_t * fsg_history_init(word_fsg_t *fsg, int32 n_ciphone)
struct fsg_history_s fsg_history_t
void fsg_history_free(fsg_history_t *)
void fsg_history_reset(fsg_history_t *)
int32 lc
Definition: fsg_history.h:129