fast-shortest-distance.h

Go to the documentation of this file.

// shortest-distance.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@google.com (Cyril Allauzen)
//
// \file
// Functions and classes to find shortest distance in an FST.
//
// This file has been modified by Aurelien Waite from the University of
// Cambridge.
//
// This algorithm performed the plus operation twice for two identical
// weights. The plus operation is expensive for tropical monomial weights
// The first weight is now stored in a temporary variable for speed.

#ifndef MERT_FST_LIB_SHORTEST_DISTANCE_H__
#define MERT_FST_LIB_SHORTEST_DISTANCE_H__

#include <deque>
#include <vector>

#include <fst/arcfilter.h>
#include <fst/cache.h>
#include <fst/queue.h>
#include <fst/reverse.h>
#include <fst/test-properties.h>

namespace mertfst {

template <class Arc, class Queue, class ArcFilter>
struct ShortestDistanceOptions {
  typedef typename Arc::StateId StateId;

  Queue *state_queue;    // Queue discipline used; owned by caller
  ArcFilter arc_filter;  // Arc filter (e.g., limit to only epsilon graph)
  StateId source;        // If kNoStateId, use the Fst's initial state
  float delta;           // Determines the degree of convergence required
  bool first_path;       // For a semiring with the path property (o.w.
  // undefined), compute the shortest-distances along
  // along the first path to a final state found
  // by the algorithm. That path is the shortest-path
  // only if the FST has a unique final state (or all
  // the final states have the same final weight), the
  // queue discipline is shortest-first and all the
  // weights in the FST are between One() and Zero()
  // according to NaturalLess.

  ShortestDistanceOptions (Queue *q, ArcFilter filt,
                           StateId src = fst::kNoStateId,
                           float d = fst::kDelta)
    : state_queue (q), arc_filter (filt), source (src), delta (d),
      first_path (false) {}
};

// Computation state of the shortest-distance algorithm. Reusable
// information is maintained across calls to member function
// ShortestDistance(source) when 'retain' is true for improved
// efficiency when calling multiple times from different source states
// (e.g., in epsilon removal). Contrary to usual conventions, 'fst'
// may not be freed before this class. Vector 'distance' should not be
// modified by the user between these calls.
template<class Arc, class Queue, class ArcFilter>
class ShortestDistanceState {
 public:
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  ShortestDistanceState (
    const fst::Fst<Arc>& fst,
    std::vector<Weight> *distance,
    const ShortestDistanceOptions<Arc, Queue, ArcFilter>& opts,
    bool retain)
    : fst_ (fst), distance_ (distance), state_queue_ (opts.state_queue),
      arc_filter_ (opts.arc_filter),
      delta_ (opts.delta), first_path_ (opts.first_path), retain_ (retain) {
    distance_->clear();
  }

  ~ShortestDistanceState() {}

  void ShortestDistance (StateId source);

 private:
  const fst::Fst<Arc>& fst_;
  std::vector<Weight> *distance_;
  Queue *state_queue_;
  ArcFilter arc_filter_;
  float delta_;
  bool first_path_;
  bool retain_;               // Retain and reuse information across calls

