summaryrefslogtreecommitdiff
path: root/kaldi_io/src/tools/openfst/include/fst/closure.h
diff options
context:
space:
mode:
authorDeterminant <[email protected]>2015-08-14 11:51:42 +0800
committerDeterminant <[email protected]>2015-08-14 11:51:42 +0800
commit96a32415ab43377cf1575bd3f4f2980f58028209 (patch)
tree30a2d92d73e8f40ac87b79f6f56e227bfc4eea6e /kaldi_io/src/tools/openfst/include/fst/closure.h
parentc177a7549bd90670af4b29fa813ddea32cfe0f78 (diff)
add implementation for kaldi io (by ymz)
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/closure.h')
-rw-r--r--kaldi_io/src/tools/openfst/include/fst/closure.h155
1 files changed, 155 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/closure.h b/kaldi_io/src/tools/openfst/include/fst/closure.h
new file mode 100644
index 0000000..541562b
--- /dev/null
+++ b/kaldi_io/src/tools/openfst/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: [email protected] (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__