FST  openfst-1.7.3
OpenFst Library
weight-tester.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 // Utility class for regression testing of FST weights.
5 
6 #ifndef FST_TEST_WEIGHT_TESTER_H_
7 #define FST_TEST_WEIGHT_TESTER_H_
8 
9 #include <sstream>
10 #include <utility>
11 
12 #include <fst/log.h>
13 #include <fst/weight.h>
14 
15 namespace fst {
16 
17 // This class tests a variety of identities and properties that must
18 // hold for the Weight class to be well-defined. It calls function object
19 // WEIGHT_GENERATOR to select weights that are used in the tests.
20 template <class Weight, class WeightGenerator>
21 class WeightTester {
22  public:
23  WeightTester(WeightGenerator generator)
24  : weight_generator_(std::move(generator)) {}
25 
26  void Test(int iterations, bool test_division = true) {
27  for (int i = 0; i < iterations; ++i) {
28  // Selects the test weights.
29  const Weight w1(weight_generator_());
30  const Weight w2(weight_generator_());
31  const Weight w3(weight_generator_());
32 
33  VLOG(1) << "weight type = " << Weight::Type();
34  VLOG(1) << "w1 = " << w1;
35  VLOG(1) << "w2 = " << w2;
36  VLOG(1) << "w3 = " << w3;
37 
38  TestSemiring(w1, w2, w3);
39  if (test_division) TestDivision(w1, w2);
40  TestReverse(w1, w2);
41  TestEquality(w1, w2, w3);
42  TestIO(w1);
43  TestCopy(w1);
44  }
45  }
46 
47  private:
48  // Note in the tests below we use ApproxEqual rather than == and add
49  // kDelta to inequalities where the weights might be inexact.
50 
51  // Tests (Plus, Times, Zero, One) defines a commutative semiring.
52  void TestSemiring(Weight w1, Weight w2, Weight w3) {
53  // Checks that the operations are closed.
54  CHECK(Plus(w1, w2).Member());
55  CHECK(Times(w1, w2).Member());
56 
57  // Checks that the operations are associative.
58  CHECK(ApproxEqual(Plus(w1, Plus(w2, w3)), Plus(Plus(w1, w2), w3)));
59  CHECK(ApproxEqual(Times(w1, Times(w2, w3)), Times(Times(w1, w2), w3)));
60 
61  // Checks the identity elements.
62  CHECK(Plus(w1, Weight::Zero()) == w1);
63  CHECK(Plus(Weight::Zero(), w1) == w1);
64  CHECK(Times(w1, Weight::One()) == w1);
65  CHECK(Times(Weight::One(), w1) == w1);
66 
67  // Check the no weight element.
68  CHECK(!Weight::NoWeight().Member());
69  CHECK(!Plus(w1, Weight::NoWeight()).Member());
70  CHECK(!Plus(Weight::NoWeight(), w1).Member());
71  CHECK(!Times(w1, Weight::NoWeight()).Member());
72  CHECK(!Times(Weight::NoWeight(), w1).Member());
73 
74  // Checks that the operations commute.
75  CHECK(ApproxEqual(Plus(w1, w2), Plus(w2, w1)));
76 
77  if (Weight::Properties() & kCommutative)
78  CHECK(ApproxEqual(Times(w1, w2), Times(w2, w1)));
79 
80  // Checks Zero() is the annihilator.
81  CHECK(Times(w1, Weight::Zero()) == Weight::Zero());
82  CHECK(Times(Weight::Zero(), w1) == Weight::Zero());
83 
84  // Check Power(w, 0) is Weight::One()
85  CHECK(Power(w1, 0) == Weight::One());
86 
87  // Check Power(w, 1) is w
88  CHECK(Power(w1, 1) == w1);
89 
90  // Check Power(w, 2) is Times(w, w)
91  CHECK(Power(w1, 2) == Times(w1, w1));
92 
93  // Check Power(w, 3) is Times(w, Times(w, w))
94  CHECK(Power(w1, 3) == Times(w1, Times(w1, w1)));
95 
96  // Checks distributivity.
97  if (Weight::Properties() & kLeftSemiring) {
98  CHECK(ApproxEqual(Times(w1, Plus(w2, w3)),
99  Plus(Times(w1, w2), Times(w1, w3))));
100  }
101  if (Weight::Properties() & kRightSemiring)
102  CHECK(ApproxEqual(Times(Plus(w1, w2), w3),
103  Plus(Times(w1, w3), Times(w2, w3))));
104 
105  if (Weight::Properties() & kIdempotent) CHECK(Plus(w1, w1) == w1);
106 
107  if (Weight::Properties() & kPath)
108  CHECK(Plus(w1, w2) == w1 || Plus(w1, w2) == w2);
109 
110  // Ensure weights form a left or right semiring.
111  CHECK(Weight::Properties() & (kLeftSemiring | kRightSemiring));
112 
113  // Check when Times() is commutative that it is marked as a semiring.
114  if (Weight::Properties() & kCommutative)
115  CHECK(Weight::Properties() & kSemiring);
116  }
117 
118  // Tests division operation.
119  void TestDivision(Weight w1, Weight w2) {
120  Weight p = Times(w1, w2);
121 
122  if (Weight::Properties() & kLeftSemiring) {
123  Weight d = Divide(p, w1, DIVIDE_LEFT);
124  if (d.Member()) CHECK(ApproxEqual(p, Times(w1, d)));
125  CHECK(!Divide(w1, Weight::NoWeight(), DIVIDE_LEFT).Member());
126  CHECK(!Divide(Weight::NoWeight(), w1, DIVIDE_LEFT).Member());
127  }
128 
129  if (Weight::Properties() & kRightSemiring) {
130  Weight d = Divide(p, w2, DIVIDE_RIGHT);
131  if (d.Member()) CHECK(ApproxEqual(p, Times(d, w2)));
132  CHECK(!Divide(w1, Weight::NoWeight(), DIVIDE_RIGHT).Member());
133  CHECK(!Divide(Weight::NoWeight(), w1, DIVIDE_RIGHT).Member());
134  }
135 
136  if (Weight::Properties() & kCommutative) {
137  Weight d = Divide(p, w1, DIVIDE_RIGHT);
138  if (d.Member()) CHECK(ApproxEqual(p, Times(d, w1)));
139  }
140  }
141 
142  // Tests reverse operation.
143  void TestReverse(Weight w1, Weight w2) {
144  typedef typename Weight::ReverseWeight ReverseWeight;
145 
146  ReverseWeight rw1 = w1.Reverse();
147  ReverseWeight rw2 = w2.Reverse();
148 
149  CHECK(rw1.Reverse() == w1);
150  CHECK(Plus(w1, w2).Reverse() == Plus(rw1, rw2));
151  CHECK(Times(w1, w2).Reverse() == Times(rw2, rw1));
152  }
153 
154  // Tests == is an equivalence relation.
155  void TestEquality(Weight w1, Weight w2, Weight w3) {
156  // Checks reflexivity.
157  CHECK(w1 == w1);
158 
159  // Checks symmetry.
160  CHECK((w1 == w2) == (w2 == w1));
161 
162  // Checks transitivity.
163  if (w1 == w2 && w2 == w3) CHECK(w1 == w3);
164 
165  // Checks that two weights are either equal or not equal.
166  CHECK((w1 == w2) ^ (w1 != w2));
167 
168  if (w1 == w2) {
169  // Checks that equal weights have identical hashes.
170  CHECK(w1.Hash() == w2.Hash());
171  // Checks that equal weights are also approximately equal.
172  CHECK(ApproxEqual(w1, w2));
173  }
174 
175  // Checks that weights which are not even approximately equal are also
176  // strictly unequal.
177  if (!ApproxEqual(w1, w2)) {
178  CHECK(w1 != w2);
179  }
180  }
181 
182  // Tests binary serialization and textual I/O.
183  void TestIO(Weight w) {
184  // Tests binary I/O
185  {
186  std::ostringstream os;
187  w.Write(os);
188  os.flush();
189  std::istringstream is(os.str());
190  Weight v;
191  v.Read(is);
192  CHECK_EQ(w, v);
193  }
194 
195  // Tests textual I/O.
196  {
197  std::ostringstream os;
198  os << w;
199  std::istringstream is(os.str());
200  Weight v(Weight::One());
201  is >> v;
202  CHECK(ApproxEqual(w, v));
203  }
204  }
205 
206  // Tests copy constructor and assignment operator
207  void TestCopy(Weight w) {
208  Weight x = w;
209  CHECK(w == x);
210 
211  x = Weight(w);
212  CHECK(w == x);
213 
214  x.operator=(x);
215  CHECK(w == x);
216  }
217 
218  // Generates weights used in testing.
219  WeightGenerator weight_generator_;
220 };
221 
222 } // namespace fst
223 
224 #endif // FST_TEST_WEIGHT_TESTER_H_
ExpectationWeight< X1, X2 > Divide(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2, DivideType typ=DIVIDE_ANY)
constexpr uint64 kRightSemiring
Definition: weight.h:115
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
constexpr uint64 kCommutative
Definition: weight.h:120
constexpr uint64 kLeftSemiring
Definition: weight.h:112
void Reverse(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, std::vector< typename Arc::Label > *assignments, MutableFst< RevArc > *ofst)
Definition: reverse.h:20
WeightTester(WeightGenerator generator)
Definition: weight-tester.h:23
constexpr uint64 kSemiring
Definition: weight.h:117
constexpr uint64 kIdempotent
Definition: weight.h:123
#define VLOG(level)
Definition: log.h:47
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
void Test(int iterations, bool test_division=true)
Definition: weight-tester.h:26
#define CHECK_EQ(x, y)
Definition: log.h:60
constexpr uint64 kPath
Definition: weight.h:126
constexpr bool ApproxEqual(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2, float delta=kDelta)
Definition: float-weight.h:140
#define CHECK(x)
Definition: log.h:59
constexpr TropicalWeightTpl< T > Power(const TropicalWeightTpl< T > &w, V n)
Definition: float-weight.h:376