diff options
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/arc-map.h')
| -rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/arc-map.h | 1146 |
1 files changed, 1146 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/arc-map.h b/kaldi_io/src/tools/openfst/include/fst/arc-map.h new file mode 100644 index 0000000..914f81c --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/arc-map.h @@ -0,0 +1,1146 @@ +// arc-map.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 map over/transform arcs e.g., change semirings or +// implement project/invert. Consider using when operation does +// not change the number of arcs (except possibly superfinal arcs). + +#ifndef FST_LIB_ARC_MAP_H__ +#define FST_LIB_ARC_MAP_H__ + +#include <tr1/unordered_map> +using std::tr1::unordered_map; +using std::tr1::unordered_multimap; +#include <string> +#include <utility> +using std::pair; using std::make_pair; + +#include <fst/cache.h> +#include <fst/mutable-fst.h> + + +namespace fst { + +// This determines how final weights are mapped. +enum MapFinalAction { + // A final weight is mapped into a final weight. An error + // is raised if this is not possible. + MAP_NO_SUPERFINAL, + + // A final weight is mapped to an arc to the superfinal state + // when the result cannot be represented as a final weight. + // The superfinal state will be added only if it is needed. + MAP_ALLOW_SUPERFINAL, + + // A final weight is mapped to an arc to the superfinal state + // unless the result can be represented as a final weight of weight + // Zero(). The superfinal state is always added (if the input is + // not the empty Fst). + MAP_REQUIRE_SUPERFINAL +}; + +// This determines how symbol tables are mapped. +enum MapSymbolsAction { + // Symbols should be cleared in the result by the map. + MAP_CLEAR_SYMBOLS, + + // Symbols should be copied from the input FST by the map. + MAP_COPY_SYMBOLS, + + // Symbols should not be modified in the result by the map itself. + // (They may set by the mapper). + MAP_NOOP_SYMBOLS +}; + +// ArcMapper Interface - class determinies how arcs and final weights +// are mapped. Useful for implementing operations that do not change +// the number of arcs (expect possibly superfinal arcs). +// +// class ArcMapper { +// public: +// typedef A FromArc; +// typedef B ToArc; +// +// // Maps an arc type A to arc type B. +// B operator()(const A &arc); +// // Specifies final action the mapper requires (see above). +// // The mapper will be passed final weights as arcs of the +// // form A(0, 0, weight, kNoStateId). +// MapFinalAction FinalAction() const; +// // Specifies input symbol table action the mapper requires (see above). +// MapSymbolsAction InputSymbolsAction() const; +// // Specifies output symbol table action the mapper requires (see above). +// MapSymbolsAction OutputSymbolsAction() const; +// // This specifies the known properties of an Fst mapped by this +// // mapper. It takes as argument the input Fst's known properties. +// uint64 Properties(uint64 props) const; +// }; +// +// The ArcMap functions and classes below will use the FinalAction() +// method of the mapper to determine how to treat final weights, +// e.g. whether to add a superfinal state. They will use the Properties() +// method to set the result Fst properties. +// +// We include a various map versions below. One dimension of +// variation is whether the mapping mutates its input, writes to a +// new result Fst, or is an on-the-fly Fst. Another dimension is how +// we pass the mapper. We allow passing the mapper by pointer +// for cases that we need to change the state of the user's mapper. +// This is the case with the encode mapper, which is reused during +// decoding. We also include map versions that pass the mapper +// by value or const reference when this suffices. + + +// Maps an arc type A using a mapper function object C, passed +// by pointer. This version modifies its Fst input. +template<class A, class C> +void ArcMap(MutableFst<A> *fst, C* mapper) { + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS) + fst->SetInputSymbols(0); + + if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS) + fst->SetOutputSymbols(0); + + if (fst->Start() == kNoStateId) + return; + + uint64 props = fst->Properties(kFstProperties, false); + + MapFinalAction final_action = mapper->FinalAction(); + StateId superfinal = kNoStateId; + if (final_action == MAP_REQUIRE_SUPERFINAL) { + superfinal = fst->AddState(); + fst->SetFinal(superfinal, Weight::One()); + } + + for (StateId s = 0; s < fst->NumStates(); ++s) { + for (MutableArcIterator< MutableFst<A> > aiter(fst, s); + !aiter.Done(); aiter.Next()) { + const A &arc = aiter.Value(); + aiter.SetValue((*mapper)(arc)); + } + + switch (final_action) { + case MAP_NO_SUPERFINAL: + default: { + A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc"; + fst->SetProperties(kError, kError); + } + + fst->SetFinal(s, final_arc.weight); + break; + } + case MAP_ALLOW_SUPERFINAL: { + if (s != superfinal) { + A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + // Add a superfinal state if not already done. + if (superfinal == kNoStateId) { + superfinal = fst->AddState(); + fst->SetFinal(superfinal, Weight::One()); + } + final_arc.nextstate = superfinal; + fst->AddArc(s, final_arc); + fst->SetFinal(s, Weight::Zero()); + } else { + fst->SetFinal(s, final_arc.weight); + } + break; + } + } + case MAP_REQUIRE_SUPERFINAL: { + if (s != superfinal) { + A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0 || + final_arc.weight != Weight::Zero()) + fst->AddArc(s, A(final_arc.ilabel, final_arc.olabel, + final_arc.weight, superfinal)); + fst->SetFinal(s, Weight::Zero()); + } + break; + } + } + } + fst->SetProperties(mapper->Properties(props), kFstProperties); +} + + +// Maps an arc type A using a mapper function object C, passed +// by value. This version modifies its Fst input. +template<class A, class C> +void ArcMap(MutableFst<A> *fst, C mapper) { + ArcMap(fst, &mapper); +} + + +// Maps an arc type A to an arc type B using mapper function +// object C, passed by pointer. This version writes the mapped +// input Fst to an output MutableFst. +template<class A, class B, class C> +void ArcMap(const Fst<A> &ifst, MutableFst<B> *ofst, C* mapper) { + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + ofst->DeleteStates(); + + if (mapper->InputSymbolsAction() == MAP_COPY_SYMBOLS) + ofst->SetInputSymbols(ifst.InputSymbols()); + else if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS) + ofst->SetInputSymbols(0); + + if (mapper->OutputSymbolsAction() == MAP_COPY_SYMBOLS) + ofst->SetOutputSymbols(ifst.OutputSymbols()); + else if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS) + ofst->SetOutputSymbols(0); + + uint64 iprops = ifst.Properties(kCopyProperties, false); + + if (ifst.Start() == kNoStateId) { + if (iprops & kError) ofst->SetProperties(kError, kError); + return; + } + + MapFinalAction final_action = mapper->FinalAction(); + if (ifst.Properties(kExpanded, false)) { + ofst->ReserveStates(CountStates(ifst) + + final_action == MAP_NO_SUPERFINAL ? 0 : 1); + } + + // Add all states. + for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next()) + ofst->AddState(); + + StateId superfinal = kNoStateId; + if (final_action == MAP_REQUIRE_SUPERFINAL) { + superfinal = ofst->AddState(); + ofst->SetFinal(superfinal, B::Weight::One()); + } + for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next()) { + StateId s = siter.Value(); + if (s == ifst.Start()) + ofst->SetStart(s); + + ofst->ReserveArcs(s, ifst.NumArcs(s)); + for (ArcIterator< Fst<A> > aiter(ifst, s); !aiter.Done(); aiter.Next()) + ofst->AddArc(s, (*mapper)(aiter.Value())); + + switch (final_action) { + case MAP_NO_SUPERFINAL: + default: { + B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc"; + ofst->SetProperties(kError, kError); + } + ofst->SetFinal(s, final_arc.weight); + break; + } + case MAP_ALLOW_SUPERFINAL: { + B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + // Add a superfinal state if not already done. + if (superfinal == kNoStateId) { + superfinal = ofst->AddState(); + ofst->SetFinal(superfinal, B::Weight::One()); + } + final_arc.nextstate = superfinal; + ofst->AddArc(s, final_arc); + ofst->SetFinal(s, B::Weight::Zero()); + } else { + ofst->SetFinal(s, final_arc.weight); + } + break; + } + case MAP_REQUIRE_SUPERFINAL: { + B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0 || + final_arc.weight != B::Weight::Zero()) + ofst->AddArc(s, B(final_arc.ilabel, final_arc.olabel, + final_arc.weight, superfinal)); + ofst->SetFinal(s, B::Weight::Zero()); + break; + } + } + } + uint64 oprops = ofst->Properties(kFstProperties, false); + ofst->SetProperties(mapper->Properties(iprops) | oprops, kFstProperties); +} + +// Maps an arc type A to an arc type B using mapper function +// object C, passed by value. This version writes the mapped input +// Fst to an output MutableFst. +template<class A, class B, class C> +void ArcMap(const Fst<A> &ifst, MutableFst<B> *ofst, C mapper) { + ArcMap(ifst, ofst, &mapper); +} + + +struct ArcMapFstOptions : public CacheOptions { + // ArcMapFst default caching behaviour is to do no caching. Most + // mappers are cheap and therefore we save memory by not doing + // caching. + ArcMapFstOptions() : CacheOptions(true, 0) {} + ArcMapFstOptions(const CacheOptions& opts) : CacheOptions(opts) {} +}; + + +template <class A, class B, class C> class ArcMapFst; + +// Implementation of delayed ArcMapFst. +template <class A, class B, class C> +class ArcMapFstImpl : public CacheImpl<B> { + public: + using FstImpl<B>::SetType; + using FstImpl<B>::SetProperties; + using FstImpl<B>::SetInputSymbols; + using FstImpl<B>::SetOutputSymbols; + + using VectorFstBaseImpl<typename CacheImpl<B>::State>::NumStates; + + using CacheImpl<B>::PushArc; + using CacheImpl<B>::HasArcs; + using CacheImpl<B>::HasFinal; + using CacheImpl<B>::HasStart; + using CacheImpl<B>::SetArcs; + using CacheImpl<B>::SetFinal; + using CacheImpl<B>::SetStart; + + friend class StateIterator< ArcMapFst<A, B, C> >; + + typedef B Arc; + typedef typename B::Weight Weight; + typedef typename B::StateId StateId; + + ArcMapFstImpl(const Fst<A> &fst, const C &mapper, + const ArcMapFstOptions& opts) + : CacheImpl<B>(opts), + fst_(fst.Copy()), + mapper_(new C(mapper)), + own_mapper_(true), + superfinal_(kNoStateId), + nstates_(0) { + Init(); + } + + ArcMapFstImpl(const Fst<A> &fst, C *mapper, + const ArcMapFstOptions& opts) + : CacheImpl<B>(opts), + fst_(fst.Copy()), + mapper_(mapper), + own_mapper_(false), + superfinal_(kNoStateId), + nstates_(0) { + Init(); + } + + ArcMapFstImpl(const ArcMapFstImpl<A, B, C> &impl) + : CacheImpl<B>(impl), + fst_(impl.fst_->Copy(true)), + mapper_(new C(*impl.mapper_)), + own_mapper_(true), + superfinal_(kNoStateId), + nstates_(0) { + Init(); + } + + ~ArcMapFstImpl() { + delete fst_; + if (own_mapper_) delete mapper_; + } + + StateId Start() { + if (!HasStart()) + SetStart(FindOState(fst_->Start())); + return CacheImpl<B>::Start(); + } + + Weight Final(StateId s) { + if (!HasFinal(s)) { + switch (final_action_) { + case MAP_NO_SUPERFINAL: + default: { + B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)), + kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + FSTERROR() << "ArcMapFst: non-zero arc labels for superfinal arc"; + SetProperties(kError, kError); + } + SetFinal(s, final_arc.weight); + break; + } + case MAP_ALLOW_SUPERFINAL: { + if (s == superfinal_) { + SetFinal(s, Weight::One()); + } else { + B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)), + kNoStateId)); + if (final_arc.ilabel == 0 && final_arc.olabel == 0) + SetFinal(s, final_arc.weight); + else + SetFinal(s, Weight::Zero()); + } + break; + } + case MAP_REQUIRE_SUPERFINAL: { + SetFinal(s, s == superfinal_ ? Weight::One() : Weight::Zero()); + break; + } + } + } + return CacheImpl<B>::Final(s); + } + + size_t NumArcs(StateId s) { + if (!HasArcs(s)) + Expand(s); + return CacheImpl<B>::NumArcs(s); + } + + size_t NumInputEpsilons(StateId s) { + if (!HasArcs(s)) + Expand(s); + return CacheImpl<B>::NumInputEpsilons(s); + } + + size_t NumOutputEpsilons(StateId s) { + if (!HasArcs(s)) + Expand(s); + return CacheImpl<B>::NumOutputEpsilons(s); + } + + uint64 Properties() const { return Properties(kFstProperties); } + + // Set error if found; return FST impl properties. + uint64 Properties(uint64 mask) const { + if ((mask & kError) && (fst_->Properties(kError, false) || + (mapper_->Properties(0) & kError))) + SetProperties(kError, kError); + return FstImpl<Arc>::Properties(mask); + } + + void InitArcIterator(StateId s, ArcIteratorData<B> *data) { + if (!HasArcs(s)) + Expand(s); + CacheImpl<B>::InitArcIterator(s, data); + } + + void Expand(StateId s) { + // Add exiting arcs. + if (s == superfinal_) { SetArcs(s); return; } + + for (ArcIterator< Fst<A> > aiter(*fst_, FindIState(s)); + !aiter.Done(); aiter.Next()) { + A aarc(aiter.Value()); + aarc.nextstate = FindOState(aarc.nextstate); + const B& barc = (*mapper_)(aarc); + PushArc(s, barc); + } + + // Check for superfinal arcs. + if (!HasFinal(s) || Final(s) == Weight::Zero()) + switch (final_action_) { + case MAP_NO_SUPERFINAL: + default: + break; + case MAP_ALLOW_SUPERFINAL: { + B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)), + kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + if (superfinal_ == kNoStateId) + superfinal_ = nstates_++; + final_arc.nextstate = superfinal_; + PushArc(s, final_arc); + } + break; + } + case MAP_REQUIRE_SUPERFINAL: { + B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)), + kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0 || + final_arc.weight != B::Weight::Zero()) + PushArc(s, B(final_arc.ilabel, final_arc.olabel, + final_arc.weight, superfinal_)); + break; + } + } + SetArcs(s); + } + + private: + void Init() { + SetType("map"); + + if (mapper_->InputSymbolsAction() == MAP_COPY_SYMBOLS) + SetInputSymbols(fst_->InputSymbols()); + else if (mapper_->InputSymbolsAction() == MAP_CLEAR_SYMBOLS) + SetInputSymbols(0); + + if (mapper_->OutputSymbolsAction() == MAP_COPY_SYMBOLS) + SetOutputSymbols(fst_->OutputSymbols()); + else if (mapper_->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS) + SetOutputSymbols(0); + + if (fst_->Start() == kNoStateId) { + final_action_ = MAP_NO_SUPERFINAL; + SetProperties(kNullProperties); + } else { + final_action_ = mapper_->FinalAction(); + uint64 props = fst_->Properties(kCopyProperties, false); + SetProperties(mapper_->Properties(props)); + if (final_action_ == MAP_REQUIRE_SUPERFINAL) + superfinal_ = 0; + } + } + + // Maps from output state to input state. + StateId FindIState(StateId s) { + if (superfinal_ == kNoStateId || s < superfinal_) + return s; + else + return s - 1; + } + + // Maps from input state to output state. + StateId FindOState(StateId is) { + StateId os; + if (superfinal_ == kNoStateId || is < superfinal_) + os = is; + else + os = is + 1; + + if (os >= nstates_) + nstates_ = os + 1; + + return os; + } + + + const Fst<A> *fst_; + C* mapper_; + bool own_mapper_; + MapFinalAction final_action_; + + StateId superfinal_; + StateId nstates_; + + void operator=(const ArcMapFstImpl<A, B, C> &); // disallow +}; + + +// Maps an arc type A to an arc type B using Mapper function object +// C. This version is a delayed Fst. +template <class A, class B, class C> +class ArcMapFst : public ImplToFst< ArcMapFstImpl<A, B, C> > { + public: + friend class ArcIterator< ArcMapFst<A, B, C> >; + friend class StateIterator< ArcMapFst<A, B, C> >; + + typedef B Arc; + typedef typename B::Weight Weight; + typedef typename B::StateId StateId; + typedef CacheState<B> State; + typedef ArcMapFstImpl<A, B, C> Impl; + + ArcMapFst(const Fst<A> &fst, const C &mapper, const ArcMapFstOptions& opts) + : ImplToFst<Impl>(new Impl(fst, mapper, opts)) {} + + ArcMapFst(const Fst<A> &fst, C* mapper, const ArcMapFstOptions& opts) + : ImplToFst<Impl>(new Impl(fst, mapper, opts)) {} + + ArcMapFst(const Fst<A> &fst, const C &mapper) + : ImplToFst<Impl>(new Impl(fst, mapper, ArcMapFstOptions())) {} + + ArcMapFst(const Fst<A> &fst, C* mapper) + : ImplToFst<Impl>(new Impl(fst, mapper, ArcMapFstOptions())) {} + + // See Fst<>::Copy() for doc. + ArcMapFst(const ArcMapFst<A, B, C> &fst, bool safe = false) + : ImplToFst<Impl>(fst, safe) {} + + // Get a copy of this ArcMapFst. See Fst<>::Copy() for further doc. + virtual ArcMapFst<A, B, C> *Copy(bool safe = false) const { + return new ArcMapFst<A, B, C>(*this, safe); + } + + virtual inline void InitStateIterator(StateIteratorData<B> *data) const; + + virtual void InitArcIterator(StateId s, ArcIteratorData<B> *data) const { + GetImpl()->InitArcIterator(s, data); + } + + private: + // Makes visible to friends. + Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); } + + void operator=(const ArcMapFst<A, B, C> &fst); // disallow +}; + + +// Specialization for ArcMapFst. +template<class A, class B, class C> +class StateIterator< ArcMapFst<A, B, C> > : public StateIteratorBase<B> { + public: + typedef typename B::StateId StateId; + + explicit StateIterator(const ArcMapFst<A, B, C> &fst) + : impl_(fst.GetImpl()), siter_(*impl_->fst_), s_(0), + superfinal_(impl_->final_action_ == MAP_REQUIRE_SUPERFINAL) + { CheckSuperfinal(); } + + bool Done() const { return siter_.Done() && !superfinal_; } + + StateId Value() const { return s_; } + + void Next() { + ++s_; + if (!siter_.Done()) { + siter_.Next(); + CheckSuperfinal(); + } + else if (superfinal_) + superfinal_ = false; + } + + void Reset() { + s_ = 0; + siter_.Reset(); + superfinal_ = impl_->final_action_ == MAP_REQUIRE_SUPERFINAL; + CheckSuperfinal(); + } + + private: + // This allows base-class virtual access to non-virtual derived- + // class members of the same name. It makes the derived class more + // efficient to use but unsafe to further derive. + bool Done_() const { return Done(); } + StateId Value_() const { return Value(); } + void Next_() { Next(); } + void Reset_() { Reset(); } + + void CheckSuperfinal() { + if (impl_->final_action_ != MAP_ALLOW_SUPERFINAL || superfinal_) + return; + if (!siter_.Done()) { + B final_arc = (*impl_->mapper_)(A(0, 0, impl_->fst_->Final(s_), + kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) + superfinal_ = true; + } + } + + const ArcMapFstImpl<A, B, C> *impl_; + StateIterator< Fst<A> > siter_; + StateId s_; + bool superfinal_; // true if there is a superfinal state and not done + + DISALLOW_COPY_AND_ASSIGN(StateIterator); +}; + + +// Specialization for ArcMapFst. +template <class A, class B, class C> +class ArcIterator< ArcMapFst<A, B, C> > + : public CacheArcIterator< ArcMapFst<A, B, C> > { + public: + typedef typename A::StateId StateId; + + ArcIterator(const ArcMapFst<A, B, C> &fst, StateId s) + : CacheArcIterator< ArcMapFst<A, B, C> >(fst.GetImpl(), s) { + if (!fst.GetImpl()->HasArcs(s)) + fst.GetImpl()->Expand(s); + } + + private: + DISALLOW_COPY_AND_ASSIGN(ArcIterator); +}; + +template <class A, class B, class C> inline +void ArcMapFst<A, B, C>::InitStateIterator(StateIteratorData<B> *data) + const { + data->base = new StateIterator< ArcMapFst<A, B, C> >(*this); +} + + +// +// Utility Mappers +// + +// Mapper that returns its input. +template <class A> +struct IdentityArcMapper { + typedef A FromArc; + typedef A ToArc; + + A operator()(const A &arc) const { return arc; } + + MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;} + + uint64 Properties(uint64 props) const { return props; } +}; + + +// Mapper that returns its input with final states redirected to +// a single super-final state. +template <class A> +struct SuperFinalMapper { + typedef A FromArc; + typedef A ToArc; + + A operator()(const A &arc) const { return arc; } + + MapFinalAction FinalAction() const { return MAP_REQUIRE_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;} + + uint64 Properties(uint64 props) const { + return props & kAddSuperFinalProperties; + } +}; + + +// Mapper that leaves labels and nextstate unchanged and constructs a new weight +// from the underlying value of the arc weight. Requires that there is a +// WeightConvert class specialization that converts the weights. +template <class A, class B> +class WeightConvertMapper { + public: + typedef A FromArc; + typedef B ToArc; + typedef typename FromArc::Weight FromWeight; + typedef typename ToArc::Weight ToWeight; + + ToArc operator()(const FromArc &arc) const { + return ToArc(arc.ilabel, arc.olabel, + convert_weight_(arc.weight), arc.nextstate); + } + + MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;} + + uint64 Properties(uint64 props) const { return props; } + + private: + WeightConvert<FromWeight, ToWeight> convert_weight_; +}; + +// Non-precision-changing weight conversions. +// Consider using more efficient Cast (fst.h) instead. +typedef WeightConvertMapper<StdArc, LogArc> StdToLogMapper; +typedef WeightConvertMapper<LogArc, StdArc> LogToStdMapper; + +// Precision-changing weight conversions. +typedef WeightConvertMapper<StdArc, Log64Arc> StdToLog64Mapper; +typedef WeightConvertMapper<LogArc, Log64Arc> LogToLog64Mapper; +typedef WeightConvertMapper<Log64Arc, StdArc> Log64ToStdMapper; +typedef WeightConvertMapper<Log64Arc, LogArc> Log64ToLogMapper; + +// Mapper from A to GallicArc<A>. +template <class A, StringType S = STRING_LEFT> +struct ToGallicMapper { + typedef A FromArc; + typedef GallicArc<A, S> ToArc; + + typedef StringWeight<typename A::Label, S> SW; + typedef typename A::Weight AW; + typedef typename GallicArc<A, S>::Weight GW; + + ToArc operator()(const A &arc) const { + // 'Super-final' arc. + if (arc.nextstate == kNoStateId && arc.weight != AW::Zero()) + return ToArc(0, 0, GW(SW::One(), arc.weight), kNoStateId); + // 'Super-non-final' arc. + else if (arc.nextstate == kNoStateId) + return ToArc(0, 0, GW(SW::Zero(), arc.weight), kNoStateId); + // Epsilon label. + else if (arc.olabel == 0) + return ToArc(arc.ilabel, arc.ilabel, + GW(SW::One(), arc.weight), arc.nextstate); + // Regular label. + else + return ToArc(arc.ilabel, arc.ilabel, + GW(SW(arc.olabel), arc.weight), arc.nextstate); + } + + MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;} + + uint64 Properties(uint64 props) const { + return ProjectProperties(props, true) & kWeightInvariantProperties; + } +}; + + +// Mapper from GallicArc<A> to A. +template <class A, StringType S = STRING_LEFT> +struct FromGallicMapper { + typedef GallicArc<A, S> FromArc; + typedef A ToArc; + + typedef typename A::Label Label; + typedef StringWeight<Label, S> SW; + typedef typename A::Weight AW; + typedef typename GallicArc<A, S>::Weight GW; + + FromGallicMapper(Label superfinal_label = 0) + : superfinal_label_(superfinal_label), error_(false) {} + + A operator()(const FromArc &arc) const { + // 'Super-non-final' arc. + if (arc.nextstate == kNoStateId && arc.weight == GW::Zero()) + return A(arc.ilabel, 0, AW::Zero(), kNoStateId); + + SW w1 = arc.weight.Value1(); + AW w2 = arc.weight.Value2(); + StringWeightIterator<Label, S> iter1(w1); + + Label l = w1.Size() == 1 ? iter1.Value() : 0; + + if (l == kStringInfinity || l == kStringBad || + arc.ilabel != arc.olabel || w1.Size() > 1) { + FSTERROR() << "FromGallicMapper: unrepesentable weight"; + error_ = true; + } + + if (arc.ilabel == 0 && l != 0 && arc.nextstate == kNoStateId) + return A(superfinal_label_, l, w2, arc.nextstate); + else + return A(arc.ilabel, l, w2, arc.nextstate); + } + + MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;} + + uint64 Properties(uint64 inprops) const { + uint64 outprops = inprops & kOLabelInvariantProperties & + kWeightInvariantProperties & kAddSuperFinalProperties; + if (error_) + outprops |= kError; + return outprops; + } + + private: + Label superfinal_label_; + mutable bool error_; +}; + + +// Mapper from GallicArc<A> to A. +template <class A, StringType S = STRING_LEFT> +struct GallicToNewSymbolsMapper { + typedef GallicArc<A, S> FromArc; + typedef A ToArc; + + typedef typename A::StateId StateId; + typedef typename A::Label Label; + typedef StringWeight<Label, S> SW; + typedef typename A::Weight AW; + typedef typename GallicArc<A, S>::Weight GW; + + GallicToNewSymbolsMapper(MutableFst<ToArc> *fst) + : fst_(fst), lmax_(0), osymbols_(fst->OutputSymbols()), + isymbols_(0), error_(false) { + fst_->DeleteStates(); + state_ = fst_->AddState(); + fst_->SetStart(state_); + fst_->SetFinal(state_, AW::One()); + if (osymbols_) { + string name = osymbols_->Name() + "_from_gallic"; + fst_->SetInputSymbols(new SymbolTable(name)); + isymbols_ = fst_->MutableInputSymbols(); + isymbols_->AddSymbol(osymbols_->Find((int64) 0), 0); + } else { + fst_->SetInputSymbols(0); + } + } + + A operator()(const FromArc &arc) { + // 'Super-non-final' arc. + if (arc.nextstate == kNoStateId && arc.weight == GW::Zero()) + return A(arc.ilabel, 0, AW::Zero(), kNoStateId); + + SW w1 = arc.weight.Value1(); + AW w2 = arc.weight.Value2(); + Label l; + + if (w1.Size() == 0) { + l = 0; + } else { + typename Map::iterator miter = map_.find(w1); + if (miter != map_.end()) { + l = (*miter).second; + } else { + l = ++lmax_; + map_.insert(pair<const SW, Label>(w1, l)); + StringWeightIterator<Label, S> iter1(w1); + StateId n; + string s; + for(size_t i = 0, p = state_; + i < w1.Size(); + ++i, iter1.Next(), p = n) { + n = i == w1.Size() - 1 ? state_ : fst_->AddState(); + fst_->AddArc(p, ToArc(i ? 0 : l, iter1.Value(), AW::One(), n)); + if (isymbols_) { + if (i) s = s + "_"; + s = s + osymbols_->Find(iter1.Value()); + } + } + if (isymbols_) + isymbols_->AddSymbol(s, l); + } + } + + if (l == kStringInfinity || l == kStringBad || arc.ilabel != arc.olabel) { + FSTERROR() << "GallicToNewSymbolMapper: unrepesentable weight"; + error_ = true; + } + + return A(arc.ilabel, l, w2, arc.nextstate); + } + + MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; } + + uint64 Properties(uint64 inprops) const { + uint64 outprops = inprops & kOLabelInvariantProperties & + kWeightInvariantProperties & kAddSuperFinalProperties; + if (error_) + outprops |= kError; + return outprops; + } + + private: + class StringKey { + public: + size_t operator()(const SW &x) const { + return x.Hash(); + } + }; + + typedef unordered_map<SW, Label, StringKey> Map; + + MutableFst<ToArc> *fst_; + Map map_; + Label lmax_; + StateId state_; + const SymbolTable *osymbols_; + SymbolTable *isymbols_; + mutable bool error_; + + DISALLOW_COPY_AND_ASSIGN(GallicToNewSymbolsMapper); +}; + + +// Mapper to add a constant to all weights. +template <class A> +struct PlusMapper { + typedef A FromArc; + typedef A ToArc; + typedef typename A::Weight Weight; + + explicit PlusMapper(Weight w) : weight_(w) {} + + A operator()(const A &arc) const { + if (arc.weight == Weight::Zero()) + return arc; + Weight w = Plus(arc.weight, weight_); + return A(arc.ilabel, arc.olabel, w, arc.nextstate); + } + + MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;} + + uint64 Properties(uint64 props) const { + return props & kWeightInvariantProperties; + } + + private: + + + + Weight weight_; +}; + + +// Mapper to (right) multiply a constant to all weights. +template <class A> +struct TimesMapper { + typedef A FromArc; + typedef A ToArc; + typedef typename A::Weight Weight; + + explicit TimesMapper(Weight w) : weight_(w) {} + + A operator()(const A &arc) const { + if (arc.weight == Weight::Zero()) + return arc; + Weight w = Times(arc.weight, weight_); + return A(arc.ilabel, arc.olabel, w, arc.nextstate); + } + + MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } + + MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; } + + MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;} + + uint64 Properties(uint64 props) const { + return props & kWeightInvariantProperties; + } + + private: + Weight weight_; +}; + + +// Mapper to reciprocate all non-Zero() weigh |