Loading...
Searching...
No Matches
EST_viterbi.cc
/*************************************************************************/
/* */
/* Centre for Speech Technology Research */
/* University of Edinburgh, UK */
/* Copyright (c) 1996,1997 */
/* All Rights Reserved. */
/* */
/* Permission is hereby granted, free of charge, to use and distribute */
/* this software and its documentation without restriction, including */
/* without limitation the rights to use, copy, modify, merge, publish, */
/* distribute, sublicense, and/or sell copies of this work, and to */
/* permit persons to whom this work is furnished to do so, subject to */
/* the following conditions: */
/* 1. The code must retain the above copyright notice, this list of */
/* conditions and the following disclaimer. */
/* 2. Any modifications must be clearly marked as such. */
/* 3. Original authors' names are not deleted. */
/* 4. The authors' names are not used to endorse or promote products */
/* derived from this software without specific prior written */
/* permission. */
/* */
/* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
/* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
/* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
/* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
/* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
/* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
/* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
/* THIS SOFTWARE. */
/* */
/*************************************************************************/
/* Authors: Alan W Black */
/* Date : July 1996 */
/*-----------------------------------------------------------------------*/
/* A viterbi decoder */
/* */
/* User provides the candidates, target and combine score function */
/* and it searches for the best path through the candidates */
/* */
/*=======================================================================*/
#include <cstdio>
#include "EST_viterbi.h"
static void init_paths_array(EST_VTPoint *n,int num_states);
static void debug_output_1(EST_VTPoint *p,EST_VTCandidate *c,
EST_VTPath *np, int i);
EST_VTPoint::~EST_VTPoint()
{
int i;
if (paths != 0) delete paths;
if (num_states != 0)
{
for (i=0; i<num_states; i++)
if (st_paths[i] != 0)
delete st_paths[i];
delete [] st_paths;
}
if (cands != 0) delete cands;
if (next != 0) delete next;
}
EST_Viterbi_Decoder::EST_Viterbi_Decoder(uclist_f_t a, unpath_f_t b)
: vit_a_big_number(1.0e10)
{
beam_width = 0;
cand_width = 0;
user_clist = a;
user_npath = b;
num_states = 0;
do_pruning = FALSE;
overall_path_pruning_envelope_width = -1;
candidate_pruning_envelope_width = -1;
debug = FALSE;
trace = FALSE;
big_is_good = TRUE; // for probabilities it is
}
EST_Viterbi_Decoder::EST_Viterbi_Decoder(uclist_f_t a, unpath_f_t b, int s)
: vit_a_big_number(1.0e10)
{
beam_width = 0;
cand_width = 0;
user_clist = a;
user_npath = b;
do_pruning = FALSE;
overall_path_pruning_envelope_width = -1;
candidate_pruning_envelope_width = -1;
// if s == -1 number of states is determined by number of cands
// this is specific to a particular search but very efficient
num_states = s; // can do the lattice search more directly
debug = FALSE;
trace = FALSE;
big_is_good = TRUE; // for probabilities it is
}
EST_Viterbi_Decoder::~EST_Viterbi_Decoder()
{
delete timeline;
}
void EST_Viterbi_Decoder::initialise(EST_Relation *p)
{
// Creates a time line with each point pointing at each item in p
EST_Item *i;
EST_VTPoint *t = 0,*n;
for (i=p->head(); i != 0; i=inext(i))
{
n = new EST_VTPoint;
n->s = i;
if (num_states > 0)
init_paths_array(n,num_states);
if (t == 0)
timeline = n;
else
t->next = n;
t=n;
}
// Extra one at the end for final paths
n = new EST_VTPoint;
if (num_states > 0)
init_paths_array(n,num_states);
// Need init path on first point so a search can start
if (num_states == 0) // general search case
timeline->paths = new EST_VTPath;
if (num_states == -1)
init_paths_array(timeline,1); // a start point
if (t == 0)
timeline = n; // its an empty stream
else
t->next = n;
}
static void init_paths_array(EST_VTPoint *n,int num_states)
{
// Create the states array and initialize it
int j;
n->num_states = num_states;
n->st_paths = new EST_VTPath*[num_states];
for (j=0;j<num_states;j++)
n->st_paths[j] = 0;
}
const int EST_Viterbi_Decoder::betterthan(const float a,const float b) const
{
// Some thing big is better, others want it to be as small as possible
// this just tells you if a is better than b by checking the variable
// in the decoder itself.
// For probabilities big_is_good == TRUE (or log probabilities)
if (big_is_good)
return (a > b);
else
return (a < b);
}
static int init_dynamic_states(EST_VTPoint *p, EST_VTCandidate *cands)
{
// In a special (hmm maybe not so special), the number of "states"
// is the number of candidates
EST_VTCandidate *c;
int i;
for (i=0, c=cands; c != 0; c=c->next,i++)
c->pos = i;
init_paths_array(p,i);
return i;
}
void EST_Viterbi_Decoder::set_pruning_parameters(float beam, float
ob_beam)
{
do_pruning = TRUE;
overall_path_pruning_envelope_width = beam;
candidate_pruning_envelope_width = ob_beam;
}
void EST_Viterbi_Decoder::turn_on_debug()
{
debug = TRUE;
}
void EST_Viterbi_Decoder::turn_on_trace()
{
trace = TRUE;
}
void EST_Viterbi_Decoder::search(void)
{
// Searches for the best path
EST_VTPoint *p;
EST_VTPath *t,*np;
EST_VTCandidate *c;
int i=0;
double best_score=0.0,score_cutoff=0.0;
double best_candidate_score=0.0,candidate_cutoff=0;
int dcount,pcount;
int cand_count=0, cands_considered=0;
for (p=timeline; p->next != 0; p=p->next)
{ // For each point in time
// Find the candidates
p->cands = (*user_clist)(p->s,f); // P(S|B)
if (do_pruning)
prune_initialize(p,best_score,best_candidate_score,
score_cutoff,candidate_cutoff,
cand_count);
if (num_states != 0) // true viterbi -- optimized for states
{
if (num_states == -1) // special case, dynamic state size
init_dynamic_states(p->next,p->cands);
cands_considered=0; // moved by simonk
for (i=0; i<p->num_states; i++)
{ // for each path up to here
//cands_considered=0;
if (((p == timeline) && i==0) || (p->st_paths[i] != 0))
for (c=p->cands; c != 0; c=c->next)
{
// for each new candidate
// candidate pruning (a.k.a. observation pruning)
if(!do_pruning ||
betterthan(c->score,candidate_cutoff))
{
cands_considered++;
// Find path extension costs
np = (*user_npath)(p->st_paths[i],c,f);
if (debug) debug_output_1(p,c,np,i);
if (do_pruning && betterthan(np->score,best_score))
{
best_score = np->score;
if(big_is_good)
score_cutoff = best_score
- overall_path_pruning_envelope_width;
else
score_cutoff = best_score
+ overall_path_pruning_envelope_width;
}
// can prune here, although score_cutoff will
// be generally too generous at this point.
// It's unclear whether this pruning takes more
// time than it saves !
if(!do_pruning||betterthan(np->score,score_cutoff))
vit_add_paths(p->next,np);
else
delete np;
}
}
}
if (do_pruning)
{
if(big_is_good)
score_cutoff =
best_score - overall_path_pruning_envelope_width;
else
score_cutoff =
best_score + overall_path_pruning_envelope_width;
if(trace)
{
cerr << "Considered " << cands_considered << " of ";
cerr << cand_count*p->num_states << " candidate paths" << endl;
cerr << "FRAME: best score " << best_score;
cerr << " score cutoff " << score_cutoff << endl;
cerr << " best candidate score " << best_candidate_score;
cerr << " candidate cutoff " << candidate_cutoff << endl;
}
dcount=0; pcount=0;
for (i=0; i<p->next->num_states; i++)
if(p->next->st_paths[i] != 0)
{
pcount++;
if(!betterthan(p->next->st_paths[i]->score,
score_cutoff))
{
delete p->next->st_paths[i];
p->next->st_paths[i] = 0;
dcount++;
}
}
if(trace)
{
cerr << "Pruned " << dcount << " of " << pcount;
cerr << " paths" << endl << endl;
}
}
}
else // general beam search
for (t=p->paths; t != 0; t=t->next)
{ // for each path up to here
for (c=p->cands; c != 0; c=c->next)
{ // for each new candidate
np = (*user_npath)(t,c,f);
add_path(p->next,np); // be a little cleverer
}
}
if (debug) fprintf(stdout,"\n");
}
}
void EST_Viterbi_Decoder::
prune_initialize(EST_VTPoint *p,
double &best_score, double &best_candidate_score,
double &score_cutoff, double &candidate_cutoff,
int &cand_count)
{ // Find best candidate, count them and set some vars.
EST_VTCandidate *c;
if (big_is_good)
{
best_score = -vit_a_big_number;
best_candidate_score = -vit_a_big_number;
score_cutoff = -vit_a_big_number;
candidate_cutoff = - candidate_pruning_envelope_width;
}
else
{
best_candidate_score = vit_a_big_number;
best_score = vit_a_big_number;
score_cutoff = vit_a_big_number;
candidate_cutoff = candidate_pruning_envelope_width;
}
for (cand_count=0,c=p->cands; c; c=c->next,cand_count++)
if (betterthan(c->score,best_candidate_score))
best_candidate_score = c->score;
candidate_cutoff += best_candidate_score;
}
static void debug_output_1(EST_VTPoint *p,EST_VTCandidate *c,
EST_VTPath *np,int i)
{
printf("%s: ",(const char *)p->s->name());
cout << c->name;
printf(" %1.3f B %1.3f (%1.3f) st %d s %1.3f ",
np->c->score,
(np->c->score==0 ? 0 :
((float)np->f("lscore"))/np->c->score),
(float)np->f("lscore"),np->state,
np->score);
if (p->st_paths[i] == 0)
cout << "(I)" << endl;
else
cout << p->st_paths[i]->c->name << endl;
}
void EST_Viterbi_Decoder::vit_add_paths(EST_VTPoint *pt, EST_VTPath *np)
{
// Add set of paths
EST_VTPath *p,*next_p;
for (p=np; p != 0; p=next_p)
{
next_p = p->next; // need to save this as p could be deleted
vit_add_path(pt,p);
}
}
void EST_Viterbi_Decoder::vit_add_path(EST_VTPoint *p, EST_VTPath *np)
{
// We are doing true viterbi so we need only keep the best
// path for each state. This means we can index into the
// array of paths ending at P and only keep np if its score
// is better than any other path of that state
if ((np->state < 0) || (np->state > p->num_states))
{
cerr << "EST_Viterbi: state too big (" << np->state << ")" << endl;
}
else if ((p->st_paths[np->state] == 0) ||
(betterthan(np->score,p->st_paths[np->state]->score)))
{
// This new one is better so replace it
if (p->st_paths[np->state] != 0)
delete p->st_paths[np->state];
p->st_paths[np->state] = np;
}
else
delete np;
}
bool EST_Viterbi_Decoder::vit_prune_path(double path_score, double score_cutoff)
{
// a bit of a simple function !!
// if it falls below cutoff, then prune point
// typically will only be one path at this point anyway (Viterbi)
if(!betterthan(path_score,score_cutoff))
return TRUE;
return FALSE;
}
void EST_Viterbi_Decoder::add_path(EST_VTPoint *p, EST_VTPath *np)
{
// Add new path to point, Prunes as appropriate to strategy
EST_VTPath *pp;
if (p == 0)
cerr << "Viterbi: tried to add path to NULL point\n";
else
{
if ((beam_width == 0) || // Add if no beam restrictions or
(p->num_paths < beam_width) || // beam not filled or
(betterthan(np->score,p->paths->score)))//this is better than best
// (np->score > p->paths->score)) // this is better than best
{
EST_VTPath **l = &p->paths;
EST_VTPath *a;
for (a=p->paths; /* scary */ ; a=a->next)
{
if ((a == 0) || (betterthan(a->score,np->score)))
{ // Add new path here
np->next = a;
*l = np;
p->num_paths++;
break;
}
l = &a->next;
}
// Prune the first one of the list
if ((beam_width > 0) &&
(p->num_paths > beam_width))
{
pp = p->paths;
p->paths = pp->next;
pp->next = 0;
p->num_paths--;
delete pp;
}
}
else
{
delete np; // failed to make it
}
}
}
EST_VTCandidate *EST_Viterbi_Decoder::add_cand_prune(EST_VTCandidate *newcand,
EST_VTCandidate *allcands)
{
// Add newcand to allcand, in score order and prune it to
// cand_width, delete newcand if its not good enough
EST_VTCandidate *newlist = allcands;
EST_VTCandidate *pp;
int numcands;
if (allcands == 0)
numcands = 0;
else
numcands = allcands->pos;
if ((cand_width == 0) || // Add if no candbeam restrictions or
(numcands < cand_width) || // candbeam not filled or
(betterthan(newcand->score,allcands->score))) //this better than best
{
EST_VTCandidate **l = &newlist;
EST_VTCandidate *a;
for (a=newlist; /* scary */ ; a=a->next)
{
if ((a == 0) || (betterthan(a->score,newcand->score)))
{ // Add new path here
newcand->next = a;
*l = newcand;
numcands++;
break;
}
l = &a->next;
}
// Prune the first one off the list
if ((cand_width > 0) &&
(numcands > cand_width))
{
pp = newlist;
newlist = pp->next;
pp->next = 0;
numcands--;
delete pp;
}
}
else
delete newcand; // failed to make it
newlist->pos = numcands;
return newlist;
}
bool EST_Viterbi_Decoder::result(const EST_String &n)
{
// Finds best path through the search space (previously searched)
// Adds field to the EST_Items, named n, with chosen value
EST_VTPath *p;
if ((timeline == 0) || (timeline->next == 0))
return TRUE; // it's an empty list so it has succeeded
p = find_best_end();
if (p == 0)
return FALSE; // there isn't any answer
for (; p != 0; p=p->from)
{
// Hmm need the original EST_Item
if (p->c != 0)
{
p->c->s->set_val(n,p->c->name);
p->c->s->set(n+"_score",p->f.F("lscore",0.0));
}
}
return TRUE;
}
bool EST_Viterbi_Decoder::result( EST_VTPath **bestPathEnd )
{
// Finds best path through the search space (previously searched)
*bestPathEnd = 0;
if ((timeline == 0) || (timeline->next == 0))
return TRUE; // it's an empty list so it has succeeded
*bestPathEnd = find_best_end();
if (*bestPathEnd == 0)
return FALSE; // there isn't any answer
return TRUE;
}
void EST_Viterbi_Decoder::copy_feature(const EST_String &n)
{
// Copy feature from path to related stream
EST_VTPath *p;
p = find_best_end();
if(p == 0)
return;
for (; p != 0; p=p->from)
{
// Hmm need the original EST_Item
if ((p->c != 0) && (p->f.present(n)))
p->c->s->set_val(n,p->f(n));
}
}
EST_VTPath *EST_Viterbi_Decoder::find_best_end() const
{
EST_VTPoint *t;
double best,worst;
EST_VTPath *p, *best_p=0;
int i;
// I'd like to use HUGE_VAL or FLT_MAX for this but its not portable
// (on alphas)
if (big_is_good)
worst = -vit_a_big_number; // worst possible;
else
worst = vit_a_big_number; // worst possible;
best = worst; // hopefully we can find something better;
for (i=0,t=timeline; t->next != 0; t=t->next,i++)
{
if ((t->num_states == 0) && (t->num_paths == 0))
{
cerr << "No paths at frame " << i << " " << t->s->name() << endl;
return 0;
}
}
if (num_states != 0)
for (i=0; i<t->num_states; i++)
{
if ((t->st_paths[i] != 0) &&
(betterthan(t->st_paths[i]->score,best)))
{
best = t->st_paths[i]->score;
best_p = t->st_paths[i];
}
}
else
for (p=t->paths; p!=0; p=p->next)
{
if (betterthan(p->score,best))
{
best = p->score;
best_p = p;
}
}
if (debug)
{
if (best == worst)
cerr << "Failed to find path" << endl;
cout << "Best score is " << best << endl;
}
return best_p;
}
EST_Features::F
const float F(const EST_String &path) const
Definition EST_Features.h:135
EST_Features::present
int present(const EST_String &name) const
Definition EST_Features.cc:147
EST_Item
Definition EST_Item.h:83
EST_Item::set
void set(const EST_String &name, int ival)
Definition EST_Item.h:179
EST_Item::set_val
void set_val(const EST_String &name, const EST_Val &sval)
Definition EST_Item.h:214
EST_Relation
Definition EST_Relation.h:68
EST_Relation::head
EST_Item * head() const
Definition EST_Relation.h:125
EST_String
Definition EST_String.h:70
EST_VTCandidate
Definition EST_viterbi.h:58
EST_VTPath
Definition EST_viterbi.h:76