| // concat.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 |
| // Functions and classes to compute the concat of two FSTs. |
| |
| #ifndef FST_LIB_CONCAT_H__ |
| #define FST_LIB_CONCAT_H__ |
| |
| #include <vector> |
| using std::vector; |
| #include <algorithm> |
| |
| #include <fst/mutable-fst.h> |
| #include <fst/rational.h> |
| |
| |
| namespace fst { |
| |
| // Computes the concatenation (product) of two FSTs. If FST1 |
| // transduces string x to y with weight a and FST2 transduces string w |
| // to v with weight b, then their concatenation transduces string xw |
| // to yv with Times(a, b). |
| // |
| // This version modifies its MutableFst argument (in first position). |
| // |
| // Complexity: |
| // - Time: O(V1 + V2 + E2) |
| // - Space: O(V1 + V2 + E2) |
| // where Vi = # of states and Ei = # of arcs of the ith FST. |
| // |
| template<class Arc> |
| void Concat(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) { |
| typedef typename Arc::StateId StateId; |
| typedef typename Arc::Label Label; |
| typedef typename Arc::Weight Weight; |
| |
| // TODO(riley): restore when voice actions issues fixed |
| // Check that the symbol table are compatible |
| if (!CompatSymbols(fst1->InputSymbols(), fst2.InputSymbols()) || |
| !CompatSymbols(fst1->OutputSymbols(), fst2.OutputSymbols())) { |
| LOG(ERROR) << "Concat: input/output symbol tables of 1st argument " |
| << "do not match input/output symbol tables of 2nd argument"; |
| // fst1->SetProperties(kError, kError); |
| // return; |
| } |
| |
| uint64 props1 = fst1->Properties(kFstProperties, false); |
| uint64 props2 = fst2.Properties(kFstProperties, false); |
| |
| StateId start1 = fst1->Start(); |
| if (start1 == kNoStateId) { |
| if (props2 & kError) fst1->SetProperties(kError, kError); |
| return; |
| } |
| |
| StateId numstates1 = fst1->NumStates(); |
| if (fst2.Properties(kExpanded, false)) |
| fst1->ReserveStates(numstates1 + CountStates(fst2)); |
| |
| for (StateIterator< Fst<Arc> > siter2(fst2); |
| !siter2.Done(); |
| siter2.Next()) { |
| StateId s1 = fst1->AddState(); |
| StateId s2 = siter2.Value(); |
| fst1->SetFinal(s1, fst2.Final(s2)); |
| fst1->ReserveArcs(s1, fst2.NumArcs(s2)); |
| for (ArcIterator< Fst<Arc> > aiter(fst2, s2); |
| !aiter.Done(); |
| aiter.Next()) { |
| Arc arc = aiter.Value(); |
| arc.nextstate += numstates1; |
| fst1->AddArc(s1, arc); |
| } |
| } |
| |
| StateId start2 = fst2.Start(); |
| for (StateId s1 = 0; s1 < numstates1; ++s1) { |
| Weight final = fst1->Final(s1); |
| if (final != Weight::Zero()) { |
| fst1->SetFinal(s1, Weight::Zero()); |
| if (start2 != kNoStateId) |
| fst1->AddArc(s1, Arc(0, 0, final, start2 + numstates1)); |
| } |
| } |
| if (start2 != kNoStateId) |
| fst1->SetProperties(ConcatProperties(props1, props2), kFstProperties); |
| } |
| |
| // Computes the concatentation of two FSTs. This version modifies its |
| // MutableFst argument (in second position). |
| // |
| // Complexity: |
| // - Time: O(V1 + E1) |
| // - Space: O(V1 + E1) |
| // where Vi = # of states and Ei = # of arcs of the ith FST. |
| // |
| template<class Arc> |
| void Concat(const Fst<Arc> &fst1, MutableFst<Arc> *fst2) { |
| typedef typename Arc::StateId StateId; |
| typedef typename Arc::Label Label; |
| typedef typename Arc::Weight Weight; |
| |
| // Check that the symbol table are compatible |
| if (!CompatSymbols(fst1.InputSymbols(), fst2->InputSymbols()) || |
| !CompatSymbols(fst1.OutputSymbols(), fst2->OutputSymbols())) { |
| LOG(ERROR) << "Concat: input/output symbol tables of 1st argument " |
| << "do not match input/output symbol tables of 2nd argument"; |
| // fst2->SetProperties(kError, kError); |
| // return; |
| } |
| |
| uint64 props1 = fst1.Properties(kFstProperties, false); |
| uint64 props2 = fst2->Properties(kFstProperties, false); |
| |
| StateId start2 = fst2->Start(); |
| if (start2 == kNoStateId) { |
| if (props1 & kError) fst2->SetProperties(kError, kError); |
| return; |
| } |
| |
| StateId numstates2 = fst2->NumStates(); |
| if (fst1.Properties(kExpanded, false)) |
| fst2->ReserveStates(numstates2 + CountStates(fst1)); |
| |
| for (StateIterator< Fst<Arc> > siter(fst1); |
| !siter.Done(); |
| siter.Next()) { |
| StateId s1 = siter.Value(); |
| StateId s2 = fst2->AddState(); |
| Weight final = fst1.Final(s1); |
| fst2->ReserveArcs(s2, fst1.NumArcs(s1) + (final != Weight::Zero() ? 1 : 0)); |
| if (final != Weight::Zero()) |
| fst2->AddArc(s2, Arc(0, 0, final, start2)); |
| for (ArcIterator< Fst<Arc> > aiter(fst1, s1); |
| !aiter.Done(); |
| aiter.Next()) { |
| Arc arc = aiter.Value(); |
| arc.nextstate += numstates2; |
| fst2->AddArc(s2, arc); |
| } |
| } |
| StateId start1 = fst1.Start(); |
| fst2->SetStart(start1 == kNoStateId ? fst2->AddState() : start1 + numstates2); |
| if (start1 != kNoStateId) |
| fst2->SetProperties(ConcatProperties(props1, props2), kFstProperties); |
| } |
| |
| |
| // Computes the concatentation of two FSTs. This version modifies its |
| // RationalFst input (in first position). |
| template<class Arc> |
| void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) { |
| fst1->GetImpl()->AddConcat(fst2, true); |
| } |
| |
| // Computes the concatentation of two FSTs. This version modifies its |
| // RationalFst input (in second position). |
| template<class Arc> |
| void Concat(const Fst<Arc> &fst1, RationalFst<Arc> *fst2) { |
| fst2->GetImpl()->AddConcat(fst1, false); |
| } |
| |
| typedef RationalFstOptions ConcatFstOptions; |
| |
| |
| // Computes the concatenation (product) of two FSTs; this version is a |
| // delayed Fst. If FST1 transduces string x to y with weight a and FST2 |
| // transduces string w to v with weight b, then their concatenation |
| // transduces string xw to yv with Times(a, b). |
| // |
| // Complexity: |
| // - Time: O(v1 + e1 + v2 + e2), |
| // - Space: O(v1 + v2) |
| // where vi = # of states visited and ei = # of arcs visited of the |
| // ith FST. Constant time and space to visit an input state or arc is |
| // assumed and exclusive of caching. |
| template <class A> |
| class ConcatFst : public RationalFst<A> { |
| public: |
| using ImplToFst< RationalFstImpl<A> >::GetImpl; |
| |
| typedef A Arc; |
| typedef typename A::Weight Weight; |
| typedef typename A::StateId StateId; |
| |
| ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2) { |
| GetImpl()->InitConcat(fst1, fst2); |
| } |
| |
| ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2, |
| const ConcatFstOptions &opts) : RationalFst<A>(opts) { |
| GetImpl()->InitConcat(fst1, fst2); |
| } |
| |
| // See Fst<>::Copy() for doc. |
| ConcatFst(const ConcatFst<A> &fst, bool safe = false) |
| : RationalFst<A>(fst, safe) {} |
| |
| // Get a copy of this ConcatFst. See Fst<>::Copy() for further doc. |
| virtual ConcatFst<A> *Copy(bool safe = false) const { |
| return new ConcatFst<A>(*this, safe); |
| } |
| }; |
| |
| |
| // Specialization for ConcatFst. |
| template <class A> |
| class StateIterator< ConcatFst<A> > : public StateIterator< RationalFst<A> > { |
| public: |
| explicit StateIterator(const ConcatFst<A> &fst) |
| : StateIterator< RationalFst<A> >(fst) {} |
| }; |
| |
| |
| // Specialization for ConcatFst. |
| template <class A> |
| class ArcIterator< ConcatFst<A> > : public ArcIterator< RationalFst<A> > { |
| public: |
| typedef typename A::StateId StateId; |
| |
| ArcIterator(const ConcatFst<A> &fst, StateId s) |
| : ArcIterator< RationalFst<A> >(fst, s) {} |
| }; |
| |
| |
| // Useful alias when using StdArc. |
| typedef ConcatFst<StdArc> StdConcatFst; |
| |
| } // namespace fst |
| |
| #endif // FST_LIB_CONCAT_H__ |