include/fst/randgen.h

// randgen.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.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Classes and functions to generate random paths through an FST.

#ifndef FST_LIB_RANDGEN_H__
#define FST_LIB_RANDGEN_H__

#include <cmath>
#include <cstdlib>
#include <ctime>
#include <map>

#include <fst/accumulator.h>
#include <fst/cache.h>
#include <fst/dfs-visit.h>
#include <fst/mutable-fst.h>

namespace fst {

//
// ARC SELECTORS - these function objects are used to select a random
// transition to take from an FST's state. They should return a number
// N s.t. 0 <= N <= NumArcs(). If N < NumArcs(), then the N-th
// transition is selected. If N == NumArcs(), then the final weight at
// that state is selected (i.e., the 'super-final' transition is selected).
// It can be assumed these will not be called unless either there
// are transitions leaving the state and/or the state is final.
//

// Randomly selects a transition using the uniform distribution.
template <class A>
struct UniformArcSelector {
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;

  UniformArcSelector(int seed = time(0)) { srand(seed); }

  size_t operator()(const Fst<A> &fst, StateId s) const {
    double r = rand()/(RAND_MAX + 1.0);
    size_t n = fst.NumArcs(s);
    if (fst.Final(s) != Weight::Zero())
      ++n;
    return static_cast<size_t>(r * n);
  }
};


// Randomly selects a transition w.r.t. the weights treated as negative
// log probabilities after normalizing for the total weight leaving
// the state. Weight::zero transitions are disregarded.
// Assumes Weight::Value() accesses the floating point
// representation of the weight.
template <class A>
class LogProbArcSelector {
 public:
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;

  LogProbArcSelector(int seed = time(0)) { srand(seed); }

  size_t operator()(const Fst<A> &fst, StateId s) const {
    // Find total weight leaving state
    double sum = 0.0;
    for (ArcIterator< Fst<A> > aiter(fst, s); !aiter.Done();
         aiter.Next()) {
      const A &arc = aiter.Value();
      sum += exp(-to_log_weight_(arc.weight).Value());
    }
    sum += exp(-to_log_weight_(fst.Final(s)).Value());

    double r = rand()/(RAND_MAX + 1.0);
    double p = 0.0;
    int n = 0;
    for (ArcIterator< Fst<A> > aiter(fst, s); !aiter.Done();
         aiter.Next(), ++n) {
      const A &arc = aiter.Value();
      p += exp(-to_log_weight_(arc.weight).Value());
      if (p > r * sum) return n;
    }
    return n;
  }

 private:
  WeightConvert<Weight, Log64Weight> to_log_weight_;
};

// Convenience definitions
typedef LogProbArcSelector<StdArc> StdArcSelector;
typedef LogProbArcSelector<LogArc> LogArcSelector;


// Same as LogProbArcSelector but use CacheLogAccumulator to cache
// the cummulative weight computations.
template <class A>
class FastLogProbArcSelector : public LogProbArcSelector<A> {
 public:
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;
  using LogProbArcSelector<A>::operator();

  FastLogProbArcSelector(int seed = time(0))
      : LogProbArcSelector<A>(seed),
        seed_(seed) {}

  size_t operator()(const Fst<A> &fst, StateId s,
                    CacheLogAccumulator<A> *accumulator) const {
    accumulator->SetState(s);
    ArcIterator< Fst<A> > aiter(fst, s);
    // Find total weight leaving state
    double sum = to_log_weight_(accumulator->Sum(fst.Final(s), &aiter, 0,
                                                 fst.NumArcs(s))).Value();
    double r = -log(rand()/(RAND_MAX + 1.0));
    return accumulator->LowerBound(r + sum, &aiter);
  }

  int Seed() const { return seed_; }
 private:
  int seed_;
  WeightConvert<Weight, Log64Weight> to_log_weight_;
};

// Random path state info maintained by RandGenFst and passed to samplers.
template <typename A>
struct RandState {
  typedef typename A::StateId StateId;

