OpenFST源码解析一：权重前移或后移操作

秒速五厘米 2023-05-31 07:59 2阅读 0赞

**openfst中reweight部分的源码解析（在注释部分）**

对边上的权重进行重新分配：

公式为：arc.weight = arc.weight + P(arc.nextstate) - P(state)

// reweight.h
    //
    // Licensed under the Apache License, Version 2.0 (the "License");
    // you may not use this file except in compliance with the License.
    // You may obtain a copy of the License at
    //
    //      http://www.apache.org/licenses/LICENSE-2.0
    //
    // Unless required by applicable law or agreed to in writing, software
    // distributed under the License is distributed on an "AS IS" BASIS,
    // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    // See the License for the specific language governing permissions and
    // limitations under the License.
    //
    // Author: allauzen@cs.nyu.edu (Cyril Allauzen)
    //
    // \file
    // Function to reweight an FST.
    
    #ifndef FST_LIB_REWEIGHT_H__
    #define FST_LIB_REWEIGHT_H__
    
    #include "fst/lib/mutable-fst.h"
    
    namespace fst {
    //操作类型：
    //  指示权重后移还是前移？
    enum ReweightType { REWEIGHT_TO_INITIAL, REWEIGHT_TO_FINAL };
    
    // Reweight FST according to the potentials defined by the POTENTIAL
    // vector in the direction defined by TYPE. Weight needs to be left
    // distributive when reweighting towards the initial state and right
    // distributive when reweighting towards the final states.
    //
    // An arc of weight w, with an origin state of potential p and
    // destination state of potential q, is reweighted by p\wq when
    // reweighting towards the initial state and by pw/q when reweighting
    // towards the final states.
    /*
    参数为：可改变的FST(对原FST做修改)，
            FST上结点上的势(最短路径算法可求出，表示每一结点到终止状态（或开始状态）的最短距离), 
            操作类型
    */
    template <class Arc>
    void Reweight(MutableFst<Arc> *fst, vector<typename Arc::Weight> potential,
                  ReweightType type) {
      typedef typename Arc::Weight Weight;
    
      if (!fst->NumStates())
        return;
      while (potential.size() < fst->NumStates())
        potential.push_back(Weight::Zero());
    
      if (type == REWEIGHT_TO_FINAL && !(Weight::Properties() & kRightSemiring))
        LOG(FATAL) << "Reweight: Reweighting to the final states requires "
                   << "Weight to be right distributive: "
                   << Weight::Type();
    
      if (type == REWEIGHT_TO_INITIAL && !(Weight::Properties() & kLeftSemiring))
        LOG(FATAL) << "Reweight: Reweighting to the initial state requires "
                   << "Weight to be left distributive: "
                   << Weight::Type();
      //遍历每个状态
      for (StateIterator< MutableFst<Arc> > sit(*fst);
           !sit.Done();
           sit.Next()) {
        typename Arc::StateId state = sit.Value();
        //遍历每一条边
        for (MutableArcIterator< MutableFst<Arc> > ait(fst, state);
             !ait.Done();
             ait.Next()) {
          Arc arc = ait.Value();
          //如果结点上的势为0，则不操作（对前移操作来说，终止状态上可能会出现）
          if ((potential[state] == Weight::Zero()) || (potential[arc.nextstate] == Weight::Zero()))
    	      continue; //temp fix: needs to find best solution for zeros
          //若是前移操作，边上的权重按照P(q) + weight - P(p) 计算，反之亦然
          if ((type == REWEIGHT_TO_INITIAL) && (potential[state] != Weight::Zero()))
            arc.weight = Divide(Times(arc.weight, potential[arc.nextstate]), potential[state], DIVIDE_LEFT);
          else if ((type == REWEIGHT_TO_FINAL) && (potential[arc.nextstate] != Weight::Zero()))
            arc.weight = Divide(Times(potential[state], arc.weight), potential[arc.nextstate], DIVIDE_RIGHT);
          ait.SetValue(arc);
        }
        //处理终止结点上的权重
        if ((type == REWEIGHT_TO_INITIAL) && (potential[state] != Weight::Zero()))
          fst->SetFinal(state, Divide(fst->Final(state), potential[state], DIVIDE_LEFT));
        else if (type == REWEIGHT_TO_FINAL)
          fst->SetFinal(state, Times(potential[state], fst->Final(state)));
      }
    
      //处理开始结点上的权重
      if ((potential[fst->Start()] != Weight::One()) && (potential[fst->Start()] != Weight::Zero())) {
        //若开始结点无环路，则做如下处理：
        if (fst->Properties(kInitialAcyclic, true) & kInitialAcyclic) {
          typename Arc::StateId state = fst->Start();
          for (MutableArcIterator< MutableFst<Arc> > ait(fst, state);
               !ait.Done();
               ait.Next()) {
            Arc arc = ait.Value();
            if (type == REWEIGHT_TO_INITIAL)
              arc.weight = Times(potential[state], arc.weight);
            else
              arc.weight = Times(
                  Divide(Weight::One(), potential[state], DIVIDE_RIGHT),
                  arc.weight);
            ait.SetValue(arc);
          }
          if (type == REWEIGHT_TO_INITIAL)
            fst->SetFinal(state, Times(potential[state], fst->Final(state)));
          else
            fst->SetFinal(state, Times(Divide(Weight::One(), potential[state],
                                              DIVIDE_RIGHT),
                                       fst->Final(state)));
        }
        //若开始结点有环路，则做如下处理：
        else {
          typename Arc::StateId state = fst->AddState();
          Weight w = type == REWEIGHT_TO_INITIAL ?
                     potential[fst->Start()] :
                     Divide(Weight::One(), potential[fst->Start()], DIVIDE_RIGHT);
          Arc arc (0, 0, w, fst->Start());
          fst->AddArc(state, arc);
          fst->SetStart(state);
        }
      }
    
      fst->SetProperties(ReweightProperties(
                             fst->Properties(kFstProperties, false)),
                         kFstProperties);
    }
    
    }  // namespace fst
    
    #endif /* FST_LIB_REWEIGHT_H_ */