"Fossies" - the Fresh Open Source Software Archive 
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 #include <cstdio>
43 #include "EST_viterbi.h"
44
45 static void init_paths_array(EST_VTPoint *n,int num_states);
46 static void debug_output_1(EST_VTPoint *p,EST_VTCandidate *c,
47 EST_VTPath *np, int i);
48
49 EST_VTPoint::~EST_VTPoint()
50 {
51 int i;
52
53 if (paths != 0) delete paths;
54 if (num_states != 0)
55 {
56 for (i=0; i<num_states; i++)
57 if (st_paths[i] != 0)
58 delete st_paths[i];
59 delete [] st_paths;
60 }
61 if (cands != 0) delete cands;
62 if (next != 0) delete next;
63 }
64
65 EST_Viterbi_Decoder::EST_Viterbi_Decoder(uclist_f_t a, unpath_f_t b)
66 : vit_a_big_number(1.0e10)
67 {
68 beam_width = 0;
69 cand_width = 0;
70 user_clist = a;
71 user_npath = b;
72 num_states = 0;
73
74 do_pruning = FALSE;
75 overall_path_pruning_envelope_width = -1;
76 candidate_pruning_envelope_width = -1;
77
78 debug = FALSE;
79 trace = FALSE;
80 big_is_good = TRUE; // for probabilities it is
81 }
82
83 EST_Viterbi_Decoder::EST_Viterbi_Decoder(uclist_f_t a, unpath_f_t b, int s)
84 : vit_a_big_number(1.0e10)
85 {
86 beam_width = 0;
87 cand_width = 0;
88 user_clist = a;
89 user_npath = b;
90
91 do_pruning = FALSE;
92 overall_path_pruning_envelope_width = -1;
93 candidate_pruning_envelope_width = -1;
94
95 // if s == -1 number of states is determined by number of cands
96 // this is specific to a particular search but very efficient
97 num_states = s; // can do the lattice search more directly
98 debug = FALSE;
99 trace = FALSE;
100 big_is_good = TRUE; // for probabilities it is
101 }
102
103 EST_Viterbi_Decoder::~EST_Viterbi_Decoder()
104 {
105 delete timeline;
106 }
107
108 void EST_Viterbi_Decoder::initialise(EST_Relation *p)
109 {
110 // Creates a time line with each point pointing at each item in p
111 EST_Item *i;
112 EST_VTPoint *t = 0,*n;
113
114 for (i=p->head(); i != 0; i=inext(i))
115 {
116 n = new EST_VTPoint;
117 n->s = i;
118 if (num_states > 0)
119 init_paths_array(n,num_states);
120 if (t == 0)
121 timeline = n;
122 else
123 t->next = n;
124 t=n;
125 }
126 // Extra one at the end for final paths
127 n = new EST_VTPoint;
128 if (num_states > 0)
129 init_paths_array(n,num_states);
130
131 // Need init path on first point so a search can start
132 if (num_states == 0) // general search case
133 timeline->paths = new EST_VTPath;
134 if (num_states == -1)
135 init_paths_array(timeline,1); // a start point
136
137 if (t == 0)
138 timeline = n; // its an empty stream
139 else
140 t->next = n;
141 }
142
143 static void init_paths_array(EST_VTPoint *n,int num_states)
144 {
145 // Create the states array and initialize it
146 int j;
147
148 n->num_states = num_states;
149 n->st_paths = new EST_VTPath*[num_states];
150 for (j=0;j<num_states;j++)
151 n->st_paths[j] = 0;
152 }
153
154 const int EST_Viterbi_Decoder::betterthan(const float a,const float b) const
155 {
156 // Some thing big is better, others want it to be as small as possible
157 // this just tells you if a is better than b by checking the variable
158 // in the decoder itself.
159
160 // For probabilities big_is_good == TRUE (or log probabilities)
161
162 if (big_is_good)
163 return (a > b);
164 else
165 return (a < b);
166 }
167
168 static int init_dynamic_states(EST_VTPoint *p, EST_VTCandidate *cands)
169 {
170 // In a special (hmm maybe not so special), the number of "states"
171 // is the number of candidates
172 EST_VTCandidate *c;
173 int i;
174
175 for (i=0, c=cands; c != 0; c=c->next,i++)
176 c->pos = i;
177 init_paths_array(p,i);
178
179 return i;
180 }
181
182 void EST_Viterbi_Decoder::set_pruning_parameters(float beam, float
183 ob_beam)
184 {
185
186 do_pruning = TRUE;
187 overall_path_pruning_envelope_width = beam;
188 candidate_pruning_envelope_width = ob_beam;
189
190 }
191
192 void EST_Viterbi_Decoder::turn_on_debug()
193 {
194 debug = TRUE;
195 }
196
197 void EST_Viterbi_Decoder::turn_on_trace()
198 {
199 trace = TRUE;
200 }
201
202
203 void EST_Viterbi_Decoder::search(void)
204 {
205 // Searches for the best path
206 EST_VTPoint *p;
207 EST_VTPath *t,*np;
208 EST_VTCandidate *c;
209 int i=0;
210
211 double best_score=0.0,score_cutoff=0.0;
212 double best_candidate_score=0.0,candidate_cutoff=0;
213 int dcount,pcount;
214 int cand_count=0, cands_considered=0;
215
216 for (p=timeline; p->next != 0; p=p->next)
217 { // For each point in time
218 // Find the candidates
219 p->cands = (*user_clist)(p->s,f); // P(S|B)
220 if (do_pruning)
221 prune_initialize(p,best_score,best_candidate_score,
222 score_cutoff,candidate_cutoff,
223 cand_count);
224 if (num_states != 0) // true viterbi -- optimized for states
225 {
226 if (num_states == -1) // special case, dynamic state size
227 init_dynamic_states(p->next,p->cands);
228
229 cands_considered=0; // moved by simonk
230 for (i=0; i<p->num_states; i++)
231 { // for each path up to here
232 //cands_considered=0;
233 if (((p == timeline) && i==0) || (p->st_paths[i] != 0))
234 for (c=p->cands; c != 0; c=c->next)
235 {
236 // for each new candidate
237 // candidate pruning (a.k.a. observation pruning)
238 if(!do_pruning ||
239 betterthan(c->score,candidate_cutoff))
240 {
241 cands_considered++;
242 // Find path extension costs
243 np = (*user_npath)(p->st_paths[i],c,f);
244 if (debug) debug_output_1(p,c,np,i);
245 if (do_pruning && betterthan(np->score,best_score))
246 {
247 best_score = np->score;
248 if(big_is_good)
249 score_cutoff = best_score
250 - overall_path_pruning_envelope_width;
251 else
252 score_cutoff = best_score
253 + overall_path_pruning_envelope_width;
254 }
255 // can prune here, although score_cutoff will
256 // be generally too generous at this point.
257 // It's unclear whether this pruning takes more
258 // time than it saves !
259 if(!do_pruning||betterthan(np->score,score_cutoff))
260 vit_add_paths(p->next,np);
261 else
262 delete np;
263 }
264 }
265 }
266
267 if (do_pruning)
268 {
269 if(big_is_good)
270 score_cutoff =
271 best_score - overall_path_pruning_envelope_width;
272 else
273 score_cutoff =
274 best_score + overall_path_pruning_envelope_width;
275 if(trace)
276 {
277 cerr << "Considered " << cands_considered << " of ";
278 cerr << cand_count*p->num_states << " candidate paths" << endl;
279 cerr << "FRAME: best score " << best_score;
280 cerr << " score cutoff " << score_cutoff << endl;
281 cerr << " best candidate score " << best_candidate_score;
282 cerr << " candidate cutoff " << candidate_cutoff << endl;
283 }
284
285 dcount=0; pcount=0;
286 for (i=0; i<p->next->num_states; i++)
287 if(p->next->st_paths[i] != 0)
288 {
289 pcount++;
290 if(!betterthan(p->next->st_paths[i]->score,
291 score_cutoff))
292 {
293 delete p->next->st_paths[i];
294 p->next->st_paths[i] = 0;
295 dcount++;
296 }
297 }
298 if(trace)
299 {
300 cerr << "Pruned " << dcount << " of " << pcount;
301 cerr << " paths" << endl << endl;
302 }
303 }
304 }
305 else // general beam search
306 for (t=p->paths; t != 0; t=t->next)
307 { // for each path up to here
308 for (c=p->cands; c != 0; c=c->next)
309 { // for each new candidate
310 np = (*user_npath)(t,c,f);
311 add_path(p->next,np); // be a little cleverer
312 }
313 }
314 if (debug) fprintf(stdout,"\n");
315 }
316
317 }
318
319 void EST_Viterbi_Decoder::
320 prune_initialize(EST_VTPoint *p,
321 double &best_score, double &best_candidate_score,
322 double &score_cutoff, double &candidate_cutoff,
323 int &cand_count)
324 { // Find best candidate, count them and set some vars.
325 EST_VTCandidate *c;
326 if (big_is_good)
327 {
328 best_score = -vit_a_big_number;
329 best_candidate_score = -vit_a_big_number;
330 score_cutoff = -vit_a_big_number;
331 candidate_cutoff = - candidate_pruning_envelope_width;
332 }
333 else
334 {
335 best_candidate_score = vit_a_big_number;
336 best_score = vit_a_big_number;
337 score_cutoff = vit_a_big_number;
338 candidate_cutoff = candidate_pruning_envelope_width;
339 }
340
341 for (cand_count=0,c=p->cands; c; c=c->next,cand_count++)
342 if (betterthan(c->score,best_candidate_score))
343 best_candidate_score = c->score;
344 candidate_cutoff += best_candidate_score;
345 }
346
347 static void debug_output_1(EST_VTPoint *p,EST_VTCandidate *c,
348 EST_VTPath *np,int i)
349 {
350 printf("%s: ",(const char *)p->s->name());
351 cout << c->name;
352 printf(" %1.3f B %1.3f (%1.3f) st %d s %1.3f ",
353 np->c->score,
354 (np->c->score==0 ? 0 :
355 ((float)np->f("lscore"))/np->c->score),
356 (float)np->f("lscore"),np->state,
357 np->score);
358 if (p->st_paths[i] == 0)
359 cout << "(I)" << endl;
360 else
361 cout << p->st_paths[i]->c->name << endl;
362 }
363
364 void EST_Viterbi_Decoder::vit_add_paths(EST_VTPoint *pt, EST_VTPath *np)
365 {
366 // Add set of paths
367 EST_VTPath *p,*next_p;
368
369 for (p=np; p != 0; p=next_p)
370 {
371 next_p = p->next; // need to save this as p could be deleted
372 vit_add_path(pt,p);
373 }
374
375 }
376 void EST_Viterbi_Decoder::vit_add_path(EST_VTPoint *p, EST_VTPath *np)
377 {
378 // We are doing true viterbi so we need only keep the best
379 // path for each state. This means we can index into the
380 // array of paths ending at P and only keep np if its score
381 // is better than any other path of that state
382
383 if ((np->state < 0) || (np->state > p->num_states))
384 {
385 cerr << "EST_Viterbi: state too big (" << np->state << ")" << endl;
386 }
387 else if ((p->st_paths[np->state] == 0) ||
388 (betterthan(np->score,p->st_paths[np->state]->score)))
389 {
390 // This new one is better so replace it
391 if (p->st_paths[np->state] != 0)
392 delete p->st_paths[np->state];
393 p->st_paths[np->state] = np;
394 }
395 else
396 delete np;
397 }
398
399 bool EST_Viterbi_Decoder::vit_prune_path(double path_score, double score_cutoff)
400 {
401
402 // a bit of a simple function !!
403
404 // if it falls below cutoff, then prune point
405 // typically will only be one path at this point anyway (Viterbi)
406 if(!betterthan(path_score,score_cutoff))
407 return TRUE;
408
409 return FALSE;
410 }
411
412
413
414 void EST_Viterbi_Decoder::add_path(EST_VTPoint *p, EST_VTPath *np)
415 {
416 // Add new path to point, Prunes as appropriate to strategy
417 EST_VTPath *pp;
418
419 if (p == 0)
420 cerr << "Viterbi: tried to add path to NULL point\n";
421 else
422 {
423 if ((beam_width == 0) || // Add if no beam restrictions or
424 (p->num_paths < beam_width) || // beam not filled or
425 (betterthan(np->score,p->paths->score)))//this is better than best
426 // (np->score > p->paths->score)) // this is better than best
427 {
428 EST_VTPath **l = &p->paths;
429 EST_VTPath *a;
430
431 for (a=p->paths; /* scary */ ; a=a->next)
432 {
433 if ((a == 0) || (betterthan(a->score,np->score)))
434 { // Add new path here
435 np->next = a;
436 *l = np;
437 p->num_paths++;
438 break;
439 }
440 l = &a->next;
441 }
442 // Prune the first one of the list
443 if ((beam_width > 0) &&
444 (p->num_paths > beam_width))
445 {
446 pp = p->paths;
447 p->paths = pp->next;
448 pp->next = 0;
449 p->num_paths--;
450 delete pp;
451 }
452 }
453 else
454 {
455 delete np; // failed to make it
456 }
457 }
458
459 }
460
461 EST_VTCandidate *EST_Viterbi_Decoder::add_cand_prune(EST_VTCandidate *newcand,
462 EST_VTCandidate *allcands)
463 {
464 // Add newcand to allcand, in score order and prune it to
465 // cand_width, delete newcand if its not good enough
466 EST_VTCandidate *newlist = allcands;
467 EST_VTCandidate *pp;
468 int numcands;
469
470 if (allcands == 0)
471 numcands = 0;
472 else
473 numcands = allcands->pos;
474
475 if ((cand_width == 0) || // Add if no candbeam restrictions or
476 (numcands < cand_width) || // candbeam not filled or
477 (betterthan(newcand->score,allcands->score))) //this better than best
478 {
479 EST_VTCandidate **l = &newlist;
480 EST_VTCandidate *a;
481
482 for (a=newlist; /* scary */ ; a=a->next)
483 {
484 if ((a == 0) || (betterthan(a->score,newcand->score)))
485 { // Add new path here
486 newcand->next = a;
487 *l = newcand;
488 numcands++;
489 break;
490 }
491 l = &a->next;
492 }
493 // Prune the first one off the list
494 if ((cand_width > 0) &&
495 (numcands > cand_width))
496 {
497 pp = newlist;
498 newlist = pp->next;
499 pp->next = 0;
500 numcands--;
501 delete pp;
502 }
503 }
504 else
505 delete newcand; // failed to make it
506
507 newlist->pos = numcands;
508 return newlist;
509 }
510
511 bool EST_Viterbi_Decoder::result(const EST_String &n)
512 {
513 // Finds best path through the search space (previously searched)
514 // Adds field to the EST_Items, named n, with chosen value
515 EST_VTPath *p;
516
517 if ((timeline == 0) || (timeline->next == 0))
518 return TRUE; // it's an empty list so it has succeeded
519 p = find_best_end();
520 if (p == 0)
521 return FALSE; // there isn't any answer
522
523 for (; p != 0; p=p->from)
524 {
525 // Hmm need the original EST_Item
526 if (p->c != 0)
527 {
528 p->c->s->set_val(n,p->c->name);
529 p->c->s->set(n+"_score",p->f.F("lscore",0.0));
530 }
531 }
532 return TRUE;
533 }
534
535 bool EST_Viterbi_Decoder::result( EST_VTPath **bestPathEnd )
536 {
537 // Finds best path through the search space (previously searched)
538 *bestPathEnd = 0;
539
540 if ((timeline == 0) || (timeline->next == 0))
541 return TRUE; // it's an empty list so it has succeeded
542
543 *bestPathEnd = find_best_end();
544
545 if (*bestPathEnd == 0)
546 return FALSE; // there isn't any answer
547
548 return TRUE;
549 }
550
551
552 void EST_Viterbi_Decoder::copy_feature(const EST_String &n)
553 {
554 // Copy feature from path to related stream
555 EST_VTPath *p;
556
557 p = find_best_end();
558 if(p == 0)
559 return;
560
561 for (; p != 0; p=p->from)
562 {
563 // Hmm need the original EST_Item
564 if ((p->c != 0) && (p->f.present(n)))
565 p->c->s->set_val(n,p->f(n));
566 }
567 }
568
569 EST_VTPath *EST_Viterbi_Decoder::find_best_end() const
570 {
571 EST_VTPoint *t;
572 double best,worst;
573 EST_VTPath *p, *best_p=0;
574 int i;
575 // I'd like to use HUGE_VAL or FLT_MAX for this but its not portable
576 // (on alphas)
577
578 if (big_is_good)
579 worst = -vit_a_big_number; // worst possible;
580 else
581 worst = vit_a_big_number; // worst possible;
582 best = worst; // hopefully we can find something better;
583
584 for (i=0,t=timeline; t->next != 0; t=t->next,i++)
585 {
586 if ((t->num_states == 0) && (t->num_paths == 0))
587 {
588 cerr << "No paths at frame " << i << " " << t->s->name() << endl;
589 return 0;
590 }
591 }
592
593 if (num_states != 0)
594 for (i=0; i<t->num_states; i++)
595 {
596 if ((t->st_paths[i] != 0) &&
597 (betterthan(t->st_paths[i]->score,best)))
598 {
599 best = t->st_paths[i]->score;
600 best_p = t->st_paths[i];
601 }
602 }
603 else
604 for (p=t->paths; p!=0; p=p->next)
605 {
606 if (betterthan(p->score,best))
607 {
608 best = p->score;
609 best_p = p;
610 }
611 }
612
613
614 if (debug)
615 {
616 if (best == worst)
617 cerr << "Failed to find path" << endl;
618 cout << "Best score is " << best << endl;
619 }
620
621 return best_p;
622 }
623
2.4-release_vs_2.5.0-release.