add implementation for kaldi io (by ymz)

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__