Edinburgh Speech Tools 2.4-release
 
Loading...
Searching...
No Matches
EST_viterbi.h
1/*************************************************************************/
2/* */
3/* Centre for Speech Technology Research */
4/* University of Edinburgh, UK */
5/* Copyright (c) 1996,1997 */
6/* All Rights Reserved. */
7/* */
8/* Permission is hereby granted, free of charge, to use and distribute */
9/* this software and its documentation without restriction, including */
10/* without limitation the rights to use, copy, modify, merge, publish, */
11/* distribute, sublicense, and/or sell copies of this work, and to */
12/* permit persons to whom this work is furnished to do so, subject to */
13/* the following conditions: */
14/* 1. The code must retain the above copyright notice, this list of */
15/* conditions and the following disclaimer. */
16/* 2. Any modifications must be clearly marked as such. */
17/* 3. Original authors' names are not deleted. */
18/* 4. The authors' names are not used to endorse or promote products */
19/* derived from this software without specific prior written */
20/* permission. */
21/* */
22/* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23/* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24/* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25/* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26/* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28/* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29/* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30/* THIS SOFTWARE. */
31/* */
32/*************************************************************************/
33/* Authors: Alan W Black */
34/* Date : July 1996 */
35/*-----------------------------------------------------------------------*/
36/* A viterbi decoder */
37/* */
38/* User provides the candidates, target and combine score function */
39/* and it searches for the best path through the candidates */
40/* */
41/*=======================================================================*/
42
43#ifndef __VERTERBI_H__
44#define __VERTERBI_H__
45
46#include "EST_cutils.h"
47#include "EST_Features.h"
48#include "ling_class/EST_Relation.h"
49
50/** Internal class to \Ref{EST_Viterbi_Decoder} used to a represent
51 a candidate.
52
53 These objects need to be created and set by the user of the Viterbi
54 decoder.
55
56 @author Alan W Black (awb@cstr.ed.ac.uk): July 1996
57*/
59 private:
60 public:
61 EST_VTCandidate() {score=0.0; next=0; s=0; }
62 ~EST_VTCandidate() {if (next != 0) delete next;}
63 float score;
64 EST_Val name;
65 int pos;
66 EST_Item *s;
67 EST_VTCandidate *next;
68};
69
70
71/** Internal class to \Ref{EST_Viterbi_Decoder} used to a represent
72 a link in a path the candidates.
73
74 @author Alan W Black (awb@cstr.ed.ac.uk): July 1996
75*/
77 private:
78 public:
79 EST_VTPath() {score=0.0; from=0; next=0; c=0;}
80 ~EST_VTPath() {if (next != 0) delete next;}
81 double score; /* cumulative score for path */
82 int state;
85 EST_VTPath *from;
86 EST_VTPath *next;
87};
88
89/** Internal class to \Ref{EST_Viterbi_Decoder used to a node in
90 the decoder table
91
92 @author Alan W Black (awb@cstr.ed.ac.uk): July 1996
93*/
95 private:
96 public:
97 EST_VTPoint() {next=0; s=0; paths=0; num_paths=0; cands=0; st_paths=0; num_states=0;}
99 EST_Item *s;
100 int num_states;
101 int num_paths;
102 EST_VTCandidate *cands;
103 EST_VTPath *paths;
104 EST_VTPath **st_paths;
105 EST_VTPoint *next;
106};
107
108typedef EST_VTCandidate *(*uclist_f_t)(EST_Item *s,EST_Features &f);
109typedef EST_VTPath *(*unpath_f_t)(EST_VTPath *p,EST_VTCandidate *c,
110 EST_Features &f);
111
112/** A class that offers a generalised Viterbi decoder.
113
114 This class can be used to find the best path through a set
115 of candidates based on likelihoods of the candidates and
116 some combination function. The candidate list and joining
117 are not included in the decoder itself but are user defined functions
118 that are specified at construction time.
119
120 Those functions need to return a list of candidates and score
121 a join of a path to a candidate and (optionally define a state).
122
123 Although this offers a full Viterbi search it may also be used as
124 a generalised beam search.
125
126 See {\tt viterbi_main.cc} for an example of using this.
127
128 @author Alan W Black (awb@cstr.ed.ac.uk): July 1996
129*/
131 private:
132 int num_states;
133
134 /// very detailed info - for developers
135 int debug;
136
137 /// less detailed info than debug - for users
138 int trace;
139
140 int beam_width;
141 int cand_width;
142 int big_is_good;
143 uclist_f_t user_clist;
144 unpath_f_t user_npath;
145 EST_VTPoint *timeline;
146
147 /// pruning parameters
148 bool do_pruning;
149 float overall_path_pruning_envelope_width;
150 float candidate_pruning_envelope_width;
151
152 void add_path(EST_VTPoint *p, EST_VTPath *np);
153 void vit_add_path(EST_VTPoint *p, EST_VTPath *np);
154 void vit_add_paths(EST_VTPoint *p, EST_VTPath *np);
155 EST_VTPath *find_best_end() const;
156 const int betterthan(const float a,const float b) const;
157 void prune_initialize(EST_VTPoint *p,
158 double &best_score, double &best_candidate_score,
159 double &score_cutoff, double &candidate_cutoff,
160 int &cand_count);
161 public:
162
163 /// For holding values to pass to user called functions
165
166 /// Unfortunately using MAX_DOUBLE doesn't do the right thing
167 /// (e.g. comparison don't work with MAX_DOUBLE on alphas), so
168 /// we declare our own large number.
169 const double vit_a_big_number;
170
171 /** Construct a decoder with given candidate function and join function,
172 as number of states is given this implies a beam search
173 */
174 EST_Viterbi_Decoder(uclist_f_t a, unpath_f_t b);
175 /** Construct a decoder with given candidate function and join function
176 with a state size as specified.
177 */
178 EST_Viterbi_Decoder(uclist_f_t a, unpath_f_t b, int num_states);
179 ///
181 /// Only for use in beam search mode: number of paths to consider
182 void set_beam_width(int w) {beam_width = w;}
183 /// Only for use in beam search mode: number of candidates to consider
184 void set_cand_width(int w) {cand_width = w;}
185 /// Output some debugging information
186 void set_debug(int d) {debug = d;}
187
188 /** Define whether good scores are bigger or smaller. This allows
189 the search to work for likelihoods probabilities, scores or
190 whatever
191 */
192 void set_big_is_good(int flag) { big_is_good = flag; }
193 /** Add a new candidate to list if better than others, pruning
194 the list if required.
195 */
198
199 bool vit_prune_path(double path_score, double score_cutoff);
200
201 /// Build the initial table from a \Ref{EST_Relation}
202 void initialise(EST_Relation *r);
203
204 /// set beam widths for pruning
205 void set_pruning_parameters(float beam, float ob_beam);
206
207 void turn_on_debug();
208 void turn_on_trace();
209
210 /// Do the the actual search
211 void search(void);
212 /** Extract the result from the table and store it as a feature
213 on the related \Ref{EST_Item} in the given \Ref{EST_Relation}
214 named as {\tt n}. Return FALSE if no path is found.
215 */
216 bool result(const EST_String &n);
217
218 /** Extract the end point of the best path found during search.
219 Return FALSE if no path is found.
220 */
221 bool result( EST_VTPath **bestPathEnd );
222
223 /// Copy named feature from the best path to related stream item
224 void copy_feature(const EST_String &n);
225};
226
227
228#endif // __VERTERBI_H__
void set_big_is_good(int flag)
EST_Features f
For holding values to pass to user called functions.
void set_debug(int d)
Output some debugging information.
EST_VTCandidate * add_cand_prune(EST_VTCandidate *newcand, EST_VTCandidate *allcands)
void set_cand_width(int w)
Only for use in beam search mode: number of candidates to consider.
void initialise(EST_Relation *r)
Build the initial table from a \Ref{EST_Relation}.
void search(void)
Do the the actual search.
void copy_feature(const EST_String &n)
Copy named feature from the best path to related stream item.
void set_pruning_parameters(float beam, float ob_beam)
set beam widths for pruning
void set_beam_width(int w)
Only for use in beam search mode: number of paths to consider.
const double vit_a_big_number
Unfortunately using MAX_DOUBLE doesn't do the right thing (e.g. comparison don't work with MAX_DOUBLE...
bool result(const EST_String &n)