diff options
author | Ted Yin <[email protected]> | 2015-08-14 17:42:26 +0800 |
---|---|---|
committer | Ted Yin <[email protected]> | 2015-08-14 17:42:26 +0800 |
commit | c3cffb58b9921d78753336421b52b9ffdaa5515c (patch) | |
tree | bfea20e97c200cf734021e3756d749c892e658a4 /kaldi_io/src/tools/openfst/include/fst/replace.h | |
parent | 10cce5f6a5c9e2f8e00d5a2a4d87c9cb7c26bf4c (diff) | |
parent | dfdd17afc2e984ec6c32ea01290f5c76309a456a (diff) |
Merge pull request #2 from yimmon/master
remove needless files
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/replace.h')
-rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/replace.h | 1453 |
1 files changed, 0 insertions, 1453 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/replace.h b/kaldi_io/src/tools/openfst/include/fst/replace.h deleted file mode 100644 index ef5f6cc..0000000 --- a/kaldi_io/src/tools/openfst/include/fst/replace.h +++ /dev/null @@ -1,1453 +0,0 @@ -// replace.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] (Johan Schalkwyk) -// -// \file -// Functions and classes for the recursive replacement of Fsts. -// - -#ifndef FST_LIB_REPLACE_H__ -#define FST_LIB_REPLACE_H__ - -#include <tr1/unordered_map> -using std::tr1::unordered_map; -using std::tr1::unordered_multimap; -#include <set> -#include <string> -#include <utility> -using std::pair; using std::make_pair; -#include <vector> -using std::vector; - -#include <fst/cache.h> -#include <fst/expanded-fst.h> -#include <fst/fst.h> -#include <fst/matcher.h> -#include <fst/replace-util.h> -#include <fst/state-table.h> -#include <fst/test-properties.h> - -namespace fst { - -// -// REPLACE STATE TUPLES AND TABLES -// -// The replace state table has the form -// -// template <class A, class P> -// class ReplaceStateTable { -// public: -// typedef A Arc; -// typedef P PrefixId; -// typedef typename A::StateId StateId; -// typedef ReplaceStateTuple<StateId, PrefixId> StateTuple; -// typedef typename A::Label Label; -// -// // Required constuctor -// ReplaceStateTable(const vector<pair<Label, const Fst<A>*> > &fst_tuples, -// Label root); -// -// // Required copy constructor that does not copy state -// ReplaceStateTable(const ReplaceStateTable<A,P> &table); -// -// // Lookup state ID by tuple. If it doesn't exist, then add it. -// StateId FindState(const StateTuple &tuple); -// -// // Lookup state tuple by ID. -// const StateTuple &Tuple(StateId id) const; -// }; - - -// \struct ReplaceStateTuple -// \brief Tuple of information that uniquely defines a state in replace -template <class S, class P> -struct ReplaceStateTuple { - typedef S StateId; - typedef P PrefixId; - - ReplaceStateTuple() - : prefix_id(-1), fst_id(kNoStateId), fst_state(kNoStateId) {} - - ReplaceStateTuple(PrefixId p, StateId f, StateId s) - : prefix_id(p), fst_id(f), fst_state(s) {} - - PrefixId prefix_id; // index in prefix table - StateId fst_id; // current fst being walked - StateId fst_state; // current state in fst being walked, not to be - // confused with the state_id of the combined fst -}; - - -// Equality of replace state tuples. -template <class S, class P> -inline bool operator==(const ReplaceStateTuple<S, P>& x, - const ReplaceStateTuple<S, P>& y) { - return x.prefix_id == y.prefix_id && - x.fst_id == y.fst_id && - x.fst_state == y.fst_state; -} - - -// \class ReplaceRootSelector -// Functor returning true for tuples corresponding to states in the root FST -template <class S, class P> -class ReplaceRootSelector { - public: - bool operator()(const ReplaceStateTuple<S, P> &tuple) const { - return tuple.prefix_id == 0; - } -}; - - -// \class ReplaceFingerprint -// Fingerprint for general replace state tuples. -template <class S, class P> -class ReplaceFingerprint { - public: - ReplaceFingerprint(const vector<uint64> *size_array) - : cumulative_size_array_(size_array) {} - - uint64 operator()(const ReplaceStateTuple<S, P> &tuple) const { - return tuple.prefix_id * (cumulative_size_array_->back()) + - cumulative_size_array_->at(tuple.fst_id - 1) + - tuple.fst_state; - } - - private: - const vector<uint64> *cumulative_size_array_; -}; - - -// \class ReplaceFstStateFingerprint -// Useful when the fst_state uniquely define the tuple. -template <class S, class P> -class ReplaceFstStateFingerprint { - public: - uint64 operator()(const ReplaceStateTuple<S, P>& tuple) const { - return tuple.fst_state; - } -}; - - -// \class ReplaceHash -// A generic hash function for replace state tuples. -template <typename S, typename P> -class ReplaceHash { - public: - size_t operator()(const ReplaceStateTuple<S, P>& t) const { - return t.prefix_id + t.fst_id * kPrime0 + t.fst_state * kPrime1; - } - private: - static const size_t kPrime0; - static const size_t kPrime1; -}; - -template <typename S, typename P> -const size_t ReplaceHash<S, P>::kPrime0 = 7853; - -template <typename S, typename P> -const size_t ReplaceHash<S, P>::kPrime1 = 7867; - -template <class A, class T> class ReplaceFstMatcher; - - -// \class VectorHashReplaceStateTable -// A two-level state table for replace. -// Warning: calls CountStates to compute the number of states of each -// component Fst. -template <class A, class P = ssize_t> -class VectorHashReplaceStateTable { - public: - typedef A Arc; - typedef typename A::StateId StateId; - typedef typename A::Label Label; - typedef P PrefixId; - typedef ReplaceStateTuple<StateId, P> StateTuple; - typedef VectorHashStateTable<ReplaceStateTuple<StateId, P>, - ReplaceRootSelector<StateId, P>, - ReplaceFstStateFingerprint<StateId, P>, - ReplaceFingerprint<StateId, P> > StateTable; - - VectorHashReplaceStateTable( - const vector<pair<Label, const Fst<A>*> > &fst_tuples, - Label root) : root_size_(0) { - cumulative_size_array_.push_back(0); - for (size_t i = 0; i < fst_tuples.size(); ++i) { - if (fst_tuples[i].first == root) { - root_size_ = CountStates(*(fst_tuples[i].second)); - cumulative_size_array_.push_back(cumulative_size_array_.back()); - } else { - cumulative_size_array_.push_back(cumulative_size_array_.back() + - CountStates(*(fst_tuples[i].second))); - } - } - state_table_ = new StateTable( - new ReplaceRootSelector<StateId, P>, - new ReplaceFstStateFingerprint<StateId, P>, - new ReplaceFingerprint<StateId, P>(&cumulative_size_array_), - root_size_, - root_size_ + cumulative_size_array_.back()); - } - - VectorHashReplaceStateTable(const VectorHashReplaceStateTable<A, P> &table) - : root_size_(table.root_size_), - cumulative_size_array_(table.cumulative_size_array_) { - state_table_ = new StateTable( - new ReplaceRootSelector<StateId, P>, - new ReplaceFstStateFingerprint<StateId, P>, - new ReplaceFingerprint<StateId, P>(&cumulative_size_array_), - root_size_, - root_size_ + cumulative_size_array_.back()); - } - - ~VectorHashReplaceStateTable() { - delete state_table_; - } - - StateId FindState(const StateTuple &tuple) { - return state_table_->FindState(tuple); - } - - const StateTuple &Tuple(StateId id) const { - return state_table_->Tuple(id); - } - - private: - StateId root_size_; - vector<uint64> cumulative_size_array_; - StateTable *state_table_; -}; - - -// \class DefaultReplaceStateTable -// Default replace state table -template <class A, class P = ssize_t> -class DefaultReplaceStateTable : public CompactHashStateTable< - ReplaceStateTuple<typename A::StateId, P>, - ReplaceHash<typename A::StateId, P> > { - public: - typedef A Arc; - typedef typename A::StateId StateId; - typedef typename A::Label Label; - typedef P PrefixId; - typedef ReplaceStateTuple<StateId, P> StateTuple; - typedef CompactHashStateTable<StateTuple, - ReplaceHash<StateId, PrefixId> > StateTable; - - using StateTable::FindState; - using StateTable::Tuple; - - DefaultReplaceStateTable( - const vector<pair<Label, const Fst<A>*> > &fst_tuples, - Label root) {} - - DefaultReplaceStateTable(const DefaultReplaceStateTable<A, P> &table) - : StateTable() {} -}; - -// -// REPLACE FST CLASS -// - -// By default ReplaceFst will copy the input label of the 'replace arc'. -// For acceptors we do not want this behaviour. Instead we need to -// create an epsilon arc when recursing into the appropriate Fst. -// The 'epsilon_on_replace' option can be used to toggle this behaviour. -template <class A, class T = DefaultReplaceStateTable<A> > -struct ReplaceFstOptions : CacheOptions { - int64 root; // root rule for expansion - bool epsilon_on_replace; - bool take_ownership; // take ownership of input Fst(s) - T* state_table; - - ReplaceFstOptions(const CacheOptions &opts, int64 r) - : CacheOptions(opts), - root(r), - epsilon_on_replace(false), - take_ownership(false), - state_table(0) {} - explicit ReplaceFstOptions(int64 r) - : root(r), - epsilon_on_replace(false), - take_ownership(false), - state_table(0) {} - ReplaceFstOptions(int64 r, bool epsilon_replace_arc) - : root(r), - epsilon_on_replace(epsilon_replace_arc), - take_ownership(false), - state_table(0) {} - ReplaceFstOptions() - : root(kNoLabel), - epsilon_on_replace(false), - take_ownership(false), - state_table(0) {} -}; - - -// \class ReplaceFstImpl -// \brief Implementation class for replace class Fst -// -// The replace implementation class supports a dynamic -// expansion of a recursive transition network represented as Fst -// with dynamic replacable arcs. -// -template <class A, class T> -class ReplaceFstImpl : public CacheImpl<A> { - friend class ReplaceFstMatcher<A, T>; - - public: - using FstImpl<A>::SetType; - using FstImpl<A>::SetProperties; - using FstImpl<A>::WriteHeader; - using FstImpl<A>::SetInputSymbols; - using FstImpl<A>::SetOutputSymbols; - using FstImpl<A>::InputSymbols; - using FstImpl<A>::OutputSymbols; - - using CacheImpl<A>::PushArc; - using CacheImpl<A>::HasArcs; - using CacheImpl<A>::HasFinal; - using CacheImpl<A>::HasStart; - using CacheImpl<A>::SetArcs; - using CacheImpl<A>::SetFinal; - using CacheImpl<A>::SetStart; - - typedef typename A::Label Label; - typedef typename A::Weight Weight; - typedef typename A::StateId StateId; - typedef CacheState<A> State; - typedef A Arc; - typedef unordered_map<Label, Label> NonTerminalHash; - - typedef T StateTable; - typedef typename T::PrefixId PrefixId; - typedef ReplaceStateTuple<StateId, PrefixId> StateTuple; - - // constructor for replace class implementation. - // \param fst_tuples array of label/fst tuples, one for each non-terminal - ReplaceFstImpl(const vector< pair<Label, const Fst<A>* > >& fst_tuples, - const ReplaceFstOptions<A, T> &opts) - : CacheImpl<A>(opts), - epsilon_on_replace_(opts.epsilon_on_replace), - state_table_(opts.state_table ? opts.state_table : - new StateTable(fst_tuples, opts.root)) { - - SetType("replace"); - - if (fst_tuples.size() > 0) { - SetInputSymbols(fst_tuples[0].second->InputSymbols()); - SetOutputSymbols(fst_tuples[0].second->OutputSymbols()); - } - - bool all_negative = true; // all nonterminals are negative? - bool dense_range = true; // all nonterminals are positive - // and form a dense range containing 1? - for (size_t i = 0; i < fst_tuples.size(); ++i) { - Label nonterminal = fst_tuples[i].first; - if (nonterminal >= 0) - all_negative = false; - if (nonterminal > fst_tuples.size() || nonterminal <= 0) - dense_range = false; - } - - vector<uint64> inprops; - bool all_ilabel_sorted = true; - bool all_olabel_sorted = true; - bool all_non_empty = true; - fst_array_.push_back(0); - for (size_t i = 0; i < fst_tuples.size(); ++i) { - Label label = fst_tuples[i].first; - const Fst<A> *fst = fst_tuples[i].second; - nonterminal_hash_[label] = fst_array_.size(); - nonterminal_set_.insert(label); - fst_array_.push_back(opts.take_ownership ? fst : fst->Copy()); - if (fst->Start() == kNoStateId) - all_non_empty = false; - if(!fst->Properties(kILabelSorted, false)) - all_ilabel_sorted = false; - if(!fst->Properties(kOLabelSorted, false)) - all_olabel_sorted = false; - inprops.push_back(fst->Properties(kCopyProperties, false)); - if (i) { - if (!CompatSymbols(InputSymbols(), fst->InputSymbols())) { - FSTERROR() << "ReplaceFstImpl: input symbols of Fst " << i - << " does not match input symbols of base Fst (0'th fst)"; - SetProperties(kError, kError); - } - if (!CompatSymbols(OutputSymbols(), fst->OutputSymbols())) { - FSTERROR() << "ReplaceFstImpl: output symbols of Fst " << i - << " does not match output symbols of base Fst " - << "(0'th fst)"; - SetProperties(kError, kError); - } - } - } - Label nonterminal = nonterminal_hash_[opts.root]; - if ((nonterminal == 0) && (fst_array_.size() > 1)) { - FSTERROR() << "ReplaceFstImpl: no Fst corresponding to root label '" - << opts.root << "' in the input tuple vector"; - SetProperties(kError, kError); - } - root_ = (nonterminal > 0) ? nonterminal : 1; - - SetProperties(ReplaceProperties(inprops, root_ - 1, epsilon_on_replace_, - all_non_empty)); - // We assume that all terminals are positive. The resulting - // ReplaceFst is known to be kILabelSorted when all sub-FSTs are - // kILabelSorted and one of the 3 following conditions is satisfied: - // 1. 'epsilon_on_replace' is false, or - // 2. all non-terminals are negative, or - // 3. all non-terninals are positive and form a dense range containing 1. - if (all_ilabel_sorted && - (!epsilon_on_replace_ || all_negative || dense_range)) - SetProperties(kILabelSorted, kILabelSorted); - // Similarly, the resulting ReplaceFst is known to be - // kOLabelSorted when all sub-FSTs are kOLabelSorted and one of - // the 2 following conditions is satisfied: - // 1. all non-terminals are negative, or - // 2. all non-terninals are positive and form a dense range containing 1. - if (all_olabel_sorted && (all_negative || dense_range)) - SetProperties(kOLabelSorted, kOLabelSorted); - - // Enable optional caching as long as sorted and all non empty. - if (Properties(kILabelSorted | kOLabelSorted) && all_non_empty) - always_cache_ = false; - else - always_cache_ = true; - VLOG(2) << "ReplaceFstImpl::ReplaceFstImpl: always_cache = " - << (always_cache_ ? "true" : "false"); - } - - ReplaceFstImpl(const ReplaceFstImpl& impl) - : CacheImpl<A>(impl), - epsilon_on_replace_(impl.epsilon_on_replace_), - always_cache_(impl.always_cache_), - state_table_(new StateTable(*(impl.state_table_))), - nonterminal_set_(impl.nonterminal_set_), - nonterminal_hash_(impl.nonterminal_hash_), - root_(impl.root_) { - SetType("replace"); - SetProperties(impl.Properties(), kCopyProperties); - SetInputSymbols(impl.InputSymbols()); - SetOutputSymbols(impl.OutputSymbols()); - fst_array_.reserve(impl.fst_array_.size()); - fst_array_.push_back(0); - for (size_t i = 1; i < impl.fst_array_.size(); ++i) { - fst_array_.push_back(impl.fst_array_[i]->Copy(true)); - } - } - - ~ReplaceFstImpl() { - VLOG(2) << "~ReplaceFstImpl: gc = " - << (CacheImpl<A>::GetCacheGc() ? "true" : "false") - << ", gc_size = " << CacheImpl<A>::GetCacheSize() - << ", gc_limit = " << CacheImpl<A>::GetCacheLimit(); - - delete state_table_; - for (size_t i = 1; i < fst_array_.size(); ++i) { - delete fst_array_[i]; - } - } - - // Computes the dependency graph of the replace class and returns - // true if the dependencies are cyclic. Cyclic dependencies will result - // in an un-expandable replace fst. - bool CyclicDependencies() const { - ReplaceUtil<A> replace_util(fst_array_, nonterminal_hash_, root_); - return replace_util.CyclicDependencies(); - } - - // Return or compute start state of replace fst - StateId Start() { - if (!HasStart()) { - if (fst_array_.size() == 1) { // no fsts defined for replace - SetStart(kNoStateId); - return kNoStateId; - } else { - const Fst<A>* fst = fst_array_[root_]; - StateId fst_start = fst->Start(); - if (fst_start == kNoStateId) // root Fst is empty - return kNoStateId; - - PrefixId prefix = GetPrefixId(StackPrefix()); - StateId start = state_table_->FindState( - StateTuple(prefix, root_, fst_start)); - SetStart(start); - return start; - } - } else { - return CacheImpl<A>::Start(); - } - } - - // return final weight of state (kInfWeight means state is not final) - Weight Final(StateId s) { - if (!HasFinal(s)) { - const StateTuple& tuple = state_table_->Tuple(s); - const StackPrefix& stack = stackprefix_array_[tuple.prefix_id]; - const Fst<A>* fst = fst_array_[tuple.fst_id]; - StateId fst_state = tuple.fst_state; - - if (fst->Final(fst_state) != Weight::Zero() && stack.Depth() == 0) - SetFinal(s, fst->Final(fst_state)); - else - SetFinal(s, Weight::Zero()); - } - return CacheImpl<A>::Final(s); - } - - size_t NumArcs(StateId s) { - if (HasArcs(s)) { // If state cached, use the cached value. - return CacheImpl<A>::NumArcs(s); - } else if (always_cache_) { // If always caching, expand and cache state. - Expand(s); - return CacheImpl<A>::NumArcs(s); - } else { // Otherwise compute the number of arcs without expanding. - StateTuple tuple = state_table_->Tuple(s); - if (tuple.fst_state == kNoStateId) - return 0; - - const Fst<A>* fst = fst_array_[tuple.fst_id]; - size_t num_arcs = fst->NumArcs(tuple.fst_state); - if (ComputeFinalArc(tuple, 0)) - num_arcs++; - - return num_arcs; - } - } - - // Returns whether a given label is a non terminal - bool IsNonTerminal(Label l) const { - // TODO(allauzen): be smarter and take advantage of - // all_dense or all_negative. - // Use also in ComputeArc, this would require changes to replace - // so that recursing into an empty fst lead to a non co-accessible - // state instead of deleting the arc as done currently. - // Current use correct, since i/olabel sorted iff all_non_empty. - typename NonTerminalHash::const_iterator it = - nonterminal_hash_.find(l); - return it != nonterminal_hash_.end(); - } - - size_t NumInputEpsilons(StateId s) { - if (HasArcs(s)) { - // If state cached, use the cached value. - return CacheImpl<A>::NumInputEpsilons(s); - } else if (always_cache_ || !Properties(kILabelSorted)) { - // If always caching or if the number of input epsilons is too expensive - // to compute without caching (i.e. not ilabel sorted), - // then expand and cache state. - Expand(s); - return CacheImpl<A>::NumInputEpsilons(s); - } else { - // Otherwise, compute the number of input epsilons without caching. - StateTuple tuple = state_table_->Tuple(s); - if (tuple.fst_state == kNoStateId) - return 0; - const Fst<A>* fst = fst_array_[tuple.fst_id]; - size_t num = 0; - if (!epsilon_on_replace_) { - // If epsilon_on_replace is false, all input epsilon arcs - // are also input epsilons arcs in the underlying machine. - fst->NumInputEpsilons(tuple.fst_state); - } else { - // Otherwise, one need to consider that all non-terminal arcs - // in the underlying machine also become input epsilon arc. - ArcIterator<Fst<A> > aiter(*fst, tuple.fst_state); - for (; !aiter.Done() && - ((aiter.Value().ilabel == 0) || - IsNonTerminal(aiter.Value().olabel)); - aiter.Next()) - ++num; - } - if (ComputeFinalArc(tuple, 0)) - num++; - return num; - } - } - - size_t NumOutputEpsilons(StateId s) { - if (HasArcs(s)) { - // If state cached, use the cached value. - return CacheImpl<A>::NumOutputEpsilons(s); - } else if(always_cache_ || !Properties(kOLabelSorted)) { - // If always caching or if the number of output epsilons is too expensive - // to compute without caching (i.e. not olabel sorted), - // then expand and cache state. - Expand(s); - return CacheImpl<A>::NumOutputEpsilons(s); - } else { - // Otherwise, compute the number of output epsilons without caching. - StateTuple tuple = state_table_->Tuple(s); - if (tuple.fst_state == kNoStateId) - return 0; - const Fst<A>* fst = fst_array_[tuple.fst_id]; - size_t num = 0; - ArcIterator<Fst<A> > aiter(*fst, tuple.fst_state); - for (; !aiter.Done() && - ((aiter.Value().olabel == 0) || - IsNonTerminal(aiter.Value().olabel)); - aiter.Next()) - ++num; - if (ComputeFinalArc(tuple, 0)) - num++; - return num; - } - } - - uint64 Properties() const { return Properties(kFstProperties); } - - // Set error if found; return FST impl properties. - uint64 Properties(uint64 mask) const { - if (mask & kError) { - for (size_t i = 1; i < fst_array_.size(); ++i) { - if (fst_array_[i]->Properties(kError, false)) - SetProperties(kError, kError); - } - } - return FstImpl<Arc>::Properties(mask); - } - - // return the base arc iterator, if arcs have not been computed yet, - // extend/recurse for new arcs. - void InitArcIterator(StateId s, ArcIteratorData<A> *data) { - if (!HasArcs(s)) - Expand(s); - CacheImpl<A>::InitArcIterator(s, data); - // TODO(allauzen): Set behaviour of generic iterator - // Warning: ArcIterator<ReplaceFst<A> >::InitCache() - // relies on current behaviour. - } - - - // Extend current state (walk arcs one level deep) - void Expand(StateId s) { - StateTuple tuple = state_table_->Tuple(s); - - // If local fst is empty - if (tuple.fst_state == kNoStateId) { - SetArcs(s); - return; - } - - ArcIterator< Fst<A> > aiter( - *(fst_array_[tuple.fst_id]), tuple.fst_state); - Arc arc; - - // Create a final arc when needed - if (ComputeFinalArc(tuple, &arc)) - PushArc(s, arc); - - // Expand all arcs leaving the state - for (;!aiter.Done(); aiter.Next()) { - if (ComputeArc(tuple, aiter.Value(), &arc)) - PushArc(s, arc); - } - - SetArcs(s); - } - - void Expand(StateId s, const StateTuple &tuple, - const ArcIteratorData<A> &data) { - // If local fst is empty - if (tuple.fst_state == kNoStateId) { - SetArcs(s); - return; - } - - ArcIterator< Fst<A> > aiter(data); - Arc arc; - - // Create a final arc when needed - if (ComputeFinalArc(tuple, &arc)) - AddArc(s, arc); - - // Expand all arcs leaving the state - for (; !aiter.Done(); aiter.Next()) { - if (ComputeArc(tuple, aiter.Value(), &arc)) - AddArc(s, arc); - } - - SetArcs(s); - } - - // If arcp == 0, only returns if a final arc is required, does not - // actually compute it. - bool ComputeFinalArc(const StateTuple &tuple, A* arcp, - uint32 flags = kArcValueFlags) { - const Fst<A>* fst = fst_array_[tuple.fst_id]; - StateId fst_state = tuple.fst_state; - if (fst_state == kNoStateId) - return false; - - // if state is final, pop up stack - const StackPrefix& stack = stackprefix_array_[tuple.prefix_id]; - if (fst->Final(fst_state) != Weight::Zero() && stack.Depth()) { - if (arcp) { - arcp->ilabel = 0; - arcp->olabel = 0; - if (flags & kArcNextStateValue) { - PrefixId prefix_id = PopPrefix(stack); - const PrefixTuple& top = stack.Top(); - arcp->nextstate = state_table_->FindState( - StateTuple(prefix_id, top.fst_id, top.nextstate)); - } - if (flags & kArcWeightValue) - arcp->weight = fst->Final(fst_state); - } - return true; - } else { - return false; - } - } - - // Compute the arc in the replace fst corresponding to a given - // in the underlying machine. Returns false if the underlying arc - // corresponds to no arc in the replace. - bool ComputeArc(const StateTuple &tuple, const A &arc, A* arcp, - uint32 flags = kArcValueFlags) { - if (!epsilon_on_replace_ && - (flags == (flags & (kArcILabelValue | kArcWeightValue)))) { - *arcp = arc; - return true; - } - - if (arc.olabel == 0) { // expand local fst - StateId nextstate = flags & kArcNextStateValue - ? state_table_->FindState( - StateTuple(tuple.prefix_id, tuple.fst_id, arc.nextstate)) - : kNoStateId; - *arcp = A(arc.ilabel, arc.olabel, arc.weight, nextstate); - } else { - // check for non terminal - typename NonTerminalHash::const_iterator it = - nonterminal_hash_.find(arc.olabel); - if (it != nonterminal_hash_.end()) { // recurse into non terminal - Label nonterminal = it->second; - const Fst<A>* nt_fst = fst_array_[nonterminal]; - PrefixId nt_prefix = PushPrefix(stackprefix_array_[tuple.prefix_id], - tuple.fst_id, arc.nextstate); - - // if start state is valid replace, else arc is implicitly - // deleted - StateId nt_start = nt_fst->Start(); - if (nt_start != kNoStateId) { - StateId nt_nextstate = flags & kArcNextStateValue - ? state_table_->FindState( - StateTuple(nt_prefix, nonterminal, nt_start)) - : kNoStateId; - Label ilabel = (epsilon_on_replace_) ? 0 : arc.ilabel; - *arcp = A(ilabel, 0, arc.weight, nt_nextstate); - } else { - return false; - } - } else { - StateId nextstate = flags & kArcNextStateValue - ? state_table_->FindState( - StateTuple(tuple.prefix_id, tuple.fst_id, arc.nextstate)) - : kNoStateId; - *arcp = A(arc.ilabel, arc.olabel, arc.weight, nextstate); - } - } - return true; - } - - // Returns the arc iterator flags supported by this Fst. - uint32 ArcIteratorFlags() const { - uint32 flags = kArcValueFlags; - if (!always_cache_) - flags |= kArcNoCache; - return flags; - } - - T* GetStateTable() const { - return state_table_; - } - - const Fst<A>* GetFst(Label fst_id) const { - return fst_array_[fst_id]; - } - - bool EpsilonOnReplace() const { return epsilon_on_replace_; } - - // private helper classes - private: - static const size_t kPrime0; - - // \class PrefixTuple - // \brief Tuple of fst_id and destination state (entry in stack prefix) - struct PrefixTuple { - PrefixTuple(Label f, StateId s) : fst_id(f), nextstate(s) {} - - Label fst_id; - StateId nextstate; - }; - - // \class StackPrefix - // \brief Container for stack prefix. - class StackPrefix { - public: - StackPrefix() {} - - // copy constructor - StackPrefix(const StackPrefix& x) : - prefix_(x.prefix_) { - } - - void Push(StateId fst_id, StateId nextstate) { - prefix_.push_back(PrefixTuple(fst_id, nextstate)); - } - - void Pop() { - prefix_.pop_back(); - } - - const PrefixTuple& Top() const { - return prefix_[prefix_.size()-1]; - } - - size_t Depth() const { - return prefix_.size(); - } - - public: - vector<PrefixTuple> prefix_; - }; - - - // \class StackPrefixEqual - // \brief Compare two stack prefix classes for equality - class StackPrefixEqual { - public: - bool operator()(const StackPrefix& x, const StackPrefix& y) const { - if (x.prefix_.size() != y.prefix_.size()) return false; - for (size_t i = 0; i < x.prefix_.size(); ++i) { - if (x.prefix_[i].fst_id != y.prefix_[i].fst_id || - x.prefix_[i].nextstate != y.prefix_[i].nextstate) return false; - } - return true; - } - }; - - // - // \class StackPrefixKey - // \brief Hash function for stack prefix to prefix id - class StackPrefixKey { - public: - size_t operator()(const StackPrefix& x) const { - size_t sum = 0; - for (size_t i = 0; i < x.prefix_.size(); ++i) { - sum += x.prefix_[i].fst_id + x.prefix_[i].nextstate*kPrime0; - } - return sum; - } - }; - - typedef unordered_map<StackPrefix, PrefixId, StackPrefixKey, StackPrefixEqual> - StackPrefixHash; - - // private methods - private: - // hash stack prefix (return unique index into stackprefix array) - PrefixId GetPrefixId(const StackPrefix& prefix) { - typename StackPrefixHash::iterator it = prefix_hash_.find(prefix); - if (it == prefix_hash_.end()) { - PrefixId prefix_id = stackprefix_array_.size(); - stackprefix_array_.push_back(prefix); - prefix_hash_[prefix] = prefix_id; - return prefix_id; - } else { - return it->second; - } - } - - // prefix id after a stack pop - PrefixId PopPrefix(StackPrefix prefix) { - prefix.Pop(); - return GetPrefixId(prefix); - } - - // prefix id after a stack push - PrefixId PushPrefix(StackPrefix prefix, Label fst_id, StateId nextstate) { - prefix.Push(fst_id, nextstate); - return GetPrefixId(prefix); - } - - - // private data - private: - // runtime options - bool epsilon_on_replace_; - bool always_cache_; // Optionally caching arc iterator disabled when true - - // state table - StateTable *state_table_; - - // cross index of unique stack prefix - // could potentially have one copy of prefix array - StackPrefixHash prefix_hash_; - vector<StackPrefix> stackprefix_array_; - - set<Label> nonterminal_set_; - NonTerminalHash nonterminal_hash_; - vector<const Fst<A>*> fst_array_; - Label root_; - - void operator=(const ReplaceFstImpl<A, T> &); // disallow -}; - - -template <class A, class T> -const size_t ReplaceFstImpl<A, T>::kPrime0 = 7853; - -// -// \class ReplaceFst -// \brief Recursivively replaces arcs in the root Fst with other Fsts. -// This version is a delayed Fst. -// -// ReplaceFst supports dynamic replacement of arcs in one Fst with -// another Fst. This replacement is recursive. ReplaceFst can be used -// to support a variety of delayed constructions such as recursive -// transition networks, union, or closure. It is constructed with an -// array of Fst(s). One Fst represents the root (or topology) -// machine. The root Fst refers to other Fsts by recursively replacing -// arcs labeled as non-terminals with the matching non-terminal -// Fst. Currently the ReplaceFst uses the output symbols of the arcs -// to determine whether the arc is a non-terminal arc or not. A -// non-terminal can be any label that is not a non-zero terminal label -// in the output alphabet. -// -// Note that the constructor uses a vector of pair<>. These correspond -// to the tuple of non-terminal Label and corresponding Fst. For example -// to implement the closure operation we need 2 Fsts. The first root -// Fst is a single Arc on the start State that self loops, it references -// the particular machine for which we are performing the closure operation. -// -// The ReplaceFst class supports an optionally caching arc iterator: -// ArcIterator< ReplaceFst<A> > -// The ReplaceFst need to be built such that it is known to be ilabel -// or olabel sorted (see usage below). -// -// Observe that Matcher<Fst<A> > will use the optionally caching arc -// iterator when available (Fst is ilabel sorted and matching on the -// input, or Fst is olabel sorted and matching on the output). -// In order to obtain the most efficient behaviour, it is recommended -// to set 'epsilon_on_replace' to false (this means constructing acceptors -// as transducers with epsilons on the input side of nonterminal arcs) -// and matching on the input side. -// -// This class attaches interface to implementation and handles -// reference counting, delegating most methods to ImplToFst. -template <class A, class T = DefaultReplaceStateTable<A> > -class ReplaceFst : public ImplToFst< ReplaceFstImpl<A, T> > { - public: - friend class ArcIterator< ReplaceFst<A, T> >; - friend class StateIterator< ReplaceFst<A, T> >; - friend class ReplaceFstMatcher<A, T>; - - typedef A Arc; - typedef typename A::Label Label; - typedef typename A::Weight Weight; - typedef typename A::StateId StateId; - typedef CacheState<A> State; - typedef ReplaceFstImpl<A, T> Impl; - - using ImplToFst<Impl>::Properties; - - ReplaceFst(const vector<pair<Label, const Fst<A>* > >& fst_array, - Label root) - : ImplToFst<Impl>(new Impl(fst_array, ReplaceFstOptions<A, T>(root))) {} - - ReplaceFst(const vector<pair<Label, const Fst<A>* > >& fst_array, - const ReplaceFstOptions<A, T> &opts) - : ImplToFst<Impl>(new Impl(fst_array, opts)) {} - - // See Fst<>::Copy() for doc. - ReplaceFst(const ReplaceFst<A, T>& fst, bool safe = false) - : ImplToFst<Impl>(fst, safe) {} - - // Get a copy of this ReplaceFst. See Fst<>::Copy() for further doc. - virtual ReplaceFst<A, T> *Copy(bool safe = false) const { - return new ReplaceFst<A, T>(*this, safe); - } - - virtual inline void InitStateIterator(StateIteratorData<A> *data) const; - - virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { - GetImpl()->InitArcIterator(s, data); - } - - virtual MatcherBase<A> *InitMatcher(MatchType match_type) const { - if ((GetImpl()->ArcIteratorFlags() & kArcNoCache) && - ((match_type == MATCH_INPUT && Properties(kILabelSorted, false)) || - (match_type == MATCH_OUTPUT && Properties(kOLabelSorted, false)))) { - return new ReplaceFstMatcher<A, T>(*this, match_type); - } - else { - VLOG(2) << "Not using replace matcher"; - return 0; - } - } - - bool CyclicDependencies() const { - return GetImpl()->CyclicDependencies(); - } - - private: - // Makes visible to friends. - Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); } - - void operator=(const ReplaceFst<A> &fst); // disallow -}; - - -// Specialization for ReplaceFst. -template<class A, class T> -class StateIterator< ReplaceFst<A, T> > - : public CacheStateIterator< ReplaceFst<A, T> > { - public: - explicit StateIterator(const ReplaceFst<A, T> &fst) - : CacheStateIterator< ReplaceFst<A, T> >(fst, fst.GetImpl()) {} - - private: - DISALLOW_COPY_AND_ASSIGN(StateIterator); -}; - - -// Specialization for ReplaceFst. -// Implements optional caching. It can be used as follows: -// -// ReplaceFst<A> replace; -// ArcIterator< ReplaceFst<A> > aiter(replace, s); -// // Note: ArcIterator< Fst<A> > is always a caching arc iterator. -// aiter.SetFlags(kArcNoCache, kArcNoCache); -// // Use the arc iterator, no arc will be cached, no state will be expanded. -// // The varied 'kArcValueFlags' can be used to decide which part -// // of arc values needs to be computed. -// aiter.SetFlags(kArcILabelValue, kArcValueFlags); -// // Only want the ilabel for this arc -// aiter.Value(); // Does not compute the destination state. -// aiter.Next(); -// aiter.SetFlags(kArcNextStateValue, kArcNextStateValue); -// // Want both ilabel and nextstate for that arc -// aiter.Value(); // Does compute the destination state and inserts it -// // in the replace state table. -// // No Arc has been cached at that point. -// -template <class A, class T> -class ArcIterator< ReplaceFst<A, T> > { - public: - typedef A Arc; - typedef typename A::StateId StateId; - - ArcIterator(const ReplaceFst<A, T> &fst, StateId s) - : fst_(fst), state_(s), pos_(0), offset_(0), flags_(0), arcs_(0), - data_flags_(0), final_flags_(0) { - cache_data_.ref_count = 0; - local_data_.ref_count = 0; - - // If FST does not support optional caching, force caching. - if(!(fst_.GetImpl()->ArcIteratorFlags() & kArcNoCache) && - !(fst_.GetImpl()->HasArcs(state_))) - fst_.GetImpl()->Expand(state_); - - // If state is already cached, use cached arcs array. - if (fst_.GetImpl()->HasArcs(state_)) { - (fst_.GetImpl())->template CacheImpl<A>::InitArcIterator(state_, - &cache_data_); - num_arcs_ = cache_data_.narcs; - arcs_ = cache_data_.arcs; // 'arcs_' is a ptr to the cached arcs. - data_flags_ = kArcValueFlags; // All the arc member values are valid. - } else { // Otherwise delay decision until Value() is called. - tuple_ = fst_.GetImpl()->GetStateTable()->Tuple(state_); - if (tuple_.fst_state == kNoStateId) { - num_arcs_ = 0; - } else { - // The decision to cache or not to cache has been defered - // until Value() or SetFlags() is called. However, the arc - // iterator is set up now to be ready for non-caching in order - // to keep the Value() method simple and efficient. - const Fst<A>* fst = fst_.GetImpl()->GetFst(tuple_.fst_id); - fst->InitArcIterator(tuple_.fst_state, &local_data_); - // 'arcs_' is a pointer to the arcs in the underlying machine. - arcs_ = local_data_.arcs; - // Compute the final arc (but not its destination state) - // if a final arc is required. - bool has_final_arc = fst_.GetImpl()->ComputeFinalArc( - tuple_, - &final_arc_, - kArcValueFlags & ~kArcNextStateValue); - // Set the arc value flags that hold for 'final_arc_'. - final_flags_ = kArcValueFlags & ~kArcNextStateValue; - // Compute the number of arcs. - num_arcs_ = local_data_.narcs; - if (has_final_arc) - ++num_arcs_; - // Set the offset between the underlying arc positions and - // the positions in the arc iterator. - offset_ = num_arcs_ - local_data_.narcs; - // Defers the decision to cache or not until Value() or - // SetFlags() is called. - data_flags_ = 0; - } - } - } - - ~ArcIterator() { - if (cache_data_.ref_count) - --(*cache_data_.ref_count); - if (local_data_.ref_count) - --(*local_data_.ref_count); - } - - void ExpandAndCache() const { - // TODO(allauzen): revisit this - // fst_.GetImpl()->Expand(state_, tuple_, local_data_); - // (fst_.GetImpl())->CacheImpl<A>*>::InitArcIterator(state_, - // &cache_data_); - // - fst_.InitArcIterator(state_, &cache_data_); // Expand and cache state. - arcs_ = cache_data_.arcs; // 'arcs_' is a pointer to the cached arcs. - data_flags_ = kArcValueFlags; // All the arc member values are valid. - offset_ = 0; // No offset - - } - - void Init() { - if (flags_ & kArcNoCache) { // If caching is disabled - // 'arcs_' is a pointer to the arcs in the underlying machine. - arcs_ = local_data_.arcs; - // Set the arcs value flags that hold for 'arcs_'. - data_flags_ = kArcWeightValue; - if (!fst_.GetImpl()->EpsilonOnReplace()) - data_flags_ |= kArcILabelValue; - // Set the offset between the underlying arc positions and - // the positions in the arc iterator. - offset_ = num_arcs_ - local_data_.narcs; - } else { // Otherwise, expand and cache - ExpandAndCache(); - } - } - - bool Done() const { return pos_ >= num_arcs_; } - - const A& Value() const { - // If 'data_flags_' was set to 0, non-caching was not requested - if (!data_flags_) { - // TODO(allauzen): revisit this. - if (flags_ & kArcNoCache) { - // Should never happen. - FSTERROR() << "ReplaceFst: inconsistent arc iterator flags"; - } - ExpandAndCache(); // Expand and cache. - } - - if (pos_ - offset_ >= 0) { // The requested arc is not the 'final' arc. - const A& arc = arcs_[pos_ - offset_]; - if ((data_flags_ & flags_) == (flags_ & kArcValueFlags)) { - // If the value flags for 'arc' match the recquired value flags - // then return 'arc'. - return arc; - } else { - // Otherwise, compute the corresponding arc on-the-fly. - fst_.GetImpl()->ComputeArc(tuple_, arc, &arc_, flags_ & kArcValueFlags); - return arc_; - } - } else { // The requested arc is the 'final' arc. - if ((final_flags_ & flags_) != (flags_ & kArcValueFlags)) { - // If the arc value flags that hold for the final arc - // do not match the requested value flags, then - // 'final_arc_' needs to be updated. - fst_.GetImpl()->ComputeFinalArc(tuple_, &final_arc_, - flags_ & kArcValueFlags); - final_flags_ = flags_ & kArcValueFlags; - } - return final_arc_; - } - } - - void Next() { ++pos_; } - - size_t Position() const { return pos_; } - - void Reset() { pos_ = 0; } - - void Seek(size_t pos) { pos_ = pos; } - - uint32 Flags() const { return flags_; } - - void SetFlags(uint32 f, uint32 mask) { - // Update the flags taking into account what flags are supported - // by the Fst. - flags_ &= ~mask; - flags_ |= (f & fst_.GetImpl()->ArcIteratorFlags()); - // If non-caching is not requested (and caching has not already - // been performed), then flush 'data_flags_' to request caching - // during the next call to Value(). - if (!(flags_ & kArcNoCache) && data_flags_ != kArcValueFlags) { - if (!fst_.GetImpl()->HasArcs(state_)) - data_flags_ = 0; - } - // If 'data_flags_' has been flushed but non-caching is requested - // before calling Value(), then set up the iterator for non-caching. - if ((f & kArcNoCache) && (!data_flags_)) - Init(); - } - - private: - const ReplaceFst<A, T> &fst_; // Reference to the FST - StateId state_; // State in the FST - mutable typename T::StateTuple tuple_; // Tuple corresponding to state_ - - ssize_t pos_; // Current position - mutable ssize_t offset_; // Offset between position in iterator and in arcs_ - ssize_t num_arcs_; // Number of arcs at state_ - uint32 flags_; // Behavorial flags for the arc iterator - mutable Arc arc_; // Memory to temporarily store computed arcs - - mutable ArcIteratorData<Arc> cache_data_; // Arc iterator data in cache - mutable ArcIteratorData<Arc> local_data_; // Arc iterator data in local fst - - mutable const A* arcs_; // Array of arcs - mutable uint32 data_flags_; // Arc value flags valid for data in arcs_ - mutable Arc final_arc_; // Final arc (when required) - mutable uint32 final_flags_; // Arc value flags valid for final_arc_ - - DISALLOW_COPY_AND_ASSIGN(ArcIterator); -}; - - -template <class A, class T> -class ReplaceFstMatcher : public MatcherBase<A> { - public: - typedef A Arc; - typedef typename A::StateId StateId; - typedef typename A::Label Label; - typedef MultiEpsMatcher<Matcher<Fst<A> > > LocalMatcher; - - ReplaceFstMatcher(const ReplaceFst<A, T> &fst, fst::MatchType match_type) - : fst_(fst), - impl_(fst_.GetImpl()), - s_(fst::kNoStateId), - match_type_(match_type), - current_loop_(false), - final_arc_(false), - loop_(fst::kNoLabel, 0, A::Weight::One(), fst::kNoStateId) { - if (match_type_ == fst::MATCH_OUTPUT) - swap(loop_.ilabel, loop_.olabel); - InitMatchers(); - } - - ReplaceFstMatcher(const ReplaceFstMatcher<A, T> &matcher, bool safe = false) - : fst_(matcher.fst_), - impl_(fst_.GetImpl()), - s_(fst::kNoStateId), - match_type_(matcher.match_type_), - current_loop_(false), - loop_(fst::kNoLabel, 0, A::Weight::One(), fst::kNoStateId) { - if (match_type_ == fst::MATCH_OUTPUT) - swap(loop_.ilabel, loop_.olabel); - InitMatchers(); - } - - // Create a local matcher for each component Fst of replace. - // LocalMatcher is a multi epsilon wrapper matcher. MultiEpsilonMatcher - // is used to match each non-terminal arc, since these non-terminal - // turn into epsilons on recursion. - void InitMatchers() { - const vector<const Fst<A>*>& fst_array = impl_->fst_array_; - matcher_.resize(fst_array.size(), 0); - for (size_t i = 0; i < fst_array.size(); ++i) { - if (fst_array[i]) { - matcher_[i] = - new LocalMatcher(*fst_array[i], match_type_, kMultiEpsList); - - typename set<Label>::iterator it = impl_->nonterminal_set_.begin(); - for (; it != impl_->nonterminal_set_.end(); ++it) { - matcher_[i]->AddMultiEpsLabel(*it); - } - } - } - } - - virtual ReplaceFstMatcher<A, T> *Copy(bool safe = false) const { - return new ReplaceFstMatcher<A, T>(*this, safe); - } - - virtual ~ReplaceFstMatcher() { - for (size_t i = 0; i < matcher_.size(); ++i) - delete matcher_[i]; - } - - virtual MatchType Type(bool test) const { - if (match_type_ == MATCH_NONE) - return match_type_; - - uint64 true_prop = match_type_ == MATCH_INPUT ? - kILabelSorted : kOLabelSorted; - uint64 false_prop = match_type_ == MATCH_INPUT ? - kNotILabelSorted : kNotOLabelSorted; - uint64 props = fst_.Properties(true_prop | false_prop, test); - - if (props & true_prop) - return match_type_; - else if (props & false_prop) - return MATCH_NONE; - else - return MATCH_UNKNOWN; - } - - virtual const Fst<A> &GetFst() const { - return fst_; - } - - virtual uint64 Properties(uint64 props) const { - return props; - } - - private: - // Set the sate from which our matching happens. - virtual void SetState_(StateId s) { - if (s_ == s) return; - - s_ = s; - tuple_ = impl_->GetStateTable()->Tuple(s_); - if (tuple_.fst_state == kNoStateId) { - done_ = true; - return; - } - // Get current matcher. Used for non epsilon matching - current_matcher_ = matcher_[tuple_.fst_id]; - current_matcher_->SetState(tuple_.fst_state); - loop_.nextstate = s_; - - final_arc_ = false; - } - - // Search for label, from previous set state. If label == 0, first - // hallucinate and epsilon loop, else use the underlying matcher to - // search for the label or epsilons. - // - Note since the ReplaceFST recursion on non-terminal arcs causes - // epsilon transitions to be created we use the MultiEpsilonMatcher - // to search for possible matches of non terminals. - // - If the component Fst reaches a final state we also need to add - // the exiting final arc. - virtual bool Find_(Label label) { - bool found = false; - label_ = label; - if (label_ == 0 || label_ == kNoLabel) { - // Compute loop directly, saving Replace::ComputeArc - if (label_ == 0) { - current_loop_ = true; - found = true; - } - // Search for matching multi epsilons - final_arc_ = impl_->ComputeFinalArc(tuple_, 0); - found = current_matcher_->Find(kNoLabel) || final_arc_ || found; - } else { - // Search on sub machine directly using sub machine matcher. - found = current_matcher_->Find(label_); - } - return found; - } - - virtual bool Done_() const { - return !current_loop_ && !final_arc_ && current_matcher_->Done(); - } - - virtual const Arc& Value_() const { - if (current_loop_) { - return loop_; - } - if (final_arc_) { - impl_->ComputeFinalArc(tuple_, &arc_); - return arc_; - } - const Arc& component_arc = current_matcher_->Value(); - impl_->ComputeArc(tuple_, component_arc, &arc_); - return arc_; - } - - virtual void Next_() { - if (current_loop_) { - current_loop_ = false; - return; - } - if (final_arc_) { - final_arc_ = false; - return; - } - current_matcher_->Next(); - } - - const ReplaceFst<A, T>& fst_; - ReplaceFstImpl<A, T> *impl_; - LocalMatcher* current_matcher_; - vector<LocalMatcher*> matcher_; - - StateId s_; // Current state - Label label_; // Current label - - MatchType match_type_; // Supplied by caller - mutable bool done_; - mutable bool current_loop_; // Current arc is the implicit loop - mutable bool final_arc_; // Current arc for exiting recursion - mutable typename T::StateTuple tuple_; // Tuple corresponding to state_ - mutable Arc arc_; - Arc loop_; -}; - -template <class A, class T> inline -void ReplaceFst<A, T>::InitStateIterator(StateIteratorData<A> *data) const { - data->base = new StateIterator< ReplaceFst<A, T> >(*this); -} - -typedef ReplaceFst<StdArc> StdReplaceFst; - - -// // Recursivively replaces arcs in the root Fst with other Fsts. -// This version writes the result of replacement to an output MutableFst. -// -// Replace supports replacement of arcs in one Fst with another -// Fst. This replacement is recursive. Replace takes an array of -// Fst(s). One Fst represents the root (or topology) machine. The root -// Fst refers to other Fsts by recursively replacing arcs labeled as -// non-terminals with the matching non-terminal Fst. Currently Replace -// uses the output symbols of the arcs to determine whether the arc is -// a non-terminal arc or not. A non-terminal can be any label that is -// not a non-zero terminal label in the output alphabet. Note that -// input argument is a vector of pair<>. These correspond to the tuple -// of non-terminal Label and corresponding Fst. -template<class Arc> -void Replace(const vector<pair<typename Arc::Label, - const Fst<Arc>* > >& ifst_array, - MutableFst<Arc> *ofst, typename Arc::Label root, - bool epsilon_on_replace) { - ReplaceFstOptions<Arc> opts(root, epsilon_on_replace); - opts.gc_limit = 0; // Cache only the last state for fastest copy. - *ofst = ReplaceFst<Arc>(ifst_array, opts); -} - -template<class Arc> -void Replace(const vector<pair<typename Arc::Label, - const Fst<Arc>* > >& ifst_array, - MutableFst<Arc> *ofst, typename Arc::Label root) { - Replace(ifst_array, ofst, root, false); -} - -} // namespace fst - -#endif // FST_LIB_REPLACE_H__ |