// equivalent.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: wojciech@google.com (Wojciech Skut)
//
// \file Functions and classes to determine the equivalence of two
// FSTs.
#ifndef FST_LIB_EQUIVALENT_H__
#define FST_LIB_EQUIVALENT_H__
#include <algorithm>
#include <deque>
using std::deque;
#include <tr1/unordered_map>
using std::tr1::unordered_map;
using std::tr1::unordered_multimap;
#include <utility>
using std::pair; using std::make_pair;
#include <vector>
using std::vector;
#include <fst/encode.h>
#include <fst/push.h>
#include <fst/union-find.h>
#include <fst/vector-fst.h>
namespace fst {
// Traits-like struct holding utility functions/typedefs/constants for
// the equivalence algorithm.
//
// Encoding device: in order to make the statesets of the two acceptors
// disjoint, we map Arc::StateId on the type MappedId. The states of
// the first acceptor are mapped on odd numbers (s -> 2s + 1), and
// those of the second one on even numbers (s -> 2s + 2). The number 0
// is reserved for an implicit (non-final) 'dead state' (required for
// the correct treatment of non-coaccessible states; kNoStateId is
// mapped to kDeadState for both acceptors). The union-find algorithm
// operates on the mapped IDs.
template <class Arc>
struct EquivalenceUtil {
typedef typename Arc::StateId StateId;
typedef typename Arc::Weight Weight;
typedef StateId MappedId; // ID for an equivalence class.
// MappedId for an implicit dead state.
static const MappedId kDeadState = 0;
// MappedId for lookup failure.
static const MappedId kInvalidId = -1;
// Maps state ID to the representative of the corresponding
// equivalence class. The parameter 'which_fst' takes the values 1
// and 2, identifying the input FST.
static MappedId MapState(StateId s, int32 which_fst) {
return
(kNoStateId == s)
?
kDeadState
:
(static_cast<MappedId>(s) << 1) + which_fst;
}
// Maps set ID to State ID.
static StateId UnMapState(MappedId id) {
return static_cast<StateId>((--id) >> 1);
}
// Convenience function: checks if state with MappedId 's' is final
// in acceptor 'fa'.
static bool IsFinal(const Fst<Arc> &fa, MappedId s) {
return
(kDeadState == s) ?
false : (fa.Final(UnMapState(s)) != Weight::Zero());
}
// Convenience function: returns the representative of 'id' in 'sets',
// creating a new set if needed.
static MappedId FindSet(UnionFind<MappedId> *sets, MappedId id) {
MappedId repr = sets->FindSet(id);
if (repr != kInvalidId) {
return repr;
} else {
sets->MakeSet(id);
return id;
}
}
};
template <class Arc> const
typename EquivalenceUtil<Arc>::MappedId EquivalenceUtil<Arc>::kDeadState;
template <class Arc> const
typename EquivalenceUtil<Arc>::MappedId EquivalenceUtil<Arc>::kInvalidId;
// Equivalence checking algorithm: determines if the two FSTs
// <code>fst1</code> and <code>fst2</code> are equivalent. The input
// FSTs must be deterministic input-side epsilon-free acceptors,
// unweighted or with weights over a left semiring. Two acceptors are
// considered equivalent if they accept exactly the same set of
// strings (with the same weights).
//
// The algorithm (cf. Aho, Hopcroft and Ullman, "The Design and
// Analysis of Computer Programs") successively constructs sets of
// states that can be reached by the same prefixes, starting with a
// set containing the start states of both acceptors. A disjoint tree
// forest (the union-find algorithm) is used to represent the sets of
// states. The algorithm returns 'false' if one of the constructed
// sets contains both final and non-final states. Returns optional error
// value (when FLAGS_error_fatal = false).
//
// Complexity: quasi-linear, i.e. O(n G(n)), where
// n = |S1| + |S2| is the number of states in both acceptors
// G(n) is a very slowly growing function that can be approximated
// by 4 by all practical purposes.
//
template <class Arc>
bool Equivalent(const Fst<Arc> &fst1,
const Fst<Arc> &fst2,
double delta = kDelta, bool *error = 0) {
typedef typename Arc::Weight Weight;
if (error) *error = false;
// Check that the symbol table are compatible
if (!CompatSymbols(fst1.InputSymbols(), fst2.InputSymbols()) ||
!CompatSymbols(fst1.OutputSymbols(), fst2.OutputSymbols())) {
FSTERROR() << "Equivalent: input/output symbol tables of 1st argument "
<< "do not match input/output symbol tables of 2nd argument";
if (error) *error = true;
return false;
}
// Check properties first:
uint64 props = kNoEpsilons | kIDeterministic | kAcceptor;
if (fst1.Properties(props, true) != props) {
FSTERROR() << "Equivalent: first argument not an"
<< " epsilon-free deterministic acceptor";
if (error) *error = true;
return false;
}
if (fst2.Properties(props, true) != props) {
FSTERROR() << "Equivalent: second argument not an"
<< " epsilon-free deterministic acceptor";
if (error) *error = true;
return false;
}
if ((fst1.Properties(kUnweighted , true) != kUnweighted)
|| (fst2.Properties(kUnweighted , true) != kUnweighted)) {
VectorFst<Arc> efst1(fst1);
VectorFst<Arc> efst2(fst2);
Push(&efst1, REWEIGHT_TO_INITIAL, delta);
Push(&efst2, REWEIGHT_TO_INITIAL, delta);
ArcMap(&efst1, QuantizeMapper<Arc>(delta));
ArcMap(&efst2, QuantizeMapper<Arc>(delta));
EncodeMapper<Arc> mapper(kEncodeWeights|kEncodeLabels, ENCODE);
ArcMap(&efst1, &mapper);
ArcMap(&efst2, &mapper);
return Equivalent(efst1, efst2);
}
// Convenience typedefs:
typedef typename Arc::StateId StateId;
typedef EquivalenceUtil<Arc> Util;
typedef typename Util::MappedId MappedId;
enum { FST1 = 1, FST2 = 2 }; // Required by Util::MapState(...)
MappedId s1 = Util::MapState(fst1.Start(), FST1);
MappedId s2 = Util::MapState(fst2.Start(), FST2);
// The union-find structure.
UnionFind<MappedId> eq_classes(1000, Util::kInvalidId);
// Initialize the union-find structure.
eq_classes.MakeSet(s1);
eq_classes.MakeSet(s2);
// Data structure for the (partial) acceptor transition function of
// fst1 and fst2: input labels mapped to pairs of MappedId's
// representing destination states of the corresponding arcs in fst1
// and fst2, respectively.
typedef
unordered_map<typename Arc::Label, pair<MappedId, MappedId> >
Label2StatePairMap;
Label2StatePairMap arc_pairs;
// Pairs of MappedId's to be processed, organized in a queue.
deque<pair<MappedId, MappedId> > q;
bool ret = true;
// Early return if the start states differ w.r.t. being final.
if (Util::IsFinal(fst1, s1) != Util::IsFinal(fst2, s2)) {
ret = false;
}
// Main loop: explores the two acceptors in a breadth-first manner,
// updating the equivalence relation on the statesets. Loop
// invariant: each block of states contains either final states only
// or non-final states only.
for (q.push_back(make_pair(s1, s2)); ret && !q.empty(); q.pop_front()) {
s1 = q.front().first;
s2 = q.front().second;
// Representatives of the equivalence classes of s1/s2.
MappedId rep1 = Util::FindSet(&eq_classes, s1);
MappedId rep2 = Util::FindSet(&eq_classes, s2);
if (rep1 != rep2) {
eq_classes.Union(rep1, rep2);
arc_pairs.clear();
// Copy outgoing arcs starting at s1 into the hashtable.
if (Util::kDeadState != s1) {
ArcIterator<Fst<Arc> > arc_iter(fst1, Util::UnMapState(s1));
for (; !arc_iter.Done(); arc_iter.Next()) {
const Arc &arc = arc_iter.Value();
if (arc.weight != Weight::Zero()) { // Zero-weight arcs
// are treated as
// non-exisitent.
arc_pairs[arc.ilabel].first = Util::MapState(arc.nextstate, FST1);
}
}
}
// Copy outgoing arcs starting at s2 into the hashtable.
if (Util::kDeadState != s2) {
ArcIterator<Fst<Arc> > arc_iter(fst2, Util::UnMapState(s2));
for (; !arc_iter.Done(); arc_iter.Next()) {
const Arc &arc = arc_iter.Value();
if (arc.weight != Weight::Zero()) { // Zero-weight arcs
// are treated as
// non-existent.
arc_pairs[arc.ilabel].second = Util::MapState(arc.nextstate, FST2);
}
}
}
// Iterate through the hashtable and process pairs of target
// states.
for (typename Label2StatePairMap::const_iterator
arc_iter = arc_pairs.begin();
arc_iter != arc_pairs.end();
++arc_iter) {
const pair<MappedId, MappedId> &p = arc_iter->second;
if (Util::IsFinal(fst1, p.first) != Util::IsFinal(fst2, p.second)) {
// Detected inconsistency: return false.
ret = false;
break;
}
q.push_back(p);
}
}
}
if (fst1.Properties(kError, false) || fst2.Properties(kError, false)) {
if (error) *error = true;
return false;
}