1// concat.h 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14// 15// 16// \file 17// Functions and classes to compute the concat of two FSTs. 18 19#ifndef FST_LIB_CONCAT_H__ 20#define FST_LIB_CONCAT_H__ 21 22#include <algorithm> 23 24#include "fst/lib/mutable-fst.h" 25#include "fst/lib/rational.h" 26 27namespace fst { 28 29// Computes the concatenation (product) of two FSTs; this version 30// modifies its MutableFst argument. If FST1 transduces string x to y 31// with weight a and FST2 transduces string w to v with weight b, then 32// their concatenation transduces string xw to yv with Times(a, b). 33// 34// Complexity: 35// - Time: O(V1 + V2 + E2) 36// - Space: O(V1 + V2 + E2) 37// where Vi = # of states and Ei = # of arcs of the ith FST. 38template<class Arc> 39void Concat(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) { 40 typedef typename Arc::StateId StateId; 41 typedef typename Arc::Label Label; 42 typedef typename Arc::Weight Weight; 43 44 StateId start1 = fst1->Start(); 45 if (start1 == kNoStateId) 46 return; 47 48 uint64 props1 = fst1->Properties(kFstProperties, false); 49 uint64 props2 = fst2.Properties(kFstProperties, false); 50 51 StateId numstates1= fst1->NumStates(); 52 53 for (StateIterator< Fst<Arc> > siter2(fst2); 54 !siter2.Done(); 55 siter2.Next()) { 56 StateId s1 = fst1->AddState(); 57 StateId s2 = siter2.Value(); 58 fst1->SetFinal(s1, fst2.Final(s2)); 59 for (ArcIterator< Fst<Arc> > aiter(fst2, s2); 60 !aiter.Done(); 61 aiter.Next()) { 62 Arc arc = aiter.Value(); 63 arc.nextstate += numstates1; 64 fst1->AddArc(s1, arc); 65 } 66 } 67 68 StateId start2 = fst2.Start(); 69 for (StateId s1 = 0; s1 < numstates1; ++s1) { 70 Weight final = fst1->Final(s1); 71 if (final != Weight::Zero()) { 72 fst1->SetFinal(s1, Weight::Zero()); 73 if (start2 != kNoStateId) 74 fst1->AddArc(s1, Arc(0, 0, final, start2 + numstates1)); 75 } 76 } 77 if (start2 != kNoStateId) 78 fst1->SetProperties(ConcatProperties(props1, props2), kFstProperties); 79} 80 81 82// Computes the concatentation of two FSTs. This version modifies its 83// RationalFst input. 84template<class Arc> 85void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) { 86 fst1->Impl()->AddConcat(fst2); 87} 88 89 90typedef RationalFstOptions ConcatFstOptions; 91 92 93// Computes the concatenation (product) of two FSTs; this version is a 94// delayed Fst. If FST1 transduces string x to y with weight a and FST2 95// transduces string w to v with weight b, then their concatenation 96// transduces string xw to yv with Times(a, b). 97// 98// Complexity: 99// - Time: O(v1 + e1 + v2 + e2), 100// - Space: O(v1 + v2) 101// where vi = # of states visited and ei = # of arcs visited of the 102// ith FST. Constant time and space to visit an input state or arc is 103// assumed and exclusive of caching. 104template <class A> 105class ConcatFst : public RationalFst<A> { 106 public: 107 using RationalFst<A>::Impl; 108 109 typedef A Arc; 110 typedef typename A::Weight Weight; 111 typedef typename A::StateId StateId; 112 113 ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2) { 114 Impl()->InitConcat(fst1, fst2); 115 } 116 117 ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2, 118 const ConcatFstOptions &opts) : RationalFst<A>(opts) { 119 Impl()->InitConcat(fst1, fst2); 120 } 121 122 ConcatFst(const ConcatFst<A> &fst) : RationalFst<A>(fst) {} 123 124 virtual ConcatFst<A> *Copy() const { return new ConcatFst<A>(*this); } 125}; 126 127 128// Specialization for ConcatFst. 129template <class A> 130class StateIterator< ConcatFst<A> > : public StateIterator< RationalFst<A> > { 131 public: 132 explicit StateIterator(const ConcatFst<A> &fst) 133 : StateIterator< RationalFst<A> >(fst) {} 134}; 135 136 137// Specialization for ConcatFst. 138template <class A> 139class ArcIterator< ConcatFst<A> > : public ArcIterator< RationalFst<A> > { 140 public: 141 typedef typename A::StateId StateId; 142 143 ArcIterator(const ConcatFst<A> &fst, StateId s) 144 : ArcIterator< RationalFst<A> >(fst, s) {} 145}; 146 147 148// Useful alias when using StdArc. 149typedef ConcatFst<StdArc> StdConcatFst; 150 151} // namespace fst 152 153#endif // FST_LIB_CONCAT_H__ 154