Loading...
Searching...
No Matches
kkcompile.cc
/*************************************************************************/
/* */
/* Centre for Speech Technology Research */
/* University of Edinburgh, UK */
/* Copyright (c) 1996-1998 */
/* 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 : December 1997 */
/*-----------------------------------------------------------------------*/
/* */
/* A Koskenniemi/Kay/Kaplan rule compiler to WFST using the techniques */
/* Ritchie et al.'s "Computational Morphology" (but followed through to */
/* make real WFSTs). */
/* */
/*=======================================================================*/
#include <iostream>
#include "EST_WFST.h"
#include "EST_cutils.h"
ostream &operator << (ostream &s, const EST_WFST &w)
{
(void)w;
return s << "<<EST_WFST>>";
}
Declare_TList(EST_WFST)
#if defined(INSTANTIATE_TEMPLATES)
#include "../base_class/EST_TList.cc"
Instantiate_TList(EST_WFST)
#endif
static LISP expand_fp(const EST_String p,LISP fp);
static LISP find_feasible_pairs(LISP rules);
static LISP all_but(LISP rulepair,LISP fp);
static LISP expand_sets(LISP sets,LISP fp);
static LISP inline_sets(LISP l, LISP sets);
static void full_kkcompile(LISP inalpha,LISP outalpha,
LISP fp, LISP rules, LISP sets,
EST_WFST &all_wfst);
void kkcompile(LISP ruleset, EST_WFST &all_wfst)
{
// Build a transducer from given kkrule (Kay/Kaplan/Koskenniemi)
// Rules are of the form LeftContext Map RightContext
// The WFST is recognizing all string except the rulepair unless
// its in the proper context.
LISP fp; // feasible pairs, those pairs with rules (rather than IxO)
LISP inalpha = siod_nth(1,siod_assoc_str("Alphabets",cdr(cdr(ruleset))));
LISP outalpha = siod_nth(2,siod_assoc_str("Alphabets",cdr(cdr(ruleset))));
LISP sets = cdr(siod_assoc_str("Sets",ruleset));
LISP rules = cdr(siod_assoc_str("Rules",ruleset));
fp = find_feasible_pairs(rules);
sets = expand_sets(sets,fp);
full_kkcompile(inalpha,outalpha,fp,rules,sets,all_wfst);
}
static void full_kkcompile(LISP inalpha,LISP outalpha,
LISP fp, LISP rules, LISP sets,
EST_WFST &all_wfst)
{
wfst_list rulelist;
LISP r;
for (r=rules; r != NIL; r=cdr(r))
{
EST_WFST r_wfst,base_wfst,det_wfst;
rulelist.append(r_wfst);
EST_WFST &rr_wfst = rulelist.last(); // to avoid copying the filled one
cout << "Rule: " << siod_llength(rules)-siod_llength(r) << endl;
pprint(car(r));
base_wfst.kkrule_compile(inalpha,outalpha,fp,car(r),sets);
cout << " base " << base_wfst.summary() << endl;
det_wfst.determinize(base_wfst);
cout << " determinized " << det_wfst.summary() << endl;
rr_wfst.minimize(det_wfst);
cout << " minimized " << rr_wfst.summary() << endl;
}
cout << "WFST: intersecting " << rulelist.length() << " rules" << endl;
EST_Litem *p,*nnp;
int i;
for (i=0,p=rulelist.head(); p->next() != 0; p=nnp)
{
EST_WFST r_wfst,base_wfst,det_wfst;
EST_WFST mmm;
rulelist.append(r_wfst);
EST_WFST &rr_wfst = rulelist.last(); // to avoid copying the filled one
cout << "intersecting " << i << " and " << i+1 << " " <<
rulelist.length()-2 << " left" << endl;
cout << " " << rulelist(p).summary() << " and " << endl;
cout << " " << rulelist(p->next()).summary() << " becomes " << endl;
mmm.intersection(rulelist(p),rulelist(p->next()));
cout << " " << mmm.summary() << " minimizes to " << endl;
rr_wfst.minimize(mmm);
cout << " " << rr_wfst.summary() << endl;
nnp=p->next()->next();
i+=2;
rulelist.remove(p->next());
rulelist.remove(p);
}
all_wfst = rulelist.first();
}
static LISP expand_sets(LISP sets,LISP fp)
{
// Expand sets into regexes that represent them. Single
// char values are converted to disjunctions of feasible pairs
// that have the same surface character
LISP s,es=NIL,e,ne;
for (s=sets; s != NIL; s=cdr(s))
{
for (ne=NIL,e=cdr(car(s)); e != NIL; e=cdr(e))
{
EST_String ss = get_c_string(car(e));
if (ss.contains("/"))
ne = cons(car(e),ne);
else
ne = append(expand_fp(ss,fp),ne);
}
if (ne == NIL)
{
cerr << "WFST: kkcompile: set " << get_c_string(car(car(s))) <<
" has no feasible pairs" << endl;
}
else if (siod_llength(ne) == 1)
es = cons(cons(car(car(s)),ne),es);
else
es = cons(cons(car(car(s)),
cons(cons(rintern("or"),reverse(ne)),
NIL)),es);
}
return reverse(es);
}
static LISP expand_fp(const EST_String p,LISP fp)
{
// Find all fp's that have this p as their surface char
LISP m=NIL,f;
EST_Regex rg(EST_String("^")+p+"/.*");
for (f=fp; f != NIL; f=cdr(f))
{
EST_String ss = get_c_string(car(f));
if ((p == ss) || (ss.matches(rg)))
m = cons(car(f),m);
}
return m;
}
static LISP find_feasible_pairs(LISP rules)
{
// Find the set of pairs that have rules associated with them
// This effectively defines the transducer alphabet.
LISP fp = NIL;
LISP r;
for (r=rules; r != NIL; r=cdr(r))
{
if (siod_member_str(get_c_string(siod_nth(0,car(r))),fp) == NIL)
fp = cons(siod_nth(0,car(r)),fp);
}
return fp;
}
static int surface_coercion(LISP rt)
{
return (streq("<=",get_c_string(rt)));
}
static int context_restriction(LISP rt)
{
return (streq("=>",get_c_string(rt)));
}
static int composite(LISP rt)
{
return (streq("<=>",get_c_string(rt)));
}
static LISP inline_sets(LISP l, LISP sets)
{
// Replace any set name with the regex equivalent
LISP s;
if (l == NIL)
return NIL;
else if (consp(l))
return cons(inline_sets(car(l),sets),inline_sets(cdr(l),sets));
else if ((s=siod_assoc_str(get_c_string(l),sets)) != NIL)
return car(cdr(s));
else
return l;
}
void EST_WFST::kkrule_compile(LISP inalpha, LISP outalpha, LISP fp,
LISP rule,LISP sets)
{
// Build a WFST to transduce this particular rule
// Accepts any other combination of feasible pairs too
LISP leftcontext = inline_sets(siod_nth(2,rule),sets);
LISP rulepair = siod_nth(0,rule);
LISP ruletype = siod_nth(1,rule);
LISP rightcontext = inline_sets(siod_nth(4,rule),sets);
LISP p;
int i;
int end_LC,end_RP,end_NOTRP,end_RC,err_state;
// Initialize alphabets
init(inalpha,outalpha); // should be passed as discretes
p_start_state = add_state(wfst_final); // empty WFST
// Add transitions for all pairs except rulepair
for (p=fp; p != NIL; p=cdr(p))
if ((!equal(rulepair,car(p))) ||
(surface_coercion(ruletype)))
build_wfst(p_start_state,p_start_state,car(p));
// build for LC
if (leftcontext)
{
end_LC = add_state(wfst_final);
build_wfst(p_start_state,end_LC,leftcontext);
// for all states in LC mark final & add epsilon to p_start_state
for (i=end_LC; i < p_num_states; i++)
{
build_wfst(i,p_start_state,epsilon_label());
p_states[i]->set_type(wfst_final);
}
}
else // no LC
end_LC = p_start_state;
// build for RP and RC from end_LC
if (composite(ruletype) || context_restriction(ruletype))
{
if (rightcontext)
{
end_RP = add_state(wfst_nonfinal);
build_wfst(end_LC,end_RP,rulepair);
// build for RC from end map to p_start_state
build_wfst(end_RP,p_start_state,rightcontext);
err_state = add_state(wfst_error);
for (i=end_RP; i < err_state; i++)
{ // for everything other that the correct path go to err_state
// without this explicit error state the epsilon to start
// allows almost everything
if (transition(i,get_c_string(epsilon_label()))
!= WFST_ERROR_STATE)
break; // not a state require extra transitions
for (p=fp; p != NIL; p=cdr(p))
if (transition(i,get_c_string(car(p))) == WFST_ERROR_STATE)
build_wfst(i,err_state,car(p));
build_wfst(i,p_start_state,epsilon_label());
p_states[i]->set_type(wfst_licence);
}
}
else // no RC, so end back at start
build_wfst(end_LC,p_start_state,rulepair);
}
// Build for notRP and RC from end_LC
if (composite(ruletype) || surface_coercion(ruletype))
{
LISP abrp = all_but(rulepair,fp);
if (abrp)
{
if (rightcontext)
{
end_RC = add_state(wfst_error);
end_NOTRP = add_state(wfst_nonfinal);
build_wfst(end_LC,end_NOTRP,abrp);
// build for RC from end RP to error state
build_wfst(end_NOTRP,end_RC,rightcontext);
// for all states in RC except final one mark final & add
// epsilon to p_start_state
for (i=end_NOTRP; i < p_num_states; i++)
{
build_wfst(i,p_start_state,epsilon_label());
p_states[i]->set_type(wfst_final);
}
}
else // no RC,
{
end_RC = add_state(wfst_error);
build_wfst(end_LC,end_RC,abrp);
}
}
}
}
static LISP all_but(LISP rulepair,LISP fp)
{
// Returns pairs that have the same surface symbol as rulepair
// but different lexical symbol
LISP r,notrp=NIL;
EST_String s,l,p,sr,lr,rr;
p = get_c_string(rulepair);
if (p.contains("/"))
{
s = p.before("/");
l = p.after("/");
}
else
{
s = p;
l = p;
}
for (r=fp; r != NIL; r = cdr(r))
{
rr = get_c_string(car(r));
if (rr.contains("/"))
{
sr = rr.before("/");
lr = rr.after("/");
}
else
{
sr = rr;
lr = rr;
}
if ((l != lr) && (s == sr))
notrp = cons(car(r),notrp);
}
if (siod_llength(notrp) > 1)
notrp = cons(strintern("or"),notrp);
return notrp;
}
void intersect(wfst_list &wl, EST_WFST &all)
{
// Intersect the wfst's in wl into all
all.intersection(wl);
}
EST_Regex
Definition EST_Regex.h:55
EST_String
Definition EST_String.h:70
EST_String::before
EST_String before(int pos, int len=0) const
Part before position.
Definition EST_String.h:286
EST_String::contains
int contains(const char *s, int pos=-1) const
Does it contain this substring?
Definition EST_String.h:375
EST_String::after
EST_String after(int pos, int len=1) const
Part after pos+len.
Definition EST_String.h:318
EST_String::matches
int matches(const char *e, int pos=0) const
Exactly match this string?
Definition EST_String.cc:652
EST_TList::last
const T & last() const
return const reference to last item in list
Definition EST_TList.h:149
EST_TList::append
void append(const T &item)
add item onto end of list
Definition EST_TList.h:191
EST_TList::remove
EST_Litem * remove(EST_Litem *ptr)
Definition EST_TList.h:175
EST_TList::first
const T & first() const
return const reference to first item in list
Definition EST_TList.h:146
EST_WFST
Definition EST_WFST.h:150
EST_WFST::add_state
int add_state(enum wfst_state_type state_type)
Add a new state, returns new name.
Definition EST_WFST.cc:652
EST_WFST::init
void init(int init_num_states=10)
Clear with (estimation of number of states required).
Definition EST_WFST.cc:145
EST_WFST::build_wfst
void build_wfst(int start, int end, LISP regex)
Basic regex constructor.
Definition wfst_regex.cc:140
EST_WFST::epsilon_label
LISP epsilon_label() const
LISP for on epsilon symbols.
Definition EST_WFST.h:216
EST_WFST::minimize
void minimize(const EST_WFST &a)
Build minimized form of a.
Definition wfst_ops.cc:484
EST_WFST::intersection
void intersection(EST_TList< EST_WFST > &wl)
Definition wfst_ops.cc:356
EST_WFST::determinize
void determinize(const EST_WFST &a)
Build determinized form of a.
Definition wfst_ops.cc:164
EST_WFST::transition
int transition(int state, int in, int out) const
Find (first) new state given in and out symbols.
Definition EST_WFST.cc:260