  StateId state_id;              // current input FST state
  size_t nsamples;               // # of samples to be sampled at this state
  size_t length;                 // length of path to this random state
  size_t select;                 // previous sample arc selection
  const RandState<A> *parent;    // previous random state on this path

  RandState(StateId s, size_t n, size_t l, size_t k, const RandState<A> *p)
      : state_id(s), nsamples(n), length(l), select(k), parent(p) {}

  RandState()
      : state_id(kNoStateId), nsamples(0), length(0), select(0), parent(0) {}
};

// This class, given an arc selector, samples, with raplacement,
// multiple random transitions from an FST's state. This is a generic
// version with a straight-forward use of the arc selector.
// Specializations may be defined for arc selectors for greater
// efficiency or special behavior.
template <class A, class S>
class ArcSampler {
 public:
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;

  // The 'max_length' may be interpreted (including ignored) by a
  // sampler as it chooses. This generic version interprets this literally.
  ArcSampler(const Fst<A> &fst, const S &arc_selector,
             int max_length = INT_MAX)
      : fst_(fst),
        arc_selector_(arc_selector),
        max_length_(max_length) {}

  // Allow updating Fst argument; pass only if changed.
  ArcSampler(const ArcSampler<A, S> &sampler, const Fst<A> *fst = 0)
      : fst_(fst ? *fst : sampler.fst_),
        arc_selector_(sampler.arc_selector_),
        max_length_(sampler.max_length_) {
    Reset();
  }

  // Samples 'rstate.nsamples' from state 'state_id'. The 'rstate.length' is
  // the length of the path to 'rstate'. Returns true if samples were
  // collected.  No samples may be collected if either there are no (including
  // 'super-final') transitions leaving that state or if the
  // 'max_length' has been deemed reached. Use the iterator members to
  // read the samples. The samples will be in their original order.
  bool Sample(const RandState<A> &rstate) {
    sample_map_.clear();
    if ((fst_.NumArcs(rstate.state_id) == 0 &&
         fst_.Final(rstate.state_id) == Weight::Zero()) ||
        rstate.length == max_length_) {
      Reset();
      return false;
    }

    for (size_t i = 0; i < rstate.nsamples; ++i)
      ++sample_map_[arc_selector_(fst_, rstate.state_id)];
    Reset();
    return true;
  }

  // More samples?
  bool Done() const { return sample_iter_ == sample_map_.end(); }

  // Gets the next sample.
  void Next() { ++sample_iter_; }

  // Returns a pair (N, K) where 0 <= N <= NumArcs(s) and 0 < K <= nsamples.
  // If N < NumArcs(s), then the N-th transition is specified.
  // If N == NumArcs(s), then the final weight at that state is
  // specified (i.e., the 'super-final' transition is specified).
  // For the specified transition, K repetitions have been sampled.
  pair<size_t, size_t> Value() const { return *sample_iter_; }

  void Reset() { sample_iter_ = sample_map_.begin(); }

  bool Error() const { return false; }

 private:
  const Fst<A> &fst_;
  const S &arc_selector_;
  int max_length_;

  // Stores (N, K) as described for Value().
  map<size_t, size_t> sample_map_;
  map<size_t, size_t>::const_iterator sample_iter_;

  // disallow
  ArcSampler<A, S> & operator=(const ArcSampler<A, S> &s);
};


// Specialization for FastLogProbArcSelector.
template <class A>
class ArcSampler<A, FastLogProbArcSelector<A> > {
 public:
  typedef FastLogProbArcSelector<A> S;
  typedef typename A::StateId StateId;
  typedef typename A::Weight Weight;
  typedef CacheLogAccumulator<A> C;

  ArcSampler(const Fst<A> &fst, const S &arc_selector, int max_length = INT_MAX)
      : fst_(fst),
        arc_selector_(arc_selector),
        max_length_(max_length),
        accumulator_(new C()) {
    accumulator_->Init(fst);
  }

