23 #ifndef FST_ISOMORPHIC_H_ 24 #define FST_ISOMORPHIC_H_ 28 #include <type_traits> 40 template <
class Weight,
41 typename std::enable_if_t<IsIdempotent<Weight>::value> * =
nullptr>
47 template <
class Weight,
48 typename std::enable_if_t<!IsIdempotent<Weight>::value> * =
nullptr>
49 bool WeightCompare(
const Weight &w1,
const Weight &w2,
float delta,
52 const auto q1 = w1.Quantize(delta);
53 const auto q2 = w2.Quantize(delta);
54 const auto n1 = q1.Hash();
55 const auto n2 = q2.Hash();
57 if (n1 == n2 && q1 != q2) {
58 VLOG(1) <<
"Isomorphic: Weight hash collision";
66 using StateId =
typename Arc::StateId;
75 comp_(delta, &error_) {}
83 VLOG(1) <<
"Isomorphic: Only one of the FSTs is empty.";
86 PairState(fst1_->Start(), fst2_->Start());
87 while (!queue_.empty()) {
88 const auto &[state1, state2] = queue_.front();
89 if (!IsIsomorphicState(state1, state2)) {
91 VLOG(1) <<
"Isomorphic: Non-determinism as an unweighted automaton. " 92 <<
"state1: " << state1 <<
" state2: " << state2;
102 bool Error()
const {
return error_; }
108 ArcCompare(
float delta,
bool *error) : delta_(delta), error_(error) {}
110 bool operator()(
const Arc &arc1,
const Arc &arc2)
const {
111 if (arc1.ilabel < arc2.ilabel)
return true;
112 if (arc1.ilabel > arc2.ilabel)
return false;
113 if (arc1.olabel < arc2.olabel)
return true;
114 if (arc1.olabel > arc2.olabel)
return false;
115 if (!
ApproxEqual(arc1.weight, arc2.weight, delta_)) {
116 return WeightCompare(arc1.weight, arc2.weight, delta_, error_);
118 return arc1.nextstate < arc2.nextstate;
128 bool PairState(StateId s1, StateId s2) {
129 if (state_pairs_.size() <= s1) state_pairs_.resize(s1 + 1,
kNoStateId);
130 if (state_pairs_[s1] == s2) {
135 VLOG(3) <<
"Pairing states: (" << s1 <<
", " << s2 <<
")";
136 state_pairs_[s1] = s2;
137 queue_.emplace(s1, s2);
142 bool IsIsomorphicState(StateId s1, StateId s2);
144 std::unique_ptr<Fst<Arc>> fst1_;
145 std::unique_ptr<Fst<Arc>> fst2_;
147 std::vector<Arc> arcs1_;
148 std::vector<Arc> arcs2_;
149 std::vector<StateId> state_pairs_;
150 std::queue<std::pair<StateId, StateId>> queue_;
158 if (!
ApproxEqual(fst1_->Final(s1), fst2_->Final(s2), delta_)) {
159 VLOG(1) <<
"Isomorphic: Final weights not equal to within delta=" << delta_
161 <<
"fst1.Final(" << s1 <<
") = " << fst1_->Final(s1) <<
", " 162 <<
"fst2.Final(" << s2 <<
") = " << fst2_->Final(s2);
165 const auto narcs1 = fst1_->NumArcs(s1);
166 const auto narcs2 = fst2_->NumArcs(s2);
167 if (narcs1 != narcs2) {
168 VLOG(1) <<
"Isomorphic: NumArcs not equal. " 169 <<
"fst1.NumArcs(" << s1 <<
") = " << narcs1 <<
", " 170 <<
"fst2.NumArcs(" << s2 <<
") = " << narcs2;
176 arcs1_.reserve(narcs1);
178 arcs2_.reserve(narcs2);
180 arcs1_.push_back(aiter1.
Value());
181 arcs2_.push_back(aiter2.
Value());
183 std::sort(arcs1_.begin(), arcs1_.end(), comp_);
184 std::sort(arcs2_.begin(), arcs2_.end(), comp_);
185 for (
size_t i = 0; i < arcs1_.size(); ++i) {
186 const auto &arc1 = arcs1_[i];
187 const auto &arc2 = arcs2_[i];
188 if (arc1.ilabel != arc2.ilabel) {
189 VLOG(1) <<
"Isomorphic: ilabels not equal. " 190 <<
"state1: " << s1 <<
" arc1: *" << arc1.ilabel <<
"* " 191 << arc1.olabel <<
" " << arc1.weight <<
" " << arc1.nextstate
192 <<
" state2: " << s2 <<
" arc2: *" << arc2.ilabel <<
"* " 193 << arc2.olabel <<
" " << arc2.weight <<
" " << arc2.nextstate;
196 if (arc1.olabel != arc2.olabel) {
197 VLOG(1) <<
"Isomorphic: olabels not equal. " 198 <<
"state1: " << s1 <<
" arc1: " << arc1.ilabel <<
" *" 199 << arc1.olabel <<
"* " << arc1.weight <<
" " << arc1.nextstate
200 <<
" state2: " << s2 <<
" arc2: " << arc2.ilabel <<
" *" 201 << arc2.olabel <<
"* " << arc2.weight <<
" " << arc2.nextstate;
204 if (!
ApproxEqual(arc1.weight, arc2.weight, delta_)) {
205 VLOG(1) <<
"Isomorphic: weights not ApproxEqual. " 206 <<
"state1: " << s1 <<
" arc1: " << arc1.ilabel <<
" " 207 << arc1.olabel <<
" *" << arc1.weight <<
"* " << arc1.nextstate
208 <<
" state2: " << s2 <<
" arc2: " << arc2.ilabel <<
" " 209 << arc2.olabel <<
" *" << arc2.weight <<
"* " << arc2.nextstate;
212 if (!PairState(arc1.nextstate, arc2.nextstate)) {
213 VLOG(1) <<
"Isomorphic: nextstates could not be paired. " 214 <<
"state1: " << s1 <<
" arc1: " << arc1.ilabel <<
" " 215 << arc1.olabel <<
" " << arc1.weight <<
" *" << arc1.nextstate
217 <<
"state2: " << s2 <<
" arc2: " << arc2.ilabel <<
" " 218 << arc2.olabel <<
" " << arc2.weight <<
" *" << arc2.nextstate
223 const auto &arc0 = arcs1_[i - 1];
224 if (arc1.ilabel == arc0.ilabel && arc1.olabel == arc0.olabel &&
229 VLOG(1) <<
"Isomorphic: Detected non-determinism as an unweighted " 230 <<
"automaton; deferring error. " 231 <<
"state: " << s1 <<
" arc1: " << arc1.ilabel <<
" " 232 << arc1.olabel <<
" " << arc1.weight <<
" " << arc1.nextstate
233 <<
" arc2: " << arc2.ilabel <<
" " << arc2.olabel <<
" " 234 << arc2.weight <<
" " << arc2.nextstate;
256 FSTERROR() <<
"Isomorphic: Cannot determine if inputs are isomorphic";
265 #endif // FST_ISOMORPHIC_H_ Isomorphism(const Fst< Arc > &fst1, const Fst< Arc > &fst2, float delta)
bool WeightCompare(const Weight &w1, const Weight &w2, float, bool *)
const Arc & Value() const
bool Isomorphic(FarReader< Arc > &reader1, FarReader< Arc > &reader2, float delta=kDelta, std::string_view begin_key="", std::string_view end_key="")
bool ApproxEqual(const ErrorWeight &, const ErrorWeight &, float)