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) --- .../src/tools/openfst/include/fst/synchronize.h | 457 +++++++++++++++++++++ 1 file changed, 457 insertions(+) create mode 100644 kaldi_io/src/tools/openfst/include/fst/synchronize.h (limited to 'kaldi_io/src/tools/openfst/include/fst/synchronize.h') diff --git a/kaldi_io/src/tools/openfst/include/fst/synchronize.h b/kaldi_io/src/tools/openfst/include/fst/synchronize.h new file mode 100644 index 0000000..9582926 --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/synchronize.h @@ -0,0 +1,457 @@ +// synchronize.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 +// Synchronize an FST with bounded delay. + +#ifndef FST_LIB_SYNCHRONIZE_H__ +#define FST_LIB_SYNCHRONIZE_H__ + +#include +#include +using std::tr1::unordered_map; +using std::tr1::unordered_multimap; +#include +using std::tr1::unordered_set; +using std::tr1::unordered_multiset; +#include +#include +using std::pair; using std::make_pair; +#include +using std::vector; + +#include +#include + + +namespace fst { + +typedef CacheOptions SynchronizeFstOptions; + + +// Implementation class for SynchronizeFst +template +class SynchronizeFstImpl + : 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 A Arc; + typedef typename A::Label Label; + typedef typename A::Weight Weight; + typedef typename A::StateId StateId; + + typedef basic_string &fst, const SynchronizeFstOptions &opts) + : CacheImpl(opts), fst_(fst.Copy()) { + SetType("synchronize"); + uint64 props = fst.Properties(kFstProperties, false); + SetProperties(SynchronizeProperties(props), kCopyProperties); + + SetInputSymbols(fst.InputSymbols()); + SetOutputSymbols(fst.OutputSymbols()); + } + + SynchronizeFstImpl(const SynchronizeFstImpl &impl) + : CacheImpl(impl), + fst_(impl.fst_->Copy(true)) { + SetType("synchronize"); + SetProperties(impl.Properties(), kCopyProperties); + SetInputSymbols(impl.InputSymbols()); + SetOutputSymbols(impl.OutputSymbols()); + } + + ~SynchronizeFstImpl() { + delete fst_; + // Extract pointers from the hash set + vector strings; + typename StringSet::iterator it = string_set_.begin(); + for (; it != string_set_.end(); ++it) + strings.push_back(*it); + // Free the extracted pointers + for (size_t i = 0; i < strings.size(); ++i) + delete strings[i]; + } + + StateId Start() { + if (!HasStart()) { + StateId s = fst_->Start(); + if (s == kNoStateId) + return kNoStateId; + const String *empty = FindString(new String()); + StateId start = FindState(Element(fst_->Start(), empty, empty)); + SetStart(start); + } + return CacheImpl::Start(); + } + + Weight Final(StateId s) { + if (!HasFinal(s)) { + const Element &e = elements_[s]; + Weight w = e.state == kNoStateId ? Weight::One() : fst_->Final(e.state); + if ((w != Weight::Zero()) && (e.istring)->empty() && (e.ostring)->empty()) + SetFinal(s, w); + else + SetFinal(s, Weight::Zero()); + } + 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)) + SetProperties(kError, kError); + return FstImpl::Properties(mask); + } + + void InitArcIterator(StateId s, ArcIteratorData *data) { + if (!HasArcs(s)) + Expand(s); + CacheImpl::InitArcIterator(s, data); + } + + // Returns the first character of the string obtained by + // concatenating s and l. + Label Car(const String *s, Label l = 0) const { + if (!s->empty()) + return (*s)[0]; + else + return l; + } + + // Computes the residual string obtained by removing the first + // character in the concatenation of s and l. + const String *Cdr(const String *s, Label l = 0) { + String *r = new String(); + for (int i = 1; i < s->size(); ++i) + r->push_back((*s)[i]); + if (l && !(s->empty())) r->push_back(l); + return FindString(r); + } + + // Computes the concatenation of s and l. + const String *Concat(const String *s, Label l = 0) { + String *r = new String(); + for (int i = 0; i < s->size(); ++i) + r->push_back((*s)[i]); + if (l) r->push_back(l); + return FindString(r); + } + + // Tests if the concatenation of s and l is empty + bool Empty(const String *s, Label l = 0) const { + if (s->empty()) + return l == 0; + else + return false; + } + + // Finds the string pointed by s in the hash set. Transfers the + // pointer ownership to the hash set. + const String *FindString(const String *s) { + typename StringSet::iterator it = string_set_.find(s); + if (it != string_set_.end()) { + delete s; + return (*it); + } else { + string_set_.insert(s); + return s; + } + } + + // Finds state corresponding to an element. Creates new state + // if element not found. + StateId FindState(const Element &e) { + typename ElementMap::iterator eit = element_map_.find(e); + if (eit != element_map_.end()) { + return (*eit).second; + } else { + StateId s = elements_.size(); + elements_.push_back(e); + element_map_.insert(pair(e, s)); + return s; + } + } + + + // Computes the outgoing transitions from a state, creating new destination + // states as needed. + void Expand(StateId s) { + Element e = elements_[s]; + + if (e.state != kNoStateId) + for (ArcIterator< Fst > ait(*fst_, e.state); + !ait.Done(); + ait.Next()) { + const A &arc = ait.Value(); + if (!Empty(e.istring, arc.ilabel) && !Empty(e.ostring, arc.olabel)) { + const String *istring = Cdr(e.istring, arc.ilabel); + const String *ostring = Cdr(e.ostring, arc.olabel); + StateId d = FindState(Element(arc.nextstate, istring, ostring)); + PushArc(s, Arc(Car(e.istring, arc.ilabel), + Car(e.ostring, arc.olabel), arc.weight, d)); + } else { + const String *istring = Concat(e.istring, arc.ilabel); + const String *ostring = Concat(e.ostring, arc.olabel); + StateId d = FindState(Element(arc.nextstate, istring, ostring)); + PushArc(s, Arc(0 , 0, arc.weight, d)); + } + } + + Weight w = e.state == kNoStateId ? Weight::One() : fst_->Final(e.state); + if ((w != Weight::Zero()) && + ((e.istring)->size() + (e.ostring)->size() > 0)) { + const String *istring = Cdr(e.istring); + const String *ostring = Cdr(e.ostring); + StateId d = FindState(Element(kNoStateId, istring, ostring)); + PushArc(s, Arc(Car(e.istring), Car(e.ostring), w, d)); + } + SetArcs(s); + } + + private: + // Equality function for Elements, assume strings have been hashed. + class ElementEqual { + public: + bool operator()(const Element &x, const Element &y) const { + return x.state == y.state && + x.istring == y.istring && + x.ostring == y.ostring; + } + }; + + // Hash function for Elements to Fst states. + class ElementKey { + public: + size_t operator()(const Element &x) const { + size_t key = x.state; + key = (key << 1) ^ (x.istring)->size(); + for (size_t i = 0; i < (x.istring)->size(); ++i) + key = (key << 1) ^ (*x.istring)[i]; + key = (key << 1) ^ (x.ostring)->size(); + for (size_t i = 0; i < (x.ostring)->size(); ++i) + key = (key << 1) ^ (*x.ostring)[i]; + return key; + } + }; + + // Equality function for strings + class StringEqual { + public: + bool operator()(const String * const &x, const String * const &y) const { + if (x->size() != y->size()) return false; + for (size_t i = 0; i < x->size(); ++i) + if ((*x)[i] != (*y)[i]) return false; + return true; + } + }; + + // Hash function for set of strings + class StringKey{ + public: + size_t operator()(const String * const & x) const { + size_t key = x->size(); + for (size_t i = 0; i < x->size(); ++i) + key = (key << 1) ^ (*x)[i]; + return key; + } + }; + + + typedef unordered_map ElementMap; + typedef unordered_set StringSet; + + const Fst *fst_; + vector elements_; // mapping Fst state to Elements + ElementMap element_map_; // mapping Elements to Fst state + StringSet string_set_; + + void operator=(const SynchronizeFstImpl &); // disallow +}; + + +// Synchronizes a transducer. This version is a delayed Fst. The +// result will be an equivalent FST that has the property that during +// the traversal of a path, the delay is either zero or strictly +// increasing, where the delay is the difference between the number of +// non-epsilon output labels and input labels along the path. +// +// For the algorithm to terminate, the input transducer must have +// bounded delay, i.e., the delay of every cycle must be zero. +// +// Complexity: +// - A has bounded delay: exponential +// - A does not have bounded delay: does not terminate +// +// References: +// - Mehryar Mohri. Edit-Distance of Weighted Automata: General +// Definitions and Algorithms, International Journal of Computer +// Science, 14(6): 957-982 (2003). +// +// This class attaches interface to implementation and handles +// reference counting, delegating most methods to ImplToFst. +template +class SynchronizeFst : public ImplToFst< SynchronizeFstImpl > { + public: + friend class ArcIterator< SynchronizeFst >; + friend class StateIterator< SynchronizeFst >; + + typedef A Arc; + typedef typename A::Weight Weight; + typedef typename A::StateId StateId; + typedef CacheState State; + typedef SynchronizeFstImpl Impl; + + SynchronizeFst(const Fst &fst) + : ImplToFst(new Impl(fst, SynchronizeFstOptions())) {} + + SynchronizeFst(const Fst &fst, const SynchronizeFstOptions &opts) + : ImplToFst(new Impl(fst, opts)) {} + + // See Fst<>::Copy() for doc. + SynchronizeFst(const SynchronizeFst &fst, bool safe = false) + : ImplToFst(fst, safe) {} + + // Get a copy of this SynchronizeFst. See Fst<>::Copy() for further doc. + virtual SynchronizeFst *Copy(bool safe = false) const { + return new SynchronizeFst(*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 SynchronizeFst &fst); // Disallow +}; + + +// Specialization for SynchronizeFst. +template +class StateIterator< SynchronizeFst > + : public CacheStateIterator< SynchronizeFst > { + public: + explicit StateIterator(const SynchronizeFst &fst) + : CacheStateIterator< SynchronizeFst >(fst, fst.GetImpl()) {} +}; + + +// Specialization for SynchronizeFst. +template +class ArcIterator< SynchronizeFst > + : public CacheArcIterator< SynchronizeFst > { + public: + typedef typename A::StateId StateId; + + ArcIterator(const SynchronizeFst &fst, StateId s) + : CacheArcIterator< SynchronizeFst >(fst.GetImpl(), s) { + if (!fst.GetImpl()->HasArcs(s)) + fst.GetImpl()->Expand(s); + } + + private: + DISALLOW_COPY_AND_ASSIGN(ArcIterator); +}; + + +template inline +void SynchronizeFst::InitStateIterator(StateIteratorData *data) const +{ + data->base = new StateIterator< SynchronizeFst >(*this); +} + + + +// Synchronizes a transducer. This version writes the synchronized +// result to a MutableFst. The result will be an equivalent FST that +// has the property that during the traversal of a path, the delay is +// either zero or strictly increasing, where the delay is the +// difference between the number of non-epsilon output labels and +// input labels along the path. +// +// For the algorithm to terminate, the input transducer must have +// bounded delay, i.e., the delay of every cycle must be zero. +// +// Complexity: +// - A has bounded delay: exponential +// - A does not have bounded delay: does not terminate +// +// References: +// - Mehryar Mohri. Edit-Distance of Weighted Automata: General +// Definitions and Algorithms, International Journal of Computer +// Science, 14(6): 957-982 (2003). +template +void Synchronize(const Fst &ifst, MutableFst *ofst) { + SynchronizeFstOptions opts; + opts.gc_limit = 0; // Cache only the last state for fastest copy. + *ofst = SynchronizeFst(ifst, opts); +} + +} // namespace fst + +#endif // FST_LIB_SYNCHRONIZE_H__ -- cgit v1.2.3-70-g09d2