  ArcSampler(const ArcSampler<A, S> &sampler, const Fst<A> *fst = 0)
      : fst_(fst ? *fst : sampler.fst_),
        arc_selector_(sampler.arc_selector_),
        max_length_(sampler.max_length_) {
    if (fst) {
      accumulator_ = new C();
      accumulator_->Init(*fst);
    } else {  // shallow copy
      accumulator_ = new C(*sampler.accumulator_);
    }
  }

  ~ArcSampler() {
    delete accumulator_;
  }

  bool Sample(const RandState<A> &rstate) {
    sample_map_.clear();
    if ((fst_.NumArcs(rstate.state_id) == 0 &&
         fst_.Final(rstate.state_id) == Weight::Zero()) ||
        rstate.length == max_length_) {
      Reset();
      return false;
    }

    for (size_t i = 0; i < rstate.nsamples; ++i)
      ++sample_map_[arc_selector_(fst_, rstate.state_id, accumulator_)];
    Reset();
    return true;
  }

  bool Done() const { return sample_iter_ == sample_map_.end(); }
  void Next() { ++sample_iter_; }
  pair<size_t, size_t> Value() const { return *sample_iter_; }
  void Reset() { sample_iter_ = sample_map_.begin(); }

  bool Error() const { return accumulator_->Error(); }

 private:
  const Fst<A> &fst_;
  const S &arc_selector_;
  int max_length_;

  // Stores (N, K) as described for Value().
  map<size_t, size_t> sample_map_;
  map<size_t, size_t>::const_iterator sample_iter_;
  C *accumulator_;

  // disallow
  ArcSampler<A, S> & operator=(const ArcSampler<A, S> &s);
};


// Options for random path generation with RandGenFst. The template argument
// is an arc sampler, typically class 'ArcSampler' above.  Ownership of
// the sampler is taken by RandGenFst.
template <class S>
struct RandGenFstOptions : public CacheOptions {
  S *arc_sampler;            // How to sample transitions at a state
  size_t npath;              // # of paths to generate
  bool weighted;             // Output tree weighted by path count; o.w.
                             // output unweighted DAG
  bool remove_total_weight;  // Remove total weight when output is weighted.

  RandGenFstOptions(const CacheOptions &copts, S *samp,
                    size_t n = 1, bool w = true, bool rw = false)
      : CacheOptions(copts),
        arc_sampler(samp),
        npath(n),
        weighted(w),
        remove_total_weight(rw) {}
};


// Implementation of RandGenFst.
template <class A, class B, class S>
class RandGenFstImpl : public CacheImpl<B> {
 public:
  using FstImpl<B>::SetType;
  using FstImpl<B>::SetProperties;
  using FstImpl<B>::SetInputSymbols;
  using FstImpl<B>::SetOutputSymbols;

  using CacheBaseImpl< CacheState<B> >::AddArc;
  using CacheBaseImpl< CacheState<B> >::HasArcs;
  using CacheBaseImpl< CacheState<B> >::HasFinal;
  using CacheBaseImpl< CacheState<B> >::HasStart;
  using CacheBaseImpl< CacheState<B> >::SetArcs;
  using CacheBaseImpl< CacheState<B> >::SetFinal;
  using CacheBaseImpl< CacheState<B> >::SetStart;

  typedef B Arc;
  typedef typename A::Label Label;
  typedef typename A::Weight Weight;
  typedef typename A::StateId StateId;

  RandGenFstImpl(const Fst<A> &fst, const RandGenFstOptions<S> &opts)
      : CacheImpl<B>(opts),
        fst_(fst.Copy()),
        arc_sampler_(opts.arc_sampler),
        npath_(opts.npath),
        weighted_(opts.weighted),
        remove_total_weight_(opts.remove_total_weight),
        superfinal_(kNoLabel) {
    SetType("randgen");

    uint64 props = fst.Properties(kFstProperties, false);
    SetProperties(RandGenProperties(props, weighted_), kCopyProperties);

    SetInputSymbols(fst.InputSymbols());
    SetOutputSymbols(fst.OutputSymbols());
  }

