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/complement.h | 338 +++++++++++++++++++++ 1 file changed, 338 insertions(+) create mode 100644 kaldi_io/src/tools/openfst/include/fst/complement.h (limited to 'kaldi_io/src/tools/openfst/include/fst/complement.h') diff --git a/kaldi_io/src/tools/openfst/include/fst/complement.h b/kaldi_io/src/tools/openfst/include/fst/complement.h new file mode 100644 index 0000000..dacf396 --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/complement.h @@ -0,0 +1,338 @@ +// complement.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: riley@google.com (Michael Riley) +// +// \file +// Class to complement an Fst. + +#ifndef FST_LIB_COMPLEMENT_H__ +#define FST_LIB_COMPLEMENT_H__ + +#include +#include +#include +using std::vector; + +#include +#include + + +namespace fst { + +template class ComplementFst; + +// Implementation of delayed ComplementFst. The algorithm used +// completes the (deterministic) FSA and then exchanges final and +// non-final states. Completion, i.e. ensuring that all labels can be +// read from every state, is accomplished by using RHO labels, which +// match all labels that are otherwise not found leaving a state. The +// first state in the output is reserved to be a new state that is the +// destination of all RHO labels. Each remaining output state s +// corresponds to input state s - 1. The first arc in the output at +// these states is the rho label, the remaining arcs correspond to the +// input arcs. +template +class ComplementFstImpl : public FstImpl { + public: + using FstImpl::SetType; + using FstImpl::SetProperties; + using FstImpl::SetInputSymbols; + using FstImpl::SetOutputSymbols; + + friend class StateIterator< ComplementFst >; + friend class ArcIterator< ComplementFst >; + + typedef A Arc; + typedef typename A::Label Label; + typedef typename A::Weight Weight; + typedef typename A::StateId StateId; + + explicit ComplementFstImpl(const Fst &fst) : fst_(fst.Copy()) { + SetType("complement"); + uint64 props = fst.Properties(kILabelSorted, false); + SetProperties(ComplementProperties(props), kCopyProperties); + SetInputSymbols(fst.InputSymbols()); + SetOutputSymbols(fst.OutputSymbols()); + } + + ComplementFstImpl(const ComplementFstImpl &impl) + : fst_(impl.fst_->Copy()) { + SetType("complement"); + SetProperties(impl.Properties(), kCopyProperties); + SetInputSymbols(impl.InputSymbols()); + SetOutputSymbols(impl.OutputSymbols()); + } + + ~ComplementFstImpl() { delete fst_; } + + StateId Start() const { + if (Properties(kError)) + return kNoStateId; + + StateId start = fst_->Start(); + if (start != kNoStateId) + return start + 1; + else + return 0; + } + + // Exchange final and non-final states; make rho destination state final. + Weight Final(StateId s) const { + if (s == 0 || fst_->Final(s - 1) == Weight::Zero()) + return Weight::One(); + else + return Weight::Zero(); + } + + size_t NumArcs(StateId s) const { + if (s == 0) + return 1; + else + return fst_->NumArcs(s - 1) + 1; + } + + size_t NumInputEpsilons(StateId s) const { + return s == 0 ? 0 : fst_->NumInputEpsilons(s - 1); + } + + size_t NumOutputEpsilons(StateId s) const { + return s == 0 ? 0 : fst_->NumOutputEpsilons(s - 1); + } + + + 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); + } + + + private: + const Fst *fst_; + + void operator=(const ComplementFstImpl &fst); // Disallow +}; + + +// Complements an automaton. This is a library-internal operation that +// introduces a (negative) 'rho' label; use Difference/DifferenceFst in +// user code, which will not see this label. This version is a delayed Fst. +// +// This class attaches interface to implementation and handles +// reference counting, delegating most methods to ImplToFst. +template +class ComplementFst : public ImplToFst< ComplementFstImpl > { + public: + friend class StateIterator< ComplementFst >; + friend class ArcIterator< ComplementFst >; + + using ImplToFst< ComplementFstImpl >::GetImpl; + + typedef A Arc; + typedef typename A::StateId StateId; + typedef typename A::Label Label; + typedef ComplementFstImpl Impl; + + explicit ComplementFst(const Fst &fst) + : ImplToFst(new Impl(fst)) { + uint64 props = kUnweighted | kNoEpsilons | kIDeterministic | kAcceptor; + if (fst.Properties(props, true) != props) { + FSTERROR() << "ComplementFst: argument not an unweighted " + << "epsilon-free deterministic acceptor"; + GetImpl()->SetProperties(kError, kError); + } + } + + // See Fst<>::Copy() for doc. + ComplementFst(const ComplementFst &fst, bool safe = false) + : ImplToFst(fst, safe) {} + + // Get a copy of this ComplementFst. See Fst<>::Copy() for further doc. + virtual ComplementFst *Copy(bool safe = false) const { + return new ComplementFst(*this, safe); + } + + virtual inline void InitStateIterator(StateIteratorData *data) const; + + virtual inline void InitArcIterator(StateId s, + ArcIteratorData *data) const; + + // Label that represents the rho transition. + // We use a negative value, which is thus private to the library and + // which will preserve FST label sort order. + static const Label kRhoLabel = -2; + private: + // Makes visible to friends. + Impl *GetImpl() const { return ImplToFst::GetImpl(); } + + void operator=(const ComplementFst &fst); // disallow +}; + +template const typename A::Label ComplementFst::kRhoLabel; + + +// Specialization for ComplementFst. +template +class StateIterator< ComplementFst > : public StateIteratorBase { + public: + typedef typename A::StateId StateId; + typedef typename A::Label Label; + + explicit StateIterator(const ComplementFst &fst) + : siter_(*fst.GetImpl()->fst_), s_(0) { + } + + bool Done() const { return s_ > 0 && siter_.Done(); } + + StateId Value() const { return s_; } + + void Next() { + if (s_ != 0) + siter_.Next(); + ++s_; + } + + void Reset() { + siter_.Reset(); + s_ = 0; + } + + private: + // This allows base class virtual access to non-virtual derived- + // class members of the same name. It makes the derived class more + // efficient to use but unsafe to further derive. + virtual bool Done_() const { return Done(); } + virtual StateId Value_() const { return Value(); } + virtual void Next_() { Next(); } + virtual void Reset_() { Reset(); } + + StateIterator< Fst > siter_; + StateId s_; + + DISALLOW_COPY_AND_ASSIGN(StateIterator); +}; + + +// Specialization for ComplementFst. +template +class ArcIterator< ComplementFst > : public ArcIteratorBase { + public: + typedef typename A::StateId StateId; + typedef typename A::Label Label; + typedef typename A::Weight Weight; + + ArcIterator(const ComplementFst &fst, StateId s) + : aiter_(0), s_(s), pos_(0) { + if (s_ != 0) + aiter_ = new ArcIterator< Fst >(*fst.GetImpl()->fst_, s - 1); + } + + virtual ~ArcIterator() { delete aiter_; } + + bool Done() const { + if (s_ != 0) + return pos_ > 0 && aiter_->Done(); + else + return pos_ > 0; + } + + // Adds the rho label to the rho destination state. + const A& Value() const { + if (pos_ == 0) { + arc_.ilabel = arc_.olabel = ComplementFst::kRhoLabel; + arc_.weight = Weight::One(); + arc_.nextstate = 0; + } else { + arc_ = aiter_->Value(); + ++arc_.nextstate; + } + return arc_; + } + + void Next() { + if (s_ != 0 && pos_ > 0) + aiter_->Next(); + ++pos_; + } + + size_t Position() const { + return pos_; + } + + void Reset() { + if (s_ != 0) + aiter_->Reset(); + pos_ = 0; + } + + void Seek(size_t a) { + if (s_ != 0) { + if (a == 0) { + aiter_->Reset(); + } else { + aiter_->Seek(a - 1); + } + } + pos_ = a; + } + + uint32 Flags() const { + return kArcValueFlags; + } + + void SetFlags(uint32 f, uint32 m) {} + + private: + // This allows base class virtual access to non-virtual derived- + // class members of the same name. It makes the derived class more + // efficient to use but unsafe to further derive. + virtual bool Done_() const { return Done(); } + virtual const A& Value_() const { return Value(); } + virtual void Next_() { Next(); } + virtual size_t Position_() const { return Position(); } + virtual void Reset_() { Reset(); } + virtual void Seek_(size_t a) { Seek(a); } + uint32 Flags_() const { return Flags(); } + void SetFlags_(uint32 f, uint32 m) { SetFlags(f, m); } + + ArcIterator< Fst > *aiter_; + StateId s_; + size_t pos_; + mutable A arc_; + DISALLOW_COPY_AND_ASSIGN(ArcIterator); +}; + + +template inline void +ComplementFst::InitStateIterator(StateIteratorData *data) const { + data->base = new StateIterator< ComplementFst >(*this); +} + +template inline void +ComplementFst::InitArcIterator(StateId s, ArcIteratorData *data) const { + data->base = new ArcIterator< ComplementFst >(*this, s); +} + + +// Useful alias when using StdArc. +typedef ComplementFst StdComplementFst; + +} // namespace fst + +#endif // FST_LIB_COMPLEMENT_H__ -- cgit v1.2.3-70-g09d2