Loading...
Searching...
No Matches
dynamic_program.cc
/*************************************************************************/
/* */
/* Centre for Speech Technology Research */
/* University of Edinburgh, UK */
/* Copyright (c) 1995,1996 */
/* 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. */
/* */
/*************************************************************************/
/* Author : Simon King */
/* Date : June 1998 */
/*************************************************************************/
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <fstream>
#include "EST_math.h"
#include "ling_class/EST_Utterance.h"
typedef EST_TVector<EST_Item*> EST_Item_ptr_Vector;
static EST_Item *const def_val_item_ptr = NULL;
template <> EST_Item* const *EST_Item_ptr_Vector::def_val = &def_val_item_ptr;
static EST_Item* error_return_item_ptr = NULL;
template <> EST_Item* *EST_Item_ptr_Vector::error_return = &error_return_item_ptr;
#if defined(INSTANTIATE_TEMPLATES)
#include "../base_class/EST_TVector.cc"
template class EST_TVector<EST_Item*>;
#endif
typedef
float (*local_cost_function)(const EST_Item *item1,
const EST_Item *item2);
typedef
bool (*local_pruning_function)(const int i,
const int j,
const int max_i,
const int max_j);
bool dp_sub(int i, int j,
const EST_Item_ptr_Vector &vr1,
const EST_Item_ptr_Vector &vr2,
EST_IMatrix &DP_path_i, EST_IMatrix &DP_path_j,
local_cost_function lcf,
local_pruning_function lpf,
EST_Item *null_sym,
EST_FMatrix &cost);
void trace_back_and_link(int i, int j,
EST_Item *p1, EST_Item *p2,
const EST_IMatrix &DP_path_i,
const EST_IMatrix &DP_path_j,
EST_Item *null_sym);
inline bool null_lpf(const int,const int,const int,const int)
{
return FALSE;
}
bool dp_match(const EST_Relation &lexical,
const EST_Relation &surface,
EST_Relation &match,
local_cost_function lcf,
local_pruning_function lpf,
EST_Item *null_sym);
bool dp_match(const EST_Relation &lexical,
const EST_Relation &surface,
EST_Relation &match,
local_cost_function lcf,
EST_Item *null_sym)
{
// dp without pruning
return dp_match(lexical,surface,match,lcf,null_lpf,null_sym);
}
static float fixed_ins;
static float fixed_del;
static float fixed_sub;
float fixed_local_cost(const EST_Item *s1, const EST_Item *s2)
{
EST_String null_sym = "nil";
// otherwise cost is either insertion cost, or cost_matrix value
if (s1->name() == s2->name())
return 0;
else
{
if (s1->name() == null_sym)
return fixed_ins;
else if (s2->name() == null_sym)
return fixed_del;
else
return fixed_sub;
}
}
bool dp_match(const EST_Relation &lexical,
const EST_Relation &surface,
EST_Relation &match,
float ins, float del, float sub)
{
fixed_ins = ins;
fixed_del = del;
fixed_sub = sub;
EST_Item null_sym;
return dp_match(lexical, surface, match, fixed_local_cost,
null_lpf, &null_sym);
}
bool dp_match(const EST_Relation &lexical,
const EST_Relation &surface,
EST_Relation &match,
local_cost_function lcf,
local_pruning_function lpf,
EST_Item *null_sym)
{
// aligns lexical and surface forms using dynamic programming
// i.e. the lexical form is transformed into the surface form
// by substitutions, insertions and deletions
// makes links between associated (matching or substituted) items
// insertions and deletions are 'left dangling'
// links are stored in a new relation called "Match"
// assumes that local cost computation is cheap (no caching)
EST_IMatrix DP_path_i,DP_path_j;
EST_Item_ptr_Vector vr1,vr2;
EST_Item *p;
int l1,l2,i,j;
l1 = lexical.length() + 1;
l2 = surface.length() + 1;
vr1.resize(l1);
vr2.resize(l2);
// prepend null_syms
vr1[0] = null_sym;
vr2[0] = null_sym;
for (p=lexical.head(),i=1; p != 0; p = inext(p),i++)
vr1[i] = p;
for (p=surface.head(),i=1; p != 0; p = inext(p),i++)
vr2[i] = p;
DP_path_i.resize(l1,l2);
DP_path_j.resize(l1,l2);
/*
cerr << "Pruning" << endl;
for(i=0;i<l1;i++)
{
for(j=0;j<l2;j++)
if(lpf(i,j,l1,l2))
cerr << "- ";
else
cerr << "+ ";
cerr << endl;
}
cerr << endl;
*/
// end conditions : must start at (0,0) and finish at (l1-1,l2-1)
// i.e. extreme corners of grid
EST_FMatrix cost;
cost.resize(vr1.length(),vr2.length());
for(i=0;i<l1;i++)
for(j=0;j<l2;j++)
cost.a_no_check(i,j) = -1; // means not computed yet
if(!dp_sub(l1-1,l2-1,
vr1,vr2,
DP_path_i,DP_path_j,
lcf,lpf,null_sym,cost))
{
cerr << "No path found (over pruning ?)" << endl;
return FALSE;
}
// make somewhere to record the relations
//utt.create_relation("Match");
for (p = lexical.head(); p; p = inext(p))
match.append(p);
/*
for(i=0;i<l1;i++)
{
for(j=0;j<l2;j++)
cerr << i << "," << j << "=[" << DP_path_i(i,j) << "," << DP_path_j(i,j) << "] ";
cerr << endl;
}
cerr << endl;
*/
trace_back_and_link(l1-1,l2-1,
match.rlast(),
surface.rlast(),
DP_path_i,DP_path_j,null_sym);
return TRUE;
}
bool dp_sub(int i, int j,
const EST_Item_ptr_Vector &vr1,
const EST_Item_ptr_Vector &vr2,
EST_IMatrix &DP_path_i, EST_IMatrix &DP_path_j,
local_cost_function lcf,
local_pruning_function lpf,
EST_Item *null_sym,
EST_FMatrix &cost)
{
// the goal is to compute cost(i,j)
// already done ?
if(cost(i,j) >= 0)
return TRUE;
//cerr << "sub " << i << " " << j << endl;
int best_i=-1,best_j=-1;
float sub,ins,del;
float best_c=MAXFLOAT;
// prune ?
if(lpf(i,j,vr1.length()-1,vr2.length()-1))
return FALSE;
// consider all paths into this point
// and select the best one (lowest cost)
if(i==0)
{
if(j==0)
{
best_i = i;
best_j = j;
best_c = lcf(null_sym,null_sym);
}
else
{
// insert j'th item from vr2
if(dp_sub(i,j-1,vr1,vr2,
DP_path_i,DP_path_j,
lcf,lpf, null_sym,cost))
{
best_i = i;
best_j = j-1;
best_c = lcf(null_sym,vr2(j)) + cost.a(i,j-1);
}
else
return FALSE;
}
}
else if(j==0)
{
// delete i'th item from vr1
if(dp_sub(i-1,j,vr1,vr2,
DP_path_i,DP_path_j,
lcf,lpf, null_sym,cost))
{
best_i = i-1;
best_j = j;
best_c = lcf(vr1(i),null_sym) + cost.a(i-1,j);
}
}
// this is the simplest local constraint (i.e. no constraints !)
// which allows unlimited consecutive insertions or deletions
else
{
if(dp_sub(i-1,j-1,vr1,vr2,
DP_path_i,DP_path_j,
lcf,lpf, null_sym,cost))
{
sub = 2 * lcf(vr1(i),vr2(j)) + cost(i-1,j-1);
if(sub < best_c)
{
best_i=i-1;
best_j=j-1;
best_c = sub;
}
}
if(dp_sub(i,j-1,vr1,vr2,
DP_path_i,DP_path_j,
lcf,lpf, null_sym,cost))
{
ins=lcf(null_sym,vr2(j)) + cost(i,j-1);
if(ins < best_c)
{
best_i=i;
best_j=j-1;
best_c = ins;
}
}
if(dp_sub(i-1,j,vr1,vr2,
DP_path_i,DP_path_j,
lcf,lpf, null_sym,cost))
{
del=lcf(vr1(i),null_sym) + cost(i-1,j);
if(del < best_c)
{
best_i=i-1;
best_j=j;
best_c = del;
}
}
}
cost.a(i,j) = best_c;
DP_path_i.a_no_check(i,j) = best_i;
DP_path_j.a_no_check(i,j) = best_j;
//cerr << "best " << i << "," << j << " = " << best_c << endl;
if(best_c == MAXFLOAT)
// didn't find a better path
return FALSE;
else
return TRUE;
}
void trace_back_and_link(int i, int j,
EST_Item *p1, EST_Item *p2,
const EST_IMatrix &DP_path_i,
const EST_IMatrix &DP_path_j,
EST_Item *null_sym)
{
//cerr << "trace " << i << " " << j << endl;
//int i,j;
//i=utt.relation("Lexical")->index(p1);
//j=utt.relation("Surface")->index(p2);
if((p1==0)&&(p2==0))
// reached start
return;
if(DP_path_i(i,j) == i-1)
{
if(DP_path_j(i,j) == j-1)
{
// match, or substitution
//cerr << "sub " << p1->name() << " with " << p2->name() << endl;
p1->append_daughter(p2);
p1=iprev(p1);
p2=iprev(p2);
}
else
// deletion
p1=iprev(p1);
}
else
{
// insertion
// p1->append_daughter(p2); // decorative
p2=iprev(p2);
}
trace_back_and_link(DP_path_i(i,j), DP_path_j(i,j),
p1,p2,
DP_path_i,DP_path_j,
null_sym);
}
EST_FMatrix
Definition EST_FMatrix.h:56
EST_IMatrix
Definition EST_IMatrix.h:50
EST_Item
Definition EST_Item.h:83
EST_Relation
Definition EST_Relation.h:68
EST_Relation::head
EST_Item * head() const
Definition EST_Relation.h:125
EST_Relation::length
int length() const
Definition EST_Relation.cc:137
EST_String
Definition EST_String.h:70
EST_TMatrix::a_no_check
INLINE const T & a_no_check(int row, int col) const
const access with no bounds check, care recommend
Definition EST_TMatrix.h:184
EST_TSimpleMatrix::resize
void resize(int rows, int cols, int set=1)
resize matrix
Definition EST_TSimpleMatrix.cc:86
EST_TVector
Definition EST_TVector.h:148
EST_TVector::resize
void resize(int n, int set=1)
Definition EST_TVector.cc:196
EST_TVector< EST_Item * >::def_val
static const EST_Item ** def_val
Definition EST_TVector.h:223
EST_TVector::length
INLINE int length() const
number of items in vector.
Definition EST_TVector.h:252
EST_TVector< EST_Item * >::error_return
static EST_Item ** error_return
Definition EST_TVector.h:230