FST  openfst-1.7.2
OpenFst Library
isomorphic.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Function to test two FSTs are isomorphic, i.e., they are equal up to a state
5 // and arc re-ordering. FSTs should be deterministic when viewed as
6 // unweighted automata.
7 
8 #ifndef FST_ISOMORPHIC_H_
9 #define FST_ISOMORPHIC_H_
10 
11 #include <algorithm>
12 #include <list>
13 #include <type_traits>
14 #include <vector>
15 
16 #include <fst/log.h>
17 
18 #include <fst/fst.h>
19 
20 
21 namespace fst {
22 namespace internal {
23 
24 // Orders weights for equality checking.
25 template <class Weight, typename std::enable_if<
26  IsIdempotent<Weight>::value>::type * = nullptr>
27 bool WeightCompare(const Weight &w1, const Weight &w2, float delta,
28  bool *error) {
29  return NaturalLess<Weight>()(w1, w2);
30 }
31 
32 template <class Weight, typename std::enable_if<
33  !IsIdempotent<Weight>::value>::type * = nullptr>
34 bool WeightCompare(const Weight &w1, const Weight &w2, float delta,
35  bool *error) {
36  // No natural order; use hash.
37  const auto q1 = w1.Quantize(delta);
38  const auto q2 = w2.Quantize(delta);
39  auto n1 = q1.Hash();
40  auto n2 = q2.Hash();
41  // Hash not unique; very unlikely to happen.
42  if (n1 == n2 && q1 != q2) {
43  VLOG(1) << "Isomorphic: Weight hash collision";
44  *error = true;
45  }
46  return n1 < n2;
47 }
48 
49 template <class Arc>
50 class Isomorphism {
51  using StateId = typename Arc::StateId;
52 
53  public:
54  Isomorphism(const Fst<Arc> &fst1, const Fst<Arc> &fst2, float delta)
55  : fst1_(fst1.Copy()),
56  fst2_(fst2.Copy()),
57  delta_(delta),
58  error_(false),
59  comp_(delta, &error_) {}
60 
61  // Checks if input FSTs are isomorphic.
62  bool IsIsomorphic() {
63  if (fst1_->Start() == kNoStateId && fst2_->Start() == kNoStateId) {
64  return true;
65  }
66  if (fst1_->Start() == kNoStateId || fst2_->Start() == kNoStateId) {
67  return false;
68  }
69  PairState(fst1_->Start(), fst2_->Start());
70  while (!queue_.empty()) {
71  const auto &pr = queue_.front();
72  if (!IsIsomorphicState(pr.first, pr.second)) return false;
73  queue_.pop_front();
74  }
75  return true;
76  }
77 
78  bool Error() const { return error_; }
79 
80  private:
81  // Orders arcs for equality checking.
82  class ArcCompare {
83  public:
84  ArcCompare(float delta, bool *error) : delta_(delta), error_(error) {}
85 
86  bool operator()(const Arc &arc1, const Arc &arc2) const {
87  if (arc1.ilabel < arc2.ilabel) return true;
88  if (arc1.ilabel > arc2.ilabel) return false;
89  if (arc1.olabel < arc2.olabel) return true;
90  if (arc1.olabel > arc2.olabel) return false;
91  return WeightCompare(arc1.weight, arc2.weight, delta_, error_);
92  }
93 
94  private:
95  float delta_;
96  bool *error_;
97  };
98 
99  // Maintains state correspondences and queue.
100  bool PairState(StateId s1, StateId s2) {
101  if (state_pairs_.size() <= s1) state_pairs_.resize(s1 + 1, kNoStateId);
102  if (state_pairs_[s1] == s2) {
103  return true; // already seen this pair
104  } else if (state_pairs_[s1] != kNoStateId) {
105  return false; // s1 already paired with another s2
106  }
107  state_pairs_[s1] = s2;
108  queue_.push_back(std::make_pair(s1, s2));
109  return true;
110  }
111 
112  // Checks if state pair is isomorphic
113  bool IsIsomorphicState(StateId s1, StateId s2);
114 
115  std::unique_ptr<Fst<Arc>> fst1_;
116  std::unique_ptr<Fst<Arc>> fst2_;
117  float delta_; // Weight equality delta.
118  std::vector<Arc> arcs1_; // For sorting arcs on FST1.
119  std::vector<Arc> arcs2_; // For sorting arcs on FST2.
120  std::vector<StateId> state_pairs_; // Maintains state correspondences.
121  std::list<std::pair<StateId, StateId>> queue_; // Queue of state pairs.
122  bool error_; // Error flag.
123  ArcCompare comp_;
124 };
125 
126 template <class Arc>
127 bool Isomorphism<Arc>::IsIsomorphicState(StateId s1, StateId s2) {
128  if (!ApproxEqual(fst1_->Final(s1), fst2_->Final(s2), delta_)) return false;
129  auto narcs1 = fst1_->NumArcs(s1);
130  auto narcs2 = fst2_->NumArcs(s2);
131  if (narcs1 != narcs2) return false;
132  ArcIterator<Fst<Arc>> aiter1(*fst1_, s1);
133  ArcIterator<Fst<Arc>> aiter2(*fst2_, s2);
134  arcs1_.clear();
135  arcs1_.reserve(narcs1);
136  arcs2_.clear();
137  arcs2_.reserve(narcs2);
138  for (; !aiter1.Done(); aiter1.Next(), aiter2.Next()) {
139  arcs1_.push_back(aiter1.Value());
140  arcs2_.push_back(aiter2.Value());
141  }
142  std::sort(arcs1_.begin(), arcs1_.end(), comp_);
143  std::sort(arcs2_.begin(), arcs2_.end(), comp_);
144  for (size_t i = 0; i < arcs1_.size(); ++i) {
145  const auto &arc1 = arcs1_[i];
146  const auto &arc2 = arcs2_[i];
147  if (arc1.ilabel != arc2.ilabel) return false;
148  if (arc1.olabel != arc2.olabel) return false;
149  if (!ApproxEqual(arc1.weight, arc2.weight, delta_)) return false;
150  if (!PairState(arc1.nextstate, arc2.nextstate)) return false;
151  if (i > 0) { // Checks for non-determinism.
152  const auto &arc0 = arcs1_[i - 1];
153  if (arc1.ilabel == arc0.ilabel && arc1.olabel == arc0.olabel &&
154  ApproxEqual(arc1.weight, arc0.weight, delta_)) {
155  VLOG(1) << "Isomorphic: Non-determinism as an unweighted automaton";
156  error_ = true;
157  return false;
158  }
159  }
160  }
161  return true;
162 }
163 
164 } // namespace internal
165 
166 // Tests if two FSTs have the same states and arcs up to a reordering.
167 // Inputs should be non-deterministic when viewed as unweighted automata.
168 template <class Arc>
169 bool Isomorphic(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
170  float delta = kDelta) {
171  internal::Isomorphism<Arc> iso(fst1, fst2, delta);
172  bool result = iso.IsIsomorphic();
173  if (iso.Error()) {
174  FSTERROR() << "Isomorphic: Cannot determine if inputs are isomorphic";
175  return false;
176  } else {
177  return result;
178  }
179 }
180 
181 } // namespace fst
182 
183 #endif // FST_ISOMORPHIC_H_
Isomorphism(const Fst< Arc > &fst1, const Fst< Arc > &fst2, float delta)
Definition: isomorphic.h:54
bool Isomorphic(const Fst< Arc > &fst1, const Fst< Arc > &fst2, float delta=kDelta)
Definition: isomorphic.h:169
constexpr int kNoStateId
Definition: fst.h:180
const Arc & Value() const
Definition: fst.h:503
#define FSTERROR()
Definition: util.h:35
#define VLOG(level)
Definition: log.h:49
bool Done() const
Definition: fst.h:499
std::integral_constant< bool,(W::Properties()&kIdempotent)!=0 > IsIdempotent
Definition: weight.h:136
constexpr bool ApproxEqual(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2, float delta=kDelta)
Definition: float-weight.h:140
constexpr float kDelta
Definition: weight.h:109
bool WeightCompare(const Weight &w1, const Weight &w2, float delta, bool *error)
Definition: isomorphic.h:27
void Next()
Definition: fst.h:507