20 #ifndef FST_EQUIVALENT_H_ 21 #define FST_EQUIVALENT_H_ 41 #include <unordered_map> 75 : (
static_cast<MappedId>(s) << 1) + which_fst;
80 return static_cast<StateId>((--id) >> 1);
86 return (kDeadState == s) ?
false 92 const auto repr = sets->
FindSet(
id);
93 if (repr != kInvalidId) {
128 float delta =
kDelta,
bool *error =
nullptr) {
129 using Weight =
typename Arc::Weight;
130 if (error) *error =
false;
134 FSTERROR() <<
"Equivalent: Input/output symbol tables of 1st argument " 135 <<
"do not match input/output symbol tables of 2nd argument";
136 if (error) *error =
true;
142 FSTERROR() <<
"Equivalent: 1st argument not an" 143 <<
" epsilon-free deterministic acceptor";
144 if (error) *error =
true;
148 FSTERROR() <<
"Equivalent: 2nd argument not an" 149 <<
" epsilon-free deterministic acceptor";
150 if (error) *error =
true;
167 using MappedId =
typename Util::MappedId;
168 enum { FST1 = 1, FST2 = 2 };
169 auto s1 = Util::MapState(fst1.
Start(), FST1);
170 auto s2 = Util::MapState(fst2.
Start(), FST2);
174 eq_classes.MakeSet(s1);
175 eq_classes.MakeSet(s2);
179 using Label2StatePairMap =
180 std::unordered_map<typename Arc::Label, std::pair<MappedId, MappedId>>;
181 Label2StatePairMap arc_pairs;
183 std::queue<std::pair<MappedId, MappedId>> q;
186 if (Util::IsFinal(fst1, s1) != Util::IsFinal(fst2, s2)) ret =
false;
190 for (q.emplace(s1, s2); ret && !q.empty(); q.pop()) {
191 s1 = q.front().first;
192 s2 = q.front().second;
194 const auto rep1 = Util::FindSet(&eq_classes, s1);
195 const auto rep2 = Util::FindSet(&eq_classes, s2);
197 eq_classes.Union(rep1, rep2);
200 if (Util::kDeadState != s1) {
202 for (; !arc_iter.
Done(); arc_iter.
Next()) {
203 const auto &arc = arc_iter.
Value();
205 if (arc.weight != Weight::Zero()) {
206 arc_pairs[arc.ilabel].first = Util::MapState(arc.nextstate, FST1);
211 if (Util::kDeadState != s2) {
213 for (; !arc_iter.
Done(); arc_iter.
Next()) {
214 const auto &arc = arc_iter.
Value();
216 if (arc.weight != Weight::Zero()) {
217 arc_pairs[arc.ilabel].second = Util::MapState(arc.nextstate, FST2);
222 for (
const auto &arc_iter : arc_pairs) {
223 const auto &pair = arc_iter.second;
224 if (Util::IsFinal(fst1, pair.first) !=
225 Util::IsFinal(fst2, pair.second)) {
235 if (error) *error =
true;
243 #endif // FST_EQUIVALENT_H_
void ArcMap(MutableFst< A > *fst, C *mapper)
static constexpr MappedId kDeadState
virtual uint64_t Properties(uint64_t mask, bool test) const =0
static MappedId MapState(StateId s, int32_t which_fst)
constexpr uint64_t kError
virtual Weight Final(StateId) const =0
const Arc & Value() const
constexpr uint8_t kEncodeLabels
constexpr uint64_t kNoEpsilons
static MappedId FindSet(UnionFind< MappedId > *sets, MappedId id)
static StateId UnMapState(MappedId id)
virtual StateId Start() const =0
typename Arc::Weight Weight
constexpr uint64_t kIDeterministic
void Push(MutableFst< Arc > *fst, ReweightType type=REWEIGHT_TO_INITIAL, float delta=kShortestDelta, bool remove_total_weight=false)
constexpr uint8_t kEncodeWeights
constexpr uint64_t kUnweighted
virtual const SymbolTable * InputSymbols() const =0
bool Equivalent(const Fst< Arc > &fst1, const Fst< Arc > &fst2, float delta=kDelta, bool *error=nullptr)
typename Arc::StateId StateId
bool CompatSymbols(const SymbolTable *syms1, const SymbolTable *syms2, bool warning=true)
static bool IsFinal(const Fst< Arc > &fa, MappedId s)
constexpr uint64_t kAcceptor
virtual const SymbolTable * OutputSymbols() const =0
static constexpr MappedId kInvalidId