  std::vector<Weight> rdistance_;  // Relaxation distance.
  std::vector<bool> enqueued_;     // Is state enqueued?
  std::vector<StateId> sources_;   // Source state for ith state in 'distance_',
  //  'rdistance_', and 'enqueued_' if retained.
};

// Compute the shortest distance. If 'source' is kNoStateId, use
// the initial state of the Fst.
template <class Arc, class Queue, class ArcFilter>
void ShortestDistanceState<Arc, Queue, ArcFilter>::ShortestDistance (
  StateId source) {
  if (fst_.Start() == fst::kNoStateId)
    return;
  if (! (Weight::Properties() & fst::kRightSemiring) )
    LOG (FATAL) << "ShortestDistance: Weight needs to be right distributive: "
                << Weight::Type();
  if (first_path_ && ! (Weight::Properties() & fst::kPath) )
    LOG (FATAL) << "ShortestDistance: first_path option disallowed when "
                << "Weight does not have the path property: "
                << Weight::Type();
  state_queue_->Clear();
  if (!retain_) {
    distance_->clear();
    rdistance_.clear();
    enqueued_.clear();
  }
  if (source == fst::kNoStateId)
    source = fst_.Start();
  while (distance_->size() <= source) {
    distance_->push_back (Weight::Zero() );
    rdistance_.push_back (Weight::Zero() );
    enqueued_.push_back (false);
  }
  if (retain_) {
    while (sources_.size() <= source)
      sources_.push_back (fst::kNoStateId);
    sources_[source] = source;
  }
  (*distance_) [source] = Weight::One();
  rdistance_[source] = Weight::One();
  enqueued_[source] = true;
  state_queue_->Enqueue (source);
  while (!state_queue_->Empty() ) {
    StateId s = state_queue_->Head();
    state_queue_->Dequeue();
    while (distance_->size() <= s) {
      distance_->push_back (Weight::Zero() );
      rdistance_.push_back (Weight::Zero() );
      enqueued_.push_back (false);
    }
    if (first_path_ && (fst_.Final (s) != Weight::Zero() ) )
      break;
    enqueued_[s] = false;
    Weight r = rdistance_[s];
    rdistance_[s] = Weight::Zero();
    for (fst::ArcIterator< fst::Fst<Arc> > aiter (fst_, s);
         !aiter.Done();
         aiter.Next() ) {
      const Arc& arc = aiter.Value();
      if (!arc_filter_ (arc) || arc.weight == Weight::Zero() )
        continue;
      while (distance_->size() <= arc.nextstate) {
        distance_->push_back (Weight::Zero() );
        rdistance_.push_back (Weight::Zero() );
        enqueued_.push_back (false);
      }
      if (retain_) {
        while (sources_.size() <= arc.nextstate)
          sources_.push_back (fst::kNoStateId);
        if (sources_[arc.nextstate] != source) {
          (*distance_) [arc.nextstate] = Weight::Zero();
          rdistance_[arc.nextstate] = Weight::Zero();
          enqueued_[arc.nextstate] = false;
          sources_[arc.nextstate] = source;
        }
      }
      Weight& nd = (*distance_) [arc.nextstate];
      Weight& nr = rdistance_[arc.nextstate];
      Weight w = Times (r, arc.weight);
      const Weight& nd_temp = Plus (nd, w);
      if (!ApproxEqual (nd, nd_temp, delta_) ) {
        nd = nd_temp;
        nr = Plus (nr, w);
        if (!enqueued_[arc.nextstate]) {
          state_queue_->Enqueue (arc.nextstate);
          enqueued_[arc.nextstate] = true;
        } else {
          state_queue_->Update (arc.nextstate);
        }
      }
    }
  }
}

// Shortest-distance algorithm: this version allows fine control
// via the options argument. See below for a simpler interface.
//
// This computes the shortest distance from the 'opts.source' state to
// each visited state S and stores the value in the 'distance' vector.
// An unvisited state S has distance Zero(), which will be stored in
// the 'distance' vector if S is less than the maximum visited state.
// The state queue discipline, arc filter, and convergence delta are
// taken in the options argument.

// The weights must must be right distributive and k-closed (i.e., 1 +
// x + x^2 + ... + x^(k +1) = 1 + x + x^2 + ... + x^k).
//
// The algorithm is from Mohri, "Semiring Framweork and Algorithms for
// Shortest-Distance Problems", Journal of Automata, Languages and
// Combinatorics 7(3):321-350, 2002. The complexity of algorithm
// depends on the properties of the semiring and the queue discipline
// used. Refer to the paper for more details.
template<class Arc, class Queue, class ArcFilter>
void ShortestDistance (
  const fst::Fst<Arc>& fst,
  std::vector<typename Arc::Weight> *distance,
  const ShortestDistanceOptions<Arc, Queue, ArcFilter>& opts) {
  ShortestDistanceState<Arc, Queue, ArcFilter>
  sd_state (fst, distance, opts, false);
  sd_state.ShortestDistance (opts.source);
}

// Shortest-distance algorithm: simplified interface. See above for a
// version that allows finer control.
//
// If 'reverse' is false, this computes the shortest distance from the
// initial state to each state S and stores the value in the
// 'distance' vector. If 'reverse' is true, this computes the shortest
// distance from each state to the final states.  An unvisited state S
// has distance Zero(), which will be stored in the 'distance' vector
// if S is less than the maximum visited state.  The state queue
// discipline is automatically-selected.
//
// The weights must must be right (left) distributive if reverse is
// false (true) and k-closed (i.e., 1 + x + x^2 + ... + x^(k +1) = 1 +
// x + x^2 + ... + x^k).
//
// The algorithm is from Mohri, "Semiring Framweork and Algorithms for
// Shortest-Distance Problems", Journal of Automata, Languages and
// Combinatorics 7(3):321-350, 2002. The complexity of algorithm
// depends on the properties of the semiring and the queue discipline
// used. Refer to the paper for more details.
template<class Arc>
void ShortestDistance (const fst::Fst<Arc>& fst,
                       std::vector<typename Arc::Weight> *distance,
                       bool reverse = false,
                       float delta = fst::kDelta) {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  if (!reverse) {
    fst::AnyArcFilter<Arc> arc_filter;
    fst::AutoQueue<StateId> state_queue (fst, distance, arc_filter);
    ShortestDistanceOptions< Arc, fst::AutoQueue<StateId>, fst::AnyArcFilter<Arc> >
    opts (&state_queue, arc_filter);
    opts.delta = delta;
    ShortestDistance (fst, distance, opts);
  } else {
    typedef fst::ReverseArc<Arc> ReverseArc;
    typedef typename ReverseArc::Weight ReverseWeight;
    fst::AnyArcFilter<ReverseArc> rarc_filter;
    fst::VectorFst<ReverseArc> rfst;
    Reverse (fst, &rfst);
    std::vector<ReverseWeight> rdistance;
    fst::AutoQueue<StateId> state_queue (rfst, &rdistance, rarc_filter);
    ShortestDistanceOptions< ReverseArc, fst::AutoQueue<StateId>,
                             fst::AnyArcFilter<ReverseArc> >
                             ropts (&state_queue, rarc_filter);
    ropts.delta = delta;
    ShortestDistance (rfst, &rdistance, ropts);
    distance->clear();
    while (distance->size() < rdistance.size() - 1)
      distance->push_back (rdistance[distance->size() + 1].Reverse() );
  }
}

// Return the sum of the weight of all successful paths in an FST, i.e.,
// the shortest-distance from the initial state to the final states.
template <class Arc>
typename Arc::Weight ShortestDistance (const fst::Fst<Arc>& fst) {
  typedef typename Arc::Weight Weight;
  typedef typename Arc::StateId StateId;
  std::vector<Weight> distance;
  if (Weight::Properties() & fst::kRightSemiring) {
    mertfst::ShortestDistance (fst, &distance, false);
    Weight sum = Weight::Zero();
    for (StateId s = 0; s < distance.size(); ++s)
      sum = Plus (sum, Times (distance[s], fst.Final (s) ) );
    return sum;
  } else {
    mertfst::ShortestDistance (fst, &distance, true);
    StateId s = fst.Start();
    return s != fst::kNoStateId && s < distance.size() ?
           distance[s] : Weight::Zero();
  }
}

}  // namespace fst

#endif  // MERT_FST_LIB_SHORTEST_DISTANCE_H__