rand-fst.h
Go to the documentation of this file.
1 // fstext/rand-fst.h
2 
3 // Copyright 2009-2011 Microsoft Corporation
4 
5 // See ../../COPYING for clarification regarding multiple authors
6 //
7 // Licensed under the Apache License, Version 2.0 (the "License");
8 // you may not use this file except in compliance with the License.
9 // You may obtain a copy of the License at
10 //
11 // http://www.apache.org/licenses/LICENSE-2.0
12 //
13 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
15 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
16 // MERCHANTABLITY OR NON-INFRINGEMENT.
17 // See the Apache 2 License for the specific language governing permissions and
18 // limitations under the License.
19 
20 #ifndef KALDI_FSTEXT_RAND_FST_H_
21 #define KALDI_FSTEXT_RAND_FST_H_
22 
23 #include <sstream>
24 #include <string>
25 
26 #include <fst/fstlib.h>
27 #include <fst/fst-decl.h>
28 #include "base/kaldi-math.h"
29 
30 namespace fst {
31 
32 // Note: all weights are constructed from nonnegative floats.
33 // (so no "negative costs").
35  size_t n_syms;
36  size_t n_states;
37  size_t n_arcs;
38  size_t n_final;
40  bool acyclic;
42  RandFstOptions() { // Initializes the options randomly.
43  n_syms = 2 + kaldi::Rand() % 5;
44  n_states = 3 + kaldi::Rand() % 10;
45  n_arcs = 5 + kaldi::Rand() % 30;
46  n_final = 1 + kaldi::Rand()%3;
47  allow_empty = true;
48  acyclic = false;
49  weight_multiplier = 0.25;
50  }
51 };
52 
53 
56 template<class Arc> VectorFst<Arc>* RandFst(RandFstOptions opts = RandFstOptions() ) {
57  typedef typename Arc::StateId StateId;
58  typedef typename Arc::Weight Weight;
59 
60  VectorFst<Arc> *fst = new VectorFst<Arc>();
61 
62  start:
63 
64  // Create states.
65  std::vector<StateId> all_states;
66  for (size_t i = 0;i < (size_t)opts.n_states;i++) {
67  StateId this_state = fst->AddState();
68  if (i == 0) fst->SetStart(i);
69  all_states.push_back(this_state);
70  }
71  // Set final states.
72  for (size_t j = 0;j < (size_t)opts.n_final;j++) {
73  StateId id = all_states[kaldi::Rand() % opts.n_states];
74  Weight weight = (Weight)(opts.weight_multiplier*(kaldi::Rand() % 5));
75  fst->SetFinal(id, weight);
76  }
77  // Create arcs.
78  for (size_t i = 0;i < (size_t)opts.n_arcs;i++) {
79  Arc a;
80  StateId start_state;
81  if(!opts.acyclic) { // no restriction on arcs.
82  start_state = all_states[kaldi::Rand() % opts.n_states];
83  a.nextstate = all_states[kaldi::Rand() % opts.n_states];
84  } else {
85  start_state = all_states[kaldi::Rand() % (opts.n_states-1)];
86  a.nextstate = start_state + 1 + (kaldi::Rand() % (opts.n_states-start_state-1));
87  }
88  a.ilabel = kaldi::Rand() % opts.n_syms;
89  a.olabel = kaldi::Rand() % opts.n_syms; // same input+output vocab.
90  a.weight = (Weight) (opts.weight_multiplier*(kaldi::Rand() % 4));
91 
92  fst->AddArc(start_state, a);
93  }
94 
95  // Trim resulting FST.
96  Connect(fst);
97  if (opts.acyclic)
98  assert(fst->Properties(kAcyclic, true) & kAcyclic);
99  if (fst->Start() == kNoStateId && !opts.allow_empty) {
100  goto start;
101  }
102  return fst;
103 }
104 
105 
108 template<class Arc> VectorFst<Arc>* RandPairFst(RandFstOptions opts = RandFstOptions() ) {
109  typedef typename Arc::StateId StateId;
110  typedef typename Arc::Weight Weight;
111 
112  VectorFst<Arc> *fst = new VectorFst<Arc>();
113 
114  start:
115 
116  // Create states.
117  std::vector<StateId> all_states;
118  for (size_t i = 0;i < (size_t)opts.n_states;i++) {
119  StateId this_state = fst->AddState();
120  if (i == 0) fst->SetStart(i);
121  all_states.push_back(this_state);
122  }
123  // Set final states.
124  for (size_t j = 0; j < (size_t)opts.n_final;j++) {
125  StateId id = all_states[kaldi::Rand() % opts.n_states];
126  Weight weight (opts.weight_multiplier*(kaldi::Rand() % 5), opts.weight_multiplier*(kaldi::Rand() % 5));
127  fst->SetFinal(id, weight);
128  }
129  // Create arcs.
130  for (size_t i = 0;i < (size_t)opts.n_arcs;i++) {
131  Arc a;
132  StateId start_state;
133  if(!opts.acyclic) { // no restriction on arcs.
134  start_state = all_states[kaldi::Rand() % opts.n_states];
135  a.nextstate = all_states[kaldi::Rand() % opts.n_states];
136  } else {
137  start_state = all_states[kaldi::Rand() % (opts.n_states-1)];
138  a.nextstate = start_state + 1 + (kaldi::Rand() % (opts.n_states-start_state-1));
139  }
140  a.ilabel = kaldi::Rand() % opts.n_syms;
141  a.olabel = kaldi::Rand() % opts.n_syms; // same input+output vocab.
142  a.weight = Weight (opts.weight_multiplier*(kaldi::Rand() % 4), opts.weight_multiplier*(kaldi::Rand() % 4));
143 
144  fst->AddArc(start_state, a);
145  }
146 
147  // Trim resulting FST.
148  Connect(fst);
149  if (opts.acyclic)
150  assert(fst->Properties(kAcyclic, true) & kAcyclic);
151  if (fst->Start() == kNoStateId && !opts.allow_empty) {
152  goto start;
153  }
154  return fst;
155 }
156 
157 
158 } // end namespace fst.
159 
160 
161 #endif
162 
fst::StdArc::StateId StateId
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
VectorFst< Arc > * RandPairFst(RandFstOptions opts=RandFstOptions())
Returns a random FST.
Definition: rand-fst.h:108
float weight_multiplier
Definition: rand-fst.h:41
VectorFst< Arc > * RandFst(RandFstOptions opts=RandFstOptions())
Returns a random FST.
Definition: rand-fst.h:56
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:45
fst::StdArc::Weight Weight