Loading...
Searching...
No Matches
EST_WFST.h
/*************************************************************************/
/* */
/* Centre for Speech Technology Research */
/* University of Edinburgh, UK */
/* Copyright (c) 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 : November 1997 */
/*-----------------------------------------------------------------------*/
/* */
/* Weighted Finite State Transducers */
/* */
/*=======================================================================*/
#ifndef __EST_WFST_H__
#define __EST_WFST_H__
#include "EST_simplestats.h"
#include "EST_rw_status.h"
#include "EST_Option.h"
#include "EST_TList.h"
#include "EST_TVector.h"
#include "EST_THash.h"
#include "siod.h"
#define wfst_error_msg(WMESS) (cerr << WMESS << endl,siod_error())
#define WFST_ERROR_STATE -1
class EST_WFST_State;
class EST_WFST;
/** an internal class for \Ref{EST_WFST} for representing transitions
in an WFST
*/
class EST_WFST_Transition {
private:
float p_weight;
int p_state;
int p_in_symbol;
int p_out_symbol;
public:
EST_WFST_Transition();
EST_WFST_Transition(const EST_WFST_Transition &t)
{ p_weight=t.p_weight; p_state=t.p_state;
p_in_symbol = t.p_in_symbol; p_out_symbol=t.p_out_symbol; }
EST_WFST_Transition(float w, int s, int i, int o)
{ p_weight=w; p_state=s; p_in_symbol=i; p_out_symbol=o;}
~EST_WFST_Transition() { };
float weight() const { return p_weight; }
int state() const { return p_state; }
int in_symbol() const { return p_in_symbol; }
int out_symbol() const { return p_out_symbol; }
void set_weight(float f) { p_weight = f; }
void set_state(int s) { p_state = s; }
};
typedef EST_TList<EST_WFST_Transition *> wfst_translist;
enum wfst_state_type {wfst_final, wfst_nonfinal, wfst_error, wfst_licence};
/** I'd like to use the enums but I need to binary read/write them **/
/** I don't believe that's portable so we need to have ints for these **/
#define WFST_FINAL 0
#define WFST_NONFINAL 1
#define WFST_ERROR 2
#define WFST_LICENCE 3
/** an internal class for \Ref{EST_WFST} used to represent a
state in a WFST
*/
class EST_WFST_State {
private:
int p_name;
enum wfst_state_type p_type;
int p_tag; // for marking in traversing
public:
wfst_translist transitions;
EST_WFST_State(int name);
EST_WFST_State(const EST_WFST_State &state);
~EST_WFST_State();
EST_WFST_Transition *add_transition(float w,
int end,
int in,
int out);
int name() const { return p_name; }
int num_transitions() const { return transitions.length(); }
enum wfst_state_type type() const { return p_type; }
void set_type(wfst_state_type t) { p_type = t; }
void set_tag(int v) { p_tag = v;}
int tag() const { return p_tag;}
};
typedef EST_TVector<EST_WFST_State *> wfst_state_vector;
typedef EST_TStringHash<int> EST_WFST_MultiStateIndex;
enum wfst_mstate_type {wfst_ms_set, wfst_ms_list};
/** an internal class to \Ref{EST_WFST} used in holding multi-states
when determinizing and find the intersections of other WFSTs.
*/
class EST_WFST_MultiState : public EST_IList {
private:
int p_name;
float p_weight;
enum wfst_mstate_type p_type;
public:
EST_WFST_MultiState() : EST_IList()
{ p_name = -1; p_weight = 0.0; p_type = wfst_ms_set; }
EST_WFST_MultiState(enum wfst_mstate_type ty) : EST_IList()
{ p_name = -1; p_weight = 0.0; p_type = ty; }
int name() const { return p_name; }
void set_name(int i) { p_name = i; }
float weight() const { return p_weight; }
void set_weight(float w) { p_weight = w; }
void set_type(enum wfst_mstate_type s) { p_type = s; }
enum wfst_mstate_type type() const { return p_type; }
void add(int i);
};
int multistate_index(EST_WFST_MultiStateIndex &i,EST_WFST_MultiState *ms);
/** a call representing a weighted finite-state transducer
*/
class EST_WFST {
private:
EST_Discrete p_in_symbols;
EST_Discrete p_out_symbols;
int p_start_state;
int current_tag;
int p_num_states;
int p_cumulate;
wfst_state_vector p_states;
int operator_and(LISP l);
int operator_or(LISP l);
int operator_star(LISP l);
int operator_plus(LISP l);
int operator_optional(LISP l);
int operator_not(LISP l);
int terminal(LISP l);
EST_WFST_State *copy_and_map_states(const EST_IVector &state_map,
const EST_WFST_State *s,
const EST_WFST &b) const;
void extend_alphabets(const EST_WFST &b);
int deterministiconstartstates(const EST_WFST &a, const EST_WFST &b) const;
EST_read_status load_transitions_from_lisp(int s, LISP trans);
void more_states(int new_max);
int can_reach_final(int state);
static int traverse_tag;
public:
/**@name Constructor and initialisation functions */
//@{
/// ?
EST_WFST();
/// ?
EST_WFST(const EST_WFST &wfst) { p_num_states = 0; copy(wfst); }
~EST_WFST();
//@}
/**@name Reseting functions */
//@{
/// Clear with (estimation of number of states required)
void init(int init_num_states=10);
/// clear an initialise with given input and out alphabets
void init(LISP in, LISP out);
/// Copy from existing wfst
void copy(const EST_WFST &wfst);
/// clear removing existing states if any
void clear();
//@}
/**@name General utility functions */
//@{
int num_states() const { return p_num_states; }
int start_state() const { return p_start_state; }
/// Map input symbol to input alphabet index
int in_symbol(const EST_String &s) const
{ return p_in_symbols.name(s); }
/// Map input alphabet index to input symbol
const EST_String &in_symbol(int i) const
{ return p_in_symbols.name(i); }
/// Map output symbol to output alphabet index
int out_symbol(const EST_String &s) const
{ return p_out_symbols.name(s); }
/// Map output alphabet index to output symbol
const EST_String &out_symbol(int i) const
{ return p_out_symbols.name(i); }
/// LISP for on epsilon symbols
LISP epsilon_label() const { return rintern("__epsilon__"); }
/// Internal index for input epsilon
int in_epsilon() const { return p_in_symbols.name("__epsilon__"); }
/// Internal index for output epsilon
int out_epsilon() const { return p_out_symbols.name("__epsilon__"); }
/// Return internal state information
const EST_WFST_State *state(int i) const { return p_states(i); }
/// Return internal state information (non-const)
EST_WFST_State *state_non_const(int i) { return p_states(i); }
/// True if state {\tt i} is final
int final(int i) const
{ return ((i != WFST_ERROR_STATE) && (state(i)->type() == wfst_final));}
/// Accessing the input alphabet
const EST_Discrete &in_symbols() const { return p_in_symbols; }
/// Accessing the output alphabet
const EST_Discrete &out_symbols() const { return p_out_symbols; }
//@}
/**@name file i/o */
//@{
/// ?
EST_write_status save(const EST_String &filename,
const EST_String type = "ascii");
EST_write_status save_binary(FILE *fd);
/// ?
EST_read_status load(const EST_String &filename);
EST_read_status load_binary(FILE *fd,
EST_Option &hinfo,
int num_states,
int swap);
//@}
/**@name transduction functions */
//@{
/// Find (first) new state given in and out symbols
int transition(int state,int in, int out) const;
int transition(int state,int in, int out, float &prob) const;
/// Find (first) transition given in and out symbols
EST_WFST_Transition *find_transition(int state,int in, int out) const;
/// Find (first) new state given in and out strings
int transition(int state,const EST_String &in,const EST_String &out) const;
/// Find (first) new state given in/out string
int transition(int state,const EST_String &inout) const;
/// Transduce in to out from state
int transduce(int state,int in,int &out) const;
/// Transduce in to out (strings) from state
int transduce(int state,const EST_String &in,EST_String &out) const;
/// Transduce in to list of transitions
void transduce(int state,int in,wfst_translist &out) const;
/// Find all possible transitions for given state/input/output
void transition_all(int state,int in, int out,
EST_WFST_MultiState *ms) const;
//@}
/**@name Cumulation functions for adding collective probabilities
for transitions from data */
//@{
/// Cumulation condition
int cumulate() const {return p_cumulate;}
/// Clear and start cumulation
void start_cumulate();
/// Stop cumulation and calculate probabilities on transitions
void stop_cumulate();
//@}
/**@name WFST construction functions from external representations **/
//@{
/// Add a new state, returns new name
int add_state(enum wfst_state_type state_type);
/// Given a multi-state return type (final, ok, error)
enum wfst_state_type ms_type(EST_WFST_MultiState *ms) const;
/// Basic regex constructor
void build_wfst(int start, int end,LISP regex);
/// Basic conjunction constructor
void build_and_transition(int start, int end, LISP conjunctions);
/// Basic disjunction constructor
void build_or_transition(int start, int end, LISP disjunctions);
// from standard REGEX
void build_from_regex(LISP inalpha, LISP outalpha, LISP regex);
// Kay/Kaplan/Koskenniemi rule compile
void kkrule_compile(LISP inalpha, LISP outalpha, LISP fp,
LISP rule, LISP sets);
// Build from regular (or pseudo-CF) grammar
void build_from_rg(LISP inalpha, LISP outalpha,
LISP distinguished, LISP rewrites,
LISP sets, LISP terms,
int max_depth);
// Build simple tree lexicon
void build_tree_lex(LISP inalpha, LISP outalpha,
LISP wlist);
//@}
/**@name Basic WFST operators */
//@{
/// Build determinized form of a
void determinize(const EST_WFST &a);
/// Build minimized form of a
void minimize(const EST_WFST &a);
/// Build complement of a
void complement(const EST_WFST &a);
/** Build intersection of all WFSTs in given list. The new WFST
recognizes the only the strings that are recognized by all WFSTs
in the given list */
void intersection(EST_TList<EST_WFST> &wl);
/** Build intersection of WFSTs a and b The new WFST
recognizes the only the strings that are recognized by both a
and b list */
void intersection(const EST_WFST &a, const EST_WFST &b);
/** Build union of all WFSTs in given list. The new WFST
recognizes the only the strings that are recognized by at least
one WFSTs in the given list */
void uunion(EST_TList<EST_WFST> &wl);
/** Build union of WFSTs a and b. The new WFST
recognizes the only the strings that are recognized by either
a or b */
void uunion(const EST_WFST &a, const EST_WFST &b);
/** Build new WFST by composition of a and b. Outputs of a are
fed to b, given a new WFSTs which has a's input language and b's
output set. a's output and b's input alphabets must be the same */
void compose(const EST_WFST &a,const EST_WFST &b);
/** Build WFST that accepts only strings in a that aren't also accepted
by strings in b. */
void difference(const EST_WFST &a,const EST_WFST &b);
/** Build WFST that accepts a language that consists of any string in
a followed by any string in b **/
void concat(const EST_WFST &a,const EST_WFST &b);
//@}
/**@name construction support functions */
//@{
/// True if WFST is deterministic
int deterministic() const;
/// Transduce a multi-state given n and out
EST_WFST_MultiState *apply_multistate(const EST_WFST &wfst,
EST_WFST_MultiState *ms,
int in, int out) const;
/// Extend multi-state with epsilon reachable states
void add_epsilon_reachable(EST_WFST_MultiState *ms) const;
/// Remove error states from the WFST.
void remove_error_states(const EST_WFST &a);
EST_String summary() const;
/// ?
EST_WFST & operator = (const EST_WFST &a) { copy(a); return *this; }
};
typedef EST_TList<EST_WFST> wfst_list;
// The basic operations on WFST
void minimize(EST_WFST &a,EST_WFST &b);
void determinize(EST_WFST &a,EST_WFST &b);
void concat(EST_WFST &a,EST_WFST &b,EST_WFST &c);
void compose(EST_WFST &a,EST_WFST &b,EST_WFST &c);
void intersect(wfst_list &wl,EST_WFST &wfst);
void complement(EST_WFST &a,EST_WFST &b);
void difference(EST_WFST &a,EST_WFST &b,EST_WFST &c);
void concatenate(EST_WFST &a,EST_WFST &b,EST_WFST &c);
// Compile a set of KK rules
void kkcompile(LISP ruleset, EST_WFST &all_wfst);
// Compile a set of LTS rules
void ltscompile(LISP lts_rules, EST_WFST &all_wfst);
// Compile a regular grammar
void rgcompile(LISP rg, EST_WFST &all_wfst);
// Compile a tree lexicon
void tlcompile(LISP rg, EST_WFST &all_wfst);
// Transduction and recognition functions
int transduce(const EST_WFST &wfst,const EST_StrList &in,EST_StrList &out);
int transduce(const EST_WFST &wfst,const EST_IList &in,EST_IList &out);
int recognize(const EST_WFST &wfst,const EST_StrList &in,int quiet);
int recognize(const EST_WFST &wfst,const EST_IList &in,
const EST_IList &out,int quite);
int recognize_for_perplexity(const EST_WFST &wfst,
const EST_StrList &in,
int quiet,
float &count,
float &sumlogp);
int recognize_for_perplexity(const EST_WFST &wfst,
const EST_IList &in,
const EST_IList &out,
int quiet,
float &count,
float &sumlogp);
VAL_REGISTER_CLASS_DCLS(wfst,EST_WFST)
#endif
EST_Discrete
Definition EST_simplestats.h:61
EST_Option
Definition EST_Option.h:50
EST_String
Definition EST_String.h:70
EST_TList
Definition EST_TList.h:109
EST_TStringHash
Definition EST_THash.h:281
EST_TVector
Definition EST_TVector.h:148
EST_WFST_MultiState
Definition EST_WFST.h:127
EST_WFST_State
Definition EST_WFST.h:96
EST_WFST_Transition
Definition EST_WFST.h:60
EST_WFST
Definition EST_WFST.h:150
EST_WFST::difference
void difference(const EST_WFST &a, const EST_WFST &b)
Definition wfst_ops.cc:898
EST_WFST::start_cumulate
void start_cumulate()
Clear and start cumulation.
Definition EST_WFST.cc:670
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::out_symbol
const EST_String & out_symbol(int i) const
Map output alphabet index to output symbol.
Definition EST_WFST.h:213
EST_WFST::state_non_const
EST_WFST_State * state_non_const(int i)
Return internal state information (non-const).
Definition EST_WFST.h:224
EST_WFST::operator=
EST_WFST & operator=(const EST_WFST &a)
?
Definition EST_WFST.h:364
EST_WFST::in_symbol
const EST_String & in_symbol(int i) const
Map input alphabet index to input symbol.
Definition EST_WFST.h:207
EST_WFST::uunion
void uunion(EST_TList< EST_WFST > &wl)
EST_WFST::add_epsilon_reachable
void add_epsilon_reachable(EST_WFST_MultiState *ms) const
Extend multi-state with epsilon reachable states.
Definition wfst_ops.cc:319
EST_WFST::EST_WFST
EST_WFST()
?
Definition EST_WFST.cc:126
EST_WFST::complement
void complement(const EST_WFST &a)
Build complement of a.
Definition wfst_ops.cc:646
EST_WFST::find_transition
EST_WFST_Transition * find_transition(int state, int in, int out) const
Find (first) transition given in and out symbols.
Definition EST_WFST.cc:267
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::clear
void clear()
clear removing existing states if any
Definition EST_WFST.cc:115
EST_WFST::transition_all
void transition_all(int state, int in, int out, EST_WFST_MultiState *ms) const
Find all possible transitions for given state/input/output.
Definition wfst_ops.cc:294
EST_WFST::compose
void compose(const EST_WFST &a, const EST_WFST &b)
Definition wfst_ops.cc:812
EST_WFST::apply_multistate
EST_WFST_MultiState * apply_multistate(const EST_WFST &wfst, EST_WFST_MultiState *ms, int in, int out) const
Transduce a multi-state given n and out.
Definition wfst_ops.cc:250
EST_WFST::out_epsilon
int out_epsilon() const
Internal index for output epsilon.
Definition EST_WFST.h:220
EST_WFST::in_symbol
int in_symbol(const EST_String &s) const
Map input symbol to input alphabet index.
Definition EST_WFST.h:204
EST_WFST::remove_error_states
void remove_error_states(const EST_WFST &a)
Remove error states from the WFST.
Definition wfst_ops.cc:917
EST_WFST::EST_WFST
EST_WFST(const EST_WFST &wfst)
?
Definition EST_WFST.h:183
EST_WFST::build_wfst
void build_wfst(int start, int end, LISP regex)
Basic regex constructor.
Definition wfst_regex.cc:140
EST_WFST::in_epsilon
int in_epsilon() const
Internal index for input epsilon.
Definition EST_WFST.h:218
EST_WFST::deterministic
int deterministic() const
True if WFST is deterministic.
Definition wfst_ops.cc:975
EST_WFST::copy
void copy(const EST_WFST &wfst)
Copy from existing wfst.
Definition EST_WFST.cc:132
EST_WFST::save
EST_write_status save(const EST_String &filename, const EST_String type="ascii")
?
Definition EST_WFST.cc:349
EST_WFST::cumulate
int cumulate() const
Cumulation condition.
Definition EST_WFST.h:277
EST_WFST::state
const EST_WFST_State * state(int i) const
Return internal state information.
Definition EST_WFST.h:222
EST_WFST::out_symbol
int out_symbol(const EST_String &s) const
Map output symbol to output alphabet index.
Definition EST_WFST.h:210
EST_WFST::epsilon_label
LISP epsilon_label() const
LISP for on epsilon symbols.
Definition EST_WFST.h:216
EST_WFST::out_symbols
const EST_Discrete & out_symbols() const
Accessing the output alphabet.
Definition EST_WFST.h:231
EST_WFST::stop_cumulate
void stop_cumulate()
Stop cumulation and calculate probabilities on transitions.
Definition EST_WFST.cc:685
EST_WFST::build_or_transition
void build_or_transition(int start, int end, LISP disjunctions)
Basic disjunction constructor.
Definition wfst_regex.cc:44
EST_WFST::minimize
void minimize(const EST_WFST &a)
Build minimized form of a.
Definition wfst_ops.cc:484
EST_WFST::transduce
int transduce(int state, int in, int &out) const
Transduce in to out from state.
Definition EST_WFST.cc:219
EST_WFST::ms_type
enum wfst_state_type ms_type(EST_WFST_MultiState *ms) const
Given a multi-state return type (final, ok, error).
Definition wfst_ops.cc:271
EST_WFST::concat
void concat(const EST_WFST &a, const EST_WFST &b)
Definition wfst_ops.cc:776
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::load
EST_read_status load(const EST_String &filename)
?
Definition EST_WFST.cc:508
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
EST_WFST::build_and_transition
void build_and_transition(int start, int end, LISP conjunctions)
Basic conjunction constructor.
Definition wfst_regex.cc:62
EST_WFST::in_symbols
const EST_Discrete & in_symbols() const
Accessing the input alphabet.
Definition EST_WFST.h:229