Home | History | Annotate | Download | only in lib 
      1 // arcsum.h
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 //
     15 //
     16 // \file
     17 // Functions to sum arcs (sum weights) in an fst.
     18 
     19 #ifndef FST_LIB_ARCSUM_H__
     20 #define FST_LIB_ARCSUM_H__
     21 
     22 #include "fst/lib/mutable-fst.h"
     23 #include "fst/lib/weight.h"
     24 
     25 namespace fst {
     26 
     27 template <class A>
     28 class ArcSumCompare {
     29  public:
     30   bool operator()(const A& x, const A& y) {
     31     if (x.ilabel < y.ilabel) return true;
     32     if (x.ilabel > y.ilabel) return false;
     33     if (x.olabel < y.olabel) return true;
     34     if (x.olabel < y.olabel) return false;
     35     if (x.nextstate < y.nextstate) return true;
     36     if (x.nextstate > y.nextstate) return false;
     37     return false;
     38   }
     39 };
     40 
     41 
     42 template <class A>
     43 class ArcSumEqual {
     44  public:
     45   bool operator()(const A& x, const A& y) {
     46     return (x.ilabel == y.ilabel &&
     47             x.olabel == y.olabel &&
     48             x.nextstate == y.nextstate);
     49   }
     50 };
     51 
     52 
     53 // Combines identically labeled arcs, summing weights. For each state
     54 // we combine arcs with the same input and output label, summing their
     55 // weights using Weight:::Plus().
     56 template <class A>
     57 void ArcSum(MutableFst<A>* fst) {
     58   typedef typename A::StateId StateId;
     59 
     60   vector<A> arcs;
     61   for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) {
     62     StateId s = siter.Value();
     63     if (fst->NumArcs(s) == 0) continue;
     64 
     65     // Sums arcs into arcs array.
     66     arcs.clear();
     67     arcs.reserve(fst->NumArcs(s));
     68     for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done();
     69          aiter.Next())
     70       arcs.push_back(aiter.Value());
     71 
     72     // At each state, first sorts the exiting arcs by input label, output label
     73     // and destination state and then combines arcs identical in these
     74     // attributes.
     75     ArcSumCompare<A> comp;
     76     sort(arcs.begin(), arcs.end(), comp);
     77 
     78     // Deletes current arcs and copy in sumed arcs.
     79     fst->DeleteArcs(s);
     80     A current_arc = arcs[0];
     81     ArcSumEqual<A> equal;
     82     for (size_t i = 1; i < arcs.size(); ++i) {
     83       if (equal(current_arc, arcs[i])) {
     84         current_arc.weight = Plus(current_arc.weight, arcs[i].weight);
     85       } else {
     86         fst->AddArc(s, current_arc);
     87         current_arc = arcs[i];
     88       }
     89     }
     90     fst->AddArc(s, current_arc);
     91   }
     92 }
     93 
     94 }
     95 
     96 #endif  // FST_LIB_ARCSUM_H__
     97