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/closure.h | |
parent | a92766f0a6ba4fac46cd6fd3856ef20c3b204f0d (diff) | |
download | openfst-jb-mr1-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/closure.h')
-rw-r--r-- | src/include/fst/closure.h | 155 |
1 files changed, 155 insertions, 0 deletions
diff --git a/src/include/fst/closure.h b/src/include/fst/closure.h new file mode 100644 index 0000000..541562b --- /dev/null +++ b/src/include/fst/closure.h @@ -0,0 +1,155 @@ +// closure.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 concatenative closure of an Fst. + +#ifndef FST_LIB_CLOSURE_H__ +#define FST_LIB_CLOSURE_H__ + +#include <vector> +using std::vector; +#include <algorithm> + +#include <fst/mutable-fst.h> +#include <fst/rational.h> + + +namespace fst { + +// Computes the concatenative closure. This version modifies its +// MutableFst input. If FST transduces string x to y with weight a, +// then the closure transduces x to y with weight a, xx to yy with +// weight Times(a, a), xxx to yyy with with Times(Times(a, a), a), +// etc. If closure_type == CLOSURE_STAR, then the empty string is +// transduced to itself with weight Weight::One() as well. +// +// Complexity: +// - Time: O(V) +// - Space: O(V) +// where V = # of states. +template<class Arc> +void Closure(MutableFst<Arc> *fst, ClosureType closure_type) { + typedef typename Arc::StateId StateId; + typedef typename Arc::Label Label; + typedef typename Arc::Weight Weight; + + uint64 props = fst->Properties(kFstProperties, false); + StateId start = fst->Start(); + for (StateIterator< MutableFst<Arc> > siter(*fst); + !siter.Done(); + siter.Next()) { + StateId s = siter.Value(); + Weight final = fst->Final(s); + if (final != Weight::Zero()) + fst->AddArc(s, Arc(0, 0, final, start)); + } + if (closure_type == CLOSURE_STAR) { + fst->ReserveStates(fst->NumStates() + 1); + StateId nstart = fst->AddState(); + fst->SetStart(nstart); + fst->SetFinal(nstart, Weight::One()); + if (start != kNoLabel) + fst->AddArc(nstart, Arc(0, 0, Weight::One(), start)); + } + fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR), + kFstProperties); +} + +// Computes the concatenative closure. This version modifies its +// RationalFst input. +template<class Arc> +void Closure(RationalFst<Arc> *fst, ClosureType closure_type) { + fst->GetImpl()->AddClosure(closure_type); +} + + +struct ClosureFstOptions : RationalFstOptions { + ClosureType type; + + ClosureFstOptions(const RationalFstOptions &opts, ClosureType t) + : RationalFstOptions(opts), type(t) {} + explicit ClosureFstOptions(ClosureType t) : type(t) {} + ClosureFstOptions() : type(CLOSURE_STAR) {} +}; + + +// Computes the concatenative closure. This version is a delayed +// Fst. If FST transduces string x to y with weight a, then the +// closure transduces x to y with weight a, xx to yy with weight +// Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If +// closure_type == CLOSURE_STAR, then The empty string is transduced +// to itself with weight Weight::One() as well. +// +// Complexity: +// - Time: O(v) +// - Space: O(v) +// where v = # of states visited. Constant time and space to visit an +// input state or arc is assumed and exclusive of caching. +template <class A> +class ClosureFst : public RationalFst<A> { + public: + using ImplToFst< RationalFstImpl<A> >::GetImpl; + + typedef A Arc; + + ClosureFst(const Fst<A> &fst, ClosureType closure_type) { + GetImpl()->InitClosure(fst, closure_type); + } + + ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts) + : RationalFst<A>(opts) { + GetImpl()->InitClosure(fst, opts.type); + } + + // See Fst<>::Copy() for doc. + ClosureFst(const ClosureFst<A> &fst, bool safe = false) + : RationalFst<A>(fst, safe) {} + + // Get a copy of this ClosureFst. See Fst<>::Copy() for further doc. + virtual ClosureFst<A> *Copy(bool safe = false) const { + return new ClosureFst<A>(*this, safe); + } +}; + + +// Specialization for ClosureFst. +template <class A> +class StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > { + public: + explicit StateIterator(const ClosureFst<A> &fst) + : StateIterator< RationalFst<A> >(fst) {} +}; + + +// Specialization for ClosureFst. +template <class A> +class ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > { + public: + typedef typename A::StateId StateId; + + ArcIterator(const ClosureFst<A> &fst, StateId s) + : ArcIterator< RationalFst<A> >(fst, s) {} +}; + + +// Useful alias when using StdArc. +typedef ClosureFst<StdArc> StdClosureFst; + +} // namespace fst + +#endif // FST_LIB_CLOSURE_H__ |