  RandGenFstImpl(const RandGenFstImpl &impl)
    : CacheImpl<B>(impl),
      fst_(impl.fst_->Copy(true)),
      arc_sampler_(new S(*impl.arc_sampler_, fst_)),
      npath_(impl.npath_),
      weighted_(impl.weighted_),
      superfinal_(kNoLabel) {
    SetType("randgen");
    SetProperties(impl.Properties(), kCopyProperties);
    SetInputSymbols(impl.InputSymbols());
    SetOutputSymbols(impl.OutputSymbols());
  }

  ~RandGenFstImpl() {
    for (int i = 0; i < state_table_.size(); ++i)
      delete state_table_[i];
    delete fst_;
    delete arc_sampler_;
  }

  StateId Start() {
    if (!HasStart()) {
      StateId s = fst_->Start();
      if (s == kNoStateId)
        return kNoStateId;
      StateId start = state_table_.size();
      SetStart(start);
      RandState<A> *rstate = new RandState<A>(s, npath_, 0, 0, 0);
      state_table_.push_back(rstate);
    }
    return CacheImpl<B>::Start();
  }

  Weight Final(StateId s) {
    if (!HasFinal(s)) {
      Expand(s);
    }
    return CacheImpl<B>::Final(s);
  }

  size_t NumArcs(StateId s) {
    if (!HasArcs(s)) {
      Expand(s);
    }
    return CacheImpl<B>::NumArcs(s);
  }

  size_t NumInputEpsilons(StateId s) {
    if (!HasArcs(s))
      Expand(s);
    return CacheImpl<B>::NumInputEpsilons(s);
  }

  size_t NumOutputEpsilons(StateId s) {
    if (!HasArcs(s))
      Expand(s);
    return CacheImpl<B>::NumOutputEpsilons(s);
  }

  uint64 Properties() const { return Properties(kFstProperties); }

  // Set error if found; return FST impl properties.
  uint64 Properties(uint64 mask) const {
    if ((mask & kError) &&
        (fst_->Properties(kError, false) || arc_sampler_->Error())) {
      SetProperties(kError, kError);
    }
    return FstImpl<Arc>::Properties(mask);
  }

  void InitArcIterator(StateId s, ArcIteratorData<B> *data) {
    if (!HasArcs(s))
      Expand(s);
    CacheImpl<B>::InitArcIterator(s, data);
  }

  // Computes the outgoing transitions from a state, creating new destination
  // states as needed.
  void Expand(StateId s) {
    if (s == superfinal_) {
      SetFinal(s, Weight::One());
      SetArcs(s);
      return;
    }

    SetFinal(s, Weight::Zero());
    const RandState<A> &rstate = *state_table_[s];
    arc_sampler_->Sample(rstate);
    ArcIterator< Fst<A> > aiter(*fst_, rstate.state_id);
    size_t narcs = fst_->NumArcs(rstate.state_id);
    for (;!arc_sampler_->Done(); arc_sampler_->Next()) {
      const pair<size_t, size_t> &sample_pair = arc_sampler_->Value();
      size_t pos = sample_pair.first;
      size_t count = sample_pair.second;
      double prob = static_cast<double>(count)/rstate.nsamples;
      if (pos < narcs) {  // regular transition
        aiter.Seek(sample_pair.first);
        const A &aarc = aiter.Value();
        Weight weight = weighted_ ? to_weight_(-log(prob)) : Weight::One();
        B barc(aarc.ilabel, aarc.olabel, weight, state_table_.size());
        AddArc(s, barc);
        RandState<A> *nrstate =
            new RandState<A>(aarc.nextstate, count, rstate.length + 1,
                             pos, &rstate);
        state_table_.push_back(nrstate);
      } else {            // super-final transition
        if (weighted_) {
          Weight weight = remove_total_weight_ ?
              to_weight_(-log(prob)) : to_weight_(-log(prob * npath_));
          SetFinal(s, weight);
        } else {
          if (superfinal_ == kNoLabel) {
            superfinal_ = state_table_.size();
            RandState<A> *nrstate = new RandState<A>(kNoStateId, 0, 0, 0, 0);
            state_table_.push_back(nrstate);
          }
          for (size_t n = 0; n < count; ++n) {
            B barc(0, 0, Weight::One(), superfinal_);
            AddArc(s, barc);
          }
        }
      }
    }
    SetArcs(s);
  }

