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