FST  openfst-1.7.2
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  ComposeFst<Arc> C5(
532  S1, S2, ComposeFstOptions<Arc, M, NoMatchComposeFilter<M>>());
533  CHECK(Equiv(C1, C5));
534  }
535 
536  if (S1.Properties(kNoOEpsilons, false) &&
537  S2.Properties(kNoIEpsilons, false)) {
538  ComposeFst<Arc> C6(S1, S2,
540  CHECK(Equiv(C1, C6));
541  }
542  }
543 
544  {
545  VLOG(1) << "Check look-ahead filters lead to equivalent results.";
546  VectorFst<Arc> C1, C2;
547  Compose(S1, S2, &C1);
548  LookAheadCompose(S1, S2, &C2);
549  CHECK(Equiv(C1, C2));
550  }
551  }
552 
553  // Tests sorting operations
554  void TestSort(const Fst<Arc> &T) {
555  ILabelCompare<Arc> icomp;
556  OLabelCompare<Arc> ocomp;
557 
558  {
559  VLOG(1) << "Check arc sorted Fst is equivalent to its input.";
560  VectorFst<Arc> S1(T);
561  ArcSort(&S1, icomp);
562  CHECK(Equiv(T, S1));
563  }
564 
565  {
566  VLOG(1) << "Check destructive and delayed arcsort are equivalent.";
567  VectorFst<Arc> S1(T);
568  ArcSort(&S1, icomp);
570  CHECK(Equiv(S1, S2));
571  }
572 
573  {
574  VLOG(1) << "Check ilabel sorting vs. olabel sorting with inversions.";
575  VectorFst<Arc> S1(T);
576  VectorFst<Arc> S2(T);
577  ArcSort(&S1, icomp);
578  Invert(&S2);
579  ArcSort(&S2, ocomp);
580  Invert(&S2);
581  CHECK(Equiv(S1, S2));
582  }
583 
584  {
585  VLOG(1) << "Check topologically sorted Fst is equivalent to its input.";
586  VectorFst<Arc> S1(T);
587  TopSort(&S1);
588  CHECK(Equiv(T, S1));
589  }
590 
591  {
592  VLOG(1) << "Check reverse(reverse(T)) = T";
593  for (int i = 0; i < 2; ++i) {
595  VectorFst<Arc> R2;
596  bool require_superinitial = i == 1;
597  Reverse(T, &R1, require_superinitial);
598  Reverse(R1, &R2, require_superinitial);
599  CHECK(Equiv(T, R2));
600  }
601  }
602  }
603 
604  // Tests optimization operations
605  void TestOptimize(const Fst<Arc> &T) {
606  uint64 tprops = T.Properties(kFstProperties, true);
607  uint64 wprops = Weight::Properties();
608 
609  VectorFst<Arc> A(T);
610  Project(&A, PROJECT_INPUT);
611  {
612  VLOG(1) << "Check connected FST is equivalent to its input.";
613  VectorFst<Arc> C1(T);
614  Connect(&C1);
615  CHECK(Equiv(T, C1));
616  }
617 
618  if ((wprops & kSemiring) == kSemiring &&
619  (tprops & kAcyclic || wprops & kIdempotent)) {
620  VLOG(1) << "Check epsilon-removed FST is equivalent to its input.";
621  VectorFst<Arc> R1(T);
622  RmEpsilon(&R1);
623  CHECK(Equiv(T, R1));
624 
625  VLOG(1) << "Check destructive and delayed epsilon removal"
626  << "are equivalent.";
627  RmEpsilonFst<Arc> R2(T);
628  CHECK(Equiv(R1, R2));
629 
630  VLOG(1) << "Check an FST with a large proportion"
631  << " of epsilon transitions:";
632  // Maps all transitions of T to epsilon-transitions and append
633  // a non-epsilon transition.
634  VectorFst<Arc> U;
635  ArcMap(T, &U, EpsMapper<Arc>());
636  VectorFst<Arc> V;
637  V.SetStart(V.AddState());
638  Arc arc(1, 1, Weight::One(), V.AddState());
639  V.AddArc(V.Start(), arc);
640  V.SetFinal(arc.nextstate, Weight::One());
641  Concat(&U, V);
642  // Check that epsilon-removal preserves the shortest-distance
643  // from the initial state to the final states.
644  std::vector<Weight> d;
645  ShortestDistance(U, &d, true);
646  Weight w = U.Start() < d.size() ? d[U.Start()] : Weight::Zero();
647  VectorFst<Arc> U1(U);
648  RmEpsilon(&U1);
649  ShortestDistance(U1, &d, true);
650  Weight w1 = U1.Start() < d.size() ? d[U1.Start()] : Weight::Zero();
651  CHECK(ApproxEqual(w, w1, kTestDelta));
652  RmEpsilonFst<Arc> U2(U);
653  ShortestDistance(U2, &d, true);
654  Weight w2 = U2.Start() < d.size() ? d[U2.Start()] : Weight::Zero();
655  CHECK(ApproxEqual(w, w2, kTestDelta));
656  }
657 
658  if ((wprops & kSemiring) == kSemiring && tprops & kAcyclic) {
659  VLOG(1) << "Check determinized FSA is equivalent to its input.";
660  DeterminizeFst<Arc> D(A);
661  CHECK(Equiv(A, D));
662 
663  {
664  VLOG(1) << "Check determinized FST is equivalent to its input.";
667  DeterminizeFst<Arc> DT(T, opts);
668  CHECK(Equiv(T, DT));
669  }
670 
671  if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
672  VLOG(1) << "Check pruning in determinization";
673  VectorFst<Arc> P;
674  Weight threshold = (*weight_generator_)();
676  opts.weight_threshold = threshold;
677  Determinize(A, &P, opts);
678  CHECK(P.Properties(kIDeterministic, true));
679  CHECK(PruneEquiv(A, P, threshold));
680  }
681 
682  if ((wprops & kPath) == kPath) {
683  VLOG(1) << "Check min-determinization";
684 
685  // Ensures no input epsilons
686  VectorFst<Arc> R(T);
687  std::vector<std::pair<Label, Label>> ipairs, opairs;
688  ipairs.push_back(std::pair<Label, Label>(0, 1));
689  Relabel(&R, ipairs, opairs);
690 
691  VectorFst<Arc> M;
694  Determinize(R, &M, opts);
695  CHECK(M.Properties(kIDeterministic, true));
696  CHECK(MinRelated(M, R));
697  }
698 
699  int n;
700  {
701  VLOG(1) << "Check size(min(det(A))) <= size(det(A))"
702  << " and min(det(A)) equiv det(A)";
703  VectorFst<Arc> M(D);
704  n = M.NumStates();
705  Minimize(&M, static_cast<MutableFst<Arc> *>(nullptr), kDelta);
706  CHECK(Equiv(D, M));
707  CHECK(M.NumStates() <= n);
708  n = M.NumStates();
709  }
710 
711  if (n && (wprops & kIdempotent) == kIdempotent &&
712  A.Properties(kNoEpsilons, true)) {
713  VLOG(1) << "Check that Revuz's algorithm leads to the"
714  << " same number of states as Brozozowski's algorithm";
715 
716  // Skip test if A is the empty machine or contains epsilons or
717  // if the semiring is not idempotent (to avoid floating point
718  // errors)
719  VectorFst<Arc> R;
720  Reverse(A, &R);
721  RmEpsilon(&R);
722  DeterminizeFst<Arc> DR(R);
723  VectorFst<Arc> RD;
724  Reverse(DR, &RD);
725  DeterminizeFst<Arc> DRD(RD);
726  VectorFst<Arc> M(DRD);
727  CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition
728  // to the initial state
729  }
730  }
731 
732  if ((wprops & kSemiring) == kSemiring && tprops & kAcyclic) {
733  VLOG(1) << "Check disambiguated FSA is equivalent to its input.";
734  VectorFst<Arc> R(A), D;
735  RmEpsilon(&R);
736  Disambiguate(R, &D);
737  CHECK(Equiv(R, D));
738  VLOG(1) << "Check disambiguated FSA is unambiguous";
739  CHECK(Unambiguous(D));
740 
741  /* TODO(riley): find out why this fails
742  if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
743  VLOG(1) << "Check pruning in disambiguation";
744  VectorFst<Arc> P;
745  Weight threshold = (*weight_generator_)();
746  DisambiguateOptions<Arc> opts;
747  opts.weight_threshold = threshold;
748  Disambiguate(R, &P, opts);
749  CHECK(Unambiguous(P));
750  CHECK(PruneEquiv(A, P, threshold));
751  }
752  */
753  }
754 
755  if (Arc::Type() == LogArc::Type() || Arc::Type() == StdArc::Type()) {
756  VLOG(1) << "Check reweight(T) equiv T";
757  std::vector<Weight> potential;
758  VectorFst<Arc> RI(T);
759  VectorFst<Arc> RF(T);
760  while (potential.size() < RI.NumStates())
761  potential.push_back((*weight_generator_)());
762 
763  Reweight(&RI, potential, REWEIGHT_TO_INITIAL);
764  CHECK(Equiv(T, RI));
765 
766  Reweight(&RF, potential, REWEIGHT_TO_FINAL);
767  CHECK(Equiv(T, RF));
768  }
769 
770  if ((wprops & kIdempotent) || (tprops & kAcyclic)) {
771  VLOG(1) << "Check pushed FST is equivalent to input FST.";
772  // Pushing towards the final state.
773  if (wprops & kRightSemiring) {
774  VectorFst<Arc> P1;
775  Push<Arc, REWEIGHT_TO_FINAL>(T, &P1, kPushLabels);
776  CHECK(Equiv(T, P1));
777 
778  VectorFst<Arc> P2;
779  Push<Arc, REWEIGHT_TO_FINAL>(T, &P2, kPushWeights);
780  CHECK(Equiv(T, P2));
781 
782  VectorFst<Arc> P3;
783  Push<Arc, REWEIGHT_TO_FINAL>(T, &P3, kPushLabels | kPushWeights);
784  CHECK(Equiv(T, P3));
785  }
786 
787  // Pushing towards the initial state.
788  if (wprops & kLeftSemiring) {
789  VectorFst<Arc> P1;
790  Push<Arc, REWEIGHT_TO_INITIAL>(T, &P1, kPushLabels);
791  CHECK(Equiv(T, P1));
792 
793  VectorFst<Arc> P2;
794  Push<Arc, REWEIGHT_TO_INITIAL>(T, &P2, kPushWeights);
795  CHECK(Equiv(T, P2));
796  VectorFst<Arc> P3;
797  Push<Arc, REWEIGHT_TO_INITIAL>(T, &P3, kPushLabels | kPushWeights);
798  CHECK(Equiv(T, P3));
799  }
800  }
801 
802  if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
803  VLOG(1) << "Check pruning algorithm";
804  {
805  VLOG(1) << "Check equiv. of constructive and destructive algorithms";
806  Weight thresold = (*weight_generator_)();
807  VectorFst<Arc> P1(T);
808  Prune(&P1, thresold);
809  VectorFst<Arc> P2;
810  Prune(T, &P2, thresold);
811  CHECK(Equiv(P1, P2));
812  }
813 
814  {
815  VLOG(1) << "Check prune(reverse) equiv reverse(prune)";
816  Weight thresold = (*weight_generator_)();
818  VectorFst<Arc> P1(T);
819  VectorFst<Arc> P2;
820  Prune(&P1, thresold);
821  Reverse(T, &R);
822  Prune(&R, thresold.Reverse());
823  Reverse(R, &P2);
824  CHECK(Equiv(P1, P2));
825  }
826  {
827  VLOG(1) << "Check: ShortestDistance(A - prune(A))"
828  << " > ShortestDistance(A) times Threshold";
829  Weight threshold = (*weight_generator_)();
830  VectorFst<Arc> P;
831  Prune(A, &P, threshold);
832  CHECK(PruneEquiv(A, P, threshold));
833  }
834  }
835  if (tprops & kAcyclic) {
836  VLOG(1) << "Check synchronize(T) equiv T";
837  SynchronizeFst<Arc> S(T);
838  CHECK(Equiv(T, S));
839  }
840  }
841 
842  // Tests search operations
843  void TestSearch(const Fst<Arc> &T) {
844  uint64 wprops = Weight::Properties();
845 
846  VectorFst<Arc> A(T);
847  Project(&A, PROJECT_INPUT);
848 
849  if ((wprops & (kPath | kRightSemiring)) == (kPath | kRightSemiring)) {
850  VLOG(1) << "Check 1-best weight.";
851  VectorFst<Arc> path;
852  ShortestPath(T, &path);
853  Weight tsum = ShortestDistance(T);
854  Weight psum = ShortestDistance(path);
855  CHECK(ApproxEqual(tsum, psum, kTestDelta));
856  }
857 
858  if ((wprops & (kPath | kSemiring)) == (kPath | kSemiring)) {
859  VLOG(1) << "Check n-best weights";
860  VectorFst<Arc> R(A);
861  RmEpsilon(&R, /*connect=*/ true, Arc::Weight::Zero(), kNoStateId,
862  kDelta);
863  int nshortest = rand() % kNumRandomShortestPaths + 2;
864  VectorFst<Arc> paths;
865  ShortestPath(R, &paths, nshortest, /*unique=*/ true,
866  /*first_path=*/ false, Weight::Zero(), kNumShortestStates,
867  kDelta);
868  std::vector<Weight> distance;
869  ShortestDistance(paths, &distance, true, kDelta);
870  StateId pstart = paths.Start();
871  if (pstart != kNoStateId) {
872  ArcIterator<Fst<Arc>> piter(paths, pstart);
873  for (; !piter.Done(); piter.Next()) {
874  StateId s = piter.Value().nextstate;
875  Weight nsum = s < distance.size()
876  ? Times(piter.Value().weight, distance[s])
877  : Weight::Zero();
878  VectorFst<Arc> path;
879  ShortestPath(R, &path, 1, false, false, Weight::Zero(), kNoStateId,
880  kDelta);
881  Weight dsum = ShortestDistance(path, kDelta);
882  CHECK(ApproxEqual(nsum, dsum, kTestDelta));
883  ArcMap(&path, RmWeightMapper<Arc>());
884  VectorFst<Arc> S;
885  Difference(R, path, &S);
886  R = S;
887  }
888  }
889  }
890  }
891 
892  // Tests if two FSTS are equivalent by checking if random
893  // strings from one FST are transduced the same by both FSTs.
894  template <class A>
895  bool Equiv(const Fst<A> &fst1, const Fst<A> &fst2) {
896  VLOG(1) << "Check FSTs for sanity (including property bits).";
897  CHECK(Verify(fst1));
898  CHECK(Verify(fst2));
899 
900  // Ensures seed used once per instantiation.
901  static UniformArcSelector<A> uniform_selector(seed_);
902  RandGenOptions<UniformArcSelector<A>> opts(uniform_selector,
903  kRandomPathLength);
904  return RandEquivalent(fst1, fst2, kNumRandomPaths, kTestDelta, opts);
905  }
906 
907  // Tests FSA is unambiguous
908  bool Unambiguous(const Fst<Arc> &fst) {
909  VectorFst<StdArc> sfst, dfst;
910  VectorFst<LogArc> lfst1, lfst2;
911  Map(fst, &sfst, RmWeightMapper<Arc, StdArc>());
912  Determinize(sfst, &dfst);
913  Map(fst, &lfst1, RmWeightMapper<Arc, LogArc>());
914  Map(dfst, &lfst2, RmWeightMapper<StdArc, LogArc>());
915  return Equiv(lfst1, lfst2);
916  }
917 
918  // Ensures input-epsilon free transducers fst1 and fst2 have the
919  // same domain and that for each string pair '(is, os)' in fst1,
920  // '(is, os)' is the minimum weight match to 'is' in fst2.
921  template <class A>
922  bool MinRelated(const Fst<A> &fst1, const Fst<A> &fst2) {
923  // Same domain
924  VectorFst<Arc> P1(fst1), P2(fst2);
925  Project(&P1, PROJECT_INPUT);
926  Project(&P2, PROJECT_INPUT);
927  if (!Equiv(P1, P2)) {
928  LOG(ERROR) << "Inputs not equivalent";
929  return false;
930  }
931 
932  // Ensures seed used once per instantiation.
933  static UniformArcSelector<A> uniform_selector(seed_);
934  RandGenOptions<UniformArcSelector<A>> opts(uniform_selector,
935  kRandomPathLength);
936 
937  VectorFst<Arc> path, paths1, paths2;
938  for (ssize_t n = 0; n < kNumRandomPaths; ++n) {
939  RandGen(fst1, &path, opts);
940  Invert(&path);
941  Map(&path, RmWeightMapper<Arc>());
942  Compose(path, fst2, &paths1);
943  Weight sum1 = ShortestDistance(paths1);
944  Compose(paths1, path, &paths2);
945  Weight sum2 = ShortestDistance(paths2);
946  if (!ApproxEqual(Plus(sum1, sum2), sum2, kTestDelta)) {
947  LOG(ERROR) << "Sums not equivalent: " << sum1 << " " << sum2;
948  return false;
949  }
950  }
951  return true;
952  }
953 
954  // Tests ShortestDistance(A - P) >=
955  // ShortestDistance(A) times Threshold.
956  template <class A>
957  bool PruneEquiv(const Fst<A> &fst, const Fst<A> &pfst, Weight threshold) {
958  VLOG(1) << "Check FSTs for sanity (including property bits).";
959  CHECK(Verify(fst));
960  CHECK(Verify(pfst));
961 
963  ArcMapFst<Arc, Arc, RmWeightMapper<Arc>>(
964  pfst, RmWeightMapper<Arc>()))));
965  Weight sum1 = Times(ShortestDistance(fst), threshold);
966  Weight sum2 = ShortestDistance(D);
967  return ApproxEqual(Plus(sum1, sum2), sum1, kTestDelta);
968  }
969 
970  // Random seed.
971  int seed_;
972  // FST with no states
973  VectorFst<Arc> zero_fst_;
974  // FST with one state that accepts epsilon.
975  VectorFst<Arc> one_fst_;
976  // FST with one state that accepts all strings.
977  VectorFst<Arc> univ_fst_;
978  // Generates weights used in testing.
979  WeightGenerator *weight_generator_;
980  // Maximum random path length.
981  static const int kRandomPathLength;
982  // Number of random paths to explore.
983  static const int kNumRandomPaths;
984  // Maximum number of nshortest paths.
985  static const int kNumRandomShortestPaths;
986  // Maximum number of nshortest states.
987  static const int kNumShortestStates;
988  // Delta for equivalence tests.
989  static const float kTestDelta;
990 
991  WeightedTester(const WeightedTester &) = delete;
992  WeightedTester &operator=(const WeightedTester &) = delete;
993 };
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>
1006 
1007 template <class A, class WG>
1008 const float WeightedTester<A, WG>::kTestDelta = .05;
1009 
1010 // This class tests a variety of identities and properties that must
1011 // hold for various algorithms on unweighted FSAs and that are not tested
1012 // by WeightedTester. Only the specialization does anything interesting.
1013 template <class Arc>
1015  public:
1016  UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
1017  const Fst<Arc> &univ_fsa) {}
1018 
1019  void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {}
1020 };
1021 
1022 // Specialization for StdArc. This should work for any commutative,
1023 // idempotent semiring when restricted to the unweighted case
1024 // (being isomorphic to the boolean semiring).
1025 template <>
1027  public:
1028  typedef StdArc Arc;
1032 
1033  UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
1034  const Fst<Arc> &univ_fsa)
1035  : zero_fsa_(zero_fsa), one_fsa_(one_fsa), univ_fsa_(univ_fsa) {}
1036 
1037  void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {
1038  TestRational(A1, A2, A3);
1039  TestIntersect(A1, A2, A3);
1040  TestOptimize(A1);
1041  }
1042 
1043  private:
1044  // Tests rational operations with identities
1045  void TestRational(const Fst<Arc> &A1, const Fst<Arc> &A2,
1046  const Fst<Arc> &A3) {
1047  {
1048  VLOG(1) << "Check the union contains its arguments (destructive).";
1049  VectorFst<Arc> U(A1);
1050  Union(&U, A2);
1051 
1052  CHECK(Subset(A1, U));
1053  CHECK(Subset(A2, U));
1054  }
1055 
1056  {
1057  VLOG(1) << "Check the union contains its arguments (delayed).";
1058  UnionFst<Arc> U(A1, A2);
1059 
1060  CHECK(Subset(A1, U));
1061  CHECK(Subset(A2, U));
1062  }
1063 
1064  {
1065  VLOG(1) << "Check if A^n c A* (destructive).";
1066  VectorFst<Arc> C(one_fsa_);
1067  int n = rand() % 5;
1068  for (int i = 0; i < n; ++i) Concat(&C, A1);
1069 
1070  VectorFst<Arc> S(A1);
1071  Closure(&S, CLOSURE_STAR);
1072  CHECK(Subset(C, S));
1073  }
1074 
1075  {
1076  VLOG(1) << "Check if A^n c A* (delayed).";
1077  int n = rand() % 5;
1078  Fst<Arc> *C = new VectorFst<Arc>(one_fsa_);
1079  for (int i = 0; i < n; ++i) {
1080  ConcatFst<Arc> *F = new ConcatFst<Arc>(*C, A1);
1081  delete C;
1082  C = F;
1083  }
1085  CHECK(Subset(*C, S));
1086  delete C;
1087  }
1088  }
1089 
1090  // Tests intersect-based operations.
1091  void TestIntersect(const Fst<Arc> &A1, const Fst<Arc> &A2,
1092  const Fst<Arc> &A3) {
1093  VectorFst<Arc> S1(A1);
1094  VectorFst<Arc> S2(A2);
1095  VectorFst<Arc> S3(A3);
1096 
1097  ILabelCompare<Arc> comp;
1098 
1099  ArcSort(&S1, comp);
1100  ArcSort(&S2, comp);
1101  ArcSort(&S3, comp);
1102 
1103  {
1104  VLOG(1) << "Check the intersection is contained in its arguments.";
1105  IntersectFst<Arc> I1(S1, S2);
1106  CHECK(Subset(I1, S1));
1107  CHECK(Subset(I1, S2));
1108  }
1109 
1110  {
1111  VLOG(1) << "Check union distributes over intersection.";
1112  IntersectFst<Arc> I1(S1, S2);
1113  UnionFst<Arc> U1(I1, S3);
1114 
1115  UnionFst<Arc> U2(S1, S3);
1116  UnionFst<Arc> U3(S2, S3);
1117  ArcSortFst<Arc, ILabelCompare<Arc>> S4(U3, comp);
1118  IntersectFst<Arc> I2(U2, S4);
1119 
1120  CHECK(Equiv(U1, I2));
1121  }
1122 
1123  VectorFst<Arc> C1;
1124  VectorFst<Arc> C2;
1125  Complement(S1, &C1);
1126  Complement(S2, &C2);
1127  ArcSort(&C1, comp);
1128  ArcSort(&C2, comp);
1129 
1130  {
1131  VLOG(1) << "Check S U S' = Sigma*";
1132  UnionFst<Arc> U(S1, C1);
1133  CHECK(Equiv(U, univ_fsa_));
1134  }
1135 
1136  {
1137  VLOG(1) << "Check S n S' = {}";
1138  IntersectFst<Arc> I(S1, C1);
1139  CHECK(Equiv(I, zero_fsa_));
1140  }
1141 
1142  {
1143  VLOG(1) << "Check (S1' U S2') == (S1 n S2)'";
1144  UnionFst<Arc> U(C1, C2);
1145 
1146  IntersectFst<Arc> I(S1, S2);
1147  VectorFst<Arc> C3;
1148  Complement(I, &C3);
1149  CHECK(Equiv(U, C3));
1150  }
1151 
1152  {
1153  VLOG(1) << "Check (S1' n S2') == (S1 U S2)'";
1154  IntersectFst<Arc> I(C1, C2);
1155 
1156  UnionFst<Arc> U(S1, S2);
1157  VectorFst<Arc> C3;
1158  Complement(U, &C3);
1159  CHECK(Equiv(I, C3));
1160  }
1161  }
1162 
1163  // Tests optimization operations
1164  void TestOptimize(const Fst<Arc> &A) {
1165  {
1166  VLOG(1) << "Check determinized FSA is equivalent to its input.";
1167  DeterminizeFst<Arc> D(A);
1168  CHECK(Equiv(A, D));
1169  }
1170 
1171  {
1172  VLOG(1) << "Check disambiguated FSA is equivalent to its input.";
1173  VectorFst<Arc> R(A), D;
1174  RmEpsilon(&R);
1175 
1176  Disambiguate(R, &D);
1177  CHECK(Equiv(R, D));
1178  }
1179 
1180  {
1181  VLOG(1) << "Check minimized FSA is equivalent to its input.";
1182  int n;
1183  {
1184  RmEpsilonFst<Arc> R(A);
1185  DeterminizeFst<Arc> D(R);
1186  VectorFst<Arc> M(D);
1187  Minimize(&M, static_cast<MutableFst<Arc> *>(nullptr), kDelta);
1188  CHECK(Equiv(A, M));
1189  n = M.NumStates();
1190  }
1191 
1192  if (n) { // Skip test if A is the empty machine
1193  VLOG(1) << "Check that Hopcroft's and Revuz's algorithms lead to the"
1194  << " same number of states as Brozozowski's algorithm";
1195  VectorFst<Arc> R;
1196  Reverse(A, &R);
1197  RmEpsilon(&R);
1198  DeterminizeFst<Arc> DR(R);
1199  VectorFst<Arc> RD;
1200  Reverse(DR, &RD);
1201  DeterminizeFst<Arc> DRD(RD);
1202  VectorFst<Arc> M(DRD);
1203  CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition
1204  // to the initial state
1205  }
1206  }
1207  }
1208 
1209  // Tests if two FSAS are equivalent.
1210  bool Equiv(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
1211  VLOG(1) << "Check FSAs for sanity (including property bits).";
1212  CHECK(Verify(fsa1));
1213  CHECK(Verify(fsa2));
1214 
1215  VectorFst<Arc> vfsa1(fsa1);
1216  VectorFst<Arc> vfsa2(fsa2);
1217  RmEpsilon(&vfsa1);
1218  RmEpsilon(&vfsa2);
1219  DeterminizeFst<Arc> dfa1(vfsa1);
1220  DeterminizeFst<Arc> dfa2(vfsa2);
1221 
1222  // Test equivalence using union-find algorithm
1223  bool equiv1 = Equivalent(dfa1, dfa2);
1224 
1225  // Test equivalence by checking if (S1 - S2) U (S2 - S1) is empty
1226  ILabelCompare<Arc> comp;
1227  VectorFst<Arc> sdfa1(dfa1);
1228  ArcSort(&sdfa1, comp);
1229  VectorFst<Arc> sdfa2(dfa2);
1230  ArcSort(&sdfa2, comp);
1231 
1232  DifferenceFst<Arc> dfsa1(sdfa1, sdfa2);
1233  DifferenceFst<Arc> dfsa2(sdfa2, sdfa1);
1234 
1235  VectorFst<Arc> ufsa(dfsa1);
1236  Union(&ufsa, dfsa2);
1237  Connect(&ufsa);
1238  bool equiv2 = ufsa.NumStates() == 0;
1239 
1240  // Check two equivalence tests match
1241  CHECK((equiv1 && equiv2) || (!equiv1 && !equiv2));
1242 
1243  return equiv1;
1244  }
1245 
1246  // Tests if FSA1 is a subset of FSA2 (disregarding weights).
1247  bool Subset(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
1248  VLOG(1) << "Check FSAs (incl. property bits) for sanity";
1249  CHECK(Verify(fsa1));
1250  CHECK(Verify(fsa2));
1251 
1252  VectorFst<StdArc> vfsa1;
1253  VectorFst<StdArc> vfsa2;
1254  RmEpsilon(&vfsa1);
1255  RmEpsilon(&vfsa2);
1256  ILabelCompare<StdArc> comp;
1257  ArcSort(&vfsa1, comp);
1258  ArcSort(&vfsa2, comp);
1259  IntersectFst<StdArc> ifsa(vfsa1, vfsa2);
1260  DeterminizeFst<StdArc> dfa1(vfsa1);
1261  DeterminizeFst<StdArc> dfa2(ifsa);
1262  return Equivalent(dfa1, dfa2);
1263  }
1264 
1265  // Returns complement Fsa
1266  void Complement(const Fst<Arc> &ifsa, MutableFst<Arc> *ofsa) {
1267  RmEpsilonFst<Arc> rfsa(ifsa);
1268  DeterminizeFst<Arc> dfa(rfsa);
1269  DifferenceFst<Arc> cfsa(univ_fsa_, dfa);
1270  *ofsa = cfsa;
1271  }
1272 
1273  // FSA with no states
1274  VectorFst<Arc> zero_fsa_;
1275 
1276  // FSA with one state that accepts epsilon.
1277  VectorFst<Arc> one_fsa_;
1278 
1279  // FSA with one state that accepts all strings.
1280  VectorFst<Arc> univ_fsa_;
1281 };
1282 
1283 // This class tests a variety of identities and properties that must
1284 // hold for various FST algorithms. It randomly generates FSTs, using
1285 // function object 'weight_generator' to select weights. 'WeightTester'
1286 // and 'UnweightedTester' are then called.
1287 template <class Arc, class WeightGenerator>
1288 class AlgoTester {
1289  public:
1290  typedef typename Arc::Label Label;
1291  typedef typename Arc::StateId StateId;
1292  typedef typename Arc::Weight Weight;
1293 
1294  AlgoTester(WeightGenerator generator, int seed)
1295  : weight_generator_(generator) {
1296  one_fst_.AddState();
1297  one_fst_.SetStart(0);
1298  one_fst_.SetFinal(0, Weight::One());
1299 
1300  univ_fst_.AddState();
1301  univ_fst_.SetStart(0);
1302  univ_fst_.SetFinal(0, Weight::One());
1303  for (int i = 0; i < kNumRandomLabels; ++i)
1304  univ_fst_.AddArc(0, Arc(i, i, Weight::One(), 0));
1305 
1306  weighted_tester_ = new WeightedTester<Arc, WeightGenerator>(
1307  seed, zero_fst_, one_fst_, univ_fst_, &weight_generator_);
1308 
1309  unweighted_tester_ =
1310  new UnweightedTester<Arc>(zero_fst_, one_fst_, univ_fst_);
1311  }
1312 
1314  delete weighted_tester_;
1315  delete unweighted_tester_;
1316  }
1317 
1319  RandFst<Arc, WeightGenerator>(kNumRandomStates, kNumRandomArcs,
1320  kNumRandomLabels, kAcyclicProb,
1321  &weight_generator_, fst);
1322  }
1323 
1324  void Test() {
1325  VLOG(1) << "weight type = " << Weight::Type();
1326 
1327  for (int i = 0; i < FLAGS_repeat; ++i) {
1328  // Random transducers
1329  VectorFst<Arc> T1;
1330  VectorFst<Arc> T2;
1331  VectorFst<Arc> T3;
1332  MakeRandFst(&T1);
1333  MakeRandFst(&T2);
1334  MakeRandFst(&T3);
1335  weighted_tester_->Test(T1, T2, T3);
1336 
1337  VectorFst<Arc> A1(T1);
1338  VectorFst<Arc> A2(T2);
1339  VectorFst<Arc> A3(T3);
1340  Project(&A1, PROJECT_OUTPUT);
1341  Project(&A2, PROJECT_INPUT);
1342  Project(&A3, PROJECT_INPUT);
1343  ArcMap(&A1, rm_weight_mapper_);
1344  ArcMap(&A2, rm_weight_mapper_);
1345  ArcMap(&A3, rm_weight_mapper_);
1346  unweighted_tester_->Test(A1, A2, A3);
1347  }
1348  }
1349 
1350  private:
1351  // Generates weights used in testing.
1352  WeightGenerator weight_generator_;
1353 
1354  // FST with no states
1355  VectorFst<Arc> zero_fst_;
1356 
1357  // FST with one state that accepts epsilon.
1358  VectorFst<Arc> one_fst_;
1359 
1360  // FST with one state that accepts all strings.
1361  VectorFst<Arc> univ_fst_;
1362 
1363  // Tests weighted FSTs
1364  WeightedTester<Arc, WeightGenerator> *weighted_tester_;
1365 
1366  // Tests unweighted FSTs
1367  UnweightedTester<Arc> *unweighted_tester_;
1368 
1369  // Mapper to remove weights from an Fst
1370  RmWeightMapper<Arc> rm_weight_mapper_;
1371 
1372  // Maximum number of states in random test Fst.
1373  static const int kNumRandomStates;
1374 
1375  // Maximum number of arcs in random test Fst.
1376  static const int kNumRandomArcs;
1377 
1378  // Number of alternative random labels.
1379  static const int kNumRandomLabels;
1380 
1381  // Probability to force an acyclic Fst
1382  static const float kAcyclicProb;
1383 
1384  // Maximum random path length.
1385  static const int kRandomPathLength;
1386 
1387  // Number of random paths to explore.
1388  static const int kNumRandomPaths;
1389 
1390  AlgoTester(const AlgoTester &) = delete;
1391  AlgoTester &operator=(const AlgoTester &) = delete;
1392 };
1393 
1394 template <class A, class G>
1395 const int AlgoTester<A, G>::kNumRandomStates = 10;
1396 
1397 template <class A, class G>
1398 const int AlgoTester<A, G>::kNumRandomArcs = 25;
1399 
1400 template <class A, class G>
1402 
1403 template <class A, class G>
1404 const float AlgoTester<A, G>::kAcyclicProb = .25;
1405 
1406 template <class A, class G>
1408 
1409 template <class A, class G>
1410 const int AlgoTester<A, G>::kNumRandomPaths = 100;
1411 
1412 } // namespace fst
1413 
1414 #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:1033
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:1291
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:1318
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:1019
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:730
MapSymbolsAction OutputSymbolsAction() const
Definition: algo_test.h:43
void Union(RationalFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: union.h:85
AlgoTester(WeightGenerator generator, int seed)
Definition: algo_test.h:1294
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:981
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:1016
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:1292
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:1037
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:1290
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