FST  openfst-1.8.2.post1
OpenFst Library
rand-fst.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 #ifndef FST_TEST_RAND_FST_H_
16 #define FST_TEST_RAND_FST_H_
17 
18 #include <cstdint>
19 #include <random>
20 
21 #include <fst/log.h>
22 #include <fst/mutable-fst.h>
23 #include <fst/verify.h>
24 
25 namespace fst {
26 
27 // Generates a random FST.
28 template <class Arc, class Generate>
29 void RandFst(const int num_random_states, const int num_random_arcs,
30  const int num_random_labels, const float acyclic_prob,
31  Generate generate, uint64_t seed, MutableFst<Arc> *fst) {
32  using Label = typename Arc::Label;
33  using StateId = typename Arc::StateId;
34  using Weight = typename Arc::Weight;
35 
36  // Determines direction of the arcs wrt state numbering. This way we
37  // can force acyclicity when desired.
38  enum ArcDirection {
39  ANY_DIRECTION = 0,
40  FORWARD_DIRECTION = 1,
41  REVERSE_DIRECTION = 2,
42  NUM_DIRECTIONS = 3
43  };
44 
45  std::mt19937_64 rand(seed);
46  const StateId ns =
47  std::uniform_int_distribution<>(0, num_random_states - 1)(rand);
48  std::uniform_int_distribution<size_t> arc_dist(0, num_random_arcs - 1);
49  std::uniform_int_distribution<Label> label_dist(0, num_random_labels - 1);
50  std::uniform_int_distribution<StateId> ns_dist(0, ns - 1);
51 
52  ArcDirection arc_direction = ANY_DIRECTION;
53  if (!std::bernoulli_distribution(acyclic_prob)(rand)) {
54  arc_direction = std::bernoulli_distribution(.5)(rand) ? FORWARD_DIRECTION
55  : REVERSE_DIRECTION;
56  }
57 
58  fst->DeleteStates();
59 
60  if (ns == 0) return;
61  fst->AddStates(ns);
62 
63  const StateId start = ns_dist(rand);
64  fst->SetStart(start);
65 
66  const size_t na = arc_dist(rand);
67  for (size_t n = 0; n < na; ++n) {
68  StateId s = ns_dist(rand);
69  Arc arc;
70  arc.ilabel = label_dist(rand);
71  arc.olabel = label_dist(rand);
72  arc.weight = generate();
73  arc.nextstate = ns_dist(rand);
74  if ((arc_direction == FORWARD_DIRECTION ||
75  arc_direction == REVERSE_DIRECTION) &&
76  s == arc.nextstate) {
77  continue; // Skips self-loops.
78  }
79 
80  if ((arc_direction == FORWARD_DIRECTION && s > arc.nextstate) ||
81  (arc_direction == REVERSE_DIRECTION && s < arc.nextstate)) {
82  StateId t = s; // reverses arcs
83  s = arc.nextstate;
84  arc.nextstate = t;
85  }
86 
87  fst->AddArc(s, arc);
88  }
89 
90  const StateId nf = std::uniform_int_distribution<>(0, ns)(rand);
91  for (StateId n = 0; n < nf; ++n) {
92  const StateId s = ns_dist(rand);
93  fst->SetFinal(s, generate());
94  }
95  VLOG(1) << "Check FST for sanity (including property bits).";
96  CHECK(Verify(*fst));
97 
98  // Get/compute all properties.
99  const uint64_t props = fst->Properties(kFstProperties, true);
100 
101  // Select random set of properties to be unknown.
102  uint64_t mask = 0;
103  for (int n = 0; n < 8; ++n) {
104  mask |= std::uniform_int_distribution<>(0, 0xff)(rand);
105  mask <<= 8;
106  }
107  mask &= ~kTrinaryProperties;
108  fst->SetProperties(props & ~mask, mask);
109 }
110 
111 } // namespace fst
112 
113 #endif // FST_TEST_RAND_FST_H_
virtual uint64_t Properties(uint64_t mask, bool test) const =0
constexpr uint64_t kTrinaryProperties
Definition: properties.h:312
virtual void SetStart(StateId)=0
virtual void SetProperties(uint64_t props, uint64_t mask)=0
void RandFst(const int num_random_states, const int num_random_arcs, const int num_random_labels, const float acyclic_prob, Generate generate, uint64_t seed, MutableFst< Arc > *fst)
Definition: rand-fst.h:29
#define VLOG(level)
Definition: log.h:50
bool Verify(const Fst< Arc > &fst, bool allow_negative_labels=false)
Definition: verify.h:35
constexpr uint64_t kFstProperties
Definition: properties.h:325
virtual void AddArc(StateId, const Arc &)=0
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
virtual void DeleteStates(const std::vector< StateId > &)=0
#define CHECK(x)
Definition: log.h:61
virtual void AddStates(size_t)=0