14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// synchronize.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// Author: allauzen@cs.nyu.edu (Cyril Allauzen) 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Synchronize an FST with bounded delay. 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_SYNCHRONIZE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_SYNCHRONIZE_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <algorithm> 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2573018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers#include <unordered_map> 2673018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers#include <unordered_set> 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/test-properties.h" 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef CacheOptions SynchronizeFstOptions; 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation class for SynchronizeFst 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass SynchronizeFstImpl 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheImpl<A> { 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetType; 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetProperties; 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::Properties; 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetInputSymbols; 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetOutputSymbols; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasStart; 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasFinal; 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasArcs; 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef basic_string<Label> String; 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project struct Element { 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element() {} 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element(StateId s, const String *i, const String *o) 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : state(s), istring(i), ostring(o) {} 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state; // Input state Id 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *istring; // Residual input labels 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *ostring; // Residual output labels 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Residual strings are represented by const pointers to 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // basic_string<Label> and are stored in a hash_set. The pointed 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // memory is owned by the hash_set string_set_. 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SynchronizeFstImpl(const Fst<A> &fst, const SynchronizeFstOptions &opts) 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheImpl<A>(opts), fst_(fst.Copy()) { 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetType("synchronize"); 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst.Properties(kFstProperties, false); 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetProperties(SynchronizeProperties(props), kCopyProperties); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetInputSymbols(fst.InputSymbols()); 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetOutputSymbols(fst.OutputSymbols()); 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~SynchronizeFstImpl() { 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete fst_; 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Extract pointers from the hash set 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<const String*> strings; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename StringSet::iterator it = string_set_.begin(); 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; it != string_set_.end(); ++it) 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project strings.push_back(*it); 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Free the extracted pointers 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; i < strings.size(); ++i) 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete strings[i]; 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Start() { 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasStart()) { 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = fst_->Start(); 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s == kNoStateId) 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return kNoStateId; 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *empty = FindString(new String()); 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start = FindState(Element(fst_->Start(), empty, empty)); 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetStart(start); 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Start(); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight Final(StateId s) { 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasFinal(s)) { 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Element &e = elements_[s]; 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w = e.state == kNoStateId ? Weight::One() : fst_->Final(e.state); 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((w != Weight::Zero()) && (e.istring)->empty() && (e.ostring)->empty()) 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetFinal(s, w); 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetFinal(s, Weight::Zero()); 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Final(s); 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumArcs(StateId s) { 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumArcs(s); 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumInputEpsilons(StateId s) { 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumInputEpsilons(s); 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumOutputEpsilons(StateId s) { 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumOutputEpsilons(s); 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitArcIterator(StateId s, ArcIteratorData<A> *data) { 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::InitArcIterator(s, data); 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Returns the first character of the string obtained by 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // concatenating s and l. 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label Car(const String *s, Label l = 0) const { 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!s->empty()) 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (*s)[0]; 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return l; 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Computes the residual string obtained by removing the first 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // character in the concatenation of s and l. 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *Cdr(const String *s, Label l = 0) { 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project String *r = new String(); 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (int i = 1; i < s->size(); ++i) 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r->push_back((*s)[i]); 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (l && !(s->empty())) r->push_back(l); 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FindString(r); 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Computes the concatenation of s and l. 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *Concat(const String *s, Label l = 0) { 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project String *r = new String(); 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (int i = 0; i < s->size(); ++i) 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r->push_back((*s)[i]); 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (l) r->push_back(l); 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FindString(r); 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Tests if the concatenation of s and l is empty 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty(const String *s, Label l = 0) const { 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s->empty()) 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return l == 0; 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Finds the string pointed by s in the hash set. Transfers the 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // pointer ownership to the hash set. 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *FindString(const String *s) { 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename StringSet::iterator it = string_set_.find(s); 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (it != string_set_.end()) { 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete s; 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (*it); 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project string_set_.insert(s); 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return s; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Finds state corresponding to an element. Creates new state 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // if element not found. 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId FindState(const Element &e) { 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename ElementMap::iterator eit = element_map_.find(e); 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (eit != element_map_.end()) { 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (*eit).second; 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = elements_.size(); 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project elements_.push_back(e); 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project element_map_.insert(pair<const Element, StateId>(e, s)); 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return s; 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Computes the outgoing transitions from a state, creating new destination 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // states as needed. 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Expand(StateId s) { 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element e = elements_[s]; 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (e.state != kNoStateId) 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<A> > ait(*fst_, e.state); 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !ait.Done(); 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ait.Next()) { 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A &arc = ait.Value(); 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!Empty(e.istring, arc.ilabel) && !Empty(e.ostring, arc.olabel)) { 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *istring = Cdr(e.istring, arc.ilabel); 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *ostring = Cdr(e.ostring, arc.olabel); 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId d = FindState(Element(arc.nextstate, istring, ostring)); 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, Arc(Car(e.istring, arc.ilabel), 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Car(e.ostring, arc.olabel), arc.weight, d)); 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *istring = Concat(e.istring, arc.ilabel); 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *ostring = Concat(e.ostring, arc.olabel); 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId d = FindState(Element(arc.nextstate, istring, ostring)); 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, Arc(0 , 0, arc.weight, d)); 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w = e.state == kNoStateId ? Weight::One() : fst_->Final(e.state); 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((w != Weight::Zero()) && 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((e.istring)->size() + (e.ostring)->size() > 0)) { 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *istring = Cdr(e.istring); 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const String *ostring = Cdr(e.ostring); 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId d = FindState(Element(kNoStateId, istring, ostring)); 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, Arc(Car(e.istring), Car(e.ostring), w, d)); 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetArcs(s); 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Equality function for Elements, assume strings have been hashed. 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class ElementEqual { 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const Element &x, const Element &y) const { 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return x.state == y.state && 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.istring == y.istring && 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.ostring == y.ostring; 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Hash function for Elements to Fst states. 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class ElementKey { 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t operator()(const Element &x) const { 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t key = x.state; 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key = (key << 1) ^ (x.istring)->size(); 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; i < (x.istring)->size(); ++i) 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key = (key << 1) ^ (*x.istring)[i]; 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key = (key << 1) ^ (x.ostring)->size(); 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; i < (x.ostring)->size(); ++i) 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key = (key << 1) ^ (*x.ostring)[i]; 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return key; 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Equality function for strings 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class StringEqual { 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const String * const &x, const String * const &y) const { 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (x->size() != y->size()) return false; 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; i < x->size(); ++i) 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*x)[i] != (*y)[i]) return false; 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Hash function for set of strings 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class StringKey{ 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t operator()(const String * const & x) const { 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t key = x->size(); 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; i < x->size(); ++i) 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key = (key << 1) ^ (*x)[i]; 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return key; 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 29073018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers typedef std::unordered_map<Element, StateId, ElementKey, ElementEqual> ElementMap; 29173018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers typedef std::unordered_set<const String*, StringKey, StringEqual> StringSet; 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst_; 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Element> elements_; // mapping Fst state to Elements 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ElementMap element_map_; // mapping Elements to Fst state 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StringSet string_set_; 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(SynchronizeFstImpl); 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Synchronizes a transducer. This version is a delayed Fst. The 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// result will be an equivalent FST that has the property that during 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the traversal of a path, the delay is either zero or strictly 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// increasing, where the delay is the difference between the number of 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// non-epsilon output labels and input labels along the path. 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// For the algorithm to terminate, the input transducer must have 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bounded delay, i.e., the delay of every cycle must be zero. 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - A has bounded delay: exponential 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - A does not have bounded delay: does not terminate 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// References: 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Mehryar Mohri. Edit-Distance of Weighted Automata: General 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Definitions and Algorithms, International Journal of Computer 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Science, 14(6): 957-982 (2003). 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass SynchronizeFst : public Fst<A> { 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class ArcIterator< SynchronizeFst<A> >; 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheStateIterator< SynchronizeFst<A> >; 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheArcIterator< SynchronizeFst<A> >; 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SynchronizeFst(const Fst<A> &fst) 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new SynchronizeFstImpl<A>(fst, SynchronizeFstOptions())) {} 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SynchronizeFst(const Fst<A> &fst, const SynchronizeFstOptions &opts) 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new SynchronizeFstImpl<A>(fst, opts)) {} 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SynchronizeFst(const SynchronizeFst<A> &fst) : impl_(fst.impl_) { 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->IncrRefCount(); 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~SynchronizeFst() { if (!impl_->DecrRefCount()) delete impl_; } 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Start() const { return impl_->Start(); } 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight Final(StateId s) const { return impl_->Final(s); } 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); } 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumInputEpsilons(StateId s) const { 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumInputEpsilons(s); 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumOutputEpsilons(StateId s) const { 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumOutputEpsilons(s); 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 Properties(uint64 mask, bool test) const { 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (test) { 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 known, test = TestProperties(*this, mask, &known); 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->SetProperties(test, known); 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return test & mask; 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->Properties(mask); 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const string& Type() const { return impl_->Type(); } 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual SynchronizeFst<A> *Copy() const { 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new SynchronizeFst<A>(*this); 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* InputSymbols() const { 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->InputSymbols(); 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* OutputSymbols() const { 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->OutputSymbols(); 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual inline void InitStateIterator(StateIteratorData<A> *data) const; 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->InitArcIterator(s, data); 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SynchronizeFstImpl<A> *Impl() { return impl_; } 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SynchronizeFstImpl<A> *impl_; 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const SynchronizeFst<A> &fst); // Disallow 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for SynchronizeFst. 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A> 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< SynchronizeFst<A> > 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheStateIterator< SynchronizeFst<A> > { 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const SynchronizeFst<A> &fst) 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheStateIterator< SynchronizeFst<A> >(fst) {} 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for SynchronizeFst. 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< SynchronizeFst<A> > 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheArcIterator< SynchronizeFst<A> > { 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const SynchronizeFst<A> &fst, StateId s) 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheArcIterator< SynchronizeFst<A> >(fst, s) { 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst.impl_->HasArcs(s)) 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst.impl_->Expand(s); 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> inline 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid SynchronizeFst<A>::InitStateIterator(StateIteratorData<A> *data) const 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->base = new StateIterator< SynchronizeFst<A> >(*this); 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Synchronizes a transducer. This version writes the synchronized 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// result to a MutableFst. The result will be an equivalent FST that 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// has the property that during the traversal of a path, the delay is 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// either zero or strictly increasing, where the delay is the 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// difference between the number of non-epsilon output labels and 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// input labels along the path. 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// For the algorithm to terminate, the input transducer must have 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bounded delay, i.e., the delay of every cycle must be zero. 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - A has bounded delay: exponential 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - A does not have bounded delay: does not terminate 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// References: 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Mehryar Mohri. Edit-Distance of Weighted Automata: General 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Definitions and Algorithms, International Journal of Computer 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Science, 14(6): 957-982 (2003). 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Synchronize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst) { 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SynchronizeFstOptions opts; 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project opts.gc_limit = 0; // Cache only the last state for fastest copy. 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *ofst = SynchronizeFst<Arc>(ifst, opts); 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_SYNCHRONIZE_H__ 460