diff options
author | Ian Hodson <idh@google.com> | 2012-05-30 21:27:06 +0100 |
---|---|---|
committer | Ian Hodson <idh@google.com> | 2012-05-30 22:47:36 +0100 |
commit | f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2 (patch) | |
tree | b131ed907f9b2d5af09c0983b651e9e69bc6aab9 /src/include/fst/union.h | |
parent | a92766f0a6ba4fac46cd6fd3856ef20c3b204f0d (diff) | |
download | openfst-jb-mr1.1-release.tar.gz |
Add openfst to external, as used by GoogleTTSandroid-sdk-support_r11android-cts-4.2_r2android-cts-4.2_r1android-cts-4.1_r4android-cts-4.1_r2android-cts-4.1_r1android-4.2_r1android-4.2.2_r1.2android-4.2.2_r1.1android-4.2.2_r1android-4.2.1_r1.2android-4.2.1_r1.1android-4.2.1_r1android-4.1.2_r2.1android-4.1.2_r2android-4.1.2_r1android-4.1.1_r6.1android-4.1.1_r6android-4.1.1_r5android-4.1.1_r4android-4.1.1_r3android-4.1.1_r2android-4.1.1_r1.1android-4.1.1_r1tools_r22tools_r21jb-releasejb-mr1.1-releasejb-mr1.1-dev-plus-aospjb-mr1.1-devjb-mr1-releasejb-mr1-dev-plus-aospjb-mr1-devjb-mr0-releasejb-dev
Moved from GoogleTTS
Change-Id: I6bc6bdadaa53bd0f810b88443339f6d899502cc8
Diffstat (limited to 'src/include/fst/union.h')
-rw-r--r-- | src/include/fst/union.h | 185 |
1 files changed, 185 insertions, 0 deletions
diff --git a/src/include/fst/union.h b/src/include/fst/union.h new file mode 100644 index 0000000..a2f97fb --- /dev/null +++ b/src/include/fst/union.h @@ -0,0 +1,185 @@ +// union.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 union of two FSTs. + +#ifndef FST_LIB_UNION_H__ +#define FST_LIB_UNION_H__ + +#include <vector> +using std::vector; +#include <algorithm> + +#include <fst/mutable-fst.h> +#include <fst/rational.h> + + +namespace fst { + +// Computes the union (sum) of two FSTs. This version writes the +// union to an output MurableFst. If A transduces string x to y with +// weight a and B transduces string w to v with weight b, then their +// union transduces x to y with weight a and w to v with weight b. +// +// Complexity: +// - Time: (V2 + E2) +// - Space: O(V2 + E2) +// where Vi = # of states and Ei = # of arcs of the ith FST. +template <class Arc> +void Union(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) << "Union: input/output symbol tables of 1st argument " + << "do not match input/output symbol tables of 2nd argument"; + // fst1->SetProperties(kError, kError); + // return; + } + + StateId numstates1 = fst1->NumStates(); + bool initial_acyclic1 = fst1->Properties(kInitialAcyclic, true); + uint64 props1 = fst1->Properties(kFstProperties, false); + uint64 props2 = fst2.Properties(kFstProperties, false); + + StateId start2 = fst2.Start(); + if (start2 == kNoStateId) { + if (props2 & kError) fst1->SetProperties(kError, kError); + return; + } + + if (fst2.Properties(kExpanded, false)) { + fst1->ReserveStates( + numstates1 + CountStates(fst2) + (initial_acyclic1 ? 0 : 1)); + } + + for (StateIterator< Fst<Arc> > siter(fst2); + !siter.Done(); + siter.Next()) { + StateId s1 = fst1->AddState(); + StateId s2 = siter.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 start1 = fst1->Start(); + if (start1 == kNoStateId) { + fst1->SetStart(start2); + fst1->SetProperties(props2, kCopyProperties); + return; + } + + if (initial_acyclic1) { + fst1->AddArc(start1, Arc(0, 0, Weight::One(), start2 + numstates1)); + } else { + StateId nstart1 = fst1->AddState(); + fst1->SetStart(nstart1); + fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start1)); + fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start2 + numstates1)); + } + fst1->SetProperties(UnionProperties(props1, props2), kFstProperties); +} + + +// Computes the union of two FSTs; this version modifies its +// RationalFst argument. +template<class Arc> +void Union(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) { + fst1->GetImpl()->AddUnion(fst2); +} + + +typedef RationalFstOptions UnionFstOptions; + + +// Computes the union (sum) of two FSTs. This version is a delayed +// Fst. If A transduces string x to y with weight a and B transduces +// string w to v with weight b, then their union transduces x to y +// with weight a and w to v with weight b. +// +// Complexity: +// - Time: O(v1 + e1 + v2 + e2) +// - Sapce: 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 UnionFst : public RationalFst<A> { + public: + using ImplToFst< RationalFstImpl<A> >::GetImpl; + + typedef A Arc; + typedef typename A::Weight Weight; + typedef typename A::StateId StateId; + + UnionFst(const Fst<A> &fst1, const Fst<A> &fst2) { + GetImpl()->InitUnion(fst1, fst2); + } + + UnionFst(const Fst<A> &fst1, const Fst<A> &fst2, const UnionFstOptions &opts) + : RationalFst<A>(opts) { + GetImpl()->InitUnion(fst1, fst2); + } + + // See Fst<>::Copy() for doc. + UnionFst(const UnionFst<A> &fst, bool safe = false) + : RationalFst<A>(fst, safe) {} + + // Get a copy of this UnionFst. See Fst<>::Copy() for further doc. + virtual UnionFst<A> *Copy(bool safe = false) const { + return new UnionFst<A>(*this, safe); + } +}; + + +// Specialization for UnionFst. +template <class A> +class StateIterator< UnionFst<A> > : public StateIterator< RationalFst<A> > { + public: + explicit StateIterator(const UnionFst<A> &fst) + : StateIterator< RationalFst<A> >(fst) {} +}; + + +// Specialization for UnionFst. +template <class A> +class ArcIterator< UnionFst<A> > : public ArcIterator< RationalFst<A> > { + public: + typedef typename A::StateId StateId; + + ArcIterator(const UnionFst<A> &fst, StateId s) + : ArcIterator< RationalFst<A> >(fst, s) {} +}; + + +// Useful alias when using StdArc. +typedef UnionFst<StdArc> StdUnionFst; + +} // namespace fst + +#endif // FST_LIB_UNION_H__ |