14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// determinize.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Functions and classes to determinize an FST. 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_DETERMINIZE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_DETERMINIZE_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <map> 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <ext/hash_map> 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectusing __gnu_cxx::hash_map; 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <ext/slist> 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectusing __gnu_cxx::slist; 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/factor-weight.h" 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/map.h" 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/test-properties.h" 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// COMMON DIVISORS - these are used in determinization to compute 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the transition weights. In the simplest case, it is just the same 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// as the semiring Plus(). However, other choices permit more efficient 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// determinization when the output contains strings. 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The default common divisor uses the semiring Plus. 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class W> 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass DefaultCommonDivisor { 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef W Weight; 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project W operator()(const W &w1, const W &w2) const { return Plus(w1, w2); } 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The label common divisor for a (left) string semiring selects a 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// single letter common prefix or the empty string. This is used in 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the determinization of output strings so that at most a single 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// letter will appear in the output of a transtion. 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename L, StringType S> 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass LabelCommonDivisor { 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef StringWeight<L, S> Weight; 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight operator()(const Weight &w1, const Weight &w2) const { 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, S> iter1(w1); 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringWeightIterator<L, S> iter2(w2); 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(StringWeight<L, S>::Properties() & kLeftSemiring)) 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "LabelCommonDivisor: Weight needs to be left semiring"; 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (w1.Size() == 0 || w2.Size() == 0) 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight::One(); 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (w1 == Weight::Zero()) 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight(iter2.Value()); 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (w2 == Weight::Zero()) 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight(iter1.Value()); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (iter1.Value() == iter2.Value()) 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight(iter1.Value()); 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight::One(); 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The gallic common divisor uses the label common divisor on the 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// string component and the template argument D common divisor on the 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// weight component, which defaults to the default common divisor. 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class L, class W, StringType S, class D = DefaultCommonDivisor<W> > 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass GallicCommonDivisor { 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef GallicWeight<L, W, S> Weight; 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight operator()(const Weight &w1, const Weight &w2) const { 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Weight(label_common_divisor_(w1.Value1(), w2.Value1()), 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project weight_common_divisor_(w1.Value2(), w2.Value2())); 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LabelCommonDivisor<L, S> label_common_divisor_; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project D weight_common_divisor_; 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Options for finite-state transducer determinization. 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct DeterminizeFstOptions : CacheOptions { 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta; // Quantization delta for subset weights 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit DeterminizeFstOptions(const CacheOptions &opts, float del = kDelta) 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheOptions(opts), delta(del) {} 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit DeterminizeFstOptions(float del = kDelta) : delta(del) {} 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation of delayed DeterminizeFst. This base class is 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// common to the variants that implement acceptor and transducer 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// determinization. 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass DeterminizeFstImplBase : public CacheImpl<A> { 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetType; 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetProperties; 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::Properties; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetInputSymbols; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetOutputSymbols; 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasStart; 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasFinal; 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasArcs; 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFstImplBase(const Fst<A> &fst, const CacheOptions &opts) 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheImpl<A>(opts), fst_(fst.Copy()) { 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetType("determinize"); 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst.Properties(kFstProperties, false); 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetProperties(DeterminizeProperties(props), kCopyProperties); 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetInputSymbols(fst.InputSymbols()); 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetOutputSymbols(fst.OutputSymbols()); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~DeterminizeFstImplBase() { delete fst_; } 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Start() { 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasStart()) { 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start = ComputeStart(); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start != kNoStateId) { 151ea4ad6085a8661b5513c394316108c0ef26f3e7bAl Sutton this->SetStart(start); 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Start(); 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight Final(StateId s) { 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasFinal(s)) { 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final = ComputeFinal(s); 160ea4ad6085a8661b5513c394316108c0ef26f3e7bAl Sutton this->SetFinal(s, final); 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Final(s); 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Expand(StateId s) = 0; 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumArcs(StateId s) { 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumArcs(s); 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumInputEpsilons(StateId s) { 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumInputEpsilons(s); 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumOutputEpsilons(StateId s) { 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumOutputEpsilons(s); 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitArcIterator(StateId s, ArcIteratorData<A> *data) { 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::InitArcIterator(s, data); 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId ComputeStart() = 0; 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight ComputeFinal(StateId s) = 0; 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project protected: 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst_; // Input Fst 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(DeterminizeFstImplBase); 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation of delayed determinization for weighted acceptors. 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// It is templated on the arc type A and the common divisor C. 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, class C> 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass DeterminizeFsaImpl : public DeterminizeFstImplBase<A> { 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using DeterminizeFstImplBase<A>::fst_; 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project struct Element { 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element() {} 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element(StateId s, Weight w) : state_id(s), weight(w) {} 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state_id; // Input state Id 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight weight; // Residual weight 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef slist<Element> Subset; 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef map<Label, Subset*> LabelMap; 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFsaImpl(const Fst<A> &fst, C common_divisor, 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const DeterminizeFstOptions &opts) 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : DeterminizeFstImplBase<A>(fst, opts), 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delta_(opts.delta), common_divisor_(common_divisor), 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project subset_hash_(0, SubsetKey(), SubsetEqual(&elements_)) { 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst.Properties(kAcceptor, true)) 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "DeterminizeFst: argument not an acceptor"; 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(Weight::Properties() & kLeftSemiring)) 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "DeterminizeFst: Weight needs to be left distributive: " 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << Weight::Type(); 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~DeterminizeFsaImpl() { 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (unsigned int i = 0; i < subsets_.size(); ++i) 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete subsets_[i]; 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId ComputeStart() { 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = fst_->Start(); 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == kNoStateId) 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return kNoStateId; 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element element(s, Weight::One()); 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Subset *subset = new Subset; 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project subset->push_front(element); 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FindState(subset); 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight ComputeFinal(StateId s) { 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Subset *subset = subsets_[s]; 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final = Weight::Zero(); 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::iterator siter = subset->begin(); 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter != subset->end(); 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++siter) { 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element &element = *siter; 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project final = Plus(final, Times(element.weight, 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst_->Final(element.state_id))); 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return final; 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Finds the state corresponding to a subset. Only creates a new state 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // if the subset is not found in the subset hash. FindState takes 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // ownership of the subset argument (so that it doesn't have to copy it 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // if it creates a new state). 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // The method exploits the following device: all pairs stored in the 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // associative container subset_hash_ are of the form (subset, 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // id(subset) + 1), i.e. subset_hash_[subset] > 0 if subset has been 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // stored previously. For unassigned subsets, the call to 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // subset_hash_[subset] creates a new pair (subset, 0). As a result, 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // subset_hash_[subset] == 0 iff subset is new. 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId FindState(Subset *subset) { 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId &assoc_value = subset_hash_[subset]; 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (assoc_value == 0) { // subset wasn't present; assign it a new ID 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project subsets_.push_back(subset); 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project assoc_value = subsets_.size(); 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete subset; 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return assoc_value - 1; // NB: assoc_value = ID + 1 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Computes the outgoing transitions from a state, creating new destination 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // states as needed. 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Expand(StateId s) { 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LabelMap label_map; 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LabelSubsets(s, &label_map); 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename LabelMap::iterator liter = label_map.begin(); 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project liter != label_map.end(); 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++liter) 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, liter->first, liter->second); 297ea4ad6085a8661b5513c394316108c0ef26f3e7bAl Sutton this->SetArcs(s); 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Constructs destination subsets per label. At return, subset 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // element weights include the input automaton label weights and the 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // subsets may contain duplicate states. 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void LabelSubsets(StateId s, LabelMap *label_map) { 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Subset *src_subset = subsets_[s]; 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::iterator siter = src_subset->begin(); 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter != src_subset->end(); 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++siter) { 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element &src_element = *siter; 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<A> > aiter(*fst_, src_element.state_id); 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) { 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A &arc = aiter.Value(); 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element dest_element(arc.nextstate, 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Times(src_element.weight, arc.weight)); 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Subset* &dest_subset = (*label_map)[arc.ilabel]; 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (dest_subset == 0) 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dest_subset = new Subset; 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dest_subset->push_front(dest_element); 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Adds an arc from state S to the destination state associated 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // with subset DEST_SUBSET (as created by LabelSubsets). 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void AddArc(StateId s, Label label, Subset *dest_subset) { 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A arc; 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.ilabel = label; 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.olabel = label; 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.weight = Weight::Zero(); 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename Subset::iterator oiter; 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::iterator diter = dest_subset->begin(); 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project diter != dest_subset->end();) { 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element &dest_element = *diter; 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Computes label weight. 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.weight = common_divisor_(arc.weight, dest_element.weight); 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)elements_.size() <= dest_element.state_id) 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project elements_.push_back(0); 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element *matching_element = elements_[dest_element.state_id]; 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (matching_element) { 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Found duplicate state: sums state weight and deletes dup. 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project matching_element->weight = Plus(matching_element->weight, 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dest_element.weight); 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++diter; 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dest_subset->erase_after(oiter); 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Saves element so we can check for duplicate for this state. 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project elements_[dest_element.state_id] = &dest_element; 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project oiter = diter; 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++diter; 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Divides out label weight from destination subset elements. 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Quantizes to ensure comparisons are effective. 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Clears element vector. 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::iterator diter = dest_subset->begin(); 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project diter != dest_subset->end(); 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++diter) { 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element &dest_element = *diter; 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dest_element.weight = Divide(dest_element.weight, arc.weight, 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DIVIDE_LEFT); 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dest_element.weight = dest_element.weight.Quantize(delta_); 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project elements_[dest_element.state_id] = 0; 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate = FindState(dest_subset); 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::AddArc(s, arc); 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Comparison object for hashing Subset(s). Subsets are not sorted in this 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // implementation, so ordering must not be assumed in the equivalence 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // test. 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class SubsetEqual { 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Constructor takes vector needed to check equality. See immediately 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // below for constraints on it. 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit SubsetEqual(vector<Element *> *elements) 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : elements_(elements) {} 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // At each call to operator(), elements_[state] must be defined and 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // NULL for each state in the subset arguments. When this operator 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // returns, elements_ will preserve that property. We keep it 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // full of NULLs so that it is ready for the next call. 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(Subset* subset1, Subset* subset2) const { 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (subset1->size() != subset2->size()) 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Loads first subset elements in element vector. 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::iterator iter1 = subset1->begin(); 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter1 != subset1->end(); 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++iter1) { 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element &element1 = *iter1; 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*elements_)[element1.state_id] = &element1; 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Checks second subset matches first via element vector. 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::iterator iter2 = subset2->begin(); 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter2 != subset2->end(); 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++iter2) { 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element &element2 = *iter2; 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element *element1 = (*elements_)[element2.state_id]; 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!element1 || element1->weight != element2.weight) { 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Mismatch found. Resets element vector before returning false. 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::iterator iter1 = subset1->begin(); 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter1 != subset1->end(); 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++iter1) 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*elements_)[iter1->state_id] = 0; 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*elements_)[element2.state_id] = 0; // Clears entry 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Element *> *elements_; 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Hash function for Subset to Fst states. Subset elements are not 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // sorted in this implementation, so the hash must be invariant 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // under subset reordering. 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class SubsetKey { 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t operator()(const Subset* subset) const { 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t hash = 0; 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (typename Subset::const_iterator iter = subset->begin(); 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project iter != subset->end(); 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++iter) { 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Element &element = *iter; 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int lshift = element.state_id % kPrime; 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int rshift = sizeof(size_t) - lshift; 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hash ^= element.state_id << lshift ^ 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project element.state_id >> rshift ^ 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project element.weight.Hash(); 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return hash; 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int kPrime = sizeof(size_t) == 8 ? 23 : 13; 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta_; // Quantization delta for subset weights 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project C common_divisor_; 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Used to test equivalence of subsets. 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Element *> elements_; 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Maps from StateId to Subset. 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Subset *> subsets_; 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Hashes from Subset to its StateId in the output automaton. 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef hash_map<Subset *, StateId, SubsetKey, SubsetEqual> 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SubsetHash; 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Hashes from Label to Subsets corr. to destination states of current state. 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SubsetHash subset_hash_; 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(DeterminizeFsaImpl); 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation of delayed determinization for transducers. 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Transducer determinization is implemented by mapping the input to 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the Gallic semiring as an acceptor whose weights contain the output 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// strings and using acceptor determinization above to determinize 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// that acceptor. 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, StringType S> 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass DeterminizeFstImpl : public DeterminizeFstImplBase<A> { 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef ToGallicMapper<A, S> ToMapper; 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef FromGallicMapper<A, S> FromMapper; 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename ToMapper::ToArc ToArc; 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef MapFst<A, ToArc, ToMapper> ToFst; 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef MapFst<ToArc, A, FromMapper> FromFst; 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef GallicCommonDivisor<Label, Weight, S> CommonDivisor; 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef GallicFactor<Label, Weight, S> FactorIterator; 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Defined after DeterminizeFst since it calls it. 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFstImpl(const Fst<A> &fst, const DeterminizeFstOptions &opts); 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~DeterminizeFstImpl() { delete from_fst_; } 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId ComputeStart() { return from_fst_->Start(); } 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight ComputeFinal(StateId s) { return from_fst_->Final(s); } 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Expand(StateId s) { 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator<FromFst> aiter(*from_fst_, s); 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::AddArc(s, aiter.Value()); 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::SetArcs(s); 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FromFst *from_fst_; 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(DeterminizeFstImpl); 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Determinizes a weighted transducer. This version is a delayed 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Fst. The result will be an equivalent FST that has the property 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// that no state has two transitions with the same input label. 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// For this algorithm, epsilon transitions are treated as regular 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// symbols (cf. RmEpsilon). 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The transducer must be functional. The weights must be (weakly) 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// left divisible (valid for TropicalWeight and LogWeight). 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Determinizable: exponential (polynomial in the size of the output) 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Non-determinizable) does not terminate 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The determinizable automata include all unweighted and all acyclic input. 5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// References: 5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Mehryar Mohri, "Finite-State Transducers in Language and Speech 5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Processing". Computational Linguistics, 23:2, 1997. 5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass DeterminizeFst : public Fst<A> { 5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class ArcIterator< DeterminizeFst<A> >; 5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheStateIterator< DeterminizeFst<A> >; 5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheArcIterator< DeterminizeFst<A> >; 5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <class B, StringType S> friend class DeterminizeFstImpl; 5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 5414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 5424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 5434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 5444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit DeterminizeFst(const Fst<A> &fst, 5464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const DeterminizeFstOptions &opts = DeterminizeFstOptions()) { 5474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst.Properties(kAcceptor, true)) { 5484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Calls implementation for acceptors. 5494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef DefaultCommonDivisor<Weight> D; 5504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_ = new DeterminizeFsaImpl<A, D>(fst, D(), opts); 5514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 5524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Calls implementation for transducers. 5534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_ = new DeterminizeFstImpl<A, STRING_LEFT_RESTRICT>(fst, opts); 5544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFst(const DeterminizeFst<A> &fst) : Fst<A>(fst), impl_(fst.impl_) { 5584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->IncrRefCount(); 5594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~DeterminizeFst() { if (!impl_->DecrRefCount()) delete impl_; } 5624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Start() const { return impl_->Start(); } 5644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight Final(StateId s) const { return impl_->Final(s); } 5664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); } 5684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumInputEpsilons(StateId s) const { 5704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumInputEpsilons(s); 5714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumOutputEpsilons(StateId s) const { 5744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumOutputEpsilons(s); 5754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 Properties(uint64 mask, bool test) const { 5784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (test) { 5794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 known, test = TestProperties(*this, mask, &known); 5804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->SetProperties(test, known); 5814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return test & mask; 5824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 5834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->Properties(mask); 5844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const string& Type() const { return impl_->Type(); } 5884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual DeterminizeFst<A> *Copy() const { 5904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new DeterminizeFst<A>(*this); 5914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* InputSymbols() const { 5944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->InputSymbols(); 5954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* OutputSymbols() const { 5984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->OutputSymbols(); 5994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual inline void InitStateIterator(StateIteratorData<A> *data) const; 6024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 6044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->InitArcIterator(s, data); 6054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project protected: 6084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFstImplBase<A> *Impl() { return impl_; } 6094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 6114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // This private version is for passing the common divisor to 6124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // FSA determinization. 6134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <class D> 6144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFst(const Fst<A> &fst, const D &common_divisor, 6154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const DeterminizeFstOptions &opts) 6164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new DeterminizeFsaImpl<A, D>(fst, common_divisor, opts)) {} 6174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFstImplBase<A> *impl_; 6194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const DeterminizeFst<A> &fst); // Disallow 6214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 6224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, StringType S> 6254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectDeterminizeFstImpl<A, S>::DeterminizeFstImpl( 6264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> &fst, const DeterminizeFstOptions &opts) 6274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : DeterminizeFstImplBase<A>(fst, opts) { 6284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Mapper to an acceptor. 6304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ToFst to_fst(fst, ToMapper()); 6314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Determinize acceptor. 6334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // This recursive call terminates since it passes the common divisor 6344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // to a private constructor. 6354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFst<ToArc> det_fsa(to_fst, CommonDivisor(), opts); 6364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Mapper back to transducer. 6384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FactorWeightOptions fopts(CacheOptions(true, 0), opts.delta, true); 6394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FactorWeightFst<ToArc, FactorIterator> factored_fst(det_fsa, fopts); 6404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project from_fst_ = new FromFst(factored_fst, FromMapper()); 6414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 6424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for DeterminizeFst. 6454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 6464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< DeterminizeFst<A> > 6474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheStateIterator< DeterminizeFst<A> > { 6484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 6494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const DeterminizeFst<A> &fst) 6504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheStateIterator< DeterminizeFst<A> >(fst) {} 6514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 6524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for DeterminizeFst. 6554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 6564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< DeterminizeFst<A> > 6574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheArcIterator< DeterminizeFst<A> > { 6584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 6594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 6604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const DeterminizeFst<A> &fst, StateId s) 6624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheArcIterator< DeterminizeFst<A> >(fst, s) { 6634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst.impl_->HasArcs(s)) 6644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst.impl_->Expand(s); 6654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 6684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 6694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 6704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> inline 6734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid DeterminizeFst<A>::InitStateIterator(StateIteratorData<A> *data) const 6744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 6754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->base = new StateIterator< DeterminizeFst<A> >(*this); 6764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 6774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful aliases when using StdArc. 6804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef DeterminizeFst<StdArc> StdDeterminizeFst; 6814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct DeterminizeOptions { 6844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta; // Quantization delta for subset weights 6854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit DeterminizeOptions(float d) : delta(d) {} 6874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeOptions() :delta(kDelta) {} 6884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 6894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Determinizes a weighted transducer. This version writes the 6924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// determinized Fst to an output MutableFst. The result will be an 6934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// equivalent FSt that has the property that no state has two 6944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transitions with the same input label. For this algorithm, epsilon 6954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// transitions are treated as regular symbols (cf. RmEpsilon). 6964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 6974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The transducer must be functional. The weights must be (weakly) 6984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// left divisible (valid for TropicalWeight and LogWeight). 6994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 7004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 7014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Determinizable: exponential (polynomial in the size of the output) 7024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Non-determinizable: does not terminate 7034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 7044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The determinizable automata include all unweighted and all acyclic input. 7054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 7064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// References: 7074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Mehryar Mohri, "Finite-State Transducers in Language and Speech 7084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Processing". Computational Linguistics, 23:2, 1997. 7094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 7104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Determinize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, 7114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const DeterminizeOptions &opts = DeterminizeOptions()) { 7124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DeterminizeFstOptions nopts; 7134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nopts.delta = opts.delta; 7144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nopts.gc_limit = 0; // Cache only the last state for fastest copy. 7154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *ofst = DeterminizeFst<Arc>(ifst, nopts); 7164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 7174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 7204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_DETERMINIZE_H__ 722