Loading...
Searching...
No Matches
align_main.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. */
/* */
/*************************************************************************/
/* Author : Alan W Black */
/* Date : September 1999 */
/*-----------------------------------------------------------------------*/
/* Simple alignment scoring program to give number of insertions, */
/* deletions, errors between a string of symbols and a reference string */
/* of symbols */
/* */
/*=======================================================================*/
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include "EST.h"
#include "EST_WFST.h"
static int align_main(int argc, char **argv);
static void nisttool_align(EST_Option &al);
static void string_align(EST_Option &al);
static void align_score(EST_Utterance &u, const EST_String &refrel,
const EST_String &hyporel,
const EST_String &alignrel,
int &total,int &ins,int &del,int &sub,int &correct);
static int name_distance(EST_Item *r,EST_Item *h);
void align(EST_Utterance &utt,
const EST_String &refrel,
const EST_String &hyporel,
const EST_String &alignrel);
static void load_sentence(EST_Utterance &u, const EST_String &relname,
EST_TokenStream &ts);
static void load_sentence(EST_Utterance &u, const EST_String &relname,
EST_String &relval);
/** @name <command>align</command> <emphasis>align stream with reference stream</emphasis>
@id align-manual
* @toc
*/
//@{
/**@name Synopsis
*/
//@{
//@synopsis
/**
*/
//@}
/**@name OPTIONS
*/
//@{
//@options
//@}
int main(int argc, char **argv)
{
align_main(argc,argv);
exit(0);
return 0;
}
static int align_main(int argc, char **argv)
{
// Top level function generates a WFST from rules
EST_Option al;
EST_StrList files;
EST_String outfile;
EST_String format;
parse_command_line
(argc, argv,
EST_String("[options] ...\n")+
"Summary: align an hypothesis with a reference string\n"+
"-rfile <ifile> Reference file\n"+
"-hfile <ifile> Hypothesis file\n"+
"-rstring <string> Reference string\n"+
"-hstring <string> Hypothesis string\n"+
"-format <string>\n"+
" Supported formats: strings, nisttool\n",
files, al);
if (al.present("-o"))
outfile = al.val("-o");
else
outfile = "-";
if (al.present("-format"))
format = al.val("-format");
else
format = "strings";
if (format == "strings")
string_align(al);
else if (format == "nisttool")
nisttool_align(al);
else
cout << "Unknown or unhandled format: " << format << endl;
return 0;
}
bool dp_match(const EST_Relation &lexical,
const EST_Relation &surface,
EST_Relation &match,
float ins, float del, float sub);
static void string_align(EST_Option &al)
{
EST_String refStr = al.val("-rstring");
EST_String hypStr = al.val("-hstring");
EST_Utterance u;
int total,ins,del,sub,correct;
load_sentence(u,"ref",refStr);
load_sentence(u,"hypo",hypStr);
align(u,"ref","hypo","align");
align_score(u,"ref","hypo","align",total,ins,del,sub,correct);
fprintf(stdout,"words %d\n",total);
fprintf(stdout,"insertions %d\n",ins);
fprintf(stdout,"deletions %d\n",del);
fprintf(stdout,"substitutions %d\n",sub);
fprintf(stdout,"correct %d\n",correct);
fprintf(stdout,"WER %f\n",(100.0 * (float)(ins+del+sub))/total);
}
static void nisttool_align(EST_Option &al)
{
// Using the format used by the NIST tools for alignment
// Sentence per line with parenthesized id at end
EST_String reffile = al.val("-rfile");
EST_String hypofile = al.val("-hfile");
EST_TokenStream rts,hts;
EST_Item *r, *h;
static EST_Regex id("^(.*)$");
int sents=0;
int total,ins,del,sub,correct;
int s_total,s_ins,s_del,s_sub,s_correct;
rts.open(reffile);
hts.open(hypofile);
s_total=s_ins=s_del=s_sub=s_correct=0;
while (!rts.eof())
{
EST_Utterance u;
load_sentence(u,"ref",rts);
load_sentence(u,"hypo",hts);
r = u.relation("ref")->rlast();
h = u.relation("hypo")->rlast();
if ((!r->name().matches(id)) ||
(r->name() != h->name()))
{
cerr << "Align: failed to match sentence " <<
sents << " at id " << r->name() << endl;
}
else
{
// Ids aren't counted as words
r->unref_all();
h->unref_all();
align(u,"ref","hypo","align");
// This doesn't give exactly the same as the NIST tools
// even though it should (actually I think its better)
// dp_match(*u.relation("ref"),
// *u.relation("hypo"),
// *u.create_relation("align"),
// 3,3,4);
align_score(u,"ref","hypo","align",
total,ins,del,sub,correct);
s_total += total;
s_ins += ins;
s_del += del;
s_sub += sub;
s_correct += correct;
}
sents++;
}
rts.close();
hts.close();
fprintf(stdout,"sentences %d\n",sents);
fprintf(stdout,"words %d\n",s_total);
fprintf(stdout,"insertions %d\n",s_ins);
fprintf(stdout,"deletions %d\n",s_del);
fprintf(stdout,"substitutions %d\n",s_sub);
fprintf(stdout,"correct %d\n",s_correct);
fprintf(stdout,"WER %f\n",(100.0 * (float)(s_ins+s_del+s_sub))/s_total);
}
static void load_sentence(EST_Utterance &u,
const EST_String &relname,
EST_TokenStream &ts)
{
EST_Relation *r = u.create_relation(relname);
do
{
EST_Item *i = r->append();
i->set_name(ts.get());
}
while ((!ts.eoln()) && (!ts.eof()));
}
static void load_sentence(EST_Utterance &u,
const EST_String &relname,
EST_String &relval)
{
EST_Relation *r = u.create_relation(relname);
EST_StrList strlist;
StringtoStrList(relval, strlist, " ");
EST_StrList::Entries iter;
for (iter.begin(strlist); iter; ++iter)
{
EST_Item *i = r->append();
i->set_name(*iter);
}
}
static void align_score(EST_Utterance &u, const EST_String &refrel,
const EST_String &hyporel,
const EST_String &alignrel,
int &total,int &ins,int &del,int &sub,int &correct)
{
// Score alignment
EST_Item *ri,*hi;
total=ins=del=correct=sub=0;
for (ri=u.relation(refrel)->first(),
hi=u.relation(hyporel)->first();
ri;
ri=inext(ri),hi=inext(hi))
{
for ( ; (as(hi,alignrel) == 0) && hi ; hi=inext(hi))
{
fprintf(stdout,"inserted: %s\n",(const char *)hi->name());
ins++;
}
for ( ; (daughter1(ri,alignrel) == 0) && ri; ri=inext(ri))
{
fprintf(stdout,"deleted: %s\n",(const char *)ri->name());
del++;
}
if (!ri)
break;
if (name_distance(ri,daughter1(ri,alignrel)) == 0)
{
fprintf(stdout,"correct: %s\n",(const char *)ri->name());
correct++;
}
else
{
fprintf(stdout,"substituted: %s\n",(const char *)ri->name());
sub++;
}
}
// For trailing hypothesized (or ref is nil)
for ( ; hi ; hi=inext(hi))
{
fprintf(stdout,"inserted: %s\n",(const char *)hi->name());
ins++;
}
total = u.relation(refrel)->length();
// fprintf(stdout,"total %d ins %d del %d subs %d correct %d\n",
// total, ins, del, sub, correct);
}
static int name_distance(EST_Item *r,EST_Item *h)
{
EST_String rname = r->name();
EST_String hname = h->name();
if ((rname == hname) ||
(downcase(rname) == downcase(hname)))
return 0;
else
return 1;
}
void align(EST_Utterance &utt,
const EST_String &refrel,
const EST_String &hyporel,
const EST_String &alignrel)
{
// Align refrel to hyporel by alignrel
int r_size = utt.relation(refrel)->length();
int h_size = utt.relation(hyporel)->length();
EST_Item *ri = utt.relation(refrel)->first();
EST_Item *hi = utt.relation(hyporel)->first();
int i,j;
int insdel_cost = 3;
int subs_cost = 4;
float to_insert,to_del,to_subs;
float cost;
EST_Relation *ar = utt.create_relation(alignrel);
EST_FMatrix dpt(r_size+1,h_size+1);
EST_IMatrix dpp(r_size+1,h_size+1);
// Initialise first row and column
dpt(0,0) = subs_cost * name_distance(ri,hi);
dpp(0,0) = 0;
for (i=1; i<r_size+1; i++)
{
dpt(i,0) = insdel_cost + dpt(i-1,0);
dpp(i,0) = -1; // deletion
}
for (j=1; j < h_size+1; j++)
{
dpt(0,j) = insdel_cost + dpt(0,j-1);
dpp(0,j) = 1; // insertion
}
ri = utt.relation(refrel)->first();
for (i=1; ri; ri=inext(ri),i++)
{
ar->append(ri); // for use later
hi = utt.relation(hyporel)->first();
for (j=1; hi; hi=inext(hi),j++)
{
cost = name_distance(ri,hi);
to_insert = insdel_cost + dpt(i,j-1);
to_del = insdel_cost + dpt(i-1,j);
to_subs = (cost * subs_cost) + dpt(i-1,j-1);
if (to_insert < to_del)
{
if (to_insert < to_subs)
{
dpt(i,j) = to_insert;
dpp(i,j) = 1;
}
else
{
dpt(i,j) = to_subs;
dpp(i,j) = 0;
}
}
else
{
if (to_del < to_subs)
{
dpt(i,j) = to_del;
dpp(i,j) = -1;
}
else
{
dpt(i,j) = to_subs;
dpp(i,j) = 0;
}
}
}
}
// for (i=1,ri=utt.relation(refrel)->first(); i < r_size+1; i++,ri=inext(ri))
// {
// fprintf(stdout,"%10s ",(const char *)ri->name());
// for (j=1,hi=utt.relation(hyporel)->first(); j<h_size+1; j++,hi=inext(hi))
// fprintf(stdout,"%3d/%2d ",(int)dpt(i,j),dpp(i,j));
// fprintf(stdout,"\n");
// }
for (i=r_size,j=h_size,
ri=utt.relation(refrel)->rlast(),
hi=utt.relation(hyporel)->rlast();
ri; i--,ri=iprev(ri))
{
while (dpp(i,j) == 1)
{
j--;
// fprintf(stdout,"skipping hi %s\n",
// (const char *)hi->name());
hi=iprev(hi);
}
if (dpp(i,j) == 0)
{
// fprintf(stdout,"linking %s %s\n",
// (const char *)ri->name(),
// (const char *)hi->name());
append_daughter(ri,alignrel,hi);
j--;
hi=iprev(hi);
}
// else
// fprintf(stdout,"skipping ri %s\n",
// (const char *)ri->name());
}
}
EST_FMatrix
Definition EST_FMatrix.h:56
EST_IMatrix
Definition EST_IMatrix.h:50
EST_Item
Definition EST_Item.h:83
EST_Option
Definition EST_Option.h:50
EST_Regex
Definition EST_Regex.h:55
EST_Relation
Definition EST_Relation.h:68
EST_Relation::length
int length() const
Definition EST_Relation.cc:137
EST_String
Definition EST_String.h:70
EST_String::matches
int matches(const char *e, int pos=0) const
Exactly match this string?
Definition EST_String.cc:652
EST_TIterator::begin
void begin(const Container &over)
Set the iterator ready to run over this container.
Definition EST_TIterator.h:115
EST_TKVL::val
const V & val(const K &rkey, bool m=0) const
return value according to key (const)
Definition EST_TKVL.cc:145
EST_TKVL::present
const int present(const K &rkey) const
Returns true if key is present.
Definition EST_TKVL.cc:222
EST_TokenStream
Definition EST_Token.h:235
EST_TokenStream::eof
int eof()
end of file
Definition EST_Token.h:356
EST_TokenStream::eoln
int eoln()
end of line
Definition EST_Token.cc:818
EST_TokenStream::close
void close(void)
Close stream.
Definition EST_Token.cc:406
EST_TokenStream::open
int open(const EST_String &filename)
open a \Ref{EST_TokenStream} for a file.
Definition EST_Token.cc:200
EST_TokenStream::get
EST_TokenStream & get(EST_Token &t)
get next token in stream
Definition EST_Token.cc:486
EST_Utterance
Definition EST_Utterance.h:54
EST_Utterance::relation
EST_Relation * relation(const char *name, int err_on_not_found=1) const
get relation by name
Definition EST_Utterance.cc:160
EST_Utterance::create_relation
EST_Relation * create_relation(const EST_String &relname)
create a new relation called <parameter>n</parameter>.
Definition EST_Utterance.cc:98