14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// rmepsilon.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// Functions and classes that implemement epsilon-removal. 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_RMEPSILON_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_RMEPSILON_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2373018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers#include <unordered_map> 2473018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers#include <forward_list> 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/arcfilter.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/connect.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/factor-weight.h" 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/invert.h" 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/map.h" 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/queue.h" 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/shortest-distance.h" 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/topsort.h" 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class Queue> 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct RmEpsilonOptions 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public ShortestDistanceOptions<Arc, Queue, EpsilonArcFilter<Arc> > { 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool connect; // Connect output 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonOptions(Queue *q, float d = kDelta, bool c = true) 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ShortestDistanceOptions<Arc, Queue, EpsilonArcFilter<Arc> >( 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project q, EpsilonArcFilter<Arc>(), kNoStateId, d), connect(c) {} 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Computation state of the epsilon-removal algorithm. 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class Queue> 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass RmEpsilonState { 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Label Label; 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonState(const Fst<Arc> &fst, 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *distance, 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const RmEpsilonOptions<Arc, Queue> &opts) 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : fst_(fst), distance_(distance), sd_state_(fst_, distance, opts, true) { 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Compute arcs and final weight for state 's' 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Expand(StateId s); 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Returns arcs of expanded state. 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Arc> &Arcs() { return arcs_; } 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Returns final weight of expanded state. 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Weight &Final() const { return final_; } 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project struct Element { 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label ilabel; 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Label olabel; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nextstate; 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element() {} 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element(Label i, Label o, StateId s) 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ilabel(i), olabel(o), nextstate(s) {} 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class ElementKey { 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t operator()(const Element& e) const { 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return static_cast<size_t>(e.nextstate); 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return static_cast<size_t>(e.nextstate + 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project e.ilabel * kPrime0 + 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project e.olabel * kPrime1); 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int kPrime0 = 7853; 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static const int kPrime1 = 7867; 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project class ElementEqual { 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const Element &e1, const Element &e2) const { 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (e1.ilabel == e2.ilabel) && (e1.olabel == e2.olabel) 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project && (e1.nextstate == e2.nextstate); 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 11073018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers typedef std::unordered_map<Element, pair<StateId, ssize_t>, 11173018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers ElementKey, ElementEqual> ElementMap; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<Arc> &fst_; 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Distance from state being expanded in epsilon-closure. 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *distance_; 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Shortest distance algorithm computation state. 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistanceState<Arc, Queue, EpsilonArcFilter<Arc> > sd_state_; 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Maps an element 'e' to a pair 'p' corresponding to a position 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // in the arcs vector of the state being expanded. 'e' corresponds 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // to the position 'p.second' in the 'arcs_' vector if 'p.first' is 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // equal to the state being expanded. 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ElementMap element_map_; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project EpsilonArcFilter<Arc> eps_filter_; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project stack<StateId> eps_queue_; // Queue used to visit the epsilon-closure 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> visited_; // '[i] = true' if state 'i' has been visited 12673018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers std::forward_list<StateId> visited_states_; // List of visited states 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Arc> arcs_; // Arcs of state being expanded 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final_; // Final weight of state being expanded 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const RmEpsilonState); // Disallow 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class Queue> 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid RmEpsilonState<Arc,Queue>::Expand(typename Arc::StateId source) { 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sd_state_.ShortestDistance(source); 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project eps_queue_.push(source); 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project final_ = Weight::Zero(); 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs_.clear(); 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!eps_queue_.empty()) { 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state = eps_queue_.top(); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project eps_queue_.pop(); 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)visited_.size() <= state) visited_.push_back(false); 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visited_[state] = true; 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visited_states_.push_front(state); 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<Arc> > ait(fst_, state); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !ait.Done(); 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ait.Next()) { 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Arc arc = ait.Value(); 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.weight = Times((*distance_)[state], arc.weight); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (eps_filter_(arc)) { 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)visited_.size() <= arc.nextstate) 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visited_.push_back(false); 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!visited_[arc.nextstate]) 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project eps_queue_.push(arc.nextstate); 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Element element(arc.ilabel, arc.olabel, arc.nextstate); 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename ElementMap::iterator it = element_map_.find(element); 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (it == element_map_.end()) { 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project element_map_.insert( 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pair<Element, pair<StateId, ssize_t> > 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (element, pair<StateId, ssize_t>(source, arcs_.size()))); 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs_.push_back(arc); 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (((*it).second).first == source) { 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight &w = arcs_[((*it).second).second].weight; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project w = Plus(w, arc.weight); 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((*it).second).first = source; 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((*it).second).second = arcs_.size(); 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs_.push_back(arc); 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project final_ = Plus(final_, Times((*distance_)[state], fst_.Final(state))); 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!visited_states_.empty()) { 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visited_[visited_states_.front()] = false; 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visited_states_.pop_front(); 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Removes epsilon-transitions (when both the input and output label 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// are an epsilon) from a transducer. The result will be an equivalent 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST that has no such epsilon transitions. This version modifies 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// its input. It allows fine control via the options argument; see 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// below for a simpler interface. 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The vector 'distance' will be used to hold the shortest distances 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// during the epsilon-closure computation. The state queue discipline 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// and convergence delta are taken in the options argument. 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class Queue> 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid RmEpsilon(MutableFst<Arc> *fst, 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<typename Arc::Weight> *distance, 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const RmEpsilonOptions<Arc, Queue> &opts) { 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Label Label; 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // States sorted in topological order when (acyclic) or generic 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // topological order (cyclic). 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> states; 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst->Properties(kTopSorted, false) & kTopSorted) { 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < (StateId)fst->NumStates(); i++) 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project states.push_back(i); 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (fst->Properties(kAcyclic, false) & kAcyclic) { 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> order; 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool acyclic; 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic); 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(*fst, &top_order_visitor, EpsilonArcFilter<Arc>()); 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!acyclic) 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "RmEpsilon: not acyclic though property bit is set"; 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project states.resize(order.size()); 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < (StateId)order.size(); i++) 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project states[order[i]] = i; 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props; 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> scc; 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccVisitor<Arc> scc_visitor(&scc, 0, 0, &props); 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(*fst, &scc_visitor, EpsilonArcFilter<Arc>()); 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> first(scc.size(), kNoStateId); 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> next(scc.size(), kNoStateId); 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < (StateId)scc.size(); i++) { 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (first[scc[i]] != kNoStateId) 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project next[i] = first[scc[i]]; 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project first[scc[i]] = i; 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < (StateId)first.size(); i++) 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId j = first[i]; j != kNoStateId; j = next[j]) 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project states.push_back(j); 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonState<Arc, Queue> 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rmeps_state(*fst, distance, opts); 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!states.empty()) { 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state = states.back(); 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project states.pop_back(); 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rmeps_state.Expand(state); 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetFinal(state, rmeps_state.Final()); 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->DeleteArcs(state); 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Arc> &arcs = rmeps_state.Arcs(); 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!arcs.empty()) { 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(state, arcs.back()); 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.pop_back(); 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetProperties(RmEpsilonProperties( 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->Properties(kFstProperties, false)), 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kFstProperties); 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (opts.connect) 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(fst); 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Removes epsilon-transitions (when both the input and output label 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// are an epsilon) from a transducer. The result will be an equivalent 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST that has no such epsilon transitions. This version modifies its 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// input. It has a simplified interface; see above for a version that 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// allows finer control. 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Unweighted: O(V2 + V E) 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Acyclic: O(V2 + V E) 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Tropical semiring: O(V2 log V + V E) 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - General: exponential 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(V E) 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where V = # of states visited, E = # of arcs. 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// References: 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Mehryar Mohri. Generic Epsilon-Removal and Input 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Epsilon-Normalization Algorithms for Weighted Transducers, 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// "International Journal of Computer Science", 13(1):129-143 (2002). 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid RmEpsilon(MutableFst<Arc> *fst, bool connect = true) { 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Label Label; 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> distance; 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AutoQueue<StateId> state_queue(*fst, &distance, EpsilonArcFilter<Arc>()); 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonOptions<Arc, AutoQueue<StateId> > 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project opts(&state_queue, kDelta, connect); 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilon(fst, &distance, opts); 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct RmEpsilonFstOptions : CacheOptions { 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float delta; 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonFstOptions(const CacheOptions &opts, float delta = kDelta) 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheOptions(opts), delta(delta) {} 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit RmEpsilonFstOptions(float delta = kDelta) : delta(delta) {} 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation of delayed RmEpsilonFst. 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass RmEpsilonFstImpl : public CacheImpl<A> { 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetType; 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetProperties; 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::Properties; 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetInputSymbols; 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using FstImpl<A>::SetOutputSymbols; 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasStart; 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasFinal; 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using CacheBaseImpl< CacheState<A> >::HasArcs; 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Label Label; 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonFstImpl(const Fst<A>& fst, const RmEpsilonFstOptions &opts) 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheImpl<A>(opts), 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst_(fst.Copy()), 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rmeps_state_( 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *fst_, 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project &distance_, 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonOptions<A, FifoQueue<StateId> >(&queue_, opts.delta, 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project false) 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ) { 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetType("rmepsilon"); 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst.Properties(kFstProperties, false); 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetProperties(RmEpsilonProperties(props, true), kCopyProperties); 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~RmEpsilonFstImpl() { 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete fst_; 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Start() { 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasStart()) { 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetStart(fst_->Start()); 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Start(); 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight Final(StateId s) { 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasFinal(s)) { 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::Final(s); 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumArcs(StateId s) { 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumArcs(s); 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumInputEpsilons(StateId s) { 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumInputEpsilons(s); 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t NumOutputEpsilons(StateId s) { 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return CacheImpl<A>::NumOutputEpsilons(s); 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitArcIterator(StateId s, ArcIteratorData<A> *data) { 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!HasArcs(s)) 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Expand(s); 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CacheImpl<A>::InitArcIterator(s, data); 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Expand(StateId s) { 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rmeps_state_.Expand(s); 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetFinal(s, rmeps_state_.Final()); 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<A> &arcs = rmeps_state_.Arcs(); 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!arcs.empty()) { 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AddArc(s, arcs.back()); 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.pop_back(); 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SetArcs(s); 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Fst<A> *fst_; 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> distance_; 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FifoQueue<StateId> queue_; 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonState<A, FifoQueue<StateId> > rmeps_state_; 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(RmEpsilonFstImpl); 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Removes epsilon-transitions (when both the input and output label 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// are an epsilon) from a transducer. The result will be an equivalent 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST that has no such epsilon transitions. This version is a 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// delayed Fst. 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Unweighted: O(v^2 + v e) 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - General: exponential 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(v e) 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where v = # of states visited, e = # of arcs visited. Constant time 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to visit an input state or arc is assumed and exclusive of caching. 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// References: 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Mehryar Mohri. Generic Epsilon-Removal and Input 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Epsilon-Normalization Algorithms for Weighted Transducers, 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// "International Journal of Computer Science", 13(1):129-143 (2002). 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass RmEpsilonFst : public Fst<A> { 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class ArcIterator< RmEpsilonFst<A> >; 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheStateIterator< RmEpsilonFst<A> >; 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project friend class CacheArcIterator< RmEpsilonFst<A> >; 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef CacheState<A> State; 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonFst(const Fst<A> &fst) 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new RmEpsilonFstImpl<A>(fst, RmEpsilonFstOptions())) {} 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonFst(const Fst<A> &fst, const RmEpsilonFstOptions &opts) 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : impl_(new RmEpsilonFstImpl<A>(fst, opts)) {} 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit RmEpsilonFst(const RmEpsilonFst<A> &fst) : impl_(fst.impl_) { 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->IncrRefCount(); 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~RmEpsilonFst() { if (!impl_->DecrRefCount()) delete impl_; } 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Start() const { return impl_->Start(); } 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual Weight Final(StateId s) const { return impl_->Final(s); } 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); } 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumInputEpsilons(StateId s) const { 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumInputEpsilons(s); 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual size_t NumOutputEpsilons(StateId s) const { 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->NumOutputEpsilons(s); 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual uint64 Properties(uint64 mask, bool test) const { 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (test) { 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 known, test = TestProperties(*this, mask, &known); 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->SetProperties(test, known); 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return test & mask; 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->Properties(mask); 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const string& Type() const { return impl_->Type(); } 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual RmEpsilonFst<A> *Copy() const { 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return new RmEpsilonFst<A>(*this); 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* InputSymbols() const { 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->InputSymbols(); 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual const SymbolTable* OutputSymbols() const { 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return impl_->OutputSymbols(); 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual inline void InitStateIterator(StateIteratorData<A> *data) const; 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project impl_->InitArcIterator(s, data); 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project protected: 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonFstImpl<A> *Impl() { return impl_; } 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RmEpsilonFstImpl<A> *impl_; 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void operator=(const RmEpsilonFst<A> &fst); // disallow 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for RmEpsilonFst. 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A> 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< RmEpsilonFst<A> > 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheStateIterator< RmEpsilonFst<A> > { 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const RmEpsilonFst<A> &fst) 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheStateIterator< RmEpsilonFst<A> >(fst) {} 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for RmEpsilonFst. 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< RmEpsilonFst<A> > 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public CacheArcIterator< RmEpsilonFst<A> > { 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const RmEpsilonFst<A> &fst, StateId s) 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : CacheArcIterator< RmEpsilonFst<A> >(fst, s) { 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fst.impl_->HasArcs(s)) 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst.impl_->Expand(s); 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> inline 5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid RmEpsilonFst<A>::InitStateIterator(StateIteratorData<A> *data) const { 5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data->base = new StateIterator< RmEpsilonFst<A> >(*this); 5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef RmEpsilonFst<StdArc> StdRmEpsilonFst; 5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_RMEPSILON_H__ 541