14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// equivalent.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file Functions and classes to determine the equivalence of two 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FSTs. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_EQUIVALENT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_EQUIVALENT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2473018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers#include <unordered_map> 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/encode.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/push.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/union-find.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/vector-fst.h" 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Traits-like struct holding utility functions/typedefs/constants for 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the equivalence algorithm. 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Encoding device: in order to make the statesets of the two acceptors 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// disjoint, we map Arc::StateId on the type MappedId. The states of 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the first acceptor are mapped on odd numbers (s -> 2s + 1), and 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// those of the second one on even numbers (s -> 2s + 2). The number 0 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// is reserved for an implicit (non-final) 'dead state' (required for 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the correct treatment of non-coaccessible states; kNoStateId is 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// mapped to kDeadState for both acceptors). The union-find algorithm 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// operates on the mapped IDs. 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct EquivalenceUtil { 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef int32 MappedId; // ID for an equivalence class. 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // MappedId for an implicit dead state. 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const MappedId kDeadState = 0; 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // MappedId for lookup failure. 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const MappedId kInvalidId = -1; 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Maps state ID to the representative of the corresponding 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // equivalence class. The parameter 'which_fst' takes the values 1 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // and 2, identifying the input FST. 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static MappedId MapState(StateId s, int32 which_fst) { 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (kNoStateId == s) 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ? 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kDeadState 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (static_cast<MappedId>(s) << 1) + which_fst; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Maps set ID to State ID. 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static StateId UnMapState(MappedId id) { 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return static_cast<StateId>((--id) >> 1); 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Convenience function: checks if state with MappedId 's' is final 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // in acceptor 'fa'. 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static bool IsFinal(const Fst<Arc> &fa, MappedId s) { 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (kDeadState == s) ? 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project false : (fa.Final(UnMapState(s)) != Weight::Zero()); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Convenience function: returns the representative of 'id' in 'sets', 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // creating a new set if needed. 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static MappedId FindSet(UnionFind<MappedId> *sets, MappedId id) { 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MappedId repr = sets->FindSet(id); 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (repr != kInvalidId) { 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return repr; 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sets->MakeSet(id); 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return id; 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Equivalence checking algorithm: determines if the two FSTs 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// <code>fst1</code> and <code>fst2</code> are equivalent. The input 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FSTs must be deterministic input-side epsilon-free acceptors, 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// unweighted or with weights over a left semiring. Two acceptors are 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// considered equivalent if they accept exactly the same set of 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// strings (with the same weights). 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The algorithm (cf. Aho, Hopcroft and Ullman, "The Design and 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Analysis of Computer Programs") successively constructs sets of 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// states that can be reached by the same prefixes, starting with a 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// set containing the start states of both acceptors. A disjoint tree 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// forest (the union-find algorithm) is used to represent the sets of 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// states. The algorithm returns 'false' if one of the constructed 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// sets contains both final and non-final states. 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: quasi-linear, i.e. O(n G(n)), where 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// n = |S1| + |S2| is the number of states in both acceptors 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// G(n) is a very slowly growing function that can be approximated 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// by 4 by all practical purposes. 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectbool Equivalent(const Fst<Arc> &fst1, const Fst<Arc> &fst2) { 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Check properties first: 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = kNoEpsilons | kIDeterministic | kAcceptor; 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst1.Properties(props, true) != props) { 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "Equivalent: first argument not an" 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << " epsilon-free deterministic acceptor"; 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst2.Properties(props, true) != props) { 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "Equivalent: second argument not an" 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << " epsilon-free deterministic acceptor"; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((fst1.Properties(kUnweighted , true) != kUnweighted) 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project || (fst2.Properties(kUnweighted , true) != kUnweighted)) { 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VectorFst<Arc> efst1(fst1); 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VectorFst<Arc> efst2(fst2); 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Push(&efst1, REWEIGHT_TO_INITIAL); 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Push(&efst2, REWEIGHT_TO_INITIAL); 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(&efst1, QuantizeMapper<Arc>()); 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(&efst2, QuantizeMapper<Arc>()); 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project EncodeMapper<Arc> mapper(kEncodeWeights|kEncodeLabels, ENCODE); 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(&efst1, &mapper); 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(&efst2, &mapper); 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Equivalent(efst1, efst2); 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Convenience typedefs: 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef EquivalenceUtil<Arc> Util; 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Util::MappedId MappedId; 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enum { FST1 = 1, FST2 = 2 }; // Required by Util::MapState(...) 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MappedId s1 = Util::MapState(fst1.Start(), FST1); 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MappedId s2 = Util::MapState(fst2.Start(), FST2); 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // The union-find structure. 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project UnionFind<MappedId> eq_classes(1000, Util::kInvalidId); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Initialize the union-find structure. 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project eq_classes.MakeSet(s1); 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project eq_classes.MakeSet(s2); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Early return if the start states differ w.r.t. being final. 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (Util::IsFinal(fst1, s1) != Util::IsFinal(fst2, s2)) { 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Data structure for the (partial) acceptor transition function of 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // fst1 and fst2: input labels mapped to pairs of MappedId's 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // representing destination states of the corresponding arcs in fst1 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // and fst2, respectively. 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef 16473018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers std::unordered_map<typename Arc::Label, pair<MappedId, MappedId> > 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label2StatePairMap; 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label2StatePairMap arc_pairs; 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Pairs of MappedId's to be processed, organized in a queue. 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project deque<pair<MappedId, MappedId> > q; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Main loop: explores the two acceptors in a breadth-first manner, 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // updating the equivalence relation on the statesets. Loop 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invariant: each block of states contains either final states only 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // or non-final states only. 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (q.push_back(make_pair(s1, s2)); !q.empty(); q.pop_front()) { 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project s1 = q.front().first; 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project s2 = q.front().second; 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Representatives of the equivalence classes of s1/s2. 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MappedId rep1 = Util::FindSet(&eq_classes, s1); 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MappedId rep2 = Util::FindSet(&eq_classes, s2); 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (rep1 != rep2) { 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project eq_classes.Union(rep1, rep2); 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_pairs.clear(); 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Copy outgoing arcs starting at s1 into the hashtable. 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (Util::kDeadState != s1) { 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator<Fst<Arc> > arc_iter(fst1, Util::UnMapState(s1)); 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; !arc_iter.Done(); arc_iter.Next()) { 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &arc = arc_iter.Value(); 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc.weight != Weight::Zero()) { // Zero-weight arcs 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // are treated as 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // non-exisitent. 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_pairs[arc.ilabel].first = Util::MapState(arc.nextstate, FST1); 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Copy outgoing arcs starting at s2 into the hashtable. 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (Util::kDeadState != s2) { 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator<Fst<Arc> > arc_iter(fst2, Util::UnMapState(s2)); 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; !arc_iter.Done(); arc_iter.Next()) { 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &arc = arc_iter.Value(); 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc.weight != Weight::Zero()) { // Zero-weight arcs 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // are treated as 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // non-existent. 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_pairs[arc.ilabel].second = Util::MapState(arc.nextstate, FST2); 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Iterate through the hashtable and process pairs of target 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // states. 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Label2StatePairMap::const_iterator 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_iter = arc_pairs.begin(); 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc_iter != arc_pairs.end(); 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++arc_iter) { 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const pair<MappedId, MappedId> &p = arc_iter->second; 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (Util::IsFinal(fst1, p.first) != Util::IsFinal(fst2, p.second)) { 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Detected inconsistency: return false. 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project q.push_back(p); 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_EQUIVALENT_H__ 233