FST  openfst-1.7.1
OpenFst Library
algo_test.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 // Regression test for various FST algorithms.
5 
6 #ifndef FST_TEST_ALGO_TEST_H_
7 #define FST_TEST_ALGO_TEST_H_
8 
9 #include <fst/log.h>
10 
11 #include <fst/fstlib.h>
12 #include <fst/test/rand-fst.h>
13 
14 DECLARE_int32(repeat); // defined in ./algo_test.cc
15 
16 namespace fst {
17 
18 // Mapper to change input and output label of every transition into
19 // epsilons.
20 template <class A>
21 class EpsMapper {
22  public:
23  EpsMapper() {}
24 
25  A operator()(const A &arc) const {
26  return A(0, 0, arc.weight, arc.nextstate);
27  }
28 
29  uint64 Properties(uint64 props) const {
30  props &= ~kNotAcceptor;
31  props |= kAcceptor;
32  props &= ~kNoIEpsilons & ~kNoOEpsilons & ~kNoEpsilons;
33  props |= kIEpsilons | kOEpsilons | kEpsilons;
35  props |= kILabelSorted | kOLabelSorted;
36  return props;
37  }
38 
40 
42 
44 };
45 
46 // Generic - no lookahead.
47 template <class Arc>
48 void LookAheadCompose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
49  MutableFst<Arc> *ofst) {
50  Compose(ifst1, ifst2, ofst);
51 }
52 
53 // Specialized and epsilon olabel acyclic - lookahead.
54 void LookAheadCompose(const Fst<StdArc> &ifst1, const Fst<StdArc> &ifst2,
55  MutableFst<StdArc> *ofst) {
56  std::vector<StdArc::StateId> order;
57  bool acyclic;
58  TopOrderVisitor<StdArc> visitor(&order, &acyclic);
59  DfsVisit(ifst1, &visitor, OutputEpsilonArcFilter<StdArc>());
60  if (acyclic) { // no ifst1 output epsilon cycles?
61  StdOLabelLookAheadFst lfst1(ifst1);
62  StdVectorFst lfst2(ifst2);
63  LabelLookAheadRelabeler<StdArc>::Relabel(&lfst2, lfst1, true);
64  Compose(lfst1, lfst2, ofst);
65  } else {
66  Compose(ifst1, ifst2, ofst);
67  }
68 }
69 
70 // This class tests a variety of identities and properties that must
71 // hold for various algorithms on weighted FSTs.
72 template <class Arc, class WeightGenerator>
74  public:
75  typedef typename Arc::Label Label;
76  typedef typename Arc::StateId StateId;
77  typedef typename Arc::Weight Weight;
78 
79  WeightedTester(time_t seed, const Fst<Arc> &zero_fst, const Fst<Arc> &one_fst,
80  const Fst<Arc> &univ_fst, WeightGenerator *weight_generator)
81  : seed_(seed),
82  zero_fst_(zero_fst),
83  one_fst_(one_fst),
84  univ_fst_(univ_fst),
85  weight_generator_(weight_generator) {}
86 
87  void Test(const Fst<Arc> &T1, const Fst<Arc> &T2, const Fst<Arc> &T3) {
88  TestRational(T1, T2, T3);
89  TestMap(T1);
90  TestCompose(T1, T2, T3);
91  TestSort(T1);
92  TestOptimize(T1);
93  TestSearch(T1);
94  }
95 
96  private:
97  // Tests rational operations with identities
98  void TestRational(const Fst<Arc> &T1, const Fst<Arc> &T2,
99  const Fst<Arc> &T3) {
100  {
101  VLOG(1) << "Check destructive and delayed union are equivalent.";
102  VectorFst<Arc> U1(T1);
103  Union(&U1, T2);
104  UnionFst<Arc> U2(T1, T2);
105  CHECK(Equiv(U1, U2));
106  }
107 
108  {
109  VLOG(1) << "Check destructive and delayed concatenation are equivalent.";
110  VectorFst<Arc> C1(T1);
111  Concat(&C1, T2);
112  ConcatFst<Arc> C2(T1, T2);
113  CHECK(Equiv(C1, C2));
114  VectorFst<Arc> C3(T2);
115  Concat(T1, &C3);
116  CHECK(Equiv(C3, C2));
117  }
118 
119  {
120  VLOG(1) << "Check destructive and delayed closure* are equivalent.";
121  VectorFst<Arc> C1(T1);
122  Closure(&C1, CLOSURE_STAR);
124  CHECK(Equiv(C1, C2));
125  }
126 
127  {
128  VLOG(1) << "Check destructive and delayed closure+ are equivalent.";
129  VectorFst<Arc> C1(T1);
130  Closure(&C1, CLOSURE_PLUS);
132  CHECK(Equiv(C1, C2));
133  }
134 
135  {
136  VLOG(1) << "Check union is associative (destructive).";
137  VectorFst<Arc> U1(T1);
138  Union(&U1, T2);
139  Union(&U1, T3);
140 
141  VectorFst<Arc> U3(T2);
142  Union(&U3, T3);
143  VectorFst<Arc> U4(T1);
144  Union(&U4, U3);
145 
146  CHECK(Equiv(U1, U4));
147  }
148 
149  {
150  VLOG(1) << "Check union is associative (delayed).";
151  UnionFst<Arc> U1(T1, T2);
152  UnionFst<Arc> U2(U1, T3);
153 
154  UnionFst<Arc> U3(T2, T3);
155  UnionFst<Arc> U4(T1, U3);
156 
157  CHECK(Equiv(U2, U4));
158  }
159 
160  {
161  VLOG(1) << "Check union is associative (destructive delayed).";
162  UnionFst<Arc> U1(T1, T2);
163  Union(&U1, T3);
164 
165  UnionFst<Arc> U3(T2, T3);
166  UnionFst<Arc> U4(T1, U3);
167 
168  CHECK(Equiv(U1, U4));
169  }
170 
171  {
172  VLOG(1) << "Check concatenation is associative (destructive).";
173  VectorFst<Arc> C1(T1);
174  Concat(&C1, T2);
175  Concat(&C1, T3);
176 
177  VectorFst<Arc> C3(T2);
178  Concat(&C3, T3);
179  VectorFst<Arc> C4(T1);
180  Concat(&C4, C3);
181 
182  CHECK(Equiv(C1, C4));
183  }
184 
185  {
186  VLOG(1) << "Check concatenation is associative (delayed).";
187  ConcatFst<Arc> C1(T1, T2);
188  ConcatFst<Arc> C2(C1, T3);
189 
190  ConcatFst<Arc> C3(T2, T3);
191  ConcatFst<Arc> C4(T1, C3);
192 
193  CHECK(Equiv(C2, C4));
194  }
195 
196  {
197  VLOG(1) << "Check concatenation is associative (destructive delayed).";
198  ConcatFst<Arc> C1(T1, T2);
199  Concat(&C1, T3);
200 
201  ConcatFst<Arc> C3(T2, T3);
202  ConcatFst<Arc> C4(T1, C3);
203 
204  CHECK(Equiv(C1, C4));
205  }
206 
207  if (Weight::Properties() & kLeftSemiring) {
208  VLOG(1) << "Check concatenation left distributes"
209  << " over union (destructive).";
210 
211  VectorFst<Arc> U1(T1);
212  Union(&U1, T2);
213  VectorFst<Arc> C1(T3);
214  Concat(&C1, U1);
215 
216  VectorFst<Arc> C2(T3);
217  Concat(&C2, T1);
218  VectorFst<Arc> C3(T3);
219  Concat(&C3, T2);
220  VectorFst<Arc> U2(C2);
221  Union(&U2, C3);
222 
223  CHECK(Equiv(C1, U2));
224  }
225 
226  if (Weight::Properties() & kRightSemiring) {
227  VLOG(1) << "Check concatenation right distributes"
228  << " over union (destructive).";
229  VectorFst<Arc> U1(T1);
230  Union(&U1, T2);
231  VectorFst<Arc> C1(U1);
232  Concat(&C1, T3);
233 
234  VectorFst<Arc> C2(T1);
235  Concat(&C2, T3);
236  VectorFst<Arc> C3(T2);
237  Concat(&C3, T3);
238  VectorFst<Arc> U2(C2);
239  Union(&U2, C3);
240 
241  CHECK(Equiv(C1, U2));
242  }
243 
244  if (Weight::Properties() & kLeftSemiring) {
245  VLOG(1) << "Check concatenation left distributes over union (delayed).";
246  UnionFst<Arc> U1(T1, T2);
247  ConcatFst<Arc> C1(T3, U1);
248 
249  ConcatFst<Arc> C2(T3, T1);
250  ConcatFst<Arc> C3(T3, T2);
251  UnionFst<Arc> U2(C2, C3);
252 
253  CHECK(Equiv(C1, U2));
254  }
255 
256  if (Weight::Properties() & kRightSemiring) {
257  VLOG(1) << "Check concatenation right distributes over union (delayed).";
258  UnionFst<Arc> U1(T1, T2);
259  ConcatFst<Arc> C1(U1, T3);
260 
261  ConcatFst<Arc> C2(T1, T3);
262  ConcatFst<Arc> C3(T2, T3);
263  UnionFst<Arc> U2(C2, C3);
264 
265  CHECK(Equiv(C1, U2));
266  }
267 
268  if (Weight::Properties() & kLeftSemiring) {
269  VLOG(1) << "Check T T* == T+ (destructive).";
270  VectorFst<Arc> S(T1);
271  Closure(&S, CLOSURE_STAR);
272  VectorFst<Arc> C(T1);
273  Concat(&C, S);
274 
275  VectorFst<Arc> P(T1);
276  Closure(&P, CLOSURE_PLUS);
277 
278  CHECK(Equiv(C, P));
279  }
280 
281  if (Weight::Properties() & kRightSemiring) {
282  VLOG(1) << "Check T* T == T+ (destructive).";
283  VectorFst<Arc> S(T1);
284  Closure(&S, CLOSURE_STAR);
285  VectorFst<Arc> C(S);
286  Concat(&C, T1);
287 
288  VectorFst<Arc> P(T1);
289  Closure(&P, CLOSURE_PLUS);
290 
291  CHECK(Equiv(C, P));
292  }
293 
294  if (Weight::Properties() & kLeftSemiring) {
295  VLOG(1) << "Check T T* == T+ (delayed).";
297  ConcatFst<Arc> C(T1, S);
298 
300 
301  CHECK(Equiv(C, P));
302  }
303 
304  if (Weight::Properties() & kRightSemiring) {
305  VLOG(1) << "Check T* T == T+ (delayed).";
307  ConcatFst<Arc> C(S, T1);
308 
310 
311  CHECK(Equiv(C, P));
312  }
313  }
314 
315  // Tests map-based operations.
316  void TestMap(const Fst<Arc> &T) {
317  {
318  VLOG(1) << "Check destructive and delayed projection are equivalent.";
319  VectorFst<Arc> P1(T);
320  Project(&P1, PROJECT_INPUT);
322  CHECK(Equiv(P1, P2));
323  }
324 
325  {
326  VLOG(1) << "Check destructive and delayed inversion are equivalent.";
327  VectorFst<Arc> I1(T);
328  Invert(&I1);
329  InvertFst<Arc> I2(T);
330  CHECK(Equiv(I1, I2));
331  }
332 
333  {
334  VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (destructive).";
335  VectorFst<Arc> P1(T);
336  VectorFst<Arc> I1(T);
337  Project(&P1, PROJECT_INPUT);
338  Invert(&I1);
339  Project(&I1, PROJECT_OUTPUT);
340  CHECK(Equiv(P1, I1));
341  }
342 
343  {
344  VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (destructive).";
345  VectorFst<Arc> P1(T);
346  VectorFst<Arc> I1(T);
347  Project(&P1, PROJECT_OUTPUT);
348  Invert(&I1);
349  Project(&I1, PROJECT_INPUT);
350  CHECK(Equiv(P1, I1));
351  }
352 
353  {
354  VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (delayed).";
356  InvertFst<Arc> I1(T);
358  CHECK(Equiv(P1, P2));
359  }
360 
361  {
362  VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (delayed).";
364  InvertFst<Arc> I1(T);
366  CHECK(Equiv(P1, P2));
367  }
368 
369  {
370  VLOG(1) << "Check destructive relabeling";
371  static const int kNumLabels = 10;
372  // set up relabeling pairs
373  std::vector<Label> labelset(kNumLabels);
374  for (size_t i = 0; i < kNumLabels; ++i) labelset[i] = i;
375  for (size_t i = 0; i < kNumLabels; ++i) {
376  using std::swap;
377  swap(labelset[i], labelset[rand() % kNumLabels]);
378  }
379 
380  std::vector<std::pair<Label, Label>> ipairs1(kNumLabels);
381  std::vector<std::pair<Label, Label>> opairs1(kNumLabels);
382  for (size_t i = 0; i < kNumLabels; ++i) {
383  ipairs1[i] = std::make_pair(i, labelset[i]);
384  opairs1[i] = std::make_pair(labelset[i], i);
385  }
386  VectorFst<Arc> R(T);
387  Relabel(&R, ipairs1, opairs1);
388 
389  std::vector<std::pair<Label, Label>> ipairs2(kNumLabels);
390  std::vector<std::pair<Label, Label>> opairs2(kNumLabels);
391  for (size_t i = 0; i < kNumLabels; ++i) {
392  ipairs2[i] = std::make_pair(labelset[i], i);
393  opairs2[i] = std::make_pair(i, labelset[i]);
394  }
395  Relabel(&R, ipairs2, opairs2);
396  CHECK(Equiv(R, T));
397 
398  VLOG(1) << "Check on-the-fly relabeling";
399  RelabelFst<Arc> Rdelay(T, ipairs1, opairs1);
400 
401  RelabelFst<Arc> RRdelay(Rdelay, ipairs2, opairs2);
402  CHECK(Equiv(RRdelay, T));
403  }
404 
405  {
406  VLOG(1) << "Check encoding/decoding (destructive).";
407  VectorFst<Arc> D(T);
408  uint32 encode_props = 0;
409  if (rand() % 2) encode_props |= kEncodeLabels;
410  if (rand() % 2) encode_props |= kEncodeWeights;
411  EncodeMapper<Arc> encoder(encode_props, ENCODE);
412  Encode(&D, &encoder);
413  Decode(&D, encoder);
414  CHECK(Equiv(D, T));
415  }
416 
417  {
418  VLOG(1) << "Check encoding/decoding (delayed).";
419  uint32 encode_props = 0;
420  if (rand() % 2) encode_props |= kEncodeLabels;
421  if (rand() % 2) encode_props |= kEncodeWeights;
422  EncodeMapper<Arc> encoder(encode_props, ENCODE);
423  EncodeFst<Arc> E(T, &encoder);
424  VectorFst<Arc> Encoded(E);
425  DecodeFst<Arc> D(Encoded, encoder);
426  CHECK(Equiv(D, T));
427  }
428 
429  {
430  VLOG(1) << "Check gallic mappers (constructive).";
431  ToGallicMapper<Arc> to_mapper;
432  FromGallicMapper<Arc> from_mapper;
434  VectorFst<Arc> F;
435  ArcMap(T, &G, to_mapper);
436  ArcMap(G, &F, from_mapper);
437  CHECK(Equiv(T, F));
438  }
439 
440  {
441  VLOG(1) << "Check gallic mappers (delayed).";
442  ToGallicMapper<Arc> to_mapper;
443  FromGallicMapper<Arc> from_mapper;
445  ArcMapFst<GallicArc<Arc>, Arc, FromGallicMapper<Arc>> F(G, from_mapper);
446  CHECK(Equiv(T, F));
447  }
448  }
449 
450  // Tests compose-based operations.
451  void TestCompose(const Fst<Arc> &T1, const Fst<Arc> &T2, const Fst<Arc> &T3) {
452  if (!(Weight::Properties() & kCommutative)) return;
453 
454  VectorFst<Arc> S1(T1);
455  VectorFst<Arc> S2(T2);
456  VectorFst<Arc> S3(T3);
457 
458  ILabelCompare<Arc> icomp;
459  OLabelCompare<Arc> ocomp;
460 
461  ArcSort(&S1, ocomp);
462  ArcSort(&S2, ocomp);
463  ArcSort(&S3, icomp);
464 
465  {
466  VLOG(1) << "Check composition is associative.";
467  ComposeFst<Arc> C1(S1, S2);
468  ComposeFst<Arc> C2(C1, S3);
469  ComposeFst<Arc> C3(S2, S3);
470  ComposeFst<Arc> C4(S1, C3);
471 
472  CHECK(Equiv(C2, C4));
473  }
474 
475  {
476  VLOG(1) << "Check composition left distributes over union.";
477  UnionFst<Arc> U1(S2, S3);
478  ComposeFst<Arc> C1(S1, U1);
479 
480  ComposeFst<Arc> C2(S1, S2);
481  ComposeFst<Arc> C3(S1, S3);
482  UnionFst<Arc> U2(C2, C3);
483 
484  CHECK(Equiv(C1, U2));
485  }
486 
487  {
488  VLOG(1) << "Check composition right distributes over union.";
489  UnionFst<Arc> U1(S1, S2);
490  ComposeFst<Arc> C1(U1, S3);
491 
492  ComposeFst<Arc> C2(S1, S3);
493  ComposeFst<Arc> C3(S2, S3);
494  UnionFst<Arc> U2(C2, C3);
495 
496  CHECK(Equiv(C1, U2));
497  }
498 
499  VectorFst<Arc> A1(S1);
500  VectorFst<Arc> A2(S2);
501  VectorFst<Arc> A3(S3);
502  Project(&A1, PROJECT_OUTPUT);
503  Project(&A2, PROJECT_INPUT);
504  Project(&A3, PROJECT_INPUT);
505 
506  {
507  VLOG(1) << "Check intersection is commutative.";
508  IntersectFst<Arc> I1(A1, A2);
509  IntersectFst<Arc> I2(A2, A1);
510  CHECK(Equiv(I1, I2));
511  }
512 
513  {
514  VLOG(1) << "Check all epsilon filters leads to equivalent results.";
515  typedef Matcher<Fst<Arc>> M;
516  ComposeFst<Arc> C1(S1, S2);
517  ComposeFst<Arc> C2(
519  ComposeFst<Arc> C3(S1, S2,
521 
522  CHECK(Equiv(C1, C2));
523  CHECK(Equiv(C1, C3));
524 
525  if ((Weight::Properties() & kIdempotent) ||
526  S1.Properties(kNoOEpsilons, false) ||
527  S2.Properties(kNoIEpsilons, false)) {
528  ComposeFst<Arc> C4(
529  S1, S2, ComposeFstOptions<Arc, M, TrivialComposeFilter<M>>());
530  CHECK(Equiv(C1, C4));
531  }
532 
533  if (S1.Properties(kNoOEpsilons, false) &&
534  S2.Properties(kNoIEpsilons, false)) {
535  ComposeFst<Arc> C5(S1, S2,
537  CHECK(Equiv(C1, C5));
538  }
539  }
540 
541  {
542  VLOG(1) << "Check look-ahead filters lead to equivalent results.";
543  VectorFst<Arc> C1, C2;
544  Compose(S1, S2, &C1);
545  LookAheadCompose(S1, S2, &C2);
546  CHECK(Equiv(C1, C2));
547  }
548  }
549 
550  // Tests sorting operations
551  void TestSort(const Fst<Arc> &T) {
552  ILabelCompare<Arc> icomp;
553  OLabelCompare<Arc> ocomp;
554 
555  {
556  VLOG(1) << "Check arc sorted Fst is equivalent to its input.";
557  VectorFst<Arc> S1(T);
558  ArcSort(&S1, icomp);
559  CHECK(Equiv(T, S1));
560  }
561 
562  {
563  VLOG(1) << "Check destructive and delayed arcsort are equivalent.";
564  VectorFst<Arc> S1(T);
565  ArcSort(&S1, icomp);
567  CHECK(Equiv(S1, S2));
568  }
569 
570  {
571  VLOG(1) << "Check ilabel sorting vs. olabel sorting with inversions.";
572  VectorFst<Arc> S1(T);
573  VectorFst<Arc> S2(T);
574  ArcSort(&S1, icomp);
575  Invert(&S2);
576  ArcSort(&S2, ocomp);
577  Invert(&S2);
578  CHECK(Equiv(S1, S2));
579  }
580 
581  {
582  VLOG(1) << "Check topologically sorted Fst is equivalent to its input.";
583  VectorFst<Arc> S1(T);
584  TopSort(&S1);
585  CHECK(Equiv(T, S1));
586  }
587 
588  {
589  VLOG(1) << "Check reverse(reverse(T)) = T";
590  for (int i = 0; i < 2; ++i) {
592  VectorFst<Arc> R2;
593  bool require_superinitial = i == 1;
594  Reverse(T, &R1, require_superinitial);
595  Reverse(R1, &R2, require_superinitial);
596  CHECK(Equiv(T, R2));
597  }
598  }
599  }
600 
601  // Tests optimization operations
602  void TestOptimize(const Fst<Arc> &T) {
603  uint64 tprops = T.Properties(kFstProperties, true);
604  uint64 wprops = Weight::Properties();
605 
606  VectorFst<Arc> A(T);
607  Project(&A, PROJECT_INPUT);
608  {
609  VLOG(1) << "Check connected FST is equivalent to its input.";
610  VectorFst<Arc> C1(T);
611  Connect(&C1);
612  CHECK(Equiv(T, C1));
613  }
614 
615  if ((wprops & kSemiring) == kSemiring &&
616  (tprops & kAcyclic || wprops & kIdempotent)) {
617  VLOG(1) << "Check epsilon-removed FST is equivalent to its input.";
618  VectorFst<Arc> R1(T);
619  RmEpsilon(&R1);
620  CHECK(Equiv(T, R1));
621 
622  VLOG(1) << "Check destructive and delayed epsilon removal"
623  << "are equivalent.";
624  RmEpsilonFst<Arc> R2(T);
625  CHECK(Equiv(R1, R2));
626 
627  VLOG(1) << "Check an FST with a large proportion"
628  << " of epsilon transitions:";
629  // Maps all transitions of T to epsilon-transitions and append
630  // a non-epsilon transition.
631  VectorFst<Arc> U;
632  ArcMap(T, &U, EpsMapper<Arc>());
633  VectorFst<Arc> V;
634  V.SetStart(V.AddState());
635  Arc arc(1, 1, Weight::One(), V.AddState());
636  V.AddArc(V.Start(), arc);
637  V.SetFinal(arc.nextstate, Weight::One());
638  Concat(&U, V);
639  // Check that epsilon-removal preserves the shortest-distance
640  // from the initial state to the final states.
641  std::vector<Weight> d;
642  ShortestDistance(U, &d, true);
643  Weight w = U.Start() < d.size() ? d[U.Start()] : Weight::Zero();
644  VectorFst<Arc> U1(U);
645  RmEpsilon(&U1);
646  ShortestDistance(U1, &d, true);
647  Weight w1 = U1.Start() < d.size() ? d[U1.Start()] : Weight::Zero();
648  CHECK(ApproxEqual(w, w1, kTestDelta));
649  RmEpsilonFst<Arc> U2(U);
650  ShortestDistance(U2, &d, true);
651  Weight w2 = U2.Start() < d.size() ? d[U2.Start()] : Weight::Zero();
652  CHECK(ApproxEqual(w, w2, kTestDelta));
653  }
654 
655  if ((wprops & kSemiring) == kSemiring && tprops & kAcyclic) {
656  VLOG(1) << "Check determinized FSA is equivalent to its input.";
657  DeterminizeFst<Arc> D(A);
658  CHECK(Equiv(A, D));
659 
660  {
661  VLOG(1) << "Check determinized FST is equivalent to its input.";
664  DeterminizeFst<Arc> DT(T, opts);
665  CHECK(Equiv(T, DT));
666  }
667 
668  if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
669  VLOG(1) << "Check pruning in determinization";
670  VectorFst<Arc> P;
671  Weight threshold = (*weight_generator_)();
673  opts.weight_threshold = threshold;
674  Determinize(A, &P, opts);
675  CHECK(P.Properties(kIDeterministic, true));
676  CHECK(PruneEquiv(A, P, threshold));
677  }
678 
679  if ((wprops & kPath) == kPath) {
680  VLOG(1) << "Check min-determinization";
681 
682  // Ensures no input epsilons
683  VectorFst<Arc> R(T);
684  std::vector<std::pair<Label, Label>> ipairs, opairs;
685  ipairs.push_back(std::pair<Label, Label>(0, 1));
686  Relabel(&R, ipairs, opairs);
687 
688  VectorFst<Arc> M;
691  Determinize(R, &M, opts);
692  CHECK(M.Properties(kIDeterministic, true));
693  CHECK(MinRelated(M, R));
694  }
695 
696  int n;
697  {
698  VLOG(1) << "Check size(min(det(A))) <= size(det(A))"
699  << " and min(det(A)) equiv det(A)";
700  VectorFst<Arc> M(D);
701  n = M.NumStates();
702  Minimize(&M, static_cast<MutableFst<Arc> *>(nullptr), kDelta);
703  CHECK(Equiv(D, M));
704  CHECK(M.NumStates() <= n);
705  n = M.NumStates();
706  }
707 
708  if (n && (wprops & kIdempotent) == kIdempotent &&
709  A.Properties(kNoEpsilons, true)) {
710  VLOG(1) << "Check that Revuz's algorithm leads to the"
711  << " same number of states as Brozozowski's algorithm";
712 
713  // Skip test if A is the empty machine or contains epsilons or
714  // if the semiring is not idempotent (to avoid floating point
715  // errors)
716  VectorFst<Arc> R;
717  Reverse(A, &R);
718  RmEpsilon(&R);
719  DeterminizeFst<Arc> DR(R);
720  VectorFst<Arc> RD;
721  Reverse(DR, &RD);
722  DeterminizeFst<Arc> DRD(RD);
723  VectorFst<Arc> M(DRD);
724  CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition
725  // to the initial state
726  }
727  }
728 
729  if ((wprops & kSemiring) == kSemiring && tprops & kAcyclic) {
730  VLOG(1) << "Check disambiguated FSA is equivalent to its input.";
731  VectorFst<Arc> R(A), D;
732  RmEpsilon(&R);
733  Disambiguate(R, &D);
734  CHECK(Equiv(R, D));
735  VLOG(1) << "Check disambiguated FSA is unambiguous";
736  CHECK(Unambiguous(D));
737 
738  /* TODO(riley): find out why this fails
739  if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
740  VLOG(1) << "Check pruning in disambiguation";
741  VectorFst<Arc> P;
742  Weight threshold = (*weight_generator_)();
743  DisambiguateOptions<Arc> opts;
744  opts.weight_threshold = threshold;
745  Disambiguate(R, &P, opts);
746  CHECK(Unambiguous(P));
747  CHECK(PruneEquiv(A, P, threshold));
748  }
749  */
750  }
751 
752  if (Arc::Type() == LogArc::Type() || Arc::Type() == StdArc::Type()) {
753  VLOG(1) << "Check reweight(T) equiv T";
754  std::vector<Weight> potential;
755  VectorFst<Arc> RI(T);
756  VectorFst<Arc> RF(T);
757  while (potential.size() < RI.NumStates())
758  potential.push_back((*weight_generator_)());
759 
760  Reweight(&RI, potential, REWEIGHT_TO_INITIAL);
761  CHECK(Equiv(T, RI));
762 
763  Reweight(&RF, potential, REWEIGHT_TO_FINAL);
764  CHECK(Equiv(T, RF));
765  }
766 
767  if ((wprops & kIdempotent) || (tprops & kAcyclic)) {
768  VLOG(1) << "Check pushed FST is equivalent to input FST.";
769  // Pushing towards the final state.
770  if (wprops & kRightSemiring) {
771  VectorFst<Arc> P1;
772  Push<Arc, REWEIGHT_TO_FINAL>(T, &P1, kPushLabels);
773  CHECK(Equiv(T, P1));
774 
775  VectorFst<Arc> P2;
776  Push<Arc, REWEIGHT_TO_FINAL>(T, &P2, kPushWeights);
777  CHECK(Equiv(T, P2));
778 
779  VectorFst<Arc> P3;
780  Push<Arc, REWEIGHT_TO_FINAL>(T, &P3, kPushLabels | kPushWeights);
781  CHECK(Equiv(T, P3));
782  }
783 
784  // Pushing towards the initial state.
785  if (wprops & kLeftSemiring) {
786  VectorFst<Arc> P1;
787  Push<Arc, REWEIGHT_TO_INITIAL>(T, &P1, kPushLabels);
788  CHECK(Equiv(T, P1));
789 
790  VectorFst<Arc> P2;
791  Push<Arc, REWEIGHT_TO_INITIAL>(T, &P2, kPushWeights);
792  CHECK(Equiv(T, P2));
793  VectorFst<Arc> P3;
794  Push<Arc, REWEIGHT_TO_INITIAL>(T, &P3, kPushLabels | kPushWeights);
795  CHECK(Equiv(T, P3));
796  }
797  }
798 
799  if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
800  VLOG(1) << "Check pruning algorithm";
801  {
802  VLOG(1) << "Check equiv. of constructive and destructive algorithms";
803  Weight thresold = (*weight_generator_)();
804  VectorFst<Arc> P1(T);
805  Prune(&P1, thresold);
806  VectorFst<Arc> P2;
807  Prune(T, &P2, thresold);
808  CHECK(Equiv(P1, P2));
809  }
810 
811  {
812  VLOG(1) << "Check prune(reverse) equiv reverse(prune)";
813  Weight thresold = (*weight_generator_)();
815  VectorFst<Arc> P1(T);
816  VectorFst<Arc> P2;
817  Prune(&P1, thresold);
818  Reverse(T, &R);
819  Prune(&R, thresold.Reverse());
820  Reverse(R, &P2);
821  CHECK(Equiv(P1, P2));
822  }
823  {
824  VLOG(1) << "Check: ShortestDistance(A - prune(A))"
825  << " > ShortestDistance(A) times Threshold";
826  Weight threshold = (*weight_generator_)();
827  VectorFst<Arc> P;
828  Prune(A, &P, threshold);
829  CHECK(PruneEquiv(A, P, threshold));
830  }
831  }
832  if (tprops & kAcyclic) {
833  VLOG(1) << "Check synchronize(T) equiv T";
834  SynchronizeFst<Arc> S(T);
835  CHECK(Equiv(T, S));
836  }
837  }
838 
839  // Tests search operations
840  void TestSearch(const Fst<Arc> &T) {
841  uint64 wprops = Weight::Properties();
842 
843  VectorFst<Arc> A(T);
844  Project(&A, PROJECT_INPUT);
845 
846  if ((wprops & (kPath | kRightSemiring)) == (kPath | kRightSemiring)) {
847  VLOG(1) << "Check 1-best weight.";
848  VectorFst<Arc> path;
849  ShortestPath(T, &path);
850  Weight tsum = ShortestDistance(T);
851  Weight psum = ShortestDistance(path);
852  CHECK(ApproxEqual(tsum, psum, kTestDelta));
853  }
854 
855  if ((wprops & (kPath | kSemiring)) == (kPath | kSemiring)) {
856  VLOG(1) << "Check n-best weights";
857  VectorFst<Arc> R(A);
858  RmEpsilon(&R, /*connect=*/ true, Arc::Weight::Zero(), kNoStateId,
859  kDelta);
860  int nshortest = rand() % kNumRandomShortestPaths + 2;
861  VectorFst<Arc> paths;
862  ShortestPath(R, &paths, nshortest, /*unique=*/ true,
863  /*first_path=*/ false, Weight::Zero(), kNumShortestStates,
864  kDelta);
865  std::vector<Weight> distance;
866  ShortestDistance(paths, &distance, true, kDelta);
867  StateId pstart = paths.Start();
868  if (pstart != kNoStateId) {
869  ArcIterator<Fst<Arc>> piter(paths, pstart);
870  for (; !piter.Done(); piter.Next()) {
871  StateId s = piter.Value().nextstate;
872  Weight nsum = s < distance.size()
873  ? Times(piter.Value().weight, distance[s])
874  : Weight::Zero();
875  VectorFst<Arc> path;
876  ShortestPath(R, &path, 1, false, false, Weight::Zero(), kNoStateId,
877  kDelta);
878  Weight dsum = ShortestDistance(path, kDelta);
879  CHECK(ApproxEqual(nsum, dsum, kTestDelta));
880  ArcMap(&path, RmWeightMapper<Arc>());
881  VectorFst<Arc> S;
882  Difference(R, path, &S);
883  R = S;
884  }
885  }
886  }
887  }
888 
889  // Tests if two FSTS are equivalent by checking if random
890  // strings from one FST are transduced the same by both FSTs.
891  template <class A>
892  bool Equiv(const Fst<A> &fst1, const Fst<A> &fst2) {
893  VLOG(1) << "Check FSTs for sanity (including property bits).";
894  CHECK(Verify(fst1));
895  CHECK(Verify(fst2));
896 
897  // Ensures seed used once per instantiation.
898  static UniformArcSelector<A> uniform_selector(seed_);
899  RandGenOptions<UniformArcSelector<A>> opts(uniform_selector,
900  kRandomPathLength);
901  return RandEquivalent(fst1, fst2, kNumRandomPaths, kTestDelta, opts);
902  }
903 
904  // Tests FSA is unambiguous
905  bool Unambiguous(const Fst<Arc> &fst) {
906  VectorFst<StdArc> sfst, dfst;
907  VectorFst<LogArc> lfst1, lfst2;
908  Map(fst, &sfst, RmWeightMapper<Arc, StdArc>());
909  Determinize(sfst, &dfst);
910  Map(fst, &lfst1, RmWeightMapper<Arc, LogArc>());
911  Map(dfst, &lfst2, RmWeightMapper<StdArc, LogArc>());
912  return Equiv(lfst1, lfst2);
913  }
914 
915  // Ensures input-epsilon free transducers fst1 and fst2 have the
916  // same domain and that for each string pair '(is, os)' in fst1,
917  // '(is, os)' is the minimum weight match to 'is' in fst2.
918  template <class A>
919  bool MinRelated(const Fst<A> &fst1, const Fst<A> &fst2) {
920  // Same domain
921  VectorFst<Arc> P1(fst1), P2(fst2);
922  Project(&P1, PROJECT_INPUT);
923  Project(&P2, PROJECT_INPUT);
924  if (!Equiv(P1, P2)) {
925  LOG(ERROR) << "Inputs not equivalent";
926  return false;
927  }
928 
929  // Ensures seed used once per instantiation.
930  static UniformArcSelector<A> uniform_selector(seed_);
931  RandGenOptions<UniformArcSelector<A>> opts(uniform_selector,
932  kRandomPathLength);
933 
934  VectorFst<Arc> path, paths1, paths2;
935  for (ssize_t n = 0; n < kNumRandomPaths; ++n) {
936  RandGen(fst1, &path, opts);
937  Invert(&path);
938  Map(&path, RmWeightMapper<Arc>());
939  Compose(path, fst2, &paths1);
940  Weight sum1 = ShortestDistance(paths1);
941  Compose(paths1, path, &paths2);
942  Weight sum2 = ShortestDistance(paths2);
943  if (!ApproxEqual(Plus(sum1, sum2), sum2, kTestDelta)) {
944  LOG(ERROR) << "Sums not equivalent: " << sum1 << " " << sum2;
945  return false;
946  }
947  }
948  return true;
949  }
950 
951  // Tests ShortestDistance(A - P) >=
952  // ShortestDistance(A) times Threshold.
953  template <class A>
954  bool PruneEquiv(const Fst<A> &fst, const Fst<A> &pfst, Weight threshold) {
955  VLOG(1) << "Check FSTs for sanity (including property bits).";
956  CHECK(Verify(fst));
957  CHECK(Verify(pfst));
958 
960  ArcMapFst<Arc, Arc, RmWeightMapper<Arc>>(
961  pfst, RmWeightMapper<Arc>()))));
962  Weight sum1 = Times(ShortestDistance(fst), threshold);
963  Weight sum2 = ShortestDistance(D);
964  return ApproxEqual(Plus(sum1, sum2), sum1, kTestDelta);
965  }
966 
967  // Random seed.
968  int seed_;
969  // FST with no states
970  VectorFst<Arc> zero_fst_;
971  // FST with one state that accepts epsilon.
972  VectorFst<Arc> one_fst_;
973  // FST with one state that accepts all strings.
974  VectorFst<Arc> univ_fst_;
975  // Generates weights used in testing.
976  WeightGenerator *weight_generator_;
977  // Maximum random path length.
978  static const int kRandomPathLength;
979  // Number of random paths to explore.
980  static const int kNumRandomPaths;
981  // Maximum number of nshortest paths.
982  static const int kNumRandomShortestPaths;
983  // Maximum number of nshortest states.
984  static const int kNumShortestStates;
985  // Delta for equivalence tests.
986  static const float kTestDelta;
987 
988  WeightedTester(const WeightedTester &) = delete;
989  WeightedTester &operator=(const WeightedTester &) = delete;
990 };
991 
992 template <class A, class WG>
994 
995 template <class A, class WG>
997 
998 template <class A, class WG>
1000 
1001 template <class A, class WG>
1003 
1004 template <class A, class WG>
1005 const float WeightedTester<A, WG>::kTestDelta = .05;
1006 
1007 // This class tests a variety of identities and properties that must
1008 // hold for various algorithms on unweighted FSAs and that are not tested
1009 // by WeightedTester. Only the specialization does anything interesting.
1010 template <class Arc>
1012  public:
1013  UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
1014  const Fst<Arc> &univ_fsa) {}
1015 
1016  void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {}
1017 };
1018 
1019 // Specialization for StdArc. This should work for any commutative,
1020 // idempotent semiring when restricted to the unweighted case
1021 // (being isomorphic to the boolean semiring).
1022 template <>
1024  public:
1025  typedef StdArc Arc;
1029 
1030  UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
1031  const Fst<Arc> &univ_fsa)
1032  : zero_fsa_(zero_fsa), one_fsa_(one_fsa), univ_fsa_(univ_fsa) {}
1033 
1034  void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {
1035  TestRational(A1, A2, A3);
1036  TestIntersect(A1, A2, A3);
1037  TestOptimize(A1);
1038  }
1039 
1040  private:
1041  // Tests rational operations with identities
1042  void TestRational(const Fst<Arc> &A1, const Fst<Arc> &A2,
1043  const Fst<Arc> &A3) {
1044  {
1045  VLOG(1) << "Check the union contains its arguments (destructive).";
1046  VectorFst<Arc> U(A1);
1047  Union(&U, A2);
1048 
1049  CHECK(Subset(A1, U));
1050  CHECK(Subset(A2, U));
1051  }
1052 
1053  {
1054  VLOG(1) << "Check the union contains its arguments (delayed).";
1055  UnionFst<Arc> U(A1, A2);
1056 
1057  CHECK(Subset(A1, U));
1058  CHECK(Subset(A2, U));
1059  }
1060 
1061  {
1062  VLOG(1) << "Check if A^n c A* (destructive).";
1063  VectorFst<Arc> C(one_fsa_);
1064  int n = rand() % 5;
1065  for (int i = 0; i < n; ++i) Concat(&C, A1);
1066 
1067  VectorFst<Arc> S(A1);
1068  Closure(&S, CLOSURE_STAR);
1069  CHECK(Subset(C, S));
1070  }
1071 
1072  {
1073  VLOG(1) << "Check if A^n c A* (delayed).";
1074  int n = rand() % 5;
1075  Fst<Arc> *C = new VectorFst<Arc>(one_fsa_);
1076  for (int i = 0; i < n; ++i) {
1077  ConcatFst<Arc> *F = new ConcatFst<Arc>(*C, A1);
1078  delete C;
1079  C = F;
1080  }
1082  CHECK(Subset(*C, S));
1083  delete C;
1084  }
1085  }
1086 
1087  // Tests intersect-based operations.
1088  void TestIntersect(const Fst<Arc> &A1, const Fst<Arc> &A2,
1089  const Fst<Arc> &A3) {
1090  VectorFst<Arc> S1(A1);
1091  VectorFst<Arc> S2(A2);
1092  VectorFst<Arc> S3(A3);
1093 
1094  ILabelCompare<Arc> comp;
1095 
1096  ArcSort(&S1, comp);
1097  ArcSort(&S2, comp);
1098  ArcSort(&S3, comp);
1099 
1100  {
1101  VLOG(1) << "Check the intersection is contained in its arguments.";
1102  IntersectFst<Arc> I1(S1, S2);
1103  CHECK(Subset(I1, S1));
1104  CHECK(Subset(I1, S2));
1105  }
1106 
1107  {
1108  VLOG(1) << "Check union distributes over intersection.";
1109  IntersectFst<Arc> I1(S1, S2);
1110  UnionFst<Arc> U1(I1, S3);
1111 
1112  UnionFst<Arc> U2(S1, S3);
1113  UnionFst<Arc> U3(S2, S3);
1114  ArcSortFst<Arc, ILabelCompare<Arc>> S4(U3, comp);
1115  IntersectFst<Arc> I2(U2, S4);
1116 
1117  CHECK(Equiv(U1, I2));
1118  }
1119 
1120  VectorFst<Arc> C1;
1121  VectorFst<Arc> C2;
1122  Complement(S1, &C1);
1123  Complement(S2, &C2);
1124  ArcSort(&C1, comp);
1125  ArcSort(&C2, comp);
1126 
1127  {
1128  VLOG(1) << "Check S U S' = Sigma*";
1129  UnionFst<Arc> U(S1, C1);
1130  CHECK(Equiv(U, univ_fsa_));
1131  }
1132 
1133  {
1134  VLOG(1) << "Check S n S' = {}";
1135  IntersectFst<Arc> I(S1, C1);
1136  CHECK(Equiv(I, zero_fsa_));
1137  }
1138 
1139  {
1140  VLOG(1) << "Check (S1' U S2') == (S1 n S2)'";
1141  UnionFst<Arc> U(C1, C2);
1142 
1143  IntersectFst<Arc> I(S1, S2);
1144  VectorFst<Arc> C3;
1145  Complement(I, &C3);
1146  CHECK(Equiv(U, C3));
1147  }
1148 
1149  {
1150  VLOG(1) << "Check (S1' n S2') == (S1 U S2)'";
1151  IntersectFst<Arc> I(C1, C2);
1152 
1153  UnionFst<Arc> U(S1, S2);
1154  VectorFst<Arc> C3;
1155  Complement(U, &C3);
1156  CHECK(Equiv(I, C3));
1157  }
1158  }
1159 
1160  // Tests optimization operations
1161  void TestOptimize(const Fst<Arc> &A) {
1162  {
1163  VLOG(1) << "Check determinized FSA is equivalent to its input.";
1164  DeterminizeFst<Arc> D(A);
1165  CHECK(Equiv(A, D));
1166  }
1167 
1168  {
1169  VLOG(1) << "Check disambiguated FSA is equivalent to its input.";
1170  VectorFst<Arc> R(A), D;
1171  RmEpsilon(&R);
1172 
1173  Disambiguate(R, &D);
1174  CHECK(Equiv(R, D));
1175  }
1176 
1177  {
1178  VLOG(1) << "Check minimized FSA is equivalent to its input.";
1179  int n;
1180  {
1181  RmEpsilonFst<Arc> R(A);
1182  DeterminizeFst<Arc> D(R);
1183  VectorFst<Arc> M(D);
1184  Minimize(&M, static_cast<MutableFst<Arc> *>(nullptr), kDelta);
1185  CHECK(Equiv(A, M));
1186  n = M.NumStates();
1187  }
1188 
1189  if (n) { // Skip test if A is the empty machine
1190  VLOG(1) << "Check that Hopcroft's and Revuz's algorithms lead to the"
1191  << " same number of states as Brozozowski's algorithm";
1192  VectorFst<Arc> R;
1193  Reverse(A, &R);
1194  RmEpsilon(&R);
1195  DeterminizeFst<Arc> DR(R);
1196  VectorFst<Arc> RD;
1197  Reverse(DR, &RD);
1198  DeterminizeFst<Arc> DRD(RD);
1199  VectorFst<Arc> M(DRD);
1200  CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition
1201  // to the initial state
1202  }
1203  }
1204  }
1205 
1206  // Tests if two FSAS are equivalent.
1207  bool Equiv(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
1208  VLOG(1) << "Check FSAs for sanity (including property bits).";
1209  CHECK(Verify(fsa1));
1210  CHECK(Verify(fsa2));
1211 
1212  VectorFst<Arc> vfsa1(fsa1);
1213  VectorFst<Arc> vfsa2(fsa2);
1214  RmEpsilon(&vfsa1);
1215  RmEpsilon(&vfsa2);
1216  DeterminizeFst<Arc> dfa1(vfsa1);
1217  DeterminizeFst<Arc> dfa2(vfsa2);
1218 
1219  // Test equivalence using union-find algorithm
1220  bool equiv1 = Equivalent(dfa1, dfa2);
1221 
1222  // Test equivalence by checking if (S1 - S2) U (S2 - S1) is empty
1223  ILabelCompare<Arc> comp;
1224  VectorFst<Arc> sdfa1(dfa1);
1225  ArcSort(&sdfa1, comp);
1226  VectorFst<Arc> sdfa2(dfa2);
1227  ArcSort(&sdfa2, comp);
1228 
1229  DifferenceFst<Arc> dfsa1(sdfa1, sdfa2);
1230  DifferenceFst<Arc> dfsa2(sdfa2, sdfa1);
1231 
1232  VectorFst<Arc> ufsa(dfsa1);
1233  Union(&ufsa, dfsa2);
1234  Connect(&ufsa);
1235  bool equiv2 = ufsa.NumStates() == 0;
1236 
1237  // Check two equivalence tests match
1238  CHECK((equiv1 && equiv2) || (!equiv1 && !equiv2));
1239 
1240  return equiv1;
1241  }
1242 
1243  // Tests if FSA1 is a subset of FSA2 (disregarding weights).
1244  bool Subset(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
1245  VLOG(1) << "Check FSAs (incl. property bits) for sanity";
1246  CHECK(Verify(fsa1));
1247  CHECK(Verify(fsa2));
1248 
1249  VectorFst<StdArc> vfsa1;
1250  VectorFst<StdArc> vfsa2;
1251  RmEpsilon(&vfsa1);
1252  RmEpsilon(&vfsa2);
1253  ILabelCompare<StdArc> comp;
1254  ArcSort(&vfsa1, comp);
1255  ArcSort(&vfsa2, comp);
1256  IntersectFst<StdArc> ifsa(vfsa1, vfsa2);
1257  DeterminizeFst<StdArc> dfa1(vfsa1);
1258  DeterminizeFst<StdArc> dfa2(ifsa);
1259  return Equivalent(dfa1, dfa2);
1260  }
1261 
1262  // Returns complement Fsa
1263  void Complement(const Fst<Arc> &ifsa, MutableFst<Arc> *ofsa) {
1264  RmEpsilonFst<Arc> rfsa(ifsa);
1265  DeterminizeFst<Arc> dfa(rfsa);
1266  DifferenceFst<Arc> cfsa(univ_fsa_, dfa);
1267  *ofsa = cfsa;
1268  }
1269 
1270  // FSA with no states
1271  VectorFst<Arc> zero_fsa_;
1272 
1273  // FSA with one state that accepts epsilon.
1274  VectorFst<Arc> one_fsa_;
1275 
1276  // FSA with one state that accepts all strings.
1277  VectorFst<Arc> univ_fsa_;
1278 };
1279 
1280 // This class tests a variety of identities and properties that must
1281 // hold for various FST algorithms. It randomly generates FSTs, using
1282 // function object 'weight_generator' to select weights. 'WeightTester'
1283 // and 'UnweightedTester' are then called.
1284 template <class Arc, class WeightGenerator>
1285 class AlgoTester {
1286  public:
1287  typedef typename Arc::Label Label;
1288  typedef typename Arc::StateId StateId;
1289  typedef typename Arc::Weight Weight;
1290 
1291  AlgoTester(WeightGenerator generator, int seed)
1292  : weight_generator_(generator) {
1293  one_fst_.AddState();
1294  one_fst_.SetStart(0);
1295  one_fst_.SetFinal(0, Weight::One());
1296 
1297  univ_fst_.AddState();
1298  univ_fst_.SetStart(0);
1299  univ_fst_.SetFinal(0, Weight::One());
1300  for (int i = 0; i < kNumRandomLabels; ++i)
1301  univ_fst_.AddArc(0, Arc(i, i, Weight::One(), 0));
1302 
1303  weighted_tester_ = new WeightedTester<Arc, WeightGenerator>(
1304  seed, zero_fst_, one_fst_, univ_fst_, &weight_generator_);
1305 
1306  unweighted_tester_ =
1307  new UnweightedTester<Arc>(zero_fst_, one_fst_, univ_fst_);
1308  }
1309 
1311  delete weighted_tester_;
1312  delete unweighted_tester_;
1313  }
1314 
1316  RandFst<Arc, WeightGenerator>(kNumRandomStates, kNumRandomArcs,
1317  kNumRandomLabels, kAcyclicProb,
1318  &weight_generator_, fst);
1319  }
1320 
1321  void Test() {
1322  VLOG(1) << "weight type = " << Weight::Type();
1323 
1324  for (int i = 0; i < FLAGS_repeat; ++i) {
1325  // Random transducers
1326  VectorFst<Arc> T1;
1327  VectorFst<Arc> T2;
1328  VectorFst<Arc> T3;
1329  MakeRandFst(&T1);
1330  MakeRandFst(&T2);
1331  MakeRandFst(&T3);
1332  weighted_tester_->Test(T1, T2, T3);
1333 
1334  VectorFst<Arc> A1(T1);
1335  VectorFst<Arc> A2(T2);
1336  VectorFst<Arc> A3(T3);
1337  Project(&A1, PROJECT_OUTPUT);
1338  Project(&A2, PROJECT_INPUT);
1339  Project(&A3, PROJECT_INPUT);
1340  ArcMap(&A1, rm_weight_mapper_);
1341  ArcMap(&A2, rm_weight_mapper_);
1342  ArcMap(&A3, rm_weight_mapper_);
1343  unweighted_tester_->Test(A1, A2, A3);
1344  }
1345  }
1346 
1347  private:
1348  // Generates weights used in testing.
1349  WeightGenerator weight_generator_;
1350 
1351  // FST with no states
1352  VectorFst<Arc> zero_fst_;
1353 
1354  // FST with one state that accepts epsilon.
1355  VectorFst<Arc> one_fst_;
1356 
1357  // FST with one state that accepts all strings.
1358  VectorFst<Arc> univ_fst_;
1359 
1360  // Tests weighted FSTs
1361  WeightedTester<Arc, WeightGenerator> *weighted_tester_;
1362 
1363  // Tests unweighted FSTs
1364  UnweightedTester<Arc> *unweighted_tester_;
1365 
1366  // Mapper to remove weights from an Fst
1367  RmWeightMapper<Arc> rm_weight_mapper_;
1368 
1369  // Maximum number of states in random test Fst.
1370  static const int kNumRandomStates;
1371 
1372  // Maximum number of arcs in random test Fst.
1373  static const int kNumRandomArcs;
1374 
1375  // Number of alternative random labels.
1376  static const int kNumRandomLabels;
1377 
1378  // Probability to force an acyclic Fst
1379  static const float kAcyclicProb;
1380 
1381  // Maximum random path length.
1382  static const int kRandomPathLength;
1383 
1384  // Number of random paths to explore.
1385  static const int kNumRandomPaths;
1386 
1387  AlgoTester(const AlgoTester &) = delete;
1388  AlgoTester &operator=(const AlgoTester &) = delete;
1389 };
1390 
1391 template <class A, class G>
1392 const int AlgoTester<A, G>::kNumRandomStates = 10;
1393 
1394 template <class A, class G>
1395 const int AlgoTester<A, G>::kNumRandomArcs = 25;
1396 
1397 template <class A, class G>
1399 
1400 template <class A, class G>
1401 const float AlgoTester<A, G>::kAcyclicProb = .25;
1402 
1403 template <class A, class G>
1405 
1406 template <class A, class G>
1407 const int AlgoTester<A, G>::kNumRandomPaths = 100;
1408 
1409 } // namespace fst
1410 
1411 #endif // FST_TEST_ALGO_TEST_H_
MapSymbolsAction
Definition: arc-map.h:39
constexpr uint64 kNoEpsilons
Definition: properties.h:62
void ArcMap(MutableFst< A > *fst, C *mapper)
Definition: arc-map.h:94
void AddArc(StateId s, const Arc &arc) override
Definition: mutable-fst.h:303
Arc::Weight Weight
Definition: algo_test.h:77
void SetStart(StateId s) override
Definition: mutable-fst.h:280
void RmEpsilon(MutableFst< Arc > *fst, std::vector< typename Arc::Weight > *distance, const RmEpsilonOptions< Arc, Queue > &opts)
Definition: rmepsilon.h:192
void Invert(const Fst< Arc > &ifst, MutableFst< Arc > *ofst)
Definition: invert.h:54
W Weight
Definition: arc.h:30
int Label
Definition: arc.h:31
constexpr uint64 kNotOLabelSorted
Definition: properties.h:82
uint64_t uint64
Definition: types.h:32
void Encode(MutableFst< Arc > *fst, EncodeMapper< Arc > *mapper)
Definition: encode.h:419
void SetFinal(StateId s, Weight weight) override
Definition: mutable-fst.h:285
void Closure(MutableFst< Arc > *fst, ClosureType closure_type)
Definition: closure.h:32
static void Relabel(MutableFst< Arc > *fst, const LFST &mfst, bool relabel_input)
Arc::StateId StateId
Definition: algo_test.h:76
DECLARE_int32(repeat)
constexpr uint64 kRightSemiring
Definition: weight.h:115
void Determinize(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const DeterminizeOptions< Arc > &opts=DeterminizeOptions< Arc >())
Definition: determinize.h:1061
bool RandEquivalent(const Fst< Arc > &fst1, const Fst< Arc > &fst2, int32 num_paths, float delta, const RandGenOptions< ArcSelector > &opts, bool *error=nullptr)
constexpr uint64 kILabelSorted
Definition: properties.h:75
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:94
#define LOG(type)
Definition: log.h:48
StateId Start() const override
Definition: fst.h:875
UnweightedTester(const Fst< Arc > &zero_fsa, const Fst< Arc > &one_fsa, const Fst< Arc > &univ_fsa)
Definition: algo_test.h:1030
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
bool TopSort(MutableFst< Arc > *fst)
Definition: topsort.h:78
constexpr uint64 kCommutative
Definition: weight.h:120
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
DeterminizeType type
Definition: determinize.h:1026
constexpr uint64 kNotILabelSorted
Definition: properties.h:77
constexpr uint64 kLeftSemiring
Definition: weight.h:112
Arc::StateId StateId
Definition: algo_test.h:1288
constexpr uint64 kFstProperties
Definition: properties.h:301
constexpr int kNoStateId
Definition: fst.h:180
const Arc & Value() const
Definition: fst.h:503
void Relabel(MutableFst< Arc > *fst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &ipairs, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &opairs)
Definition: relabel.h:29
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
virtual uint64 Properties(uint64 mask, bool test) const =0
void Map(MutableFst< A > *fst, C *mapper)
Definition: map.h:17
constexpr uint64 kEpsilons
Definition: properties.h:60
void Difference(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const DifferenceOptions &opts=DifferenceOptions())
Definition: difference.h:151
void MakeRandFst(MutableFst< Arc > *fst)
Definition: algo_test.h:1315
StateId AddState() override
Definition: mutable-fst.h:298
void Test(const Fst< Arc > &A1, const Fst< Arc > &A2, const Fst< Arc > &A3)
Definition: algo_test.h:1016
MapFinalAction
Definition: arc-map.h:24
int StateId
Definition: arc.h:32
void RandGen(const Fst< FromArc > &ifst, MutableFst< ToArc > *ofst, const RandGenOptions< Selector > &opts)
Definition: randgen.h:721
MapSymbolsAction OutputSymbolsAction() const
Definition: algo_test.h:43
void Union(RationalFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: union.h:87
AlgoTester(WeightGenerator generator, int seed)
Definition: algo_test.h:1291
void ArcSort(MutableFst< Arc > *fst, Compare comp)
Definition: arcsort.h:87
constexpr uint64 kSemiring
Definition: weight.h:117
Arc::Label Label
Definition: algo_test.h:75
void Compose(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const ComposeOptions &opts=ComposeOptions())
Definition: compose.h:980
constexpr uint64 kOLabelSorted
Definition: properties.h:80
constexpr uint64 kIEpsilons
Definition: properties.h:65
constexpr uint64 kIdempotent
Definition: weight.h:123
StateId NumStates() const override
Definition: expanded-fst.h:119
MapFinalAction FinalAction() const
Definition: algo_test.h:39
void LookAheadCompose(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst)
Definition: algo_test.h:48
constexpr uint64 kIDeterministic
Definition: properties.h:50
A operator()(const A &arc) const
Definition: algo_test.h:25
#define VLOG(level)
Definition: log.h:49
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
WeightedTester(time_t seed, const Fst< Arc > &zero_fst, const Fst< Arc > &one_fst, const Fst< Arc > &univ_fst, WeightGenerator *weight_generator)
Definition: algo_test.h:79
bool Done() const
Definition: fst.h:499
constexpr uint64 kAcceptor
Definition: properties.h:45
void Test(const Fst< Arc > &T1, const Fst< Arc > &T2, const Fst< Arc > &T3)
Definition: algo_test.h:87
void Prune(MutableFst< Arc > *fst, const PruneOptions< Arc, ArcFilter > &opts=PruneOptions< Arc, ArcFilter >())
Definition: prune.h:99
void ShortestPath(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, MutableFst< Arc > *ofst, const PdtShortestPathOptions< Arc, Queue > &opts)
MapSymbolsAction InputSymbolsAction() const
Definition: algo_test.h:41
constexpr uint64 kNoOEpsilons
Definition: properties.h:72
void Concat(MutableFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: concat.h:32
void Project(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, ProjectType project_type)
Definition: project.h:65
bool Verify(const Fst< Arc > &fst, bool allow_negative_labels=false)
Definition: verify.h:19
UnweightedTester(const Fst< Arc > &zero_fsa, const Fst< Arc > &one_fsa, const Fst< Arc > &univ_fsa)
Definition: algo_test.h:1013
uint32_t uint32
Definition: types.h:31
void Minimize(MutableFst< Arc > *fst, MutableFst< Arc > *sfst=nullptr, float delta=kShortestDelta, bool allow_nondet=false)
Definition: minimize.h:495
Arc::Weight Weight
Definition: algo_test.h:1289
constexpr uint64 kNotAcceptor
Definition: properties.h:47
constexpr uint64 kAcyclic
Definition: properties.h:92
#define CHECK_EQ(x, y)
Definition: log.h:62
void Test(const Fst< Arc > &A1, const Fst< Arc > &A2, const Fst< Arc > &A3)
Definition: algo_test.h:1034
constexpr uint64 kPath
Definition: weight.h:126
static const string & Type()
Definition: arc.h:48
constexpr bool ApproxEqual(const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2, float delta=kDelta)
Definition: float-weight.h:140
bool Equivalent(const Fst< Arc > &fst1, const Fst< Arc > &fst2, float delta=kDelta, bool *error=nullptr)
Definition: equivalent.h:114
constexpr uint32 kPushWeights
Definition: push.h:93
Arc::Label Label
Definition: algo_test.h:1287
uint64 Properties(uint64 props) const
Definition: algo_test.h:29
void ShortestDistance(const Fst< Arc > &fst, std::vector< typename Arc::Weight > *distance, const ShortestDistanceOptions< Arc, Queue, ArcFilter > &opts)
#define CHECK(x)
Definition: log.h:61
uint64 Properties(uint64 mask, bool test) const override
Definition: fst.h:889
constexpr float kDelta
Definition: weight.h:109
void Disambiguate(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const DisambiguateOptions< Arc > &opts=DisambiguateOptions< Arc >())
Definition: disambiguate.h:555
constexpr uint64 kOEpsilons
Definition: properties.h:70
void Decode(MutableFst< Arc > *fst, const EncodeMapper< Arc > &mapper)
Definition: encode.h:426
void Reweight(MutableFst< Arc > *fst, const std::vector< typename Arc::Weight > &potential, ReweightType type)
Definition: reweight.h:28
constexpr uint32 kPushLabels
Definition: push.h:94
constexpr uint64 kNoIEpsilons
Definition: properties.h:67
void Next()
Definition: fst.h:507