14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// arcsum.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// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Functions to sum arcs (sum weights) in an fst. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_ARCSUM_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_ARCSUM_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/mutable-fst.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/weight.h" 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcSumCompare { 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const A& x, const A& y) { 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (x.ilabel < y.ilabel) return true; 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (x.ilabel > y.ilabel) return false; 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (x.olabel < y.olabel) return true; 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (x.olabel < y.olabel) return false; 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (x.nextstate < y.nextstate) return true; 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (x.nextstate > y.nextstate) return false; 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcSumEqual { 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const A& x, const A& y) { 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (x.ilabel == y.ilabel && 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.olabel == y.olabel && 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project x.nextstate == y.nextstate); 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Combines identically labeled arcs, summing weights. For each state 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// we combine arcs with the same input and output label, summing their 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// weights using Weight:::Plus(). 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid ArcSum(MutableFst<A>* fst) { 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<A> arcs; 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) { 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst->NumArcs(s) == 0) continue; 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Sums arcs into arcs array. 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.clear(); 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.reserve(fst->NumArcs(s)); 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.push_back(aiter.Value()); 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // At each state, first sorts the exiting arcs by input label, output label 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // and destination state and then combines arcs identical in these 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // attributes. 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSumCompare<A> comp; 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sort(arcs.begin(), arcs.end(), comp); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Deletes current arcs and copy in sumed arcs. 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->DeleteArcs(s); 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A current_arc = arcs[0]; 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcSumEqual<A> equal; 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 1; i < arcs.size(); ++i) { 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (equal(current_arc, arcs[i])) { 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project current_arc.weight = Plus(current_arc.weight, arcs[i].weight); 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(s, current_arc); 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project current_arc = arcs[i]; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(s, current_arc); 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_ARCSUM_H__ 97