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, 0 insertions, 728 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/compose.h b/kaldi_io/src/tools/openfst/include/fst/compose.h deleted file mode 100644 index db5ea3a..0000000 --- a/kaldi_io/src/tools/openfst/include/fst/compose.h +++ /dev/null @@ -1,728 +0,0 @@ -// 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__ |