// See www.openfst.org for extensive documentation on this weighted
|
// finite-state transducer library.
|
//
|
// Functions and classes to minimize an FST.
|
|
#ifndef FST_MINIMIZE_H_
|
#define FST_MINIMIZE_H_
|
|
#include <cmath>
|
|
#include <algorithm>
|
#include <map>
|
#include <queue>
|
#include <utility>
|
#include <vector>
|
|
#include <fst/log.h>
|
|
#include <fst/arcsort.h>
|
#include <fst/connect.h>
|
#include <fst/dfs-visit.h>
|
#include <fst/encode.h>
|
#include <fst/factor-weight.h>
|
#include <fst/fst.h>
|
#include <fst/mutable-fst.h>
|
#include <fst/partition.h>
|
#include <fst/push.h>
|
#include <fst/queue.h>
|
#include <fst/reverse.h>
|
#include <fst/shortest-distance.h>
|
#include <fst/state-map.h>
|
|
|
namespace fst {
|
namespace internal {
|
|
// Comparator for creating partition.
|
template <class Arc>
|
class StateComparator {
|
public:
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
StateComparator(const Fst<Arc> &fst, const Partition<StateId> &partition)
|
: fst_(fst), partition_(partition) {}
|
|
// Compares state x with state y based on sort criteria.
|
bool operator()(const StateId x, const StateId y) const {
|
// Checks for final state equivalence.
|
const auto xfinal = fst_.Final(x).Hash();
|
const auto yfinal = fst_.Final(y).Hash();
|
if (xfinal < yfinal) {
|
return true;
|
} else if (xfinal > yfinal) {
|
return false;
|
}
|
// Checks for number of arcs.
|
if (fst_.NumArcs(x) < fst_.NumArcs(y)) return true;
|
if (fst_.NumArcs(x) > fst_.NumArcs(y)) return false;
|
// If the number of arcs are equal, checks for arc match.
|
for (ArcIterator<Fst<Arc>> aiter1(fst_, x), aiter2(fst_, y);
|
!aiter1.Done() && !aiter2.Done(); aiter1.Next(), aiter2.Next()) {
|
const auto &arc1 = aiter1.Value();
|
const auto &arc2 = aiter2.Value();
|
if (arc1.ilabel < arc2.ilabel) return true;
|
if (arc1.ilabel > arc2.ilabel) return false;
|
if (partition_.ClassId(arc1.nextstate) <
|
partition_.ClassId(arc2.nextstate))
|
return true;
|
if (partition_.ClassId(arc1.nextstate) >
|
partition_.ClassId(arc2.nextstate))
|
return false;
|
}
|
return false;
|
}
|
|
private:
|
const Fst<Arc> &fst_;
|
const Partition<StateId> &partition_;
|
};
|
|
// Computes equivalence classes for cyclic unweighted acceptors. For cyclic
|
// minimization we use the classic Hopcroft minimization algorithm, which has
|
// complexity O(E log V) where E is the number of arcs and V is the number of
|
// states.
|
//
|
// For more information, see:
|
//
|
// Hopcroft, J. 1971. An n Log n algorithm for minimizing states in a finite
|
// automaton. Ms, Stanford University.
|
//
|
// Note: the original presentation of the paper was for a finite automaton (==
|
// deterministic, unweighted acceptor), but we also apply it to the
|
// nondeterministic case, where it is also applicable as long as the semiring is
|
// idempotent (if the semiring is not idempotent, there are some complexities
|
// in keeping track of the weight when there are multiple arcs to states that
|
// will be merged, and we don't deal with this).
|
template <class Arc, class Queue>
|
class CyclicMinimizer {
|
public:
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using ClassId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
using RevArc = ReverseArc<Arc>;
|
|
explicit CyclicMinimizer(const ExpandedFst<Arc> &fst) {
|
Initialize(fst);
|
Compute(fst);
|
}
|
|
const Partition<StateId> &GetPartition() const { return P_; }
|
|
private:
|
// StateILabelHasher is a hashing object that computes a hash-function
|
// of an FST state that depends only on the set of ilabels on arcs leaving
|
// the state [note: it assumes that the arcs are ilabel-sorted].
|
// In order to work correctly for non-deterministic automata, multiple
|
// instances of the same ilabel count the same as a single instance.
|
class StateILabelHasher {
|
public:
|
explicit StateILabelHasher(const Fst<Arc> &fst) : fst_(fst) {}
|
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
|
size_t operator()(const StateId s) {
|
const size_t p1 = 7603;
|
const size_t p2 = 433024223;
|
size_t result = p2;
|
size_t current_ilabel = kNoLabel;
|
for (ArcIterator<Fst<Arc>> aiter(fst_, s); !aiter.Done(); aiter.Next()) {
|
Label this_ilabel = aiter.Value().ilabel;
|
if (this_ilabel != current_ilabel) { // Ignores repeats.
|
result = p1 * result + this_ilabel;
|
current_ilabel = this_ilabel;
|
}
|
}
|
return result;
|
}
|
|
private:
|
const Fst<Arc> &fst_;
|
};
|
|
class ArcIterCompare {
|
public:
|
explicit ArcIterCompare(const Partition<StateId> &partition)
|
: partition_(partition) {}
|
|
ArcIterCompare(const ArcIterCompare &comp) : partition_(comp.partition_) {}
|
|
// Compares two iterators based on their input labels.
|
bool operator()(const ArcIterator<Fst<RevArc>> *x,
|
const ArcIterator<Fst<RevArc>> *y) const {
|
const auto &xarc = x->Value();
|
const auto &yarc = y->Value();
|
return xarc.ilabel > yarc.ilabel;
|
}
|
|
private:
|
const Partition<StateId> &partition_;
|
};
|
|
using ArcIterQueue =
|
std::priority_queue<ArcIterator<Fst<RevArc>> *,
|
std::vector<ArcIterator<Fst<RevArc>> *>,
|
ArcIterCompare>;
|
|
private:
|
// Prepartitions the space into equivalence classes. We ensure that final and
|
// non-final states always go into different equivalence classes, and we use
|
// class StateILabelHasher to make sure that most of the time, states with
|
// different sets of ilabels on arcs leaving them, go to different partitions.
|
// Note: for the O(n) guarantees we don't rely on the goodness of this
|
// hashing function---it just provides a bonus speedup.
|
void PrePartition(const ExpandedFst<Arc> &fst) {
|
VLOG(5) << "PrePartition";
|
StateId next_class = 0;
|
auto num_states = fst.NumStates();
|
// Allocates a temporary vector to store the initial class mappings, so that
|
// we can allocate the classes all at once.
|
std::vector<StateId> state_to_initial_class(num_states);
|
{
|
// We maintain two maps from hash-value to class---one for final states
|
// (final-prob == One()) and one for non-final states
|
// (final-prob == Zero()). We are processing unweighted acceptors, so the
|
// are the only two possible values.
|
using HashToClassMap = std::unordered_map<size_t, StateId>;
|
HashToClassMap hash_to_class_nonfinal;
|
HashToClassMap hash_to_class_final;
|
StateILabelHasher hasher(fst);
|
for (StateId s = 0; s < num_states; ++s) {
|
size_t hash = hasher(s);
|
HashToClassMap &this_map =
|
(fst.Final(s) != Weight::Zero() ? hash_to_class_final
|
: hash_to_class_nonfinal);
|
// Avoids two map lookups by using 'insert' instead of 'find'.
|
auto p = this_map.insert(std::make_pair(hash, next_class));
|
state_to_initial_class[s] = p.second ? next_class++ : p.first->second;
|
}
|
// Lets the unordered_maps go out of scope before we allocate the classes,
|
// to reduce the maximum amount of memory used.
|
}
|
P_.AllocateClasses(next_class);
|
for (StateId s = 0; s < num_states; ++s) {
|
P_.Add(s, state_to_initial_class[s]);
|
}
|
for (StateId c = 0; c < next_class; ++c) L_.Enqueue(c);
|
VLOG(5) << "Initial Partition: " << P_.NumClasses();
|
}
|
|
// Creates inverse transition Tr_ = rev(fst), loops over states in FST and
|
// splits on final, creating two blocks in the partition corresponding to
|
// final, non-final.
|
void Initialize(const ExpandedFst<Arc> &fst) {
|
// Constructs Tr.
|
Reverse(fst, &Tr_);
|
ILabelCompare<RevArc> ilabel_comp;
|
ArcSort(&Tr_, ilabel_comp);
|
// Tells the partition how many elements to allocate. The first state in
|
// Tr_ is super-final state.
|
P_.Initialize(Tr_.NumStates() - 1);
|
// Prepares initial partition.
|
PrePartition(fst);
|
// Allocates arc iterator queue.
|
ArcIterCompare comp(P_);
|
aiter_queue_.reset(new ArcIterQueue(comp));
|
}
|
// Partitions all classes with destination C.
|
void Split(ClassId C) {
|
// Prepares priority queue: opens arc iterator for each state in C, and
|
// inserts into priority queue.
|
for (PartitionIterator<StateId> siter(P_, C); !siter.Done(); siter.Next()) {
|
StateId s = siter.Value();
|
if (Tr_.NumArcs(s + 1)) {
|
aiter_queue_->push(new ArcIterator<Fst<RevArc>>(Tr_, s + 1));
|
}
|
}
|
// Now pops arc iterator from queue, splits entering equivalence class, and
|
// re-inserts updated iterator into queue.
|
Label prev_label = -1;
|
while (!aiter_queue_->empty()) {
|
std::unique_ptr<ArcIterator<Fst<RevArc>>> aiter(aiter_queue_->top());
|
aiter_queue_->pop();
|
if (aiter->Done()) continue;
|
const auto &arc = aiter->Value();
|
auto from_state = aiter->Value().nextstate - 1;
|
auto from_label = arc.ilabel;
|
if (prev_label != from_label) P_.FinalizeSplit(&L_);
|
auto from_class = P_.ClassId(from_state);
|
if (P_.ClassSize(from_class) > 1) P_.SplitOn(from_state);
|
prev_label = from_label;
|
aiter->Next();
|
if (!aiter->Done()) aiter_queue_->push(aiter.release());
|
}
|
P_.FinalizeSplit(&L_);
|
}
|
|
// Main loop for Hopcroft minimization.
|
void Compute(const Fst<Arc> &fst) {
|
// Processes active classes (FIFO, or FILO).
|
while (!L_.Empty()) {
|
const auto C = L_.Head();
|
L_.Dequeue();
|
Split(C); // Splits on C, all labels in C.
|
}
|
}
|
|
private:
|
// Partioning of states into equivalence classes.
|
Partition<StateId> P_;
|
// Set of active classes to be processed in partition P.
|
Queue L_;
|
// Reverses transition function.
|
VectorFst<RevArc> Tr_;
|
// Priority queue of open arc iterators for all states in the splitter
|
// equivalence class.
|
std::unique_ptr<ArcIterQueue> aiter_queue_;
|
};
|
|
// Computes equivalence classes for acyclic FST.
|
//
|
// Complexity:
|
//
|
// O(E)
|
//
|
// where E is the number of arcs.
|
//
|
// For more information, see:
|
//
|
// Revuz, D. 1992. Minimization of acyclic deterministic automata in linear
|
// time. Theoretical Computer Science 92(1): 181-189.
|
template <class Arc>
|
class AcyclicMinimizer {
|
public:
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using ClassId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
explicit AcyclicMinimizer(const ExpandedFst<Arc> &fst) {
|
Initialize(fst);
|
Refine(fst);
|
}
|
|
const Partition<StateId> &GetPartition() { return partition_; }
|
|
private:
|
// DFS visitor to compute the height (distance) to final state.
|
class HeightVisitor {
|
public:
|
HeightVisitor() : max_height_(0), num_states_(0) {}
|
|
// Invoked before DFS visit.
|
void InitVisit(const Fst<Arc> &fst) {}
|
|
// Invoked when state is discovered (2nd arg is DFS tree root).
|
bool InitState(StateId s, StateId root) {
|
// Extends height array and initialize height (distance) to 0.
|
for (StateId i = height_.size(); i <= s; ++i) height_.push_back(-1);
|
if (s >= num_states_) num_states_ = s + 1;
|
return true;
|
}
|
|
// Invoked when tree arc examined (to undiscovered state).
|
bool TreeArc(StateId s, const Arc &arc) { return true; }
|
|
// Invoked when back arc examined (to unfinished state).
|
bool BackArc(StateId s, const Arc &arc) { return true; }
|
|
// Invoked when forward or cross arc examined (to finished state).
|
bool ForwardOrCrossArc(StateId s, const Arc &arc) {
|
if (height_[arc.nextstate] + 1 > height_[s]) {
|
height_[s] = height_[arc.nextstate] + 1;
|
}
|
return true;
|
}
|
|
// Invoked when state finished (parent is kNoStateId for tree root).
|
void FinishState(StateId s, StateId parent, const Arc *parent_arc) {
|
if (height_[s] == -1) height_[s] = 0;
|
const auto h = height_[s] + 1;
|
if (parent >= 0) {
|
if (h > height_[parent]) height_[parent] = h;
|
if (h > max_height_) max_height_ = h;
|
}
|
}
|
|
// Invoked after DFS visit.
|
void FinishVisit() {}
|
|
size_t max_height() const { return max_height_; }
|
|
const std::vector<StateId> &height() const { return height_; }
|
|
size_t num_states() const { return num_states_; }
|
|
private:
|
std::vector<StateId> height_;
|
size_t max_height_;
|
size_t num_states_;
|
};
|
|
private:
|
// Cluster states according to height (distance to final state)
|
void Initialize(const Fst<Arc> &fst) {
|
// Computes height (distance to final state).
|
HeightVisitor hvisitor;
|
DfsVisit(fst, &hvisitor);
|
// Creates initial partition based on height.
|
partition_.Initialize(hvisitor.num_states());
|
partition_.AllocateClasses(hvisitor.max_height() + 1);
|
const auto &hstates = hvisitor.height();
|
for (StateId s = 0; s < hstates.size(); ++s) partition_.Add(s, hstates[s]);
|
}
|
|
// Refines states based on arc sort (out degree, arc equivalence).
|
void Refine(const Fst<Arc> &fst) {
|
using EquivalenceMap = std::map<StateId, StateId, StateComparator<Arc>>;
|
StateComparator<Arc> comp(fst, partition_);
|
// Starts with tail (height = 0).
|
auto height = partition_.NumClasses();
|
for (StateId h = 0; h < height; ++h) {
|
EquivalenceMap equiv_classes(comp);
|
// Sorts states within equivalence class.
|
PartitionIterator<StateId> siter(partition_, h);
|
equiv_classes[siter.Value()] = h;
|
for (siter.Next(); !siter.Done(); siter.Next()) {
|
auto insert_result =
|
equiv_classes.insert(std::make_pair(siter.Value(), kNoStateId));
|
if (insert_result.second) {
|
insert_result.first->second = partition_.AddClass();
|
}
|
}
|
// Creates refined partition.
|
for (siter.Reset(); !siter.Done();) {
|
const auto s = siter.Value();
|
const auto old_class = partition_.ClassId(s);
|
const auto new_class = equiv_classes[s];
|
// A move operation can invalidate the iterator, so we first update
|
// the iterator to the next element before we move the current element
|
// out of the list.
|
siter.Next();
|
if (old_class != new_class) partition_.Move(s, new_class);
|
}
|
}
|
}
|
|
private:
|
Partition<StateId> partition_;
|
};
|
|
// Given a partition and a Mutable FST, merges states of Fst in place (i.e.,
|
// destructively). Merging works by taking the first state in a class of the
|
// partition to be the representative state for the class. Each arc is then
|
// reconnected to this state. All states in the class are merged by adding
|
// their arcs to the representative state.
|
template <class Arc>
|
void MergeStates(const Partition<typename Arc::StateId> &partition,
|
MutableFst<Arc> *fst) {
|
using StateId = typename Arc::StateId;
|
std::vector<StateId> state_map(partition.NumClasses());
|
for (StateId i = 0; i < partition.NumClasses(); ++i) {
|
PartitionIterator<StateId> siter(partition, i);
|
state_map[i] = siter.Value(); // First state in partition.
|
}
|
// Relabels destination states.
|
for (StateId c = 0; c < partition.NumClasses(); ++c) {
|
for (PartitionIterator<StateId> siter(partition, c); !siter.Done();
|
siter.Next()) {
|
const auto s = siter.Value();
|
for (MutableArcIterator<MutableFst<Arc>> aiter(fst, s); !aiter.Done();
|
aiter.Next()) {
|
auto arc = aiter.Value();
|
arc.nextstate = state_map[partition.ClassId(arc.nextstate)];
|
if (s == state_map[c]) { // For the first state, just sets destination.
|
aiter.SetValue(arc);
|
} else {
|
fst->AddArc(state_map[c], std::move(arc));
|
}
|
}
|
}
|
}
|
fst->SetStart(state_map[partition.ClassId(fst->Start())]);
|
Connect(fst);
|
}
|
|
template <class Arc>
|
void AcceptorMinimize(MutableFst<Arc> *fst,
|
bool allow_acyclic_minimization = true) {
|
if (!(fst->Properties(kAcceptor | kUnweighted, true) ==
|
(kAcceptor | kUnweighted))) {
|
FSTERROR() << "FST is not an unweighted acceptor";
|
fst->SetProperties(kError, kError);
|
return;
|
}
|
// Connects FST before minimization, handles disconnected states.
|
Connect(fst);
|
if (fst->NumStates() == 0) return;
|
if (allow_acyclic_minimization && fst->Properties(kAcyclic, true)) {
|
// Acyclic minimization (Revuz).
|
VLOG(2) << "Acyclic minimization";
|
ArcSort(fst, ILabelCompare<Arc>());
|
AcyclicMinimizer<Arc> minimizer(*fst);
|
MergeStates(minimizer.GetPartition(), fst);
|
} else {
|
// Either the FST has cycles, or it's generated from non-deterministic input
|
// (which the Revuz algorithm can't handle), so use the cyclic minimization
|
// algorithm of Hopcroft.
|
VLOG(2) << "Cyclic minimization";
|
CyclicMinimizer<Arc, LifoQueue<typename Arc::StateId>> minimizer(*fst);
|
MergeStates(minimizer.GetPartition(), fst);
|
}
|
// Merges in appropriate semiring
|
ArcUniqueMapper<Arc> mapper(*fst);
|
StateMap(fst, mapper);
|
}
|
|
} // namespace internal
|
|
// In place minimization of deterministic weighted automata and transducers,
|
// and also non-deterministic ones if they use an idempotent semiring.
|
// For transducers, if the 'sfst' argument is not null, the algorithm
|
// produces a compact factorization of the minimal transducer.
|
//
|
// In the acyclic deterministic case, we use an algorithm from Revuz that is
|
// linear in the number of arcs (edges) in the machine.
|
//
|
// In the cyclic or non-deterministic case, we use the classical Hopcroft
|
// minimization (which was presented for the deterministic case but which
|
// also works for non-deterministic FSTs); this has complexity O(e log v).
|
//
|
template <class Arc>
|
void Minimize(MutableFst<Arc> *fst, MutableFst<Arc> *sfst = nullptr,
|
float delta = kShortestDelta, bool allow_nondet = false) {
|
using Weight = typename Arc::Weight;
|
const auto props = fst->Properties(
|
kAcceptor | kIDeterministic | kWeighted | kUnweighted, true);
|
bool allow_acyclic_minimization;
|
if (props & kIDeterministic) {
|
allow_acyclic_minimization = true;
|
} else {
|
// Our approach to minimization of non-deterministic FSTs will only work in
|
// idempotent semirings---for non-deterministic inputs, a state could have
|
// multiple transitions to states that will get merged, and we'd have to
|
// sum their weights. The algorithm doesn't handle that.
|
if (!(Weight::Properties() & kIdempotent)) {
|
fst->SetProperties(kError, kError);
|
FSTERROR() << "Cannot minimize a non-deterministic FST over a "
|
"non-idempotent semiring";
|
return;
|
} else if (!allow_nondet) {
|
fst->SetProperties(kError, kError);
|
FSTERROR() << "Refusing to minimize a non-deterministic FST with "
|
<< "allow_nondet = false";
|
return;
|
}
|
// The Revuz algorithm won't work for nondeterministic inputs, so if the
|
// input is nondeterministic, we'll have to pass a bool saying not to use
|
// that algorithm. We check at this level rather than in AcceptorMinimize(),
|
// because it's possible that the FST at this level could be deterministic,
|
// but a harmless type of non-determinism could be introduced by Encode()
|
// (thanks to kEncodeWeights, if the FST has epsilons and has a final
|
// weight with weights equal to some epsilon arc.)
|
allow_acyclic_minimization = false;
|
}
|
if (!(props & kAcceptor)) { // Weighted transducer.
|
VectorFst<GallicArc<Arc, GALLIC_LEFT>> gfst;
|
ArcMap(*fst, &gfst, ToGallicMapper<Arc, GALLIC_LEFT>());
|
fst->DeleteStates();
|
gfst.SetProperties(kAcceptor, kAcceptor);
|
Push(&gfst, REWEIGHT_TO_INITIAL, delta);
|
ArcMap(&gfst, QuantizeMapper<GallicArc<Arc, GALLIC_LEFT>>(delta));
|
EncodeMapper<GallicArc<Arc, GALLIC_LEFT>> encoder(
|
kEncodeLabels | kEncodeWeights, ENCODE);
|
Encode(&gfst, &encoder);
|
internal::AcceptorMinimize(&gfst, allow_acyclic_minimization);
|
Decode(&gfst, encoder);
|
if (!sfst) {
|
FactorWeightFst<GallicArc<Arc, GALLIC_LEFT>,
|
GallicFactor<typename Arc::Label, Weight, GALLIC_LEFT>>
|
fwfst(gfst);
|
std::unique_ptr<SymbolTable> osyms(
|
fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : nullptr);
|
ArcMap(fwfst, fst, FromGallicMapper<Arc, GALLIC_LEFT>());
|
fst->SetOutputSymbols(osyms.get());
|
} else {
|
sfst->SetOutputSymbols(fst->OutputSymbols());
|
GallicToNewSymbolsMapper<Arc, GALLIC_LEFT> mapper(sfst);
|
ArcMap(gfst, fst, &mapper);
|
fst->SetOutputSymbols(sfst->InputSymbols());
|
}
|
} else if (props & kWeighted) { // Weighted acceptor.
|
Push(fst, REWEIGHT_TO_INITIAL, delta);
|
ArcMap(fst, QuantizeMapper<Arc>(delta));
|
EncodeMapper<Arc> encoder(kEncodeLabels | kEncodeWeights, ENCODE);
|
Encode(fst, &encoder);
|
internal::AcceptorMinimize(fst, allow_acyclic_minimization);
|
Decode(fst, encoder);
|
} else { // Unweighted acceptor.
|
internal::AcceptorMinimize(fst, allow_acyclic_minimization);
|
}
|
}
|
|
} // namespace fst
|
|
#endif // FST_MINIMIZE_H_
|
