23 #ifndef FST_ISOMORPHIC_H_ 24 #define FST_ISOMORPHIC_H_ 30 #include <type_traits> 43 template <
class Weight,
44 typename std::enable_if_t<IsIdempotent<Weight>::value> * =
nullptr>
50 template <
class Weight,
51 typename std::enable_if_t<!IsIdempotent<Weight>::value> * =
nullptr>
52 bool WeightCompare(
const Weight &w1,
const Weight &w2,
float delta,
55 const auto q1 = w1.Quantize(delta);
56 const auto q2 = w2.Quantize(delta);
57 const auto n1 = q1.Hash();
58 const auto n2 = q2.Hash();
60 if (n1 == n2 && q1 != q2) {
61 VLOG(1) <<
"Isomorphic: Weight hash collision";
69 using StateId =
typename Arc::StateId;
78 comp_(delta, &error_) {}
86 VLOG(1) <<
"Isomorphic: Only one of the FSTs is empty.";
89 PairState(fst1_->Start(), fst2_->Start());
90 while (!queue_.empty()) {
91 const auto &[state1, state2] = queue_.front();
92 if (!IsIsomorphicState(state1, state2)) {
94 VLOG(1) <<
"Isomorphic: Non-determinism as an unweighted automaton. " 95 <<
"state1: " << state1 <<
" state2: " << state2;
105 bool Error()
const {
return error_; }
111 ArcCompare(
float delta,
bool *error) : delta_(delta), error_(error) {}
113 bool operator()(
const Arc &arc1,
const Arc &arc2)
const {
114 if (arc1.ilabel < arc2.ilabel)
return true;
115 if (arc1.ilabel > arc2.ilabel)
return false;
116 if (arc1.olabel < arc2.olabel)
return true;
117 if (arc1.olabel > arc2.olabel)
return false;
118 if (!
ApproxEqual(arc1.weight, arc2.weight, delta_)) {
119 return WeightCompare(arc1.weight, arc2.weight, delta_, error_);
121 return arc1.nextstate < arc2.nextstate;
131 bool PairState(StateId s1, StateId s2) {
132 if (state_pairs_.size() <= s1) state_pairs_.resize(s1 + 1,
kNoStateId);
133 if (state_pairs_[s1] == s2) {
138 VLOG(3) <<
"Pairing states: (" << s1 <<
", " << s2 <<
")";
139 state_pairs_[s1] = s2;
140 queue_.emplace(s1, s2);
145 bool IsIsomorphicState(StateId s1, StateId s2);
147 std::unique_ptr<Fst<Arc>> fst1_;
148 std::unique_ptr<Fst<Arc>> fst2_;
150 std::vector<Arc> arcs1_;
151 std::vector<Arc> arcs2_;
152 std::vector<StateId> state_pairs_;
153 std::queue<std::pair<StateId, StateId>> queue_;
161 if (!
ApproxEqual(fst1_->Final(s1), fst2_->Final(s2), delta_)) {
162 VLOG(1) <<
"Isomorphic: Final weights not equal to within delta=" << delta_
164 <<
"fst1.Final(" << s1 <<
") = " << fst1_->Final(s1) <<
", " 165 <<
"fst2.Final(" << s2 <<
") = " << fst2_->Final(s2);
168 const auto narcs1 = fst1_->NumArcs(s1);
169 const auto narcs2 = fst2_->NumArcs(s2);
170 if (narcs1 != narcs2) {
171 VLOG(1) <<
"Isomorphic: NumArcs not equal. " 172 <<
"fst1.NumArcs(" << s1 <<
") = " << narcs1 <<
", " 173 <<
"fst2.NumArcs(" << s2 <<
") = " << narcs2;
179 arcs1_.reserve(narcs1);
181 arcs2_.reserve(narcs2);
183 arcs1_.push_back(aiter1.
Value());
184 arcs2_.push_back(aiter2.
Value());
186 std::sort(arcs1_.begin(), arcs1_.end(), comp_);
187 std::sort(arcs2_.begin(), arcs2_.end(), comp_);
188 for (
size_t i = 0; i < arcs1_.size(); ++i) {
189 const auto &arc1 = arcs1_[i];
190 const auto &arc2 = arcs2_[i];
191 if (arc1.ilabel != arc2.ilabel) {
192 VLOG(1) <<
"Isomorphic: ilabels not equal. " 193 <<
"state1: " << s1 <<
" arc1: *" << arc1.ilabel <<
"* " 194 << arc1.olabel <<
" " << arc1.weight <<
" " << arc1.nextstate
195 <<
" state2: " << s2 <<
" arc2: *" << arc2.ilabel <<
"* " 196 << arc2.olabel <<
" " << arc2.weight <<
" " << arc2.nextstate;
199 if (arc1.olabel != arc2.olabel) {
200 VLOG(1) <<
"Isomorphic: olabels not equal. " 201 <<
"state1: " << s1 <<
" arc1: " << arc1.ilabel <<
" *" 202 << arc1.olabel <<
"* " << arc1.weight <<
" " << arc1.nextstate
203 <<
" state2: " << s2 <<
" arc2: " << arc2.ilabel <<
" *" 204 << arc2.olabel <<
"* " << arc2.weight <<
" " << arc2.nextstate;
207 if (!
ApproxEqual(arc1.weight, arc2.weight, delta_)) {
208 VLOG(1) <<
"Isomorphic: weights not ApproxEqual. " 209 <<
"state1: " << s1 <<
" arc1: " << arc1.ilabel <<
" " 210 << arc1.olabel <<
" *" << arc1.weight <<
"* " << arc1.nextstate
211 <<
" state2: " << s2 <<
" arc2: " << arc2.ilabel <<
" " 212 << arc2.olabel <<
" *" << arc2.weight <<
"* " << arc2.nextstate;
215 if (!PairState(arc1.nextstate, arc2.nextstate)) {
216 VLOG(1) <<
"Isomorphic: nextstates could not be paired. " 217 <<
"state1: " << s1 <<
" arc1: " << arc1.ilabel <<
" " 218 << arc1.olabel <<
" " << arc1.weight <<
" *" << arc1.nextstate
220 <<
"state2: " << s2 <<
" arc2: " << arc2.ilabel <<
" " 221 << arc2.olabel <<
" " << arc2.weight <<
" *" << arc2.nextstate
226 const auto &arc0 = arcs1_[i - 1];
227 if (arc1.ilabel == arc0.ilabel && arc1.olabel == arc0.olabel &&
232 VLOG(1) <<
"Isomorphic: Detected non-determinism as an unweighted " 233 <<
"automaton; deferring error. " 234 <<
"state: " << s1 <<
" arc1: " << arc1.ilabel <<
" " 235 << arc1.olabel <<
" " << arc1.weight <<
" " << arc1.nextstate
236 <<
" arc2: " << arc2.ilabel <<
" " << arc2.olabel <<
" " 237 << arc2.weight <<
" " << arc2.nextstate;
259 FSTERROR() <<
"Isomorphic: Cannot determine if inputs are isomorphic";
268 #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)