| // 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 <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() weights. |
| template <class A> |
| struct InvertWeightMapper { |
| typedef A FromArc; |
| typedef A ToArc; |
| typedef typename A::Weight Weight; |
| |
| A operator()(const A &arc) const { |
| if (arc.weight == Weight::Zero()) |
| return arc; |
| Weight w = Divide(Weight::One(), arc.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; |
| } |
| }; |
| |
| |
| // Mapper to map all non-Zero() weights to One(). |
| template <class A, class B = A> |
| struct RmWeightMapper { |
| typedef A FromArc; |
| typedef B ToArc; |
| typedef typename FromArc::Weight FromWeight; |
| typedef typename ToArc::Weight ToWeight; |
| |
| B operator()(const A &arc) const { |
| ToWeight w = arc.weight != FromWeight::Zero() ? |
| ToWeight::One() : ToWeight::Zero(); |
| return B(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) | kUnweighted; |
| } |
| }; |
| |
| |
| // Mapper to quantize all weights. |
| template <class A, class B = A> |
| struct QuantizeMapper { |
| typedef A FromArc; |
| typedef B ToArc; |
| typedef typename FromArc::Weight FromWeight; |
| typedef typename ToArc::Weight ToWeight; |
| |
| QuantizeMapper() : delta_(kDelta) {} |
| |
| explicit QuantizeMapper(float d) : delta_(d) {} |
| |
| B operator()(const A &arc) const { |
| ToWeight w = arc.weight.Quantize(delta_); |
| return B(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: |
| float delta_; |
| }; |
| |
| |
| // Mapper from A to B under the assumption: |
| // B::Weight = A::Weight::ReverseWeight |
| // B::Label == A::Label |
| // B::StateId == A::StateId |
| // The weight is reversed, while the label and nextstate preserved |
| // in the mapping. |
| template <class A, class B> |
| struct ReverseWeightMapper { |
| typedef A FromArc; |
| typedef B ToArc; |
| |
| B operator()(const A &arc) const { |
| return B(arc.ilabel, arc.olabel, arc.weight.Reverse(), 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; } |
| }; |
| |
| } // namespace fst |
| |
| #endif // FST_LIB_ARC_MAP_H__ |