 private:
  Fst<A> *fst_;
  S *arc_sampler_;
  size_t npath_;
  vector<RandState<A> *> state_table_;
  bool weighted_;
  bool remove_total_weight_;
  StateId superfinal_;
  WeightConvert<Log64Weight, Weight> to_weight_;

  void operator=(const RandGenFstImpl<A, B, S> &);  // disallow
};


// Fst class to randomly generate paths through an FST; details controlled
// by RandGenOptionsFst. Output format is a tree weighted by the
// path count.
template <class A, class B, class S>
class RandGenFst : public ImplToFst< RandGenFstImpl<A, B, S> > {
 public:
  friend class ArcIterator< RandGenFst<A, B, S> >;
  friend class StateIterator< RandGenFst<A, B, S> >;
  typedef B Arc;
  typedef S Sampler;
  typedef typename A::Label Label;
  typedef typename A::Weight Weight;
  typedef typename A::StateId StateId;
  typedef CacheState<B> State;
  typedef RandGenFstImpl<A, B, S> Impl;

  RandGenFst(const Fst<A> &fst, const RandGenFstOptions<S> &opts)
    : ImplToFst<Impl>(new Impl(fst, opts)) {}

  // See Fst<>::Copy() for doc.
 RandGenFst(const RandGenFst<A, B, S> &fst, bool safe = false)
    : ImplToFst<Impl>(fst, safe) {}

  // Get a copy of this RandGenFst. See Fst<>::Copy() for further doc.
  virtual RandGenFst<A, B, S> *Copy(bool safe = false) const {
    return new RandGenFst<A, B, S>(*this, safe);
  }

  virtual inline void InitStateIterator(StateIteratorData<B> *data) const;

  virtual void InitArcIterator(StateId s, ArcIteratorData<B> *data) const {
    GetImpl()->InitArcIterator(s, data);
  }

 private:
  // Makes visible to friends.
  Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }

  void operator=(const RandGenFst<A, B, S> &fst);  // Disallow
};


// Specialization for RandGenFst.
template <class A, class B, class S>
class StateIterator< RandGenFst<A, B, S> >
    : public CacheStateIterator< RandGenFst<A, B, S> > {
 public:
  explicit StateIterator(const RandGenFst<A, B, S> &fst)
    : CacheStateIterator< RandGenFst<A, B, S> >(fst, fst.GetImpl()) {}

 private:
  DISALLOW_COPY_AND_ASSIGN(StateIterator);
};


