diff options
author | Determinant <[email protected]> | 2015-08-14 11:51:42 +0800 |
---|---|---|
committer | Determinant <[email protected]> | 2015-08-14 11:51:42 +0800 |
commit | 96a32415ab43377cf1575bd3f4f2980f58028209 (patch) | |
tree | 30a2d92d73e8f40ac87b79f6f56e227bfc4eea6e /kaldi_io/src/tools/openfst/include/fst/concat.h | |
parent | c177a7549bd90670af4b29fa813ddea32cfe0f78 (diff) |
add implementation for kaldi io (by ymz)
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/concat.h')
-rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/concat.h | 246 |
1 files changed, 246 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/concat.h b/kaldi_io/src/tools/openfst/include/fst/concat.h new file mode 100644 index 0000000..8500d50 --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/concat.h @@ -0,0 +1,246 @@ +// 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: [email protected] (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__ |