// compose.h
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//
// \file
// Class to compute the composition of two FSTs
#ifndef FST_LIB_COMPOSE_H__
#define FST_LIB_COMPOSE_H__
#include <algorithm>
#include <ext/hash_map>
using __gnu_cxx::hash_map;
#include "fst/lib/cache.h"
#include "fst/lib/test-properties.h"
namespace fst {
// Enumeration of uint64 bits used to represent the user-defined
// properties of FST composition (in the template parameter to
// ComposeFstOptions<T>). The bits stand for extensions of generic FST
// composition. ComposeFstOptions<> (all the bits unset) is the "plain"
// compose without any extra extensions.
enum ComposeTypes {
// RHO: flags dealing with a special "rest" symbol in the FSTs.
// NB: at most one of the bits COMPOSE_FST1_RHO, COMPOSE_FST2_RHO
// may be set.
COMPOSE_FST1_RHO = 1ULL<<0, // "Rest" symbol on the output side of fst1.
COMPOSE_FST2_RHO = 1ULL<<1, // "Rest" symbol on the input side of fst2.
COMPOSE_FST1_PHI = 1ULL<<2, // "Failure" symbol on the output
// side of fst1.
COMPOSE_FST2_PHI = 1ULL<<3, // "Failure" symbol on the input side
// of fst2.
COMPOSE_FST1_SIGMA = 1ULL<<4, // "Any" symbol on the output side of
// fst1.
COMPOSE_FST2_SIGMA = 1ULL<<5, // "Any" symbol on the input side of
// fst2.
// Optimization related bits.
COMPOSE_GENERIC = 1ULL<<32, // Disables optimizations, applies
// the generic version of the
// composition algorithm. This flag
// is used for internal testing
// only.
// -----------------------------------------------------------------
// Auxiliary enum values denoting specific combinations of
// bits. Internal use only.
COMPOSE_RHO = COMPOSE_FST1_RHO | COMPOSE_FST2_RHO,
COMPOSE_PHI = COMPOSE_FST1_PHI | COMPOSE_FST2_PHI,
COMPOSE_SIGMA = COMPOSE_FST1_SIGMA | COMPOSE_FST2_SIGMA,
COMPOSE_SPECIAL_SYMBOLS = COMPOSE_RHO | COMPOSE_PHI | COMPOSE_SIGMA,
// -----------------------------------------------------------------
// The following bits, denoting specific optimizations, are
// typically set *internally* by the composition algorithm.
COMPOSE_FST1_STRING = 1ULL<<33, // fst1 is a string
COMPOSE_FST2_STRING = 1ULL<<34, // fst2 is a string
COMPOSE_FST1_DET = 1ULL<<35, // fst1 is deterministic
COMPOSE_FST2_DET = 1ULL<<36, // fst2 is deterministic
COMPOSE_INTERNAL_MASK = 0xffffffff00000000ULL
};
template <uint64 T = 0ULL>
struct ComposeFstOptions : public CacheOptions {
explicit ComposeFstOptions(const CacheOptions &opts) : CacheOptions(opts) {}
ComposeFstOptions() { }
};
// Abstract base for the implementation of delayed ComposeFst. The
// concrete specializations are templated on the (uint64-valued)
// properties of the FSTs being composed.
template <class A>
class ComposeFstImplBase : public CacheImpl<A> {
public:
using FstImpl<A>::SetType;
using FstImpl<A>::SetProperties;
using FstImpl<A>::Properties;
using FstImpl<A>::SetInputSymbols;
using FstImpl<A>::SetOutputSymbols;
using CacheBaseImpl< CacheState<A> >::HasStart;
using CacheBaseImpl< CacheState<A> >::HasFinal;
using CacheBaseImpl< CacheState<A> >::HasArcs;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
typedef CacheState<A> State;
ComposeFstImplBase(const Fst<A> &fst1,
const Fst<A> &fst2,
const CacheOptions &opts)
:CacheImpl<A>(opts), fst1_(fst1.Copy()), fst2_(fst2.Copy()) {
SetType("compose");
uint64 props1 = fst1.Properties(kFstProperties, false);
uint64 props2 = fst2.Properties(kFstProperties, false);
SetProperties(ComposeProperties(props1, props2), kCopyProperties);
if (!CompatSymbols(fst2.InputSymbols(), fst1.OutputSymbols()))
LOG(FATAL) << "ComposeFst: output symbol table of 1st argument "
<< "does not match input symbol table of 2nd argument";
SetInputSymbols(fst1.InputSymbols());
SetOutputSymbols(fst2.OutputSymbols());
}
virtual ~ComposeFstImplBase() {
delete fst1_;
delete fst2_;
}
StateId Start() {
if (!HasStart()) {
StateId start = ComputeStart();
if (start != kNoStateId) {
SetStart(start);
}
}
return CacheImpl<A>::Start();
}
Weight Final(StateId s) {
if (!HasFinal(s)) {
Weight final = ComputeFinal(s);
SetFinal(s, final);
}
return CacheImpl<A>::Final(s);
}
virtual void Expand(StateId s) = 0;
size_t NumArcs(StateId s) {
if (!HasArcs(s))
Expand(s);
return CacheImpl<A>::NumArcs(s);
}
size_t NumInputEpsilons(StateId s) {
if (!HasArcs(s))
Expand(s);
return CacheImpl<A>::NumInputEpsilons(s);
}
size_t NumOutputEpsilons(StateId s) {
if (!HasArcs(s))
Expand(s);
return CacheImpl<A>::NumOutputEpsilons(s);
}
void InitArcIterator(StateId s, ArcIteratorData<A> *data) {
if (!HasArcs(s))
Expand(s);
CacheImpl<A>::InitArcIterator(s, data);
}
// Access to flags encoding compose options/optimizations etc. (for
// debugging).
virtual uint64 ComposeFlags() const = 0;
protected:
virtual StateId ComputeStart() = 0;
virtual Weight ComputeFinal(StateId s) = 0;
const Fst<A> *fst1_; // first input Fst
const Fst<A> *fst2_; // second input Fst
};
// The following class encapsulates implementation-dependent details
// of state tuple lookup, i.e. a bijective mapping from triples of two
// FST states and an epsilon filter state to the corresponding state
// IDs of the fst resulting from composition. The mapping must
// implement the [] operator in the style of STL associative
// containers (map, hash_map), i.e. table[x] must return a reference
// to the value associated with x. If x is an unassigned tuple, the
// operator must automatically associate x with value 0.
//
// NB: "table[x] == 0" for unassigned tuples x is required by the
// following off-by-one device used in the implementation of
// ComposeFstImpl. The value stored in the table is equal to tuple ID
// plus one, i.e. it is always a strictly positive number. Therefore,
// table[x] is equal to 0 if and only if x is an unassigned tuple (in
// which the algorithm assigns a new ID to x, and sets table[x] -
// stored in a reference - to "new ID + 1"). This form of lookup is
// more efficient than calling "find(x)" and "insert(make_pair(x, new
// ID))" if x is an unassigned tuple.
//
// The generic implementation is a wrapper around a hash_map.
template <class A, uint64 T>
class ComposeStateTable {
public:
typedef typename A::StateId StateId;
struct StateTuple {
StateTuple() {}
StateTuple(StateId s1, StateId s2, int f)
: state_id1(s1), state_id2(s2), filt(f) {}
StateId state_id1; // state Id on fst1
StateId state_id2; // state Id on fst2
int filt; // epsilon filter state
};
ComposeStateTable() {
StateTuple empty_tuple(kNoStateId, kNoStateId, 0);
}
// NB: if 'tuple' is not in 'table_', the pair (tuple, StateId()) is
// inserted into 'table_' (standard STL container semantics). Since
// StateId is a built-in type, the explicit default constructor call
// StateId() returns 0.
StateId &operator[](const StateTuple &tuple) {
return table_[tuple];
}
private:
// Comparison object for hashing StateTuple(s).
class StateTupleEqual {
public:
bool operator()(const StateTuple& x, const StateTuple& y) const {
return x.state_id1 == y.state_id1 &&
x.state_id2 == y.state_id2 &&
x.filt == y.filt;
}
};
static const int kPrime0 = 7853;
static const int kPrime1 = 7867;
// Hash function for StateTuple to Fst states.
class StateTupleKey {
public:
size_t operator()(const StateTuple& x) const {
return static_cast<size_t>(x.state_id1 +
x.state_id2 * kPrime0 +
x.filt * kPrime1);
}
};
// Lookup table mapping state tuples to state IDs.
typedef hash_map<StateTuple,
StateId,
StateTupleKey,
StateTupleEqual> StateTable;
// Actual table data.
StateTable table_;
DISALLOW_EVIL_CONSTRUCTORS(ComposeStateTable);
};
// State tuple lookup table for the composition of a string FST with a
// deterministic FST. The class maps state tuples to their unique IDs
// (i.e. states of the ComposeFst). Main optimization: due to the
// 1-to-1 correspondence between the states of the input string FST
// and those of the resulting (string) FST, a state tuple (s1, s2) is
// simply mapped to StateId s1. Hence, we use an STL vector as a
// lookup table. Template argument Fst1IsString specifies which FST is
// a string (this determines whether or not we index the lookup table
// by the first or by the second state).
template <class A, bool Fst1IsString>
class StringDetComposeStateTable {
public:
typedef typename A::StateId StateId;
struct StateTuple {
typedef typename A::StateId StateId;
StateTuple() {}
StateTuple(StateId s1, StateId s2, int /* f */)
: state_id1(s1), state_id2(s2) {}
StateId state_id1; // state Id on fst1
StateId state_id2; // state Id on fst2
static const int filt = 0; // 'fake' epsilon filter - only needed
// for API compatibility
};
StringDetComposeStateTable() {}
// Subscript operator. Behaves in a way similar to its map/hash_map
// counterpart, i.e. returns a reference to the value associated
// with 'tuple', inserting a 0 value if 'tuple' is unassigned.
StateId &operator[](const StateTuple &tuple) {
StateId index = Fst1IsString ? tuple.state_id1 : tuple.state_id2;
if (index >= (StateId)data_.size()) {
// NB: all values in [old_size; index] are initialized to 0.
data_.resize(index + 1);
}
return data_[index];
}
private:
vector<StateId> data_;
DISALLOW_EVIL_CONSTRUCTORS(StringDetComposeStateTable);
};
// Specializations of ComposeStateTable for the string/det case.
// Both inherit from StringDetComposeStateTable.
template <class A>
class ComposeStateTable<A, COMPOSE_FST1_STRING | COMPOSE_FST2_DET>
: public StringDetComposeStateTable<A, true> { };
template <class A>
class ComposeStateTable<A, COMPOSE_FST2_STRING | COMPOSE_FST1_DET>
: public StringDetComposeStateTable<A, false> { };
// Parameterized implementation of FST composition for a pair of FSTs
// matching the property bit vector T. If possible,
// instantiation-specific switches in the code are based on the values
// of the bits in T, which are known at compile time, so unused code
// should be optimized away by the compiler.
template <class A, uint64 T>
class ComposeFstImpl : public ComposeFstImplBase<A> {
typedef typename A::StateId StateId;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
using FstImpl<A>::SetType;
using FstImpl<A>::SetProperties;
enum FindType { FIND_INPUT = 1, // find input label on fst2
FIND_OUTPUT = 2, // find output label on fst1
FIND_BOTH = 3 }; // find choice state dependent
typedef ComposeStateTable<A, T & COMPOSE_INTERNAL_MASK> StateTupleTable;
typedef typename StateTupleTable::StateTuple StateTuple;
public:
ComposeFstImpl(const Fst<A> &fst1,
const Fst<A> &fst2,
const CacheOptions &opts)
:ComposeFstImplBase<A>(fst1, fst2, opts) {
bool osorted = fst1.Properties(kOLabelSorted, false);
bool isorted = fst2.Properties(kILabelSorted, false);
switch (T & COMPOSE_SPECIAL_SYMBOLS) {
case COMPOSE_FST1_RHO:
case COMPOSE_FST1_PHI:
case COMPOSE_FST1_SIGMA:
if (!osorted || FLAGS_fst_verify_properties)
osorted = fst1.Properties(kOLabelSorted, true);
if (!osorted)
LOG(FATAL) << "ComposeFst: 1st argument not output label "
<< "sorted (special symbols present)";
break;
case COMPOSE_FST2_RHO:
case COMPOSE_FST2_PHI:
case COMPOSE_FST2_SIGMA:
if (!isorted || FLAGS_fst_verify_properties)
isorted = fst2.Properties(kILabelSorted, true);
if (!isorted)
LOG(FATAL) << "ComposeFst: 2nd argument not input label "
<< "sorted (special symbols present)";
break;
case 0:
if (!isorted && !osorted || FLAGS_fst_verify_properties) {
osorted = fst1.Properties(kOLabelSorted, true);
if (!osorted)
isorted = fst2.Properties(kILabelSorted, true);
}
break;
default:
LOG(FATAL)
<< "ComposeFst: More than one special symbol used in composition";
}
if (isorted && (T & COMPOSE_FST2_SIGMA)) {
find_type_ = FIND_INPUT;
} else if (osorted && (T & COMPOSE_FST1_SIGMA)) {
find_type_ = FIND_OUTPUT;
} else if (isorted && (T & COMPOSE_FST2_PHI)) {
find_type_ = FIND_INPUT;
} else if (osorted && (T & COMPOSE_FST1_PHI)) {
find_type_ = FIND_OUTPUT;
} else if (isorted && (T & COMPOSE_FST2_RHO)) {
find_type_ = FIND_INPUT;
} else if (osorted && (T & COMPOSE_FST1_RHO)) {
find_type_ = FIND_OUTPUT;
} else if (isorted && (T & COMPOSE_FST1_STRING)) {
find_type_ = FIND_INPUT;
} else if(osorted && (T & COMPOSE_FST2_STRING)) {
find_type_ = FIND_OUTPUT;
} else if (isorted && osorted) {
find_type_ = FIND_BOTH;
} else if (isorted) {
find_type_ = FIND_INPUT;
} else if (osorted) {
find_type_ = FIND_OUTPUT;
} else {
LOG(FATAL) << "ComposeFst: 1st argument not output label sorted "
<< "and 2nd argument is not input label sorted";
}
}
// Finds/creates an Fst state given a StateTuple. Only creates a new
// state if StateTuple is not found in the state hash.
//
// The method exploits the following device: all pairs stored in the
// associative container state_tuple_table_ are of the form (tuple,
// id(tuple) + 1), i.e. state_tuple_table_[tuple] > 0 if tuple has
// been stored previously. For unassigned tuples, the call to
// state_tuple_table_[tuple] creates a new pair (tuple, 0). As a
// result, state_tuple_table_[tuple] == 0 iff tuple is new.
StateId FindState(const StateTuple& tuple) {
StateId &assoc_value = state_tuple_table_[tuple];
if (assoc_value == 0) { // tuple wasn't present in lookup table:
// assign it a new ID.
state_tuples_.push_back(tuple);
assoc_value = state_tuples_.size();
}
return assoc_value - 1; // NB: assoc_value = ID + 1
}
// Generates arc for composition state s from matched input Fst arcs.
void AddArc(StateId s, const A &arca, const A &arcb, int f,
bool find_input) {
A arc;
if (find_input) {
arc.ilabel = arcb.ilabel;
arc.olabel = arca.olabel;
arc.weight = Times(arcb.weight, arca.weight);
StateTuple tuple(arcb.nextstate, arca.nextstate, f);
arc.nextstate = FindState(tuple);
} else {
arc.ilabel = arca.ilabel;
arc.olabel = arcb.olabel;
arc.weight = Times(arca.weight, arcb.weight);
StateTuple tuple(arca.nextstate, arcb.nextstate, f);
arc.nextstate = FindState(tuple);
}
CacheImpl<A>::AddArc(s, arc);
}
// Arranges it so that the first arg to OrderedExpand is the Fst
// that will be passed to FindLabel.
void Expand(StateId s) {
StateTuple &tuple = state_tuples_[s];
StateId s1 = tuple.state_id1;
StateId s2 = tuple.state_id2;
int f = tuple.filt;
if (find_type_ == FIND_INPUT)
OrderedExpand(s, ComposeFstImplBase<A>::fst2_, s2,
ComposeFstImplBase<A>::fst1_, s1, f, true);
else
OrderedExpand(s, ComposeFstImplBase<A>::fst1_, s1,
ComposeFstImplBase<A>::fst2_, s2, f, false);
}
// Access to flags encoding compose options/optimizations etc. (for
// debugging).
virtual uint64 ComposeFlags() const { return T; }
private:
// This does that actual matching of labels in the composition. The
// arguments are ordered so FindLabel is called with state SA of
// FSTA for each arc leaving state SB of FSTB. The FIND_INPUT arg
// determines whether the input or output label of arcs at SB is
// the one to match on.
void OrderedExpand(StateId s, const Fst<A> *fsta, StateId sa,
const Fst<A> *fstb, StateId sb, int f, bool find_input) {
size_t numarcsa = fsta->NumArcs(sa);
size_t numepsa = find_input ? fsta->NumInputEpsilons(sa) :
fsta->NumOutputEpsilons(sa);
bool finala = fsta->Final(sa) != Weight::Zero();
ArcIterator< Fst<A> > aitera(*fsta, sa);
// First handle special epsilons and sigmas on FSTA
for (; !aitera.Done(); aitera.Next()) {
const A &arca = aitera.Value();
Label match_labela = find_input ? arca.ilabel : arca.olabel;
if (match_labela > 0) {
break;
}
if ((T & COMPOSE_SIGMA) != 0 && match_labela == kSigmaLabel) {
// Found a sigma? Match it against all (non-special) symbols
// on side b.
for (ArcIterator< Fst<A> > aiterb(*fstb, sb);
!aiterb.Done();
aiterb.Next()) {
const A &arcb = aiterb.Value();
Label labelb = find_input ? arcb.olabel : arcb.ilabel;
if (labelb <= 0) continue;
AddArc(s, arca, arcb, 0, find_input);
}
} else if (f == 0 && match_labela == 0) {
A earcb(0, 0, Weight::One(), sb);
AddArc(s, arca, earcb, 0, find_input); // move forward on epsilon
}
}
// Next handle non-epsilon matches, rho labels, and epsilons on FSTB
for (ArcIterator< Fst<A> > aiterb(*fstb, sb);
!aiterb.Done();
aiterb.Next()) {
const A &arcb = aiterb.Value();
Label match_labelb = find_input ? arcb.olabel : arcb.ilabel;
if (match_labelb) { // Consider non-epsilon match
if (FindLabel(&aitera, numarcsa, match_labelb, find_input)) {
for (; !aitera.Done(); aitera.Next()) {
const A &arca = aitera.Value();
Label match_labela = find_input ? arca.ilabel : arca.olabel;
if (match_labela != match_labelb)
break;
AddArc(s, arca, arcb, 0, find_input); // move forward on match
}
} else if ((T & COMPOSE_SPECIAL_SYMBOLS) != 0) {
// If there is no transition labelled 'match_labelb' in
// fsta, try matching 'match_labelb' against special symbols
// (Phi, Rho,...).
for (aitera.Reset(); !aitera.Done(); aitera.Next()) {
A arca = aitera.Value();
Label labela = find_input ? arca.ilabel : arca.olabel;
if (labela >= 0) {
break;
} else if (((T & COMPOSE_PHI) != 0) && (labela == kPhiLabel)) {
// Case 1: if a failure transition exists, follow its
// transitive closure until a) a transition labelled
// 'match_labelb' is found, or b) the initial state of
// fsta is reached.
StateId sf = sa; // Start of current failure transition.
while (labela == kPhiLabel && sf != arca.nextstate) {
sf = arca.nextstate;
size_t numarcsf = fsta->NumArcs(sf);
ArcIterator< Fst<A> > aiterf(*fsta, sf);
if (FindLabel(&aiterf, numarcsf, match_labelb, find_input)) {
// Sub-case 1a: there exists a transition starting
// in sf and consuming symbol 'match_labelb'.
AddArc(s, aiterf.Value(), arcb, 0, find_input);
break;
} else {
// No transition labelled 'match_labelb' found: try
// next failure transition (starting at 'sf').
for (aiterf.Reset(); !aiterf.Done(); aiterf.Next()) {
arca = aiterf.Value();
labela = find_input ? arca.ilabel : arca.olabel;
if (labela >= kPhiLabel) break;
}
}
}
if (labela == kPhiLabel && sf == arca.nextstate) {
// Sub-case 1b: failure transitions lead to start
// state without finding a matching
// transition. Therefore, we generate a loop in start
// state of fsta.
A loop(match_labelb, match_labelb, Weight::One(), sf);
AddArc(s, loop, arcb, 0, find_input);
}
} else if (((T & COMPOSE_RHO) != 0) && (labela == kRhoLabel)) {
// Case 2: 'match_labelb' can be matched against a
// "rest" (rho) label in fsta.
if (find_input) {
arca.ilabel = match_labelb;
if (arca.olabel == kRhoLabel)
arca.olabel = match_labelb;
} else {
arca.olabel = match_labelb;
if (arca.ilabel == kRhoLabel)
arca.ilabel = match_labelb;
}
AddArc(s, arca, arcb, 0, find_input); // move fwd on match
}
}
}
} else if (numepsa != numarcsa || finala) { // Handle FSTB epsilon
A earca(0, 0, Weight::One(), sa);
AddArc(s, earca, arcb, numepsa > 0, find_input); // move on epsilon
}
}
SetArcs(s);
}
// Finds matches to MATCH_LABEL in arcs given by AITER
// using FIND_INPUT to determine whether to look on input or output.
bool FindLabel(ArcIterator< Fst<A> > *aiter, size_t numarcs,
Label match_label, bool find_input) {
// binary search for match
size_t low = 0;
size_t high = numarcs;
while (low < high) {
size_t mid = (low + high) / 2;
aiter->Seek(mid);
Label label = find_input ?
aiter->Value().ilabel : aiter->Value().olabel;
if (label > match_label) {
high = mid;
} else if (label < match_label) {
low = mid + 1;
} else {
// find first matching label (when non-determinism)
for (size_t i = mid; i > low; --i) {
aiter->Seek(i - 1);
label = find_input ? aiter->Value().ilabel : aiter->Value().olabel;
if (label != match_label) {
aiter->Seek(i);
return true;
}
}
return true;
}
}
return false;
}
StateId ComputeStart() {
StateId s1 = ComposeFstImplBase<A>::fst1_->Start();
StateId s2 = ComposeFstImplBase<A>::fst2_->Start();
if (s1 == kNoStateId || s2 == kNoStateId)
return kNoStateId;
StateTuple tuple(s1, s2, 0);
return FindState(tuple);
}
Weight ComputeFinal(StateId s) {
StateTuple &tuple = state_tuples_[s];
Weight final = Times(ComposeFstImplBase<A>::fst1_->Final(tuple.state_id1),
ComposeFstImplBase<A>::fst2_->Final(tuple.state_id2));
return final;
}
FindType find_type_; // find label on which side?
// Maps from StateId to StateTuple.
vector<StateTuple> state_tuples_;
// Maps from StateTuple to StateId.
StateTupleTable state_tuple_table_;
DISALLOW_EVIL_CONSTRUCTORS(ComposeFstImpl);
};
// Computes the composition of two transducers. This version is a
// delayed Fst. If FST1 transduces string x to y with weight a and FST2
// transduces y to z with weight b, then their composition transduces
// string x to z with weight Times(x, z).
//
// The output labels of the first transducer or the input labels of
// the second transducer must be sorted. The weights need to form a
// commutative semiring (valid for TropicalWeight and LogWeight).
//
// Complexity:
// Assuming the first FST is unsorted and the second is sorted:
// - Time: O(v1 v2 d1 (log d2 + m2)),
// - Space: O(v1 v2)
// where vi = # of states visited, di = maximum out-degree, and mi the
// maximum multiplicity of the states visited for the ith
// FST. Constant time and space to visit an input state or arc is
// assumed and exclusive of caching.
//
// Caveats:
// - ComposeFst does not trim its output (since it is a delayed operation).
// - The efficiency of composition can be strongly affected by several factors:
// - the choice of which tnansducer is sorted - prefer sorting the FST
// that has the greater average out-degree.
// - the amount of non-determinism
// - the presence and location of epsilon transitions - avoid epsilon
// transitions on the output side of the first transducer or
// the input side of the second transducer or prefer placing
// them later in a path since they delay matching and can
// introduce non-coaccessible states and transitions.
template <class A>
class ComposeFst : public Fst<A> {
public:
friend class ArcIterator< ComposeFst<A> >;
friend class CacheStateIterator< ComposeFst<A> >;
friend class CacheArcIterator< ComposeFst<A> >;
typedef A Arc;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
typedef CacheState<A> State;
ComposeFst(const Fst<A> &fst1, const Fst<A> &fst2)
: impl_(Init(fst1, fst2, ComposeFstOptions<>())) { }
template <uint64 T>
ComposeFst(const Fst<A> &fst1,
const Fst<A> &fst2,
const ComposeFstOptions<T> &opts)
: impl_(Init(fst1, fst2, opts)) { }
ComposeFst(const ComposeFst<A> &fst) : Fst<A>(fst), impl_(fst.impl_) {
impl_->IncrRefCount();
}
virtual ~ComposeFst() { if (!impl_->DecrRefCount()) delete impl_; }
virtual StateId Start() const { return impl_->Start(); }
virtual Weight Final(StateId s) const { return impl_->Final(s); }
virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); }
virtual size_t NumInputEpsilons(StateId s) const {
return impl_->NumInputEpsilons(s);
}
virtual size_t NumOutputEpsilons(StateId s) const {
return impl_->NumOutputEpsilons(s);
}
virtual uint64 Properties(uint64 mask, bool test) const {
if (test) {
uint64 known, test = TestProperties(*this, mask, &known);
impl_->SetProperties(test, known);
return test & mask;
} else {
return impl_->Properties(mask);
}
}
virtual const string& Type() const { return impl_->Type(); }
virtual ComposeFst<A> *Copy() const {
return new ComposeFst<A>(*this);
}
virtual const SymbolTable* InputSymbols() const {
return impl_->InputSymbols();
}
virtual const SymbolTable* OutputSymbols() const {
return impl_->OutputSymbols();
}
virtual inline void InitStateIterator(StateIteratorData<A> *data) const;
virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
impl_->InitArcIterator(s, data);
}
// Access to flags encoding compose options/optimizations etc. (for
// debugging).
uint64 ComposeFlags() const { return impl_->ComposeFlags(); }
protected:
ComposeFstImplBase<A> *Impl() { return impl_; }
private:
ComposeFstImplBase<A> *impl_;
// Auxiliary method encapsulating the creation of a ComposeFst
// implementation that is appropriate for the properties of fst1 and
// fst2.
template <uint64 T>
static ComposeFstImplBase<A> *Init(
const Fst<A> &fst1,
const Fst<A> &fst2,
const ComposeFstOptions<T> &opts) {
// Filter for sort properties (forces a property check).
uint64 sort_props_mask = kILabelSorted | kOLabelSorted;
// Filter for optimization-related properties (does not force a
// property-check).
uint64 opt_props_mask =
kString | kIDeterministic | kODeterministic | kNoIEpsilons |
kNoOEpsilons;
uint64 props1 = fst1.Properties(sort_props_mask, true);
uint64 props2 = fst2.Properties(sort_props_mask, true);
props1 |= fst1.Properties(opt_props_mask, false);
props2 |= fst2.Properties(opt_props_mask, false);
if (!(Weight::Properties() & kCommutative)) {
props1 |= fst1.Properties(kUnweighted, true);
props2 |= fst2.Properties(kUnweighted, true);
if (!(props1 & kUnweighted) && !(props2 & kUnweighted))
LOG(FATAL) << "ComposeFst: Weight needs to be a commutative semiring: "
<< Weight::Type();
}
// Case 1: flag COMPOSE_GENERIC disables optimizations.
if (T & COMPOSE_GENERIC) {
return new ComposeFstImpl<A, T>(fst1, fst2, opts);
}
const uint64 kStringDetOptProps =
kIDeterministic | kILabelSorted | kNoIEpsilons;
const uint64 kDetStringOptProps =
kODeterministic | kOLabelSorted | kNoOEpsilons;
// Case 2: fst1 is a string, fst2 is deterministic and epsilon-free.
if ((props1 & kString) &&
!(T & (COMPOSE_FST1_RHO | COMPOSE_FST1_PHI | COMPOSE_FST1_SIGMA)) &&
((props2 & kStringDetOptProps) == kStringDetOptProps)) {
return new ComposeFstImpl<A, T | COMPOSE_FST1_STRING | COMPOSE_FST2_DET>(
fst1, fst2, opts);
}
// Case 3: fst1 is deterministic and epsilon-free, fst2 is string.
if ((props2 & kString) &&
!(T & (COMPOSE_FST1_RHO | COMPOSE_FST1_PHI | COMPOSE_FST1_SIGMA)) &&
((props1 & kDetStringOptProps) == kDetStringOptProps)) {
return new ComposeFstImpl<A, T | COMPOSE_FST2_STRING | COMPOSE_FST1_DET>(
fst1, fst2, opts);
}
// Default case: no optimizations.
return new ComposeFstImpl<A, T>(fst1, fst2, opts);
}
void operator=(const ComposeFst<A> &fst); // disallow
};
// Specialization for ComposeFst.
template<class A>
class StateIterator< ComposeFst<A> >
: public CacheStateIterator< ComposeFst<A> > {
public:
explicit StateIterator(const ComposeFst<A> &fst)
: CacheStateIterator< ComposeFst<A> >(fst) {}
};
// Specialization for ComposeFst.
template <class A>
class ArcIterator< ComposeFst<A> >
: public CacheArcIterator< ComposeFst<A> > {
public:
typedef typename A::StateId StateId;
ArcIterator(const ComposeFst<A> &fst, StateId s)
: CacheArcIterator< ComposeFst<A> >(fst, s) {
if (!fst.impl_->HasArcs(s))
fst.impl_->Expand(s);
}
private:
DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
};
template <class A> inline
void ComposeFst<A>::InitStateIterator(StateIteratorData<A> *data) const {
data->base = new StateIterator< ComposeFst<A> >(*this);
}
// Useful alias when using StdArc.
typedef ComposeFst<StdArc> StdComposeFst;
struct ComposeOptions {
bool connect; // Connect output
ComposeOptions(bool c) : connect(c) {}
ComposeOptions() : connect(true) { }
};
// Computes the composition of two transducers. This version writes
// the composed FST into a MurableFst. If FST1 transduces string x to
// y with weight a and FST2 transduces y to z with weight b, then
// their composition transduces string x to z with weight
// Times(x, z).
//
// The output labels of the first transducer or the input labels of
// the second transducer must be sorted. The weights need to form a
// commutative semiring (valid for TropicalWeight and LogWeight).
//
// Complexity:
// Assuming the first FST is unsorted and the second is sorted:
// - Time: O(V1 V2 D1 (log D2 + M2)),
// - Space: O(V1 V2 D1 M2)
// where Vi = # of states, Di = maximum out-degree, and Mi is
// the maximum multiplicity for the ith FST.
//
// Caveats:
// - Compose trims its output.
// - The efficiency of composition can be strongly affected by several factors:
// - the choice of which tnansducer is sorted - prefer sorting the FST
// that has the greater average out-degree.
// - the amount of non-determinism
// - the presence and location of epsilon transitions - avoid epsilon
// transitions on the output side of the first transducer or
// the input side of the second transducer or prefer placing
// them later in a path since they delay matching and can
// introduce non-coaccessible states and transitions.
template<class Arc>
void Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
MutableFst<Arc> *ofst,
const ComposeOptions &opts = ComposeOptions()) {
ComposeFstOptions<> nopts;
nopts.gc_limit = 0; // Cache only the last state for fastest copy.
*ofst = ComposeFst<Arc>(ifst1, ifst2, nopts);
if (opts.connect)
Connect(ofst);
}
} // namespace fst
#endif // FST_LIB_COMPOSE_H__