// Specialization for RandGenFst.
template <class A, class B, class S>
class ArcIterator< RandGenFst<A, B, S> >
    : public CacheArcIterator< RandGenFst<A, B, S> > {
 public:
  typedef typename A::StateId StateId;

  ArcIterator(const RandGenFst<A, B, S> &fst, StateId s)
      : CacheArcIterator< RandGenFst<A, B, S> >(fst.GetImpl(), s) {
    if (!fst.GetImpl()->HasArcs(s))
      fst.GetImpl()->Expand(s);
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(ArcIterator);
};


template <class A, class B, class S> inline
void RandGenFst<A, B, S>::InitStateIterator(StateIteratorData<B> *data) const
{
  data->base = new StateIterator< RandGenFst<A, B, S> >(*this);
}

// Options for random path generation.
template <class S>
struct RandGenOptions {
  const S &arc_selector;     // How an arc is selected at a state
  int max_length;            // Maximum path length
  size_t npath;              // # of paths to generate
  bool weighted;             // Output is tree weighted by path count; o.w.
                             // output unweighted union of paths.
  bool remove_total_weight;  // Remove total weight when output is weighted.

  RandGenOptions(const S &sel, int len = INT_MAX, size_t n = 1,
                 bool w = false, bool rw = false)
      : arc_selector(sel),
        max_length(len),
        npath(n),
        weighted(w),
        remove_total_weight(rw) {}
};


template <class IArc, class OArc>
class RandGenVisitor {
 public:
  typedef typename IArc::Weight Weight;
  typedef typename IArc::StateId StateId;

  RandGenVisitor(MutableFst<OArc> *ofst) : ofst_(ofst) {}

  void InitVisit(const Fst<IArc> &ifst) {
    ifst_ = &ifst;

    ofst_->DeleteStates();
    ofst_->SetInputSymbols(ifst.InputSymbols());
    ofst_->SetOutputSymbols(ifst.OutputSymbols());
    if (ifst.Properties(kError, false))
      ofst_->SetProperties(kError, kError);
    path_.clear();
  }

  bool InitState(StateId s, StateId root) { return true; }

  bool TreeArc(StateId s, const IArc &arc) {
    if (ifst_->Final(arc.nextstate) == Weight::Zero()) {
      path_.push_back(arc);
    } else {
      OutputPath();
    }
    return true;
  }

  bool BackArc(StateId s, const IArc &arc) {
    FSTERROR() << "RandGenVisitor: cyclic input";
    ofst_->SetProperties(kError, kError);
    return false;
  }

  bool ForwardOrCrossArc(StateId s, const IArc &arc) {
    OutputPath();
    return true;
  }

  void FinishState(StateId s, StateId p, const IArc *) {
    if (p != kNoStateId && ifst_->Final(s) == Weight::Zero())
      path_.pop_back();
  }

  void FinishVisit() {}

 private:
  void OutputPath() {
    if (ofst_->Start() == kNoStateId) {
      StateId start = ofst_->AddState();
      ofst_->SetStart(start);
    }

    StateId src = ofst_->Start();
    for (size_t i = 0; i < path_.size(); ++i) {
      StateId dest = ofst_->AddState();
      OArc arc(path_[i].ilabel, path_[i].olabel, Weight::One(), dest);
      ofst_->AddArc(src, arc);
      src = dest;
    }
    ofst_->SetFinal(src, Weight::One());
  }

  const Fst<IArc> *ifst_;
  MutableFst<OArc> *ofst_;
  vector<OArc> path_;

  DISALLOW_COPY_AND_ASSIGN(RandGenVisitor);
};


// Randomly generate paths through an FST; details controlled by
// RandGenOptions.
template<class IArc, class OArc, class Selector>
void RandGen(const Fst<IArc> &ifst, MutableFst<OArc> *ofst,
             const RandGenOptions<Selector> &opts) {
  typedef ArcSampler<IArc, Selector> Sampler;
  typedef RandGenFst<IArc, OArc, Sampler> RandFst;
  typedef typename OArc::StateId StateId;
  typedef typename OArc::Weight Weight;

  Sampler* arc_sampler = new Sampler(ifst, opts.arc_selector, opts.max_length);
  RandGenFstOptions<Sampler> fopts(CacheOptions(true, 0), arc_sampler,
                                   opts.npath, opts.weighted,
                                   opts.remove_total_weight);
  RandFst rfst(ifst, fopts);
  if (opts.weighted) {
    *ofst = rfst;
  } else {
    RandGenVisitor<IArc, OArc> rand_visitor(ofst);
    DfsVisit(rfst, &rand_visitor);
  }
}

// Randomly generate a path through an FST with the uniform distribution
// over the transitions.
template<class IArc, class OArc>
void RandGen(const Fst<IArc> &ifst, MutableFst<OArc> *ofst) {
  UniformArcSelector<IArc> uniform_selector;
  RandGenOptions< UniformArcSelector<IArc> > opts(uniform_selector);
  RandGen(ifst, ofst, opts);
}

}  // namespace fst

#endif  // FST_LIB_RANDGEN_H__