diff options
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/compose.h')
| -rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/compose.h | 728 |
1 files changed, 728 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/compose.h b/kaldi_io/src/tools/openfst/include/fst/compose.h new file mode 100644 index 0000000..db5ea3a --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/compose.h @@ -0,0 +1,728 @@ +// 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. +// +// Copyright 2005-2010 Google, Inc. +// Author: riley@google.com (Michael Riley) +// +// \file +// Class to compute the composition of two FSTs + +#ifndef FST_LIB_COMPOSE_H__ +#define FST_LIB_COMPOSE_H__ + +#include <algorithm> +#include <string> +#include <vector> +using std::vector; + +#include <fst/cache.h> +#include <fst/compose-filter.h> +#include <fst/lookahead-filter.h> +#include <fst/matcher.h> +#include <fst/state-table.h> +#include <fst/test-properties.h> + + +namespace fst { + +// Delayed composition options templated on the arc type, the matcher, +// the composition filter, and the composition state table. By +// default, the matchers, filter, and state table are constructed by +// composition. If set below, the user can instead pass in these +// objects; in that case, ComposeFst takes their ownership. This +// version controls composition implemented between generic Fst<Arc> +// types and a shared matcher type M for Fst<Arc>. This should be +// adequate for most applications, giving a reasonable tradeoff +// between efficiency and code sharing (but see ComposeFstImplOptions). +template <class A, + class M = Matcher<Fst<A> >, + class F = SequenceComposeFilter<M>, + class T = GenericComposeStateTable<A, typename F::FilterState> > +struct ComposeFstOptions : public CacheOptions { + M *matcher1; // FST1 matcher (see matcher.h) + M *matcher2; // FST2 matcher + F *filter; // Composition filter (see compose-filter.h) + T *state_table; // Composition state table (see compose-state-table.h) + + explicit ComposeFstOptions(const CacheOptions &opts, + M *mat1 = 0, M *mat2 = 0, + F *filt = 0, T *sttable= 0) + : CacheOptions(opts), matcher1(mat1), matcher2(mat2), + filter(filt), state_table(sttable) {} + + ComposeFstOptions() : matcher1(0), matcher2(0), filter(0), state_table(0) {} +}; + + +// Delayed composition options templated on the two matcher types, the +// composition filter, and the composition state table. By default, +// the matchers, filter, and state table are constructed by +// composition. If set below, the user can instead pass in these +// objects; in that case, ComposeFst takes their ownership. This +// version controls composition implemented using arbitrary matchers +// (of the same Arc type but otherwise arbitrary Fst type). The user +// must ensure the matchers are compatible. These options permit the +// most efficient use, but shares the least code. This is for advanced +// use only in the most demanding or specialized applications that can +// benefit from it (o.w. prefer ComposeFstOptions). +template <class M1, class M2, + class F = SequenceComposeFilter<M1, M2>, + class T = GenericComposeStateTable<typename M1::Arc, + typename F::FilterState> > +struct ComposeFstImplOptions : public CacheOptions { + M1 *matcher1; // FST1 matcher (see matcher.h) + M2 *matcher2; // FST2 matcher + F *filter; // Composition filter (see compose-filter.h) + T *state_table; // Composition state table (see compose-state-table.h) + + explicit ComposeFstImplOptions(const CacheOptions &opts, + M1 *mat1 = 0, M2 *mat2 = 0, + F *filt = 0, T *sttable= 0) + : CacheOptions(opts), matcher1(mat1), matcher2(mat2), + filter(filt), state_table(sttable) {} + + ComposeFstImplOptions() + : matcher1(0), matcher2(0), filter(0), state_table(0) {} +}; + + +// Implementation of delayed composition. This base class is +// common to the variants with different matchers, composition filters +// and state tables. +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; + using CacheBaseImpl< CacheState<A> >::SetFinal; + using CacheBaseImpl< CacheState<A> >::SetStart; + + 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) { + VLOG(2) << "ComposeFst(" << this << "): Begin"; + SetType("compose"); + + if (!CompatSymbols(fst2.InputSymbols(), fst1.OutputSymbols())) { + FSTERROR() << "ComposeFst: output symbol table of 1st argument " + << "does not match input symbol table of 2nd argument"; + SetProperties(kError, kError); + } + + SetInputSymbols(fst1.InputSymbols()); + SetOutputSymbols(fst2.OutputSymbols()); + } + + ComposeFstImplBase(const ComposeFstImplBase<A> &impl) + : CacheImpl<A>(impl, true) { + SetProperties(impl.Properties(), kCopyProperties); + SetInputSymbols(impl.InputSymbols()); + SetOutputSymbols(impl.OutputSymbols()); + } + + virtual ComposeFstImplBase<A> *Copy() = 0; + + virtual ~ComposeFstImplBase() {} + + 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); + } + + protected: + virtual StateId ComputeStart() = 0; + virtual Weight ComputeFinal(StateId s) = 0; +}; + + +// Implementaion of delayed composition templated on the matchers (see +// matcher.h), composition filter (see compose-filter-inl.h) and +// the composition state table (see compose-state-table.h). +template <class M1, class M2, class F, class T> +class ComposeFstImpl : public ComposeFstImplBase<typename M1::Arc> { + typedef typename M1::FST FST1; + typedef typename M2::FST FST2; + typedef typename M1::Arc Arc; + typedef typename Arc::StateId StateId; + typedef typename Arc::Label Label; + typedef typename Arc::Weight Weight; + typedef typename F::FilterState FilterState; + typedef typename F::Matcher1 Matcher1; + typedef typename F::Matcher2 Matcher2; + + using CacheBaseImpl<CacheState<Arc> >::SetArcs; + using FstImpl<Arc>::SetType; + using FstImpl<Arc>::SetProperties; + + typedef ComposeStateTuple<StateId, FilterState> StateTuple; + + public: + ComposeFstImpl(const FST1 &fst1, const FST2 &fst2, + const ComposeFstImplOptions<M1, M2, F, T> &opts); + + ComposeFstImpl(const ComposeFstImpl<M1, M2, F, T> &impl) + : ComposeFstImplBase<Arc>(impl), + filter_(new F(*impl.filter_, true)), + matcher1_(filter_->GetMatcher1()), + matcher2_(filter_->GetMatcher2()), + fst1_(matcher1_->GetFst()), + fst2_(matcher2_->GetFst()), + state_table_(new T(*impl.state_table_)), + match_type_(impl.match_type_) {} + + ~ComposeFstImpl() { + VLOG(2) << "ComposeFst(" << this + << "): End: # of visited states: " << state_table_->Size(); + + delete filter_; + delete state_table_; + } + + virtual ComposeFstImpl<M1, M2, F, T> *Copy() { + return new ComposeFstImpl<M1, M2, F, T>(*this); + } + + uint64 Properties() const { return Properties(kFstProperties); } + + // Set error if found; return FST impl properties. + uint64 Properties(uint64 mask) const { + if ((mask & kError) && + (fst1_.Properties(kError, false) || + fst2_.Properties(kError, false) || + (matcher1_->Properties(0) & kError) || + (matcher2_->Properties(0) & kError) | + (filter_->Properties(0) & kError) || + state_table_->Error())) { + SetProperties(kError, kError); + } + return FstImpl<Arc>::Properties(mask); + } + + // Arranges it so that the first arg to OrderedExpand is the Fst + // that will be matched on. + void Expand(StateId s) { + const StateTuple &tuple = state_table_->Tuple(s); + StateId s1 = tuple.state_id1; + StateId s2 = tuple.state_id2; + filter_->SetState(s1, s2, tuple.filter_state); + if (match_type_ == MATCH_OUTPUT || + (match_type_ == MATCH_BOTH && + internal::NumArcs(fst1_, s1) > internal::NumArcs(fst2_, s2))) + OrderedExpand(s, fst1_, s1, fst2_, s2, matcher1_, false); + else + OrderedExpand(s, fst2_, s2, fst1_, s1, matcher2_, true); + } + + const FST1 &GetFst1() { return fst1_; } + const FST2 &GetFst2() { return fst2_; } + M1 *GetMatcher1() { return matcher1_; } + M2 *GetMatcher2() { return matcher2_; } + F *GetFilter() { return filter_; } + T *GetStateTable() { return state_table_; } + + private: + // This does that actual matching of labels in the composition. The + // arguments are ordered so matching is called on state 'sa' of + // 'fsta' for each arc leaving state 'sb' of 'fstb'. The 'match_input' arg + // determines whether the input or output label of arcs at 'sb' is + // the one to match on. + template <class FST, class Matcher> + void OrderedExpand(StateId s, const Fst<Arc> &, StateId sa, + const FST &fstb, StateId sb, + Matcher *matchera, bool match_input) { + matchera->SetState(sa); + + // First process non-consuming symbols (e.g., epsilons) on FSTA. + Arc loop(match_input ? 0 : kNoLabel, match_input ? kNoLabel : 0, + Weight::One(), sb); + MatchArc(s, matchera, loop, match_input); + + // Then process matches on FSTB. + for (ArcIterator<FST> iterb(fstb, sb); !iterb.Done(); iterb.Next()) + MatchArc(s, matchera, iterb.Value(), match_input); + + SetArcs(s); + } + + // Matches a single transition from 'fstb' against 'fata' at 's'. + template <class Matcher> + void MatchArc(StateId s, Matcher *matchera, + const Arc &arc, bool match_input) { + if (matchera->Find(match_input ? arc.olabel : arc.ilabel)) { + for (; !matchera->Done(); matchera->Next()) { + Arc arca = matchera->Value(); + Arc arcb = arc; + if (match_input) { + const FilterState &f = filter_->FilterArc(&arcb, &arca); + if (f != FilterState::NoState()) + AddArc(s, arcb, arca, f); + } else { + const FilterState &f = filter_->FilterArc(&arca, &arcb); + if (f != FilterState::NoState()) + AddArc(s, arca, arcb, f); + } + } + } + } + + // Add a matching transition at 's'. + void AddArc(StateId s, const Arc &arc1, const Arc &arc2, + const FilterState &f) { + StateTuple tuple(arc1.nextstate, arc2.nextstate, f); + Arc oarc(arc1.ilabel, arc2.olabel, Times(arc1.weight, arc2.weight), + state_table_->FindState(tuple)); + CacheImpl<Arc>::PushArc(s, oarc); + } + + StateId ComputeStart() { + StateId s1 = fst1_.Start(); + if (s1 == kNoStateId) + return kNoStateId; + + StateId s2 = fst2_.Start(); + if (s2 == kNoStateId) + return kNoStateId; + + const FilterState &f = filter_->Start(); + StateTuple tuple(s1, s2, f); + return state_table_->FindState(tuple); + } + + Weight ComputeFinal(StateId s) { + const StateTuple &tuple = state_table_->Tuple(s); + StateId s1 = tuple.state_id1; + Weight final1 = internal::Final(fst1_, s1); + if (final1 == Weight::Zero()) + return final1; + + StateId s2 = tuple.state_id2; + Weight final2 = internal::Final(fst2_, s2); + if (final2 == Weight::Zero()) + return final2; + + filter_->SetState(s1, s2, tuple.filter_state); + filter_->FilterFinal(&final1, &final2); + return Times(final1, final2); + } + + // Identifies and verifies the capabilities of the matcher to be used for + // composition. + void SetMatchType(); + + F *filter_; + Matcher1 *matcher1_; + Matcher2 *matcher2_; + const FST1 &fst1_; + const FST2 &fst2_; + T *state_table_; + + MatchType match_type_; + + void operator=(const ComposeFstImpl<M1, M2, F, T> &); // disallow +}; + +template <class M1, class M2, class F, class T> inline +ComposeFstImpl<M1, M2, F, T>::ComposeFstImpl( + const FST1 &fst1, const FST2 &fst2, + const ComposeFstImplOptions<M1, M2, F, T> &opts) + : ComposeFstImplBase<Arc>(fst1, fst2, opts), + filter_(opts.filter ? opts.filter : + new F(fst1, fst2, opts.matcher1, opts.matcher2)), + matcher1_(filter_->GetMatcher1()), + matcher2_(filter_->GetMatcher2()), + fst1_(matcher1_->GetFst()), + fst2_(matcher2_->GetFst()), + state_table_(opts.state_table ? opts.state_table : + new T(fst1_, fst2_)) { + SetMatchType(); + if (match_type_ == MATCH_NONE) + SetProperties(kError, kError); + VLOG(2) << "ComposeFst(" << this << "): Match type: " + << (match_type_ == MATCH_OUTPUT ? "output" : + (match_type_ == MATCH_INPUT ? "input" : + (match_type_ == MATCH_BOTH ? "both" : + (match_type_ == MATCH_NONE ? "none" : "unknown")))); + + uint64 fprops1 = fst1.Properties(kFstProperties, false); + uint64 fprops2 = fst2.Properties(kFstProperties, false); + uint64 mprops1 = matcher1_->Properties(fprops1); + uint64 mprops2 = matcher2_->Properties(fprops2); + uint64 cprops = ComposeProperties(mprops1, mprops2); + SetProperties(filter_->Properties(cprops), kCopyProperties); + if (state_table_->Error()) SetProperties(kError, kError); + VLOG(2) << "ComposeFst(" << this << "): Initialized"; +} + +template <class M1, class M2, class F, class T> +void ComposeFstImpl<M1, M2, F, T>::SetMatchType() { + MatchType type1 = matcher1_->Type(false); + MatchType type2 = matcher2_->Type(false); + uint32 flags1 = matcher1_->Flags(); + uint32 flags2 = matcher2_->Flags(); + if (flags1 & flags2 & kRequireMatch) { + FSTERROR() << "ComposeFst: only one argument can require matching."; + match_type_ = MATCH_NONE; + } else if (flags1 & kRequireMatch) { + if (matcher1_->Type(true) != MATCH_OUTPUT) { + FSTERROR() << "ComposeFst: 1st argument requires matching but cannot."; + match_type_ = MATCH_NONE; + } + match_type_ = MATCH_OUTPUT; + } else if (flags2 & kRequireMatch) { + if (matcher2_->Type(true) != MATCH_INPUT) { + FSTERROR() << "ComposeFst: 2nd argument requires matching but cannot."; + match_type_ = MATCH_NONE; + } + match_type_ = MATCH_INPUT; + } else if (flags1 & flags2 & kPreferMatch && + type1 == MATCH_OUTPUT && type2 == MATCH_INPUT) { + match_type_ = MATCH_BOTH; + } else if (flags1 & kPreferMatch && type1 == MATCH_OUTPUT) { + match_type_ = MATCH_OUTPUT; + } else if (flags2 & kPreferMatch && type2 == MATCH_INPUT) { + match_type_ = MATCH_INPUT; + } else if (type1 == MATCH_OUTPUT && type2 == MATCH_INPUT) { + match_type_ = MATCH_BOTH; + } else if (type1 == MATCH_OUTPUT) { + match_type_ = MATCH_OUTPUT; + } else if (type2 == MATCH_INPUT) { + match_type_ = MATCH_INPUT; + } else if (flags1 & kPreferMatch && matcher1_->Type(true) == MATCH_OUTPUT) { + match_type_ = MATCH_OUTPUT; + } else if (flags2 & kPreferMatch && matcher2_->Type(true) == MATCH_INPUT) { + match_type_ = MATCH_INPUT; + } else if (matcher1_->Type(true) == MATCH_OUTPUT) { + match_type_ = MATCH_OUTPUT; + } else if (matcher2_->Type(true) == MATCH_INPUT) { + match_type_ = MATCH_INPUT; + } else { + FSTERROR() << "ComposeFst: 1st argument cannot match on output labels " + << "and 2nd argument cannot match on input labels (sort?)."; + match_type_ = MATCH_NONE; + } +} + + +// 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 (with the default matcher). +// 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. +// +// This class attaches interface to implementation and handles +// reference counting, delegating most methods to ImplToFst. +template <class A> +class ComposeFst : public ImplToFst< ComposeFstImplBase<A> > { + public: + friend class ArcIterator< ComposeFst<A> >; + friend class StateIterator< ComposeFst<A> >; + + typedef A Arc; + typedef typename A::Weight Weight; + typedef typename A::StateId StateId; + typedef CacheState<A> State; + typedef ComposeFstImplBase<A> Impl; + + using ImplToFst<Impl>::SetImpl; + + // Compose specifying only caching options. + ComposeFst(const Fst<A> &fst1, const Fst<A> &fst2, + const CacheOptions &opts = CacheOptions()) + : ImplToFst<Impl>(CreateBase(fst1, fst2, opts)) {} + + // Compose specifying one shared matcher type M. Requires input + // Fsts and matcher FST type (M::FST) be Fst<A>. Recommended for + // best code-sharing and matcher compatiblity. + template <class M, class F, class T> + ComposeFst(const Fst<A> &fst1, const Fst<A> &fst2, + const ComposeFstOptions<A, M, F, T> &opts) + : ImplToFst<Impl>(CreateBase1(fst1, fst2, opts)) {} + + // Compose specifying two matcher types M1 and M2. Requires input + // Fsts (of the same Arc type but o.w. arbitrary) match the + // corresponding matcher FST types (M1::FST, M2::FST). Recommended + // only for advanced use in demanding or specialized applications + // due to potential code bloat and matcher incompatibilities. + template <class M1, class M2, class F, class T> + ComposeFst(const typename M1::FST &fst1, const typename M2::FST &fst2, + const ComposeFstImplOptions<M1, M2, F, T> &opts) + : ImplToFst<Impl>(CreateBase2(fst1, fst2, opts)) {} + + // See Fst<>::Copy() for doc. + ComposeFst(const ComposeFst<A> &fst, bool safe = false) { + if (safe) + SetImpl(fst.GetImpl()->Copy()); + else + SetImpl(fst.GetImpl(), false); + } + + // Get a copy of this ComposeFst. See Fst<>::Copy() for further doc. + virtual ComposeFst<A> *Copy(bool safe = false) const { + return new ComposeFst<A>(*this, safe); + } + + virtual inline void InitStateIterator(StateIteratorData<A> *data) const; + + virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { + GetImpl()->InitArcIterator(s, data); + } + + protected: + ComposeFst() {} + + // Create compose implementation specifying two matcher types. + template <class M1, class M2, class F, class T> + static Impl *CreateBase2( + const typename M1::FST &fst1, const typename M2::FST &fst2, + const ComposeFstImplOptions<M1, M2, F, T> &opts) { + Impl *impl = new ComposeFstImpl<M1, M2, F, T>(fst1, fst2, opts); + if (!(Weight::Properties() & kCommutative)) { + int64 props1 = fst1.Properties(kUnweighted, true); + int64 props2 = fst2.Properties(kUnweighted, true); + if (!(props1 & kUnweighted) && !(props2 & kUnweighted)) { + FSTERROR() << "ComposeFst: Weights must be a commutative semiring: " + << Weight::Type(); + impl->SetProperties(kError, kError); + } + } + return impl; + } + + // Create compose implementation specifying one matcher type. + // Requires input Fsts and matcher FST type (M::FST) be Fst<A> + template <class M, class F, class T> + static Impl *CreateBase1(const Fst<A> &fst1, const Fst<A> &fst2, + const ComposeFstOptions<A, M, F, T> &opts) { + ComposeFstImplOptions<M, M, F, T> nopts(opts, opts.matcher1, opts.matcher2, + opts.filter, opts.state_table); + return CreateBase2(fst1, fst2, nopts); + } + + // Create compose implementation specifying no matcher type. + static Impl *CreateBase(const Fst<A> &fst1, const Fst<A> &fst2, + const CacheOptions &opts) { + switch (LookAheadMatchType(fst1, fst2)) { // Check for lookahead matchers + default: + case MATCH_NONE: { // Default composition (no look-ahead) + VLOG(2) << "ComposeFst: Default composition (no look-ahead)"; + ComposeFstOptions<Arc> nopts(opts); + return CreateBase1(fst1, fst2, nopts); + } + case MATCH_OUTPUT: { // Lookahead on fst1 + VLOG(2) << "ComposeFst: Lookahead on fst1"; + typedef typename DefaultLookAhead<Arc, MATCH_OUTPUT>::FstMatcher M; + typedef typename DefaultLookAhead<Arc, MATCH_OUTPUT>::ComposeFilter F; + ComposeFstOptions<Arc, M, F> nopts(opts); + return CreateBase1(fst1, fst2, nopts); + } + case MATCH_INPUT: { // Lookahead on fst2 + VLOG(2) << "ComposeFst: Lookahead on fst2"; + typedef typename DefaultLookAhead<Arc, MATCH_INPUT>::FstMatcher M; + typedef typename DefaultLookAhead<Arc, MATCH_INPUT>::ComposeFilter F; + ComposeFstOptions<Arc, M, F> nopts(opts); + return CreateBase1(fst1, fst2, nopts); + } + } + } + + private: + // Makes visible to friends. + Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); } + + 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, fst.GetImpl()) {} +}; + + +// 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.GetImpl(), s) { + if (!fst.GetImpl()->HasArcs(s)) + fst.GetImpl()->Expand(s); + } + + private: + DISALLOW_COPY_AND_ASSIGN(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; + +enum ComposeFilter { AUTO_FILTER, SEQUENCE_FILTER, ALT_SEQUENCE_FILTER, + MATCH_FILTER }; + +struct ComposeOptions { + bool connect; // Connect output + ComposeFilter filter_type; // Which pre-defined filter to use + + ComposeOptions(bool c, ComposeFilter ft = AUTO_FILTER) + : connect(c), filter_type(ft) {} + ComposeOptions() : connect(true), filter_type(AUTO_FILTER) {} +}; + +// 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()) { + typedef Matcher< Fst<Arc> > M; + + if (opts.filter_type == AUTO_FILTER) { + CacheOptions nopts; + nopts.gc_limit = 0; // Cache only the last state for fastest copy. + *ofst = ComposeFst<Arc>(ifst1, ifst2, nopts); + } else if (opts.filter_type == SEQUENCE_FILTER) { + ComposeFstOptions<Arc> copts; + copts.gc_limit = 0; // Cache only the last state for fastest copy. + *ofst = ComposeFst<Arc>(ifst1, ifst2, copts); + } else if (opts.filter_type == ALT_SEQUENCE_FILTER) { + ComposeFstOptions<Arc, M, AltSequenceComposeFilter<M> > copts; + copts.gc_limit = 0; // Cache only the last state for fastest copy. + *ofst = ComposeFst<Arc>(ifst1, ifst2, copts); + } else if (opts.filter_type == MATCH_FILTER) { + ComposeFstOptions<Arc, M, MatchComposeFilter<M> > copts; + copts.gc_limit = 0; // Cache only the last state for fastest copy. + *ofst = ComposeFst<Arc>(ifst1, ifst2, copts); + } + + if (opts.connect) + Connect(ofst); +} + +} // namespace fst + +#endif // FST_LIB_COMPOSE_H__ |