From 96a32415ab43377cf1575bd3f4f2980f58028209 Mon Sep 17 00:00:00 2001 From: Determinant Date: Fri, 14 Aug 2015 11:51:42 +0800 Subject: add implementation for kaldi io (by ymz) --- kaldi_io/src/tools/openfst/include/fst/rmepsilon.h | 600 +++++++++++++++++++++ 1 file changed, 600 insertions(+) create mode 100644 kaldi_io/src/tools/openfst/include/fst/rmepsilon.h (limited to 'kaldi_io/src/tools/openfst/include/fst/rmepsilon.h') diff --git a/kaldi_io/src/tools/openfst/include/fst/rmepsilon.h b/kaldi_io/src/tools/openfst/include/fst/rmepsilon.h new file mode 100644 index 0000000..89b8178 --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/rmepsilon.h @@ -0,0 +1,600 @@ +// rmepsilon.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: allauzen@google.com (Cyril Allauzen) +// +// \file +// Functions and classes that implemement epsilon-removal. + +#ifndef FST_LIB_RMEPSILON_H__ +#define FST_LIB_RMEPSILON_H__ + +#include +using std::tr1::unordered_map; +using std::tr1::unordered_multimap; +#include +#include +#include +#include +using std::pair; using std::make_pair; +#include +using std::vector; + +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +namespace fst { + +template +class RmEpsilonOptions + : public ShortestDistanceOptions > { + public: + typedef typename Arc::StateId StateId; + typedef typename Arc::Weight Weight; + + bool connect; // Connect output + Weight weight_threshold; // Pruning weight threshold. + StateId state_threshold; // Pruning state threshold. + + explicit RmEpsilonOptions(Queue *q, float d = kDelta, bool c = true, + Weight w = Weight::Zero(), + StateId n = kNoStateId) + : ShortestDistanceOptions< Arc, Queue, EpsilonArcFilter >( + q, EpsilonArcFilter(), kNoStateId, d), + connect(c), weight_threshold(w), state_threshold(n) {} + private: + RmEpsilonOptions(); // disallow +}; + +// Computation state of the epsilon-removal algorithm. +template +class RmEpsilonState { + public: + typedef typename Arc::Label Label; + typedef typename Arc::StateId StateId; + typedef typename Arc::Weight Weight; + + RmEpsilonState(const Fst &fst, + vector *distance, + const RmEpsilonOptions &opts) + : fst_(fst), distance_(distance), sd_state_(fst_, distance, opts, true), + expand_id_(0) {} + + // Compute arcs and final weight for state 's' + void Expand(StateId s); + + // Returns arcs of expanded state. + vector &Arcs() { return arcs_; } + + // Returns final weight of expanded state. + const Weight &Final() const { return final_; } + + // Return true if an error has occured. + bool Error() const { return sd_state_.Error(); } + + private: + static const size_t kPrime0 = 7853; + static const size_t kPrime1 = 7867; + + struct Element { + Label ilabel; + Label olabel; + StateId nextstate; + + Element() {} + + Element(Label i, Label o, StateId s) + : ilabel(i), olabel(o), nextstate(s) {} + }; + + class ElementKey { + public: + size_t operator()(const Element& e) const { + return static_cast(e.nextstate + + e.ilabel * kPrime0 + + e.olabel * kPrime1); + } + + private: + }; + + class ElementEqual { + public: + bool operator()(const Element &e1, const Element &e2) const { + return (e1.ilabel == e2.ilabel) && (e1.olabel == e2.olabel) + && (e1.nextstate == e2.nextstate); + } + }; + + typedef unordered_map, + ElementKey, ElementEqual> ElementMap; + + const Fst &fst_; + // Distance from state being expanded in epsilon-closure. + vector *distance_; + // Shortest distance algorithm computation state. + ShortestDistanceState > sd_state_; + // Maps an element 'e' to a pair 'p' corresponding to a position + // in the arcs vector of the state being expanded. 'e' corresponds + // to the position 'p.second' in the 'arcs_' vector if 'p.first' is + // equal to the state being expanded. + ElementMap element_map_; + EpsilonArcFilter eps_filter_; + stack eps_queue_; // Queue used to visit the epsilon-closure + vector visited_; // '[i] = true' if state 'i' has been visited + slist visited_states_; // List of visited states + vector arcs_; // Arcs of state being expanded + Weight final_; // Final weight of state being expanded + StateId expand_id_; // Unique ID for each call to Expand + + DISALLOW_COPY_AND_ASSIGN(RmEpsilonState); +}; + +template +const size_t RmEpsilonState::kPrime0; +template +const size_t RmEpsilonState::kPrime1; + + +template +void RmEpsilonState::Expand(typename Arc::StateId source) { + final_ = Weight::Zero(); + arcs_.clear(); + sd_state_.ShortestDistance(source); + if (sd_state_.Error()) + return; + eps_queue_.push(source); + + while (!eps_queue_.empty()) { + StateId state = eps_queue_.top(); + eps_queue_.pop(); + + while (visited_.size() <= state) visited_.push_back(false); + if (visited_[state]) continue; + visited_[state] = true; + visited_states_.push_front(state); + + for (ArcIterator< Fst > ait(fst_, state); + !ait.Done(); + ait.Next()) { + Arc arc = ait.Value(); + arc.weight = Times((*distance_)[state], arc.weight); + + if (eps_filter_(arc)) { + while (visited_.size() <= arc.nextstate) + visited_.push_back(false); + if (!visited_[arc.nextstate]) + eps_queue_.push(arc.nextstate); + } else { + Element element(arc.ilabel, arc.olabel, arc.nextstate); + typename ElementMap::iterator it = element_map_.find(element); + if (it == element_map_.end()) { + element_map_.insert( + pair > + (element, pair(expand_id_, arcs_.size()))); + arcs_.push_back(arc); + } else { + if (((*it).second).first == expand_id_) { + Weight &w = arcs_[((*it).second).second].weight; + w = Plus(w, arc.weight); + } else { + ((*it).second).first = expand_id_; + ((*it).second).second = arcs_.size(); + arcs_.push_back(arc); + } + } + } + } + final_ = Plus(final_, Times((*distance_)[state], fst_.Final(state))); + } + + while (!visited_states_.empty()) { + visited_[visited_states_.front()] = false; + visited_states_.pop_front(); + } + ++expand_id_; +} + +// Removes epsilon-transitions (when both the input and output label +// are an epsilon) from a transducer. The result will be an equivalent +// FST that has no such epsilon transitions. This version modifies +// its input. It allows fine control via the options argument; see +// below for a simpler interface. +// +// The vector 'distance' will be used to hold the shortest distances +// during the epsilon-closure computation. The state queue discipline +// and convergence delta are taken in the options argument. +template +void RmEpsilon(MutableFst *fst, + vector *distance, + const RmEpsilonOptions &opts) { + typedef typename Arc::StateId StateId; + typedef typename Arc::Weight Weight; + typedef typename Arc::Label Label; + + if (fst->Start() == kNoStateId) { + return; + } + + // 'noneps_in[s]' will be set to true iff 's' admits a non-epsilon + // incoming transition or is the start state. + vector noneps_in(fst->NumStates(), false); + noneps_in[fst->Start()] = true; + for (StateId i = 0; i < fst->NumStates(); ++i) { + for (ArcIterator > aiter(*fst, i); + !aiter.Done(); + aiter.Next()) { + if (aiter.Value().ilabel != 0 || aiter.Value().olabel != 0) + noneps_in[aiter.Value().nextstate] = true; + } + } + + // States sorted in topological order when (acyclic) or generic + // topological order (cyclic). + vector states; + states.reserve(fst->NumStates()); + + if (fst->Properties(kTopSorted, false) & kTopSorted) { + for (StateId i = 0; i < fst->NumStates(); i++) + states.push_back(i); + } else if (fst->Properties(kAcyclic, false) & kAcyclic) { + vector order; + bool acyclic; + TopOrderVisitor top_order_visitor(&order, &acyclic); + DfsVisit(*fst, &top_order_visitor, EpsilonArcFilter()); + // Sanity check: should be acyclic if property bit is set. + if(!acyclic) { + FSTERROR() << "RmEpsilon: inconsistent acyclic property bit"; + fst->SetProperties(kError, kError); + return; + } + states.resize(order.size()); + for (StateId i = 0; i < order.size(); i++) + states[order[i]] = i; + } else { + uint64 props; + vector scc; + SccVisitor scc_visitor(&scc, 0, 0, &props); + DfsVisit(*fst, &scc_visitor, EpsilonArcFilter()); + vector first(scc.size(), kNoStateId); + vector next(scc.size(), kNoStateId); + for (StateId i = 0; i < scc.size(); i++) { + if (first[scc[i]] != kNoStateId) + next[i] = first[scc[i]]; + first[scc[i]] = i; + } + for (StateId i = 0; i < first.size(); i++) + for (StateId j = first[i]; j != kNoStateId; j = next[j]) + states.push_back(j); + } + + RmEpsilonState + rmeps_state(*fst, distance, opts); + + while (!states.empty()) { + StateId state = states.back(); + states.pop_back(); + if (!noneps_in[state]) + continue; + rmeps_state.Expand(state); + fst->SetFinal(state, rmeps_state.Final()); + fst->DeleteArcs(state); + vector &arcs = rmeps_state.Arcs(); + fst->ReserveArcs(state, arcs.size()); + while (!arcs.empty()) { + fst->AddArc(state, arcs.back()); + arcs.pop_back(); + } + } + + for (StateId s = 0; s < fst->NumStates(); ++s) { + if (!noneps_in[s]) + fst->DeleteArcs(s); + } + + if(rmeps_state.Error()) + fst->SetProperties(kError, kError); + fst->SetProperties( + RmEpsilonProperties(fst->Properties(kFstProperties, false)), + kFstProperties); + + if (opts.weight_threshold != Weight::Zero() || + opts.state_threshold != kNoStateId) + Prune(fst, opts.weight_threshold, opts.state_threshold); + if (opts.connect && (opts.weight_threshold == Weight::Zero() || + opts.state_threshold != kNoStateId)) + Connect(fst); +} + +// Removes epsilon-transitions (when both the input and output label +// are an epsilon) from a transducer. The result will be an equivalent +// FST that has no such epsilon transitions. This version modifies its +// input. It has a simplified interface; see above for a version that +// allows finer control. +// +// Complexity: +// - Time: +// - Unweighted: O(V2 + V E) +// - Acyclic: O(V2 + V E) +// - Tropical semiring: O(V2 log V + V E) +// - General: exponential +// - Space: O(V E) +// where V = # of states visited, E = # of arcs. +// +// References: +// - Mehryar Mohri. Generic Epsilon-Removal and Input +// Epsilon-Normalization Algorithms for Weighted Transducers, +// "International Journal of Computer Science", 13(1):129-143 (2002). +template +void RmEpsilon(MutableFst *fst, + bool connect = true, + typename Arc::Weight weight_threshold = Arc::Weight::Zero(), + typename Arc::StateId state_threshold = kNoStateId, + float delta = kDelta) { + typedef typename Arc::StateId StateId; + typedef typename Arc::Weight Weight; + typedef typename Arc::Label Label; + + vector distance; + AutoQueue state_queue(*fst, &distance, EpsilonArcFilter()); + RmEpsilonOptions > + opts(&state_queue, delta, connect, weight_threshold, state_threshold); + + RmEpsilon(fst, &distance, opts); +} + + +struct RmEpsilonFstOptions : CacheOptions { + float delta; + + RmEpsilonFstOptions(const CacheOptions &opts, float delta = kDelta) + : CacheOptions(opts), delta(delta) {} + + explicit RmEpsilonFstOptions(float delta = kDelta) : delta(delta) {} +}; + + +// Implementation of delayed RmEpsilonFst. +template +class RmEpsilonFstImpl : public CacheImpl { + public: + using FstImpl::SetType; + using FstImpl::SetProperties; + using FstImpl::SetInputSymbols; + using FstImpl::SetOutputSymbols; + + using CacheBaseImpl< CacheState >::PushArc; + using CacheBaseImpl< CacheState >::HasArcs; + using CacheBaseImpl< CacheState >::HasFinal; + using CacheBaseImpl< CacheState >::HasStart; + using CacheBaseImpl< CacheState >::SetArcs; + using CacheBaseImpl< CacheState >::SetFinal; + using CacheBaseImpl< CacheState >::SetStart; + + typedef typename A::Label Label; + typedef typename A::Weight Weight; + typedef typename A::StateId StateId; + typedef CacheState State; + + RmEpsilonFstImpl(const Fst& fst, const RmEpsilonFstOptions &opts) + : CacheImpl(opts), + fst_(fst.Copy()), + delta_(opts.delta), + rmeps_state_( + *fst_, + &distance_, + RmEpsilonOptions >(&queue_, delta_, false)) { + SetType("rmepsilon"); + uint64 props = fst.Properties(kFstProperties, false); + SetProperties(RmEpsilonProperties(props, true), kCopyProperties); + SetInputSymbols(fst.InputSymbols()); + SetOutputSymbols(fst.OutputSymbols()); + } + + RmEpsilonFstImpl(const RmEpsilonFstImpl &impl) + : CacheImpl(impl), + fst_(impl.fst_->Copy(true)), + delta_(impl.delta_), + rmeps_state_( + *fst_, + &distance_, + RmEpsilonOptions >(&queue_, delta_, false)) { + SetType("rmepsilon"); + SetProperties(impl.Properties(), kCopyProperties); + SetInputSymbols(impl.InputSymbols()); + SetOutputSymbols(impl.OutputSymbols()); + } + + ~RmEpsilonFstImpl() { + delete fst_; + } + + StateId Start() { + if (!HasStart()) { + SetStart(fst_->Start()); + } + return CacheImpl::Start(); + } + + Weight Final(StateId s) { + if (!HasFinal(s)) { + Expand(s); + } + return CacheImpl::Final(s); + } + + size_t NumArcs(StateId s) { + if (!HasArcs(s)) + Expand(s); + return CacheImpl::NumArcs(s); + } + + size_t NumInputEpsilons(StateId s) { + if (!HasArcs(s)) + Expand(s); + return CacheImpl::NumInputEpsilons(s); + } + + size_t NumOutputEpsilons(StateId s) { + if (!HasArcs(s)) + Expand(s); + return CacheImpl::NumOutputEpsilons(s); + } + + uint64 Properties() const { return Properties(kFstProperties); } + + // Set error if found; return FST impl properties. + uint64 Properties(uint64 mask) const { + if ((mask & kError) && + (fst_->Properties(kError, false) || rmeps_state_.Error())) + SetProperties(kError, kError); + return FstImpl::Properties(mask); + } + + void InitArcIterator(StateId s, ArcIteratorData *data) { + if (!HasArcs(s)) + Expand(s); + CacheImpl::InitArcIterator(s, data); + } + + void Expand(StateId s) { + rmeps_state_.Expand(s); + SetFinal(s, rmeps_state_.Final()); + vector &arcs = rmeps_state_.Arcs(); + while (!arcs.empty()) { + PushArc(s, arcs.back()); + arcs.pop_back(); + } + SetArcs(s); + } + + private: + const Fst *fst_; + float delta_; + vector distance_; + FifoQueue queue_; + RmEpsilonState > rmeps_state_; + + void operator=(const RmEpsilonFstImpl &); // disallow +}; + + +// Removes epsilon-transitions (when both the input and output label +// are an epsilon) from a transducer. The result will be an equivalent +// FST that has no such epsilon transitions. This version is a +// delayed Fst. +// +// Complexity: +// - Time: +// - Unweighted: O(v^2 + v e) +// - General: exponential +// - Space: O(v e) +// where v = # of states visited, e = # of arcs visited. Constant time +// to visit an input state or arc is assumed and exclusive of caching. +// +// References: +// - Mehryar Mohri. Generic Epsilon-Removal and Input +// Epsilon-Normalization Algorithms for Weighted Transducers, +// "International Journal of Computer Science", 13(1):129-143 (2002). +// +// This class attaches interface to implementation and handles +// reference counting, delegating most methods to ImplToFst. +template +class RmEpsilonFst : public ImplToFst< RmEpsilonFstImpl > { + public: + friend class ArcIterator< RmEpsilonFst >; + friend class StateIterator< RmEpsilonFst >; + + typedef A Arc; + typedef typename A::StateId StateId; + typedef CacheState State; + typedef RmEpsilonFstImpl Impl; + + RmEpsilonFst(const Fst &fst) + : ImplToFst(new Impl(fst, RmEpsilonFstOptions())) {} + + RmEpsilonFst(const Fst &fst, const RmEpsilonFstOptions &opts) + : ImplToFst(new Impl(fst, opts)) {} + + // See Fst<>::Copy() for doc. + RmEpsilonFst(const RmEpsilonFst &fst, bool safe = false) + : ImplToFst(fst, safe) {} + + // Get a copy of this RmEpsilonFst. See Fst<>::Copy() for further doc. + virtual RmEpsilonFst *Copy(bool safe = false) const { + return new RmEpsilonFst(*this, safe); + } + + virtual inline void InitStateIterator(StateIteratorData *data) const; + + virtual void InitArcIterator(StateId s, ArcIteratorData *data) const { + GetImpl()->InitArcIterator(s, data); + } + + private: + // Makes visible to friends. + Impl *GetImpl() const { return ImplToFst::GetImpl(); } + + void operator=(const RmEpsilonFst &fst); // disallow +}; + +// Specialization for RmEpsilonFst. +template +class StateIterator< RmEpsilonFst > + : public CacheStateIterator< RmEpsilonFst > { + public: + explicit StateIterator(const RmEpsilonFst &fst) + : CacheStateIterator< RmEpsilonFst >(fst, fst.GetImpl()) {} +}; + + +// Specialization for RmEpsilonFst. +template +class ArcIterator< RmEpsilonFst > + : public CacheArcIterator< RmEpsilonFst > { + public: + typedef typename A::StateId StateId; + + ArcIterator(const RmEpsilonFst &fst, StateId s) + : CacheArcIterator< RmEpsilonFst >(fst.GetImpl(), s) { + if (!fst.GetImpl()->HasArcs(s)) + fst.GetImpl()->Expand(s); + } + + private: + DISALLOW_COPY_AND_ASSIGN(ArcIterator); +}; + + +template inline +void RmEpsilonFst::InitStateIterator(StateIteratorData *data) const { + data->base = new StateIterator< RmEpsilonFst >(*this); +} + + +// Useful alias when using StdArc. +typedef RmEpsilonFst StdRmEpsilonFst; + +} // namespace fst + +#endif // FST_LIB_RMEPSILON_H__ -- cgit v1.2.3