Logo Search packages:      
Sourcecode: speech-tools version File versions  Download package

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 <stdio.h>
#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=next(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 void 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);
}

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,score_cutoff;
    double best_candidate_score,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 extention 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*cand_count << " 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 restritions 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 restritions 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;
}

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;
}


Generated by  Doxygen 1.6.0   Back to index