14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// minimize.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 minimize a finite state acceptor 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_MINIMIZE_H__ 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_MINIMIZE_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <map> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <queue> 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/arcsort.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/arcsum.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/connect.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/dfs-visit.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/encode.h" 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/factor-weight.h" 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/fst.h" 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/mutable-fst.h" 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/partition.h" 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/push.h" 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/queue.h" 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/reverse.h" 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// comparator for creating partition based on sorting on 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - states 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - final weight 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - out degree, 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - (input label, output label, weight, destination_block) 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateComparator { 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int32 kCompareFinal = 0x0000001; 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int32 kCompareOutDegree = 0x0000002; 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int32 kCompareArcs = 0x0000004; 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int32 kCompareAll = (kCompareFinal | 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kCompareOutDegree | 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kCompareArcs); 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateComparator(const Fst<A>& fst, 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Partition<typename A::StateId>& partition, 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int32 flags = kCompareAll) 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : fst_(fst), partition_(partition), flags_(flags) {} 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // compare state x with state y based on sort criteria 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const StateId x, const StateId y) const { 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // check for final state equivalence 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (flags_ & kCompareFinal) { 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ssize_t xfinal = fst_.Final(x).Hash(); 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const ssize_t yfinal = fst_.Final(y).Hash(); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (xfinal < yfinal) return true; 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (xfinal > yfinal) return false; 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (flags_ & kCompareOutDegree) { 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // check for # arcs 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst_.NumArcs(x) < fst_.NumArcs(y)) return true; 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst_.NumArcs(x) > fst_.NumArcs(y)) return false; 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (flags_ & kCompareArcs) { 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // # arcs are equal, check for arc match 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator<Fst<A> > aiter1(fst_, x), aiter2(fst_, y); 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter1.Done() && !aiter2.Done(); aiter1.Next(), aiter2.Next()) { 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A& arc1 = aiter1.Value(); 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A& arc2 = aiter2.Value(); 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc1.ilabel < arc2.ilabel) return true; 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc1.ilabel > arc2.ilabel) return false; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (partition_.class_id(arc1.nextstate) < 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partition_.class_id(arc2.nextstate)) return true; 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (partition_.class_id(arc1.nextstate) > 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partition_.class_id(arc2.nextstate)) return false; 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A>& fst_; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Partition<typename A::StateId>& partition_; 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const int32 flags_; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes equivalence classes for cyclic Fsts. For cyclic minimization 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// we use the classic HopCroft minimization algorithm, which is of 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// O(E)log(N), 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where E is the number of edges in the machine and N is number of states. 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The following paper describes the original algorithm 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// An N Log N algorithm for minimizing states in a finite automaton 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// by John HopCroft, January 1971 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, class Queue> 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass CyclicMinimizer { 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId ClassId; 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef ReverseArc<A> RevA; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CyclicMinimizer(const ExpandedFst<A>& fst) { 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Initialize(fst); 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Compute(fst); 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~CyclicMinimizer() { 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete aiter_queue_; 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Partition<StateId>& partition() const { 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return P_; 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // helper classes 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef ArcIterator<Fst<RevA> > ArcIter; 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class ArcIterCompare { 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterCompare(const Partition<StateId>& partition) 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : partition_(partition) {} 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterCompare(const ArcIterCompare& comp) 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : partition_(comp.partition_) {} 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // compare two iterators based on there input labels, and proto state 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // (partition class Ids) 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const ArcIter* x, const ArcIter* y) const { 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const RevA& xarc = x->Value(); 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const RevA& yarc = y->Value(); 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (xarc.ilabel > yarc.ilabel); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Partition<StateId>& partition_; 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef priority_queue<ArcIter*, vector<ArcIter*>, ArcIterCompare> 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterQueue; 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // helper methods 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // prepartitions the space into equivalence classes with 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // same final weight 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // same # arcs per state 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // same outgoing arcs 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void PrePartition(const Fst<A>& fst) { 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(5) << "PrePartition"; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef map<StateId, StateId, StateComparator<A> > EquivalenceMap; 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateComparator<A> comp(fst, P_, StateComparator<A>::kCompareFinal); 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project EquivalenceMap equiv_map(comp); 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateIterator<Fst<A> > siter(fst); 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId class_id = P_.AddClass(); 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project P_.Add(siter.Value(), class_id); 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project equiv_map[siter.Value()] = class_id; 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project L_.Enqueue(class_id); 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (siter.Next(); !siter.Done(); siter.Next()) { 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename EquivalenceMap::const_iterator it = equiv_map.find(s); 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (it == equiv_map.end()) { 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class_id = P_.AddClass(); 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project P_.Add(s, class_id); 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project equiv_map[s] = class_id; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project L_.Enqueue(class_id); 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project P_.Add(s, it->second); 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project equiv_map[s] = it->second; 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(5) << "Initial Partition: " << P_.num_classes(); 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // - Create inverse transition Tr_ = rev(fst) 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // - loop over states in fst and split on final, creating two blocks 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // in the partition corresponding to final, non-final 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Initialize(const Fst<A>& fst) { 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // construct Tr 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Reverse(fst, &Tr_); 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ILabelCompare<RevA> ilabel_comp; 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSort(&Tr_, ilabel_comp); 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // initial split (F, S - F) 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project P_.Initialize(Tr_.NumStates() - 1); 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // prep partition 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PrePartition(fst); 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // allocate arc iterator queue 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterCompare comp(P_); 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_queue_ = new ArcIterQueue(comp); 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // partition all classes with destination C 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Split(ClassId C) { 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Prep priority queue. Open arc iterator for each state in C, and 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // insert into priority queue. 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (PartitionIterator<StateId> siter(P_, C); 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !siter.Done(); siter.Next()) { 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (Tr_.NumArcs(s + 1)) 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_queue_->push(new ArcIterator<Fst<RevA> >(Tr_, s + 1)); 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Now pop arc iterator from queue, split entering equivalence class 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // re-insert updated iterator into queue. 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label prev_label = -1; 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!aiter_queue_->empty()) { 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator<Fst<RevA> >* aiter = aiter_queue_->top(); 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_queue_->pop(); 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (aiter->Done()) { 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete aiter; 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project continue; 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const RevA& arc = aiter->Value(); 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId from_state = aiter->Value().nextstate - 1; 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label from_label = arc.ilabel; 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (prev_label != from_label) 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project P_.FinalizeSplit(&L_); 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId from_class = P_.class_id(from_state); 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (P_.class_size(from_class) > 1) 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project P_.SplitOn(from_state); 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project prev_label = from_label; 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter->Next(); 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (aiter->Done()) 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete aiter; 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter_queue_->push(aiter); 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project P_.FinalizeSplit(&L_); 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Main loop for hopcroft minimization. 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Compute(const Fst<A>& fst) { 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // process active classes (FIFO, or FILO) 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!L_.Empty()) { 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ClassId C = L_.Head(); 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project L_.Dequeue(); 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // split on C, all labels in C 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Split(C); 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // helper data 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Partioning of states into equivalence classes 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Partition<StateId> P_; 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // L = set of active classes to be processed in partition P 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Queue L_; 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // reverse transition function 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VectorFst<RevA> Tr_; 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Priority queue of open arc iterators for all states in the 'splitter' 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // equivalence class 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterQueue* aiter_queue_; 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computes equivalence classes for acyclic Fsts. The implementation details 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// for this algorithms is documented by the following paper. 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Minimization of acyclic deterministic automata in linear time 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Dominque Revuz 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity O(|E|) 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass AcyclicMinimizer { 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId ClassId; 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AcyclicMinimizer(const ExpandedFst<A>& fst) { 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Initialize(fst); 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Refine(fst); 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Partition<StateId>& partition() { 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return partition_; 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // helper classes 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // DFS visitor to compute the height (distance) to final state. 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class HeightVisitor { 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project HeightVisitor() : max_height_(0), num_states_(0) { } 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invoked before dfs visit 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitVisit(const Fst<A>& fst) {} 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invoked when state is discovered (2nd arg is DFS tree root) 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool InitState(StateId s, StateId root) { 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // extend height array and initialize height (distance) to 0 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = height_.size(); i <= (size_t)s; ++i) 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project height_.push_back(-1); 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s >= (StateId)num_states_) num_states_ = s + 1; 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invoked when tree arc examined (to undiscoverted state) 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool TreeArc(StateId s, const A& arc) { 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invoked when back arc examined (to unfinished state) 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool BackArc(StateId s, const A& arc) { 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invoked when forward or cross arc examined (to finished state) 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool ForwardOrCrossArc(StateId s, const A& arc) { 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (height_[arc.nextstate] + 1 > height_[s]) 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project height_[s] = height_[arc.nextstate] + 1; 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invoked when state finished (parent is kNoStateId for tree root) 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void FinishState(StateId s, StateId parent, const A* parent_arc) { 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (height_[s] == -1) height_[s] = 0; 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId h = height_[s] + 1; 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (parent >= 0) { 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (h > height_[parent]) height_[parent] = h; 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (h > (StateId)max_height_) max_height_ = h; 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // invoked after DFS visit 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void FinishVisit() {} 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t max_height() const { return max_height_; } 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<StateId>& height() const { return height_; } 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 36873018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers size_t num_states() const { return num_states_; } 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> height_; 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t max_height_; 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t num_states_; 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // helper methods 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // cluster states according to height (distance to final state) 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Initialize(const Fst<A>& fst) { 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // compute height (distance to final state) 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project HeightVisitor hvisitor; 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(fst, &hvisitor); 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // create initial partition based on height 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partition_.Initialize(hvisitor.num_states()); 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partition_.AllocateClasses(hvisitor.max_height() + 1); 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<StateId>& hstates = hvisitor.height(); 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t s = 0; s < hstates.size(); ++s) 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partition_.Add(s, hstates[s]); 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // refine states based on arc sort (out degree, arc equivalence) 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Refine(const Fst<A>& fst) { 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef map<StateId, StateId, StateComparator<A> > EquivalenceMap; 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateComparator<A> comp(fst, partition_); 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // start with tail (height = 0) 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t height = partition_.num_classes(); 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t h = 0; h < height; ++h) { 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project EquivalenceMap equiv_classes(comp); 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // sort states within equivalence class 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PartitionIterator<StateId> siter(partition_, h); 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project equiv_classes[siter.Value()] = h; 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (siter.Next(); !siter.Done(); siter.Next()) { 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StateId s = siter.Value(); 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename EquivalenceMap::const_iterator it = equiv_classes.find(s); 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (it == equiv_classes.end()) 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project equiv_classes[s] = partition_.AddClass(); 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project equiv_classes[s] = it->second; 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // create refined partition 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (siter.Reset(); !siter.Done();) { 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StateId s = siter.Value(); 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StateId old_class = partition_.class_id(s); 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const StateId new_class = equiv_classes[s]; 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // a move operation can invalidate the iterator, so 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // we first update the iterator to the next element 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // before we move the current element out of the list 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter.Next(); 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (old_class != new_class) 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partition_.Move(s, new_class); 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Partition<StateId> partition_; 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Given a partition and a mutable fst, merge states of Fst inplace 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// (i.e. destructively). Merging works by taking the first state in 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// a class of the partition to be the representative state for the class. 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Each arc is then reconnected to this state. All states in the class 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// are merged by adding there arcs to the representative state. 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid MergeStates( 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Partition<typename A::StateId>& partition, MutableFst<A>* fst) { 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> state_map(partition.num_classes()); 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; i < (size_t)partition.num_classes(); ++i) { 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PartitionIterator<StateId> siter(partition, i); 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_map[i] = siter.Value(); // first state in partition; 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // relabel destination states 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t c = 0; c < (size_t)partition.num_classes(); ++c) { 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (PartitionIterator<StateId> siter(partition, c); 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !siter.Done(); siter.Next()) { 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (MutableArcIterator<MutableFst<A> > aiter(fst, s); 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); aiter.Next()) { 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A arc = aiter.Value(); 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate = state_map[partition.class_id(arc.nextstate)]; 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == state_map[c]) // first state just set destination 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.SetValue(arc); 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(state_map[c], arc); 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetStart(state_map[partition.class_id(fst->Start())]); 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(fst); 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid AcceptorMinimize(MutableFst<A>* fst) { 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(fst->Properties(kAcceptor | kUnweighted, true))) 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "Input Fst is not an unweighted acceptor"; 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // connect fst before minimization, handles disconnected states 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(fst); 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst->NumStates() == 0) return; 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst->Properties(kAcyclic, true)) { 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Acyclic minimization (revuz) 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "Acyclic Minimization"; 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AcyclicMinimizer<A> minimizer(*fst); 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MergeStates(minimizer.partition(), fst); 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Cyclic minimizaton (hopcroft) 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "Cyclic Minimization"; 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CyclicMinimizer<A, LifoQueue<StateId> > minimizer(*fst); 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MergeStates(minimizer.partition(), fst); 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // sort arcs before summing 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSort(fst, ILabelCompare<A>()); 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // sum in appropriate semiring 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSum(fst); 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// In place minimization of unweighted, deterministic acceptors 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// For acyclic automata we use an algorithm from Dominique Revuz that is 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// linear in the number of arcs (edges) in the machine. 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity = O(E) 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// For cyclic automata we use the classical hopcroft minimization. 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity = O(|E|log(|N|) 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Minimize(MutableFst<A>* fst, MutableFst<A>* sfst = 0) { 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst->Properties(kAcceptor | kIDeterministic| 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kWeighted | kUnweighted, true); 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(props & kIDeterministic)) 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "Input Fst is not deterministic"; 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(props & kAcceptor)) { // weighted transducer 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VectorFst< GallicArc<A, STRING_LEFT> > gfst; 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(*fst, &gfst, ToGallicMapper<A, STRING_LEFT>()); 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->DeleteStates(); 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project gfst.SetProperties(kAcceptor, kAcceptor); 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Push(&gfst, REWEIGHT_TO_INITIAL); 5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(&gfst, QuantizeMapper< GallicArc<A, STRING_LEFT> >()); 5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project EncodeMapper< GallicArc<A, STRING_LEFT> > 5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project encoder(kEncodeLabels | kEncodeWeights, ENCODE); 5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Encode(&gfst, &encoder); 5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AcceptorMinimize(&gfst); 5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Decode(&gfst, encoder); 5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (sfst == 0) { 5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FactorWeightFst< GallicArc<A, STRING_LEFT>, 5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GallicFactor<typename A::Label, 5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename A::Weight, STRING_LEFT> > fwfst(gfst); 5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(fwfst, fst, FromGallicMapper<A, STRING_LEFT>()); 5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sfst->SetOutputSymbols(fst->OutputSymbols()); 5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project GallicToNewSymbolsMapper<A, STRING_LEFT> mapper(sfst); 5414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(gfst, fst, mapper); 5424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetOutputSymbols(sfst->InputSymbols()); 5434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (props & kWeighted) { // weighted acceptor 5454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Push(fst, REWEIGHT_TO_INITIAL); 5464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Map(fst, QuantizeMapper<A>()); 5474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project EncodeMapper<A> encoder(kEncodeLabels | kEncodeWeights, ENCODE); 5484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Encode(fst, &encoder); 5494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AcceptorMinimize(fst); 5504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Decode(fst, encoder); 5514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { // unweighted acceptor 5524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AcceptorMinimize(fst); 5534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 5574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_MINIMIZE_H__ 559