1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// rmepsilon.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: allauzen@google.com (Cyril Allauzen) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Functions and classes that implemement epsilon-removal. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_RMEPSILON_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_RMEPSILON_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 243da1eb108d36da35333b2d655202791af854996bPrzemyslaw Szczepaniak#include <tr1/unordered_map> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::tr1::unordered_map; 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::tr1::unordered_multimap; 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/slist.h> 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <stack> 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <string> 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <utility> 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::pair; using std::make_pair; 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arcfilter.h> 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/cache.h> 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/connect.h> 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/factor-weight.h> 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/invert.h> 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/prune.h> 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/queue.h> 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/shortest-distance.h> 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/topsort.h> 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue> 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass RmEpsilonOptions 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public ShortestDistanceOptions<Arc, Queue, EpsilonArcFilter<Arc> > { 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool connect; // Connect output 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight weight_threshold; // Pruning weight threshold. 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state_threshold; // Pruning state threshold. 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit RmEpsilonOptions(Queue *q, float d = kDelta, bool c = true, 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight w = Weight::Zero(), 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId n = kNoStateId) 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ShortestDistanceOptions< Arc, Queue, EpsilonArcFilter<Arc> >( 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson q, EpsilonArcFilter<Arc>(), kNoStateId, d), 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson connect(c), weight_threshold(w), state_threshold(n) {} 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonOptions(); // disallow 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Computation state of the epsilon-removal algorithm. 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue> 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass RmEpsilonState { 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Label Label; 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonState(const Fst<Arc> &fst, 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> *distance, 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const RmEpsilonOptions<Arc, Queue> &opts) 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : fst_(fst), distance_(distance), sd_state_(fst_, distance, opts, true), 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson expand_id_(0) {} 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Compute arcs and final weight for state 's' 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Expand(StateId s); 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Returns arcs of expanded state. 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Arc> &Arcs() { return arcs_; } 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Returns final weight of expanded state. 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Weight &Final() const { return final_; } 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Return true if an error has occured. 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return sd_state_.Error(); } 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const size_t kPrime0 = 7853; 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const size_t kPrime1 = 7867; 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson struct Element { 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label ilabel; 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label olabel; 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId nextstate; 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Element() {} 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Element(Label i, Label o, StateId s) 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ilabel(i), olabel(o), nextstate(s) {} 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson class ElementKey { 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t operator()(const Element& e) const { 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return static_cast<size_t>(e.nextstate + 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson e.ilabel * kPrime0 + 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson e.olabel * kPrime1); 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson class ElementEqual { 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool operator()(const Element &e1, const Element &e2) const { 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return (e1.ilabel == e2.ilabel) && (e1.olabel == e2.olabel) 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson && (e1.nextstate == e2.nextstate); 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef unordered_map<Element, pair<StateId, size_t>, 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ElementKey, ElementEqual> ElementMap; 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst_; 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Distance from state being expanded in epsilon-closure. 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> *distance_; 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Shortest distance algorithm computation state. 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceState<Arc, Queue, EpsilonArcFilter<Arc> > sd_state_; 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Maps an element 'e' to a pair 'p' corresponding to a position 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // in the arcs vector of the state being expanded. 'e' corresponds 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // to the position 'p.second' in the 'arcs_' vector if 'p.first' is 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // equal to the state being expanded. 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ElementMap element_map_; 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson EpsilonArcFilter<Arc> eps_filter_; 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson stack<StateId> eps_queue_; // Queue used to visit the epsilon-closure 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<bool> visited_; // '[i] = true' if state 'i' has been visited 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson slist<StateId> visited_states_; // List of visited states 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Arc> arcs_; // Arcs of state being expanded 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight final_; // Final weight of state being expanded 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId expand_id_; // Unique ID for each call to Expand 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(RmEpsilonState); 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue> 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst size_t RmEpsilonState<Arc, Queue>::kPrime0; 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue> 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonconst size_t RmEpsilonState<Arc, Queue>::kPrime1; 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue> 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid RmEpsilonState<Arc,Queue>::Expand(typename Arc::StateId source) { 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson final_ = Weight::Zero(); 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arcs_.clear(); 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sd_state_.ShortestDistance(source); 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (sd_state_.Error()) 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson eps_queue_.push(source); 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (!eps_queue_.empty()) { 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state = eps_queue_.top(); 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson eps_queue_.pop(); 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (visited_.size() <= state) visited_.push_back(false); 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (visited_[state]) continue; 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson visited_[state] = true; 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson visited_states_.push_front(state); 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (ArcIterator< Fst<Arc> > ait(fst_, state); 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !ait.Done(); 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ait.Next()) { 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc arc = ait.Value(); 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arc.weight = Times((*distance_)[state], arc.weight); 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (eps_filter_(arc)) { 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (visited_.size() <= arc.nextstate) 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson visited_.push_back(false); 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!visited_[arc.nextstate]) 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson eps_queue_.push(arc.nextstate); 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Element element(arc.ilabel, arc.olabel, arc.nextstate); 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename ElementMap::iterator it = element_map_.find(element); 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (it == element_map_.end()) { 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson element_map_.insert( 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson pair<Element, pair<StateId, size_t> > 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (element, pair<StateId, size_t>(expand_id_, arcs_.size()))); 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arcs_.push_back(arc); 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (((*it).second).first == expand_id_) { 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight &w = arcs_[((*it).second).second].weight; 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w = Plus(w, arc.weight); 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ((*it).second).first = expand_id_; 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ((*it).second).second = arcs_.size(); 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arcs_.push_back(arc); 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson final_ = Plus(final_, Times((*distance_)[state], fst_.Final(state))); 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (!visited_states_.empty()) { 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson visited_[visited_states_.front()] = false; 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson visited_states_.pop_front(); 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++expand_id_; 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Removes epsilon-transitions (when both the input and output label 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// are an epsilon) from a transducer. The result will be an equivalent 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST that has no such epsilon transitions. This version modifies 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// its input. It allows fine control via the options argument; see 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// below for a simpler interface. 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The vector 'distance' will be used to hold the shortest distances 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// during the epsilon-closure computation. The state queue discipline 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// and convergence delta are taken in the options argument. 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc, class Queue> 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid RmEpsilon(MutableFst<Arc> *fst, 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<typename Arc::Weight> *distance, 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const RmEpsilonOptions<Arc, Queue> &opts) { 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Label Label; 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst->Start() == kNoStateId) { 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // 'noneps_in[s]' will be set to true iff 's' admits a non-epsilon 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // incoming transition or is the start state. 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<bool> noneps_in(fst->NumStates(), false); 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson noneps_in[fst->Start()] = true; 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < fst->NumStates(); ++i) { 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (ArcIterator<Fst<Arc> > aiter(*fst, i); 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !aiter.Done(); 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson aiter.Next()) { 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (aiter.Value().ilabel != 0 || aiter.Value().olabel != 0) 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson noneps_in[aiter.Value().nextstate] = true; 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // States sorted in topological order when (acyclic) or generic 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // topological order (cyclic). 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> states; 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson states.reserve(fst->NumStates()); 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst->Properties(kTopSorted, false) & kTopSorted) { 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < fst->NumStates(); i++) 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson states.push_back(i); 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (fst->Properties(kAcyclic, false) & kAcyclic) { 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> order; 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool acyclic; 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic); 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DfsVisit(*fst, &top_order_visitor, EpsilonArcFilter<Arc>()); 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Sanity check: should be acyclic if property bit is set. 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if(!acyclic) { 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "RmEpsilon: inconsistent acyclic property bit"; 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetProperties(kError, kError); 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson states.resize(order.size()); 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < order.size(); i++) 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson states[order[i]] = i; 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props; 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> scc; 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SccVisitor<Arc> scc_visitor(&scc, 0, 0, &props); 278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DfsVisit(*fst, &scc_visitor, EpsilonArcFilter<Arc>()); 279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> first(scc.size(), kNoStateId); 280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> next(scc.size(), kNoStateId); 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < scc.size(); i++) { 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (first[scc[i]] != kNoStateId) 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson next[i] = first[scc[i]]; 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson first[scc[i]] = i; 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < first.size(); i++) 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId j = first[i]; j != kNoStateId; j = next[j]) 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson states.push_back(j); 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonState<Arc, Queue> 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rmeps_state(*fst, distance, opts); 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (!states.empty()) { 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state = states.back(); 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson states.pop_back(); 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!noneps_in[state]) 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson continue; 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rmeps_state.Expand(state); 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetFinal(state, rmeps_state.Final()); 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->DeleteArcs(state); 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Arc> &arcs = rmeps_state.Arcs(); 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->ReserveArcs(state, arcs.size()); 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (!arcs.empty()) { 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->AddArc(state, arcs.back()); 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arcs.pop_back(); 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId s = 0; s < fst->NumStates(); ++s) { 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!noneps_in[s]) 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->DeleteArcs(s); 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if(rmeps_state.Error()) 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetProperties(kError, kError); 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetProperties( 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonProperties(fst->Properties(kFstProperties, false)), 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kFstProperties); 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (opts.weight_threshold != Weight::Zero() || 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.state_threshold != kNoStateId) 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Prune(fst, opts.weight_threshold, opts.state_threshold); 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (opts.connect && (opts.weight_threshold == Weight::Zero() || 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts.state_threshold != kNoStateId)) 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Connect(fst); 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Removes epsilon-transitions (when both the input and output label 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// are an epsilon) from a transducer. The result will be an equivalent 331f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST that has no such epsilon transitions. This version modifies its 332f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// input. It has a simplified interface; see above for a version that 333f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// allows finer control. 334f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 335f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Complexity: 336f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Time: 337f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Unweighted: O(V2 + V E) 338f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Acyclic: O(V2 + V E) 339f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Tropical semiring: O(V2 log V + V E) 340f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - General: exponential 341f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Space: O(V E) 342f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// where V = # of states visited, E = # of arcs. 343f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 344f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// References: 345f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Mehryar Mohri. Generic Epsilon-Removal and Input 346f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Epsilon-Normalization Algorithms for Weighted Transducers, 347f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// "International Journal of Computer Science", 13(1):129-143 (2002). 348f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class Arc> 349f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid RmEpsilon(MutableFst<Arc> *fst, 350f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool connect = true, 351f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::Weight weight_threshold = Arc::Weight::Zero(), 352f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::StateId state_threshold = kNoStateId, 353f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float delta = kDelta) { 354f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 355f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 356f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Label Label; 357f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 358f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> distance; 359f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AutoQueue<StateId> state_queue(*fst, &distance, EpsilonArcFilter<Arc>()); 360f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonOptions<Arc, AutoQueue<StateId> > 361f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson opts(&state_queue, delta, connect, weight_threshold, state_threshold); 362f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 363f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilon(fst, &distance, opts); 364f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 365f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 366f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 367f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct RmEpsilonFstOptions : CacheOptions { 368f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float delta; 369f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 370f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFstOptions(const CacheOptions &opts, float delta = kDelta) 371f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : CacheOptions(opts), delta(delta) {} 372f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 373f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit RmEpsilonFstOptions(float delta = kDelta) : delta(delta) {} 374f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 375f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 376f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 377f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Implementation of delayed RmEpsilonFst. 378f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 379f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass RmEpsilonFstImpl : public CacheImpl<A> { 380f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 381f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetType; 382f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetProperties; 383f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetInputSymbols; 384f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetOutputSymbols; 385f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 386f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CacheBaseImpl< CacheState<A> >::PushArc; 387f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CacheBaseImpl< CacheState<A> >::HasArcs; 388f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CacheBaseImpl< CacheState<A> >::HasFinal; 389f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CacheBaseImpl< CacheState<A> >::HasStart; 390f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CacheBaseImpl< CacheState<A> >::SetArcs; 391f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CacheBaseImpl< CacheState<A> >::SetFinal; 392f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using CacheBaseImpl< CacheState<A> >::SetStart; 393f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 394f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::Label Label; 395f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::Weight Weight; 396f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 397f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef CacheState<A> State; 398f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 399f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFstImpl(const Fst<A>& fst, const RmEpsilonFstOptions &opts) 400f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : CacheImpl<A>(opts), 401f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_(fst.Copy()), 402f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delta_(opts.delta), 403f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rmeps_state_( 404f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *fst_, 405f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson &distance_, 406f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonOptions<A, FifoQueue<StateId> >(&queue_, delta_, false)) { 407f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetType("rmepsilon"); 408f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props = fst.Properties(kFstProperties, false); 409f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(RmEpsilonProperties(props, true), kCopyProperties); 410f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetInputSymbols(fst.InputSymbols()); 411f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetOutputSymbols(fst.OutputSymbols()); 412f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 413f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 414f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFstImpl(const RmEpsilonFstImpl &impl) 415f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : CacheImpl<A>(impl), 416f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_(impl.fst_->Copy(true)), 417f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delta_(impl.delta_), 418f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rmeps_state_( 419f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *fst_, 420f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson &distance_, 421f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonOptions<A, FifoQueue<StateId> >(&queue_, delta_, false)) { 422f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetType("rmepsilon"); 423f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(impl.Properties(), kCopyProperties); 424f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetInputSymbols(impl.InputSymbols()); 425f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetOutputSymbols(impl.OutputSymbols()); 426f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 427f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 428f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ~RmEpsilonFstImpl() { 429f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete fst_; 430f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 431f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 432f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Start() { 433f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!HasStart()) { 434f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetStart(fst_->Start()); 435f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 436f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return CacheImpl<A>::Start(); 437f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 438f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 439f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight Final(StateId s) { 440f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!HasFinal(s)) { 441f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Expand(s); 442f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 443f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return CacheImpl<A>::Final(s); 444f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 445f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 446f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t NumArcs(StateId s) { 447f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!HasArcs(s)) 448f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Expand(s); 449f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return CacheImpl<A>::NumArcs(s); 450f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 451f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 452f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t NumInputEpsilons(StateId s) { 453f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!HasArcs(s)) 454f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Expand(s); 455f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return CacheImpl<A>::NumInputEpsilons(s); 456f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 457f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 458f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t NumOutputEpsilons(StateId s) { 459f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!HasArcs(s)) 460f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Expand(s); 461f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return CacheImpl<A>::NumOutputEpsilons(s); 462f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 463f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 464f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 Properties() const { return Properties(kFstProperties); } 465f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 466f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Set error if found; return FST impl properties. 467f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 Properties(uint64 mask) const { 468f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((mask & kError) && 469f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (fst_->Properties(kError, false) || rmeps_state_.Error())) 470f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(kError, kError); 471f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return FstImpl<A>::Properties(mask); 472f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 473f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 474f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void InitArcIterator(StateId s, ArcIteratorData<A> *data) { 475f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!HasArcs(s)) 476f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Expand(s); 477f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CacheImpl<A>::InitArcIterator(s, data); 478f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 479f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 480f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Expand(StateId s) { 481f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rmeps_state_.Expand(s); 482f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetFinal(s, rmeps_state_.Final()); 483f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<A> &arcs = rmeps_state_.Arcs(); 484f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (!arcs.empty()) { 485f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PushArc(s, arcs.back()); 486f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson arcs.pop_back(); 487f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 488f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetArcs(s); 489f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 490f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 491f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 492f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<A> *fst_; 493f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float delta_; 494f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> distance_; 495f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FifoQueue<StateId> queue_; 496f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonState<A, FifoQueue<StateId> > rmeps_state_; 497f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 498f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const RmEpsilonFstImpl<A> &); // disallow 499f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 500f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 501f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 502f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Removes epsilon-transitions (when both the input and output label 503f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// are an epsilon) from a transducer. The result will be an equivalent 504f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST that has no such epsilon transitions. This version is a 505f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// delayed Fst. 506f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 507f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Complexity: 508f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Time: 509f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Unweighted: O(v^2 + v e) 510f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - General: exponential 511f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Space: O(v e) 512f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// where v = # of states visited, e = # of arcs visited. Constant time 513f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// to visit an input state or arc is assumed and exclusive of caching. 514f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 515f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// References: 516f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Mehryar Mohri. Generic Epsilon-Removal and Input 517f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Epsilon-Normalization Algorithms for Weighted Transducers, 518f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// "International Journal of Computer Science", 13(1):129-143 (2002). 519f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 520f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This class attaches interface to implementation and handles 521f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// reference counting, delegating most methods to ImplToFst. 522f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 523f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass RmEpsilonFst : public ImplToFst< RmEpsilonFstImpl<A> > { 524f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 525f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend class ArcIterator< RmEpsilonFst<A> >; 526f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend class StateIterator< RmEpsilonFst<A> >; 527f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 528f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 529f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 530f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef CacheState<A> State; 531f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef RmEpsilonFstImpl<A> Impl; 532f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 533f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFst(const Fst<A> &fst) 534f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ImplToFst<Impl>(new Impl(fst, RmEpsilonFstOptions())) {} 535f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 536f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFst(const Fst<A> &fst, const RmEpsilonFstOptions &opts) 537f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ImplToFst<Impl>(new Impl(fst, opts)) {} 538f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 539f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // See Fst<>::Copy() for doc. 540f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RmEpsilonFst(const RmEpsilonFst<A> &fst, bool safe = false) 541f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ImplToFst<Impl>(fst, safe) {} 542f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 543f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Get a copy of this RmEpsilonFst. See Fst<>::Copy() for further doc. 544f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual RmEpsilonFst<A> *Copy(bool safe = false) const { 545f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return new RmEpsilonFst<A>(*this, safe); 546f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 547f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 548f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual inline void InitStateIterator(StateIteratorData<A> *data) const; 549f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 550f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const { 551f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetImpl()->InitArcIterator(s, data); 552f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 553f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 554f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 555f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Makes visible to friends. 556f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); } 557f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 558f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const RmEpsilonFst<A> &fst); // disallow 559f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 560f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 561f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specialization for RmEpsilonFst. 562f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class A> 563f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StateIterator< RmEpsilonFst<A> > 564f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public CacheStateIterator< RmEpsilonFst<A> > { 565f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 566f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit StateIterator(const RmEpsilonFst<A> &fst) 567f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : CacheStateIterator< RmEpsilonFst<A> >(fst, fst.GetImpl()) {} 568f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 569f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 570f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 571f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specialization for RmEpsilonFst. 572f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 573f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ArcIterator< RmEpsilonFst<A> > 574f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public CacheArcIterator< RmEpsilonFst<A> > { 575f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 576f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 577f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 578f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcIterator(const RmEpsilonFst<A> &fst, StateId s) 579f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : CacheArcIterator< RmEpsilonFst<A> >(fst.GetImpl(), s) { 580f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!fst.GetImpl()->HasArcs(s)) 581f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst.GetImpl()->Expand(s); 582f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 583f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 584f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 585f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(ArcIterator); 586f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 587f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 588f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 589f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> inline 590f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid RmEpsilonFst<A>::InitStateIterator(StateIteratorData<A> *data) const { 591f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson data->base = new StateIterator< RmEpsilonFst<A> >(*this); 592f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 593f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 594f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 595f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Useful alias when using StdArc. 596f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef RmEpsilonFst<StdArc> StdRmEpsilonFst; 597f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 598f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 599f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 600f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_RMEPSILON_H__ 601