// replace-util.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
// Utility classes for the recursive replacement of Fsts (RTNs).
#ifndef FST_LIB_REPLACE_UTIL_H__
#define FST_LIB_REPLACE_UTIL_H__
#include <vector>
using std::vector;
#include <tr1/unordered_map>
using std::tr1::unordered_map;
using std::tr1::unordered_multimap;
#include <tr1/unordered_set>
using std::tr1::unordered_set;
using std::tr1::unordered_multiset;
#include <map>
#include <fst/connect.h>
#include <fst/mutable-fst.h>
#include <fst/topsort.h>
namespace fst {
template <class Arc>
void Replace(const vector<pair<typename Arc::Label, const Fst<Arc>* > >&,
MutableFst<Arc> *, typename Arc::Label, bool);
// Utility class for the recursive replacement of Fsts (RTNs). The
// user provides a set of Label, Fst pairs at construction. These are
// used by methods for testing cyclic dependencies and connectedness
// and doing RTN connection and specific Fst replacement by label or
// for various optimization properties. The modified results can be
// obtained with the GetFstPairs() or GetMutableFstPairs() methods.
template <class Arc>
class ReplaceUtil {
public:
typedef typename Arc::Label Label;
typedef typename Arc::Weight Weight;
typedef typename Arc::StateId StateId;
typedef pair<Label, const Fst<Arc>*> FstPair;
typedef pair<Label, MutableFst<Arc>*> MutableFstPair;
typedef unordered_map<Label, Label> NonTerminalHash;
// Constructs from mutable Fsts; Fst ownership given to ReplaceUtil.
ReplaceUtil(const vector<MutableFstPair> &fst_pairs,
Label root_label, bool epsilon_on_replace = false);
// Constructs from Fsts; Fst ownership retained by caller.
ReplaceUtil(const vector<FstPair> &fst_pairs,
Label root_label, bool epsilon_on_replace = false);
// Constructs from ReplaceFst internals; ownership retained by caller.
ReplaceUtil(const vector<const Fst<Arc> *> &fst_array,
const NonTerminalHash &nonterminal_hash, Label root_fst,
bool epsilon_on_replace = false);
~ReplaceUtil() {
for (Label i = 0; i < fst_array_.size(); ++i)
delete fst_array_[i];
}
// True if the non-terminal dependencies are cyclic. Cyclic
// dependencies will result in an unexpandable replace fst.
bool CyclicDependencies() const {
GetDependencies(false);
return depprops_ & kCyclic;
}
// Returns true if no useless Fsts, states or transitions.
bool Connected() const {
GetDependencies(false);
uint64 props = kAccessible | kCoAccessible;
for (Label i = 0; i < fst_array_.size(); ++i) {
if (!fst_array_[i])
continue;
if (fst_array_[i]->Properties(props, true) != props || !depaccess_[i])
return false;
}
return true;
}
// Removes useless Fsts, states and transitions.
void Connect();
// Replaces Fsts specified by labels.
// Does nothing if there are cyclic dependencies.
void ReplaceLabels(const vector<Label> &labels);
// Replaces Fsts that have at most 'nstates' states, 'narcs' arcs and
// 'nnonterm' non-terminals (updating in reverse dependency order).
// Does nothing if there are cyclic dependencies.
void ReplaceBySize(size_t nstates, size_t narcs, size_t nnonterms);
// Replaces singleton Fsts.
// Does nothing if there are cyclic dependencies.
void ReplaceTrivial() { ReplaceBySize(2, 1, 1); }
// Replaces non-terminals that have at most 'ninstances' instances
// (updating in dependency order).
// Does nothing if there are cyclic dependencies.
void ReplaceByInstances(size_t ninstances);
// Replaces non-terminals that have only one instance.
// Does nothing if there are cyclic dependencies.
void ReplaceUnique() { ReplaceByInstances(1); }
// Returns Label, Fst pairs; Fst ownership retained by ReplaceUtil.
void GetFstPairs(vector<FstPair> *fst_pairs);
// Returns Label, MutableFst pairs; Fst ownership given to caller.
void GetMutableFstPairs(vector<MutableFstPair> *mutable_fst_pairs);
private:
// Per Fst statistics
struct ReplaceStats {
StateId nstates; // # of states
StateId nfinal; // # of final states
size_t narcs; // # of arcs
Label nnonterms; // # of non-terminals in Fst
size_t nref; // # of non-terminal instances referring to this Fst
// # of times that ith Fst references this Fst
map<Label, size_t> inref;
// # of times that this Fst references the ith Fst
map<Label, size_t> outref;
ReplaceStats()
: nstates(0),
nfinal(0),
narcs(0),
nnonterms(0),
nref(0) {}
};
// Check Mutable Fsts exist o.w. create them.
void CheckMutableFsts();
// Computes the dependency graph of the replace Fsts.
// If 'stats' is true, dependency statistics computed as well.
void GetDependencies(bool stats) const;
void ClearDependencies() const {
depfst_.DeleteStates();
stats_.clear();
depprops_ = 0;
have_stats_ = false;
}
// Get topological order of dependencies. Returns false with cyclic input.
bool GetTopOrder(const Fst<Arc> &fst, vector<Label> *toporder) const;
// Update statistics assuming that jth Fst will be replaced.
void UpdateStats(Label j);
Label root_label_; // root non-terminal
Label root_fst_; // root Fst ID
bool epsilon_on_replace_; // see Replace()
vector<const Fst<Arc> *> fst_array_; // Fst per ID
vector<MutableFst<Arc> *> mutable_fst_array_; // MutableFst per ID
vector<Label> nonterminal_array_; // Fst ID to non-terminal
NonTerminalHash nonterminal_hash_; // non-terminal to Fst ID
mutable VectorFst<Arc> depfst_; // Fst ID dependencies
mutable vector<bool> depaccess_; // Fst ID accessibility
mutable uint64 depprops_; // dependency Fst props
mutable bool have_stats_; // have dependency statistics
mutable vector<ReplaceStats> stats_; // Per Fst statistics
DISALLOW_COPY_AND_ASSIGN(ReplaceUtil);
};
template <class Arc>
ReplaceUtil<Arc>::ReplaceUtil(
const vector<MutableFstPair> &fst_pairs,
Label root_label, bool epsilon_on_replace)
: root_label_(root_label),
epsilon_on_replace_(epsilon_on_replace),
depprops_(0),
have_stats_(false) {
fst_array_.push_back(0);
mutable_fst_array_.push_back(0);
nonterminal_array_.push_back(kNoLabel);
for (Label i = 0; i < fst_pairs.size(); ++i) {
Label label = fst_pairs[i].first;
MutableFst<Arc> *fst = fst_pairs[i].second;
nonterminal_hash_[label] = fst_array_.size();
nonterminal_array_.push_back(label);
fst_array_.push_back(fst);
mutable_fst_array_.push_back(fst);
}
root_fst_ = nonterminal_hash_[root_label_];
if (!root_fst_)
FSTERROR() << "ReplaceUtil: no root FST for label: " << root_label_;
}
template <class Arc>
ReplaceUtil<Arc>::ReplaceUtil(
const vector<FstPair> &fst_pairs,
Label root_label, bool epsilon_on_replace)
: root_label_(root_label),
epsilon_on_replace_(epsilon_on_replace),
depprops_(0),
have_stats_(false) {
fst_array_.push_back(0);
nonterminal_array_.push_back(kNoLabel);
for (Label i = 0; i < fst_pairs.size(); ++i) {
Label label = fst_pairs[i].first;
const Fst<Arc> *fst = fst_pairs[i].second;
nonterminal_hash_[label] =