summaryrefslogtreecommitdiff
path: root/kaldi_io/src/tools/openfst/include/fst/state-reachable.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/state-reachable.h
parentc177a7549bd90670af4b29fa813ddea32cfe0f78 (diff)
add implementation for kaldi io (by ymz)
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/state-reachable.h')
-rw-r--r--kaldi_io/src/tools/openfst/include/fst/state-reachable.h198
1 files changed, 198 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/state-reachable.h b/kaldi_io/src/tools/openfst/include/fst/state-reachable.h
new file mode 100644
index 0000000..6d0c971
--- /dev/null
+++ b/kaldi_io/src/tools/openfst/include/fst/state-reachable.h
@@ -0,0 +1,198 @@
+// state-reachable.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
+// Class to determine whether a given (final) state can be reached from some
+// other given state.
+
+#ifndef FST_LIB_STATE_REACHABLE_H__
+#define FST_LIB_STATE_REACHABLE_H__
+
+#include <vector>
+using std::vector;
+
+#include <fst/dfs-visit.h>
+#include <fst/fst.h>
+#include <fst/interval-set.h>
+
+
+namespace fst {
+
+// Computes the (final) states reachable from a given state in an FST.
+// After this visitor has been called, a final state f can be reached
+// from a state s iff (*isets)[s].Member(state2index[f]) is true, where
+// (*isets[s]) is a set of half-open inteval of final state indices
+// and state2index[f] maps from a final state to its index.
+//
+// If state2index is empty, it is filled-in with suitable indices.
+// If it is non-empty, those indices are used; in this case, the
+// final states must have out-degree 0.
+template <class A, typename I = typename A::StateId>
+class IntervalReachVisitor {
+ public:
+ typedef typename A::StateId StateId;
+ typedef typename A::Label Label;
+ typedef typename A::Weight Weight;
+ typedef typename IntervalSet<I>::Interval Interval;
+
+ IntervalReachVisitor(const Fst<A> &fst,
+ vector< IntervalSet<I> > *isets,
+ vector<I> *state2index)
+ : fst_(fst),
+ isets_(isets),
+ state2index_(state2index),
+ index_(state2index->empty() ? 1 : -1),
+ error_(false) {
+ isets_->clear();
+ }
+
+ void InitVisit(const Fst<A> &fst) { error_ = false; }
+
+ bool InitState(StateId s, StateId r) {
+ while (isets_->size() <= s)
+ isets_->push_back(IntervalSet<Label>());
+ while (state2index_->size() <= s)
+ state2index_->push_back(-1);
+
+ if (fst_.Final(s) != Weight::Zero()) {
+ // Create tree interval
+ vector<Interval> *intervals = (*isets_)[s].Intervals();
+ if (index_ < 0) { // Use state2index_ map to set index
+ if (fst_.NumArcs(s) > 0) {
+ FSTERROR() << "IntervalReachVisitor: state2index map must be empty "
+ << "for this FST";
+ error_ = true;
+ return false;
+ }
+ I index = (*state2index_)[s];
+ if (index < 0) {
+ FSTERROR() << "IntervalReachVisitor: state2index map incomplete";
+ error_ = true;
+ return false;
+ }
+ intervals->push_back(Interval(index, index + 1));
+ } else { // Use pre-order index
+ intervals->push_back(Interval(index_, index_ + 1));
+ (*state2index_)[s] = index_++;
+ }
+ }
+ return true;
+ }
+
+ bool TreeArc(StateId s, const A &arc) {
+ return true;
+ }
+
+ bool BackArc(StateId s, const A &arc) {
+ FSTERROR() << "IntervalReachVisitor: cyclic input";
+ error_ = true;
+ return false;
+ }
+
+ bool ForwardOrCrossArc(StateId s, const A &arc) {
+ // Non-tree interval
+ (*isets_)[s].Union((*isets_)[arc.nextstate]);
+ return true;
+ }
+
+ void FinishState(StateId s, StateId p, const A *arc) {
+ if (index_ >= 0 && fst_.Final(s) != Weight::Zero()) {
+ vector<Interval> *intervals = (*isets_)[s].Intervals();
+ (*intervals)[0].end = index_; // Update tree interval end
+ }
+ (*isets_)[s].Normalize();
+ if (p != kNoStateId)
+ (*isets_)[p].Union((*isets_)[s]); // Propagate intervals to parent
+ }
+
+ void FinishVisit() {}
+
+ bool Error() const { return error_; }
+
+ private:
+ const Fst<A> &fst_;
+ vector< IntervalSet<I> > *isets_;
+ vector<I> *state2index_;
+ I index_;
+ bool error_;
+};
+
+
+// Tests reachability of final states from a given state. To test for
+// reachability from a state s, first do SetState(s). Then a final
+// state f can be reached from state s of FST iff Reach(f) is true.
+template <class A, typename I = typename A::StateId>
+class StateReachable {
+ public:
+ typedef A Arc;
+ typedef I Index;
+ typedef typename A::StateId StateId;
+ typedef typename A::Label Label;
+ typedef typename A::Weight Weight;
+ typedef typename IntervalSet<I>::Interval Interval;
+
+ StateReachable(const Fst<A> &fst)
+ : error_(false) {
+ IntervalReachVisitor<Arc> reach_visitor(fst, &isets_, &state2index_);
+ DfsVisit(fst, &reach_visitor);
+ if (reach_visitor.Error()) error_ = true;
+ }
+
+ StateReachable(const StateReachable<A> &reachable) {
+ FSTERROR() << "Copy constructor for state reachable class "
+ << "not yet implemented.";
+ error_ = true;
+ }
+
+ // Set current state.
+ void SetState(StateId s) { s_ = s; }
+
+ // Can reach this label from current state?
+ bool Reach(StateId s) {
+ if (s >= state2index_.size())
+ return false;
+
+ I i = state2index_[s];
+ if (i < 0) {
+ FSTERROR() << "StateReachable: state non-final: " << s;
+ error_ = true;
+ return false;
+ }
+ return isets_[s_].Member(i);
+ }
+
+ // Access to the state-to-index mapping. Unassigned states have index -1.
+ vector<I> &State2Index() { return state2index_; }
+
+ // Access to the interval sets. These specify the reachability
+ // to the final states as intervals of the final state indices.
+ const vector< IntervalSet<I> > &IntervalSets() { return isets_; }
+
+ bool Error() const { return error_; }
+
+ private:
+ StateId s_; // Current state
+ vector< IntervalSet<I> > isets_; // Interval sets per state
+ vector<I> state2index_; // Finds index for a final state
+ bool error_;
+
+ void operator=(const StateReachable<A> &); // Disallow
+};
+
+} // namespace fst
+
+#endif // FST_LIB_STATE_REACHABLE_H__