14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// prune.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 implementing pruning. 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_PRUNE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_PRUNE_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/arcfilter.h" 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/shortest-distance.h" 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, class ArcFilter> 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass PruneOptions { 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Pruning threshold. 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight threshold; 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Arc filter. 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcFilter filter; 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // If non-zero, passes in pre-computed shortest distance from initial state 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // (possibly resized). 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *idistance; 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // If non-zero, passes in pre-computed shortest distance to final states 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // (possibly resized). 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *fdistance; 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PruneOptions(const Weight& t, ArcFilter f, vector<Weight> *id = 0, 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *fd = 0) 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : threshold(t), filter(f), idistance(id), fdistance(fd) {} 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Pruning algorithm: this version modifies its input and it takes an 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// options class as an argment. Delete states and arcs in 'fst' that 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// do not belong to a successful path whose weight is no more than 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'opts.threshold' Times() the weight of the shortest path. Weights 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// need to be commutative and have the path property. 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class ArcFilter> 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Prune(MutableFst<Arc> *fst, 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const PruneOptions<Arc, ArcFilter> &opts) { 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((Weight::Properties() & (kPath | kCommutative)) 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project != (kPath | kCommutative)) 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "Prune: Weight needs to have the path property and" 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << " be commutative: " 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << Weight::Type(); 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId ns = fst->NumStates(); 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (ns == 0) return; 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *idistance = opts.idistance; 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *fdistance = opts.fdistance; 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!idistance) { 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idistance = new vector<Weight>(ns, Weight::Zero()); 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistance(*fst, idistance, false); 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idistance->resize(ns, Weight::Zero()); 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fdistance) { 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fdistance = new vector<Weight>(ns, Weight::Zero()); 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistance(*fst, fdistance, true); 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fdistance->resize(ns, Weight::Zero()); 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> dead; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dead.push_back(fst->AddState()); 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project NaturalLess<Weight> less; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight ceiling = Times((*fdistance)[fst->Start()], opts.threshold); 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId state = 0; state < ns; ++state) { 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (less(ceiling, Times((*idistance)[state], (*fdistance)[state]))) { 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dead.push_back(state); 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project continue; 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (MutableArcIterator< MutableFst<Arc> > it(fst, state); 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !it.Done(); 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project it.Next()) { 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Arc arc = it.Value(); 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!opts.filter(arc)) continue; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight weight = Times(Times((*idistance)[state], arc.weight), 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*fdistance)[arc.nextstate]); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if(less(ceiling, weight)) { 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate = dead[0]; 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project it.SetValue(arc); 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (less(ceiling, Times((*idistance)[state], fst->Final(state)))) 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetFinal(state, Weight::Zero()); 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->DeleteStates(dead); 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!opts.idistance) 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete idistance; 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!opts.fdistance) 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete fdistance; 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Pruning algorithm: this version modifies its input and simply takes 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the pruning threshold as an argument. Delete states and arcs in 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'fst' that do not belong to a successful path whose weight is no 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// more than 'opts.threshold' Times() the weight of the shortest 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// path. Weights need to be commutative and have the path property. 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Prune(MutableFst<Arc> *fst, typename Arc::Weight threshold) { 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PruneOptions<Arc, AnyArcFilter<Arc> > opts(threshold, AnyArcFilter<Arc>()); 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Prune(fst, opts); 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Pruning algorithm: this version writes the pruned input Fst to an 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// output MutableFst and it takes an options class as an argument. 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'ofst' contains states and arcs that belong to a successful path in 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'ifst' whose weight is no more than 'opts.threshold' Times() the 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// weight of the shortest path. Weights need to be commutative and 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// have the path property. 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class ArcFilter> 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Prune(const Fst<Arc> &ifst, 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MutableFst<Arc> *ofst, 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const PruneOptions<Arc, ArcFilter> &opts) { 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((Weight::Properties() & (kPath | kCommutative)) 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project != (kPath | kCommutative)) 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "Prune: Weight needs to have the path property and" 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << " be commutative: " 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << Weight::Type(); 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->DeleteStates(); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (ifst.Start() == kNoStateId) 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *idistance = opts.idistance; 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Weight> *fdistance = opts.fdistance; 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!idistance) { 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idistance = new vector<Weight>; 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistance(ifst, idistance, false); 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!fdistance) { 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fdistance = new vector<Weight>; 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestDistance(ifst, fdistance, true); 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> copy; 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project NaturalLess<Weight> less; 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (fdistance->size() <= ifst.Start()) 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fdistance->push_back(Weight::Zero()); 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight ceiling = Times((*fdistance)[ifst.Start()], opts.threshold); 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator< Fst<Arc> > sit(ifst); 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !sit.Done(); 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sit.Next()) { 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state = sit.Value(); 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (idistance->size() <= state) 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idistance->push_back(Weight::Zero()); 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (fdistance->size() <= state) 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fdistance->push_back(Weight::Zero()); 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (copy.size() <= state) 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project copy.push_back(kNoStateId); 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (less(ceiling, Times((*idistance)[state], (*fdistance)[state]))) 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project continue; 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (copy[state] == kNoStateId) 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project copy[state] = ofst->AddState(); 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!less(ceiling, Times((*idistance)[state], ifst.Final(state)))) 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetFinal(copy[state], ifst.Final(state)); 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<Arc> > ait(ifst, state); 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !ait.Done(); 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ait.Next()) { 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Arc arc = ait.Value(); 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!opts.filter(arc)) continue; 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (idistance->size() <= arc.nextstate) 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idistance->push_back(Weight::Zero()); 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (fdistance->size() <= arc.nextstate) 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fdistance->push_back(Weight::Zero()); 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (copy.size() <= arc.nextstate) 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project copy.push_back(kNoStateId); 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight weight = Times(Times((*idistance)[state], arc.weight), 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*fdistance)[arc.nextstate]); 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!less(ceiling, weight)) { 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (copy[arc.nextstate] == kNoStateId) 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project copy[arc.nextstate] = ofst->AddState(); 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arc.nextstate = copy[arc.nextstate]; 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddArc(copy[state], arc); 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetStart(copy[ifst.Start()]); 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!opts.idistance) 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete idistance; 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!opts.fdistance) 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete fdistance; 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Pruning algorithm: this version writes the pruned input Fst to an 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// output MutableFst and simply takes the pruning threshold as an 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// argument. 'ofst' contains states and arcs that belong to a 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// successful path in 'ifst' whose weight is no more than 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 'opts.threshold' Times() the weight of the shortest path. Weights 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// need to be commutative and have the path property. 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Prune(const Fst<Arc> &ifst, 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MutableFst<Arc> *ofst, 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typename Arc::Weight threshold) { 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PruneOptions<Arc, AnyArcFilter<Arc> > opts(threshold, AnyArcFilter<Arc>()); 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Prune(ifst, ofst, opts); 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_PRUNE_H_ 248