FST  openfst-1.7.2
OpenFst Library
randmod.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Generates a random FST according to a class-specific transition model.
5 
6 #ifndef FST_EXTENSIONS_COMPRESS_RANDMOD_H_
7 #define FST_EXTENSIONS_COMPRESS_RANDMOD_H_
8 
9 #include <cstdlib>
10 #include <vector>
11 
12 #include <fst/compat.h>
13 #include <fst/mutable-fst.h>
14 
15 namespace fst {
16 
17 template <class Arc, class G>
18 class RandMod {
19  public:
20  typedef typename Arc::StateId StateId;
21  typedef typename Arc::Label Label;
22  typedef typename Arc::Weight Weight;
23 
24  // Generates random FST with 'nstates' with 'nclasses' in the probability
25  // generation model, and 'nlabels' in the alphabet. If 'trans' = true, then
26  // a transducer is generated; iff 'generate_' is non-null, the output is
27  // randomly weighted.
28  RandMod(StateId nstates, StateId nclasses, Label nlabels, bool trans,
29  const G *generate)
30  : nstates_(nstates),
31  nclasses_(nclasses),
32  nlabels_(nlabels),
33  trans_(trans),
34  generate_(generate) {
35  for (StateId s = 0; s < nstates; ++s) {
36  classes_.push_back(rand() % nclasses); // NOLINT
37  }
38  }
39 
40  // Generates a random FST according to a class-specific transition model
42  StateId start = rand() % nstates_; // NOLINT
43  fst->DeleteStates();
44  for (StateId s = 0; s < nstates_; ++s) {
45  fst->AddState();
46  if (s == start) fst->SetStart(start);
47  for (StateId n = 0; n <= nstates_; ++n) {
48  Arc arc;
49  StateId d = n == nstates_ ? kNoStateId : n;
50  if (!RandArc(s, d, &arc)) continue;
51  if (d == kNoStateId) { // A super-final transition?
52  fst->SetFinal(s, arc.weight);
53  } else {
54  fst->AddArc(s, arc);
55  }
56  }
57  }
58  }
59 
60  private:
61  // Generates a transition from s to d. If d == kNoStateId, a superfinal
62  // transition is generated. Returns false if no transition generated.
63  bool RandArc(StateId s, StateId d, Arc *arc) {
64  StateId sclass = classes_[s];
65  StateId dclass = d != kNoStateId ? classes_[d] : 0;
66 
67  int r = sclass + dclass + 2;
68  if ((rand() % r) != 0) // NOLINT
69  return false;
70 
71  arc->nextstate = d;
72 
73  Label ilabel = kNoLabel;
74  Label olabel = kNoLabel;
75  if (d != kNoStateId) {
76  ilabel = (dclass % nlabels_) + 1;
77  if (trans_)
78  olabel = (sclass % nlabels_) + 1;
79  else
80  olabel = ilabel;
81  }
82 
83  Weight weight = Weight::One();
84  if (generate_) weight = (*generate_)();
85 
86  arc->ilabel = ilabel;
87  arc->olabel = olabel;
88  arc->weight = weight;
89  return true;
90  }
91 
92  StateId nstates_;
93  StateId nclasses_;
94  Label nlabels_;
95  bool trans_;
96  const G *generate_;
97  std::vector<StateId> classes_;
98 };
99 
100 } // namespace fst
101 
102 #endif // FST_EXTENSIONS_COMPRESS_RANDMOD_H_
Arc::StateId StateId
Definition: randmod.h:20
constexpr int kNoLabel
Definition: fst.h:179
void Generate(StdMutableFst *fst)
Definition: randmod.h:41
virtual void AddArc(StateId, const Arc &arc)=0
virtual void SetStart(StateId)=0
constexpr int kNoStateId
Definition: fst.h:180
virtual void SetFinal(StateId, Weight)=0
Arc::Label Label
Definition: randmod.h:21
virtual StateId AddState()=0
virtual void DeleteStates(const std::vector< StateId > &)=0
Arc::Weight Weight
Definition: randmod.h:22
RandMod(StateId nstates, StateId nclasses, Label nlabels, bool trans, const G *generate)
Definition: randmod.h:28