lattice-utils-test.cc
Go to the documentation of this file.
1 // fstext/lattice-utils-test.cc
2 
3 // Copyright 2011 Microsoft Corporation
4 
5 // See ../../COPYING for clarification regarding multiple authors
6 //
7 // Licensed under the Apache License, Version 2.0 (the "License");
8 // you may not use this file except in compliance with the License.
9 // You may obtain a copy of the License at
10 //
11 // http://www.apache.org/licenses/LICENSE-2.0
12 //
13 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
15 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
16 // MERCHANTABLITY OR NON-INFRINGEMENT.
17 // See the Apache 2 License for the specific language governing permissions and
18 // limitations under the License.
19 
20 #include "fstext/lattice-utils.h"
21 #include "fstext/fst-test-utils.h"
22 #include "base/kaldi-math.h"
23 
24 namespace fst {
25 
26 template<class Weight, class Int> void TestConvert(bool invert) {
27  typedef ArcTpl<Weight> Arc;
28  typedef ArcTpl<CompactLatticeWeightTpl<Weight, Int> > CompactArc;
29  for(int i = 0; i < 5; i++) {
30  VectorFst<Arc> *fst = RandFst<Arc>();
31  std::cout << "FST before converting to compact-arc is:\n";
32  {
33  FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true, "\t");
34  fstprinter.Print(&std::cout, "standard output");
35  }
36  VectorFst<CompactArc> ofst;
37  ConvertLattice<Weight, Int>(*fst, &ofst, invert);
38 
39  std::cout << "FST after converting is:\n";
40  {
41  FstPrinter<CompactArc> fstprinter(ofst, NULL, NULL, NULL, false, true, "\t");
42  fstprinter.Print(&std::cout, "standard output");
43  }
44  VectorFst<Arc> origfst;
45  ConvertLattice<Weight, Int>(ofst, &origfst, invert);
46  std::cout << "FST after back conversion is:\n";
47  {
48  FstPrinter<Arc> fstprinter(origfst, NULL, NULL, NULL, false, true, "\t");
49  fstprinter.Print(&std::cout, "standard output");
50  }
51 
52  assert(RandEquivalent(*fst, origfst, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
53  delete fst;
54  }
55 }
56 
57 // This tests the ShortestPath algorithm, and by proxy, tests the
58 // NaturalLess template etc.
59 
60 template<class Weight, class Int> void TestShortestPath() {
61  for (int p = 0; p < 10; p++) {
62  typedef ArcTpl<Weight> Arc;
63  typedef ArcTpl<CompactLatticeWeightTpl<Weight, Int> > CompactArc;
64  for(int i = 0; i < 5; i++) {
65  VectorFst<Arc> *fst = RandPairFst<Arc>();
66  std::cout << "Testing shortest path\n";
67  std::cout << "FST before converting to compact-arc is:\n";
68  {
69  FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true, "\t");
70  fstprinter.Print(&std::cout, "standard output");
71  }
72  VectorFst<CompactArc> cfst;
73  ConvertLattice<Weight, Int>(*fst, &cfst, false); // invert == false
74 
75 
76  {
77  VectorFst<Arc> nbest_fst_1;
78  ShortestPath(*fst, &nbest_fst_1, 1);
79  VectorFst<Arc> nbest_fst_2;
80  ShortestPath(*fst, &nbest_fst_2, 3);
81  VectorFst<Arc> nbest_fst_1b;
82  ShortestPath(nbest_fst_2, &nbest_fst_1b, 1);
83 
84 
85  assert(ApproxEqual(ShortestDistance(nbest_fst_1),
86  ShortestDistance(nbest_fst_1b)));
87 
88  // since semiring is idempotent, this should succeed too.
89  assert(ApproxEqual(ShortestDistance(*fst),
90  ShortestDistance(nbest_fst_1b)));
91  }
92  {
93  VectorFst<CompactArc> nbest_fst_1;
94  ShortestPath(cfst, &nbest_fst_1, 1);
95  VectorFst<CompactArc> nbest_fst_2;
96  ShortestPath(cfst, &nbest_fst_2, 3);
97  VectorFst<CompactArc> nbest_fst_1b;
98  ShortestPath(nbest_fst_2, &nbest_fst_1b, 1);
99 
100  assert(ApproxEqual(ShortestDistance(nbest_fst_1),
101  ShortestDistance(nbest_fst_1b)));
102  // since semiring is idempotent, this should succeed too.
103  assert(ApproxEqual(ShortestDistance(cfst),
104  ShortestDistance(nbest_fst_1b)));
105  }
106 
107  delete fst;
108  }
109  }
110 }
111 
112 
113 
114 template<class Int> void TestConvert2() {
115  typedef ArcTpl<LatticeWeightTpl<float> > ArcF;
116  typedef ArcTpl<LatticeWeightTpl<double> > ArcD;
117  typedef ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<float>, Int> > CArcF;
118  typedef ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<double>, Int> > CArcD;
119 
120  for(int i = 0; i < 2; i++) {
121  {
122  VectorFst<ArcF> *fst1 = RandPairFst<ArcF>();
123  VectorFst<ArcD> fst2;
124  VectorFst<ArcF> fst3;
125  ConvertLattice(*fst1, &fst2);
126  ConvertLattice(fst2, &fst3);
127 
128  assert(RandEquivalent(*fst1, fst3, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
129  delete fst1;
130  }
131 
132  {
133  VectorFst<ArcF> *fst1 = RandPairFst<ArcF>();
134  VectorFst<CArcF> cfst1, cfst3;
135  ConvertLattice(*fst1, &cfst1);
136  VectorFst<CArcD> cfst2;
137  ConvertLattice(cfst1, &cfst2);
138  ConvertLattice(cfst2, &cfst3);
139  assert(RandEquivalent(cfst1, cfst3, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
140  delete fst1;
141  }
142 
143  {
144  VectorFst<ArcF> *fst1 = RandPairFst<ArcF>();
145  VectorFst<CArcD> cfst1, cfst3;
146  ConvertLattice(*fst1, &cfst1);
147  VectorFst<CArcF> cfst2;
148  ConvertLattice(cfst1, &cfst2);
149  ConvertLattice(cfst2, &cfst3);
150  assert(RandEquivalent(cfst1, cfst3, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
151  delete fst1;
152  }
153 
154  {
155  VectorFst<ArcD> *fst1 = RandPairFst<ArcD>();
156  VectorFst<CArcD> cfst1, cfst3;
157  ConvertLattice(*fst1, &cfst1);
158  VectorFst<CArcF> cfst2;
159  ConvertLattice(cfst1, &cfst2);
160  ConvertLattice(cfst2, &cfst3);
161  assert(RandEquivalent(cfst1, cfst3, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
162  delete fst1;
163  }
164 
165  {
166  VectorFst<ArcD> *fst1 = RandPairFst<ArcD>();
167  VectorFst<CArcF> cfst1;
168  ConvertLattice(*fst1, &cfst1);
169  VectorFst<ArcD> fst2;
170  ConvertLattice(cfst1, &fst2);
171  assert(RandEquivalent(*fst1, fst2, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
172  delete fst1;
173  }
174 
175  {
176  VectorFst<ArcF> *fst1 = RandPairFst<ArcF>();
177  VectorFst<CArcD> cfst1;
178  ConvertLattice(*fst1, &cfst1);
179  VectorFst<ArcF> fst2;
180  ConvertLattice(cfst1, &fst2);
181  assert(RandEquivalent(*fst1, fst2, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
182  delete fst1;
183  }
184 
185  {
186  VectorFst<ArcD> *fst1 = RandPairFst<ArcD>();
187  VectorFst<CArcF> cfst1;
188  ConvertLattice(*fst1, &cfst1);
189  VectorFst<ArcD> fst2;
190  ConvertLattice(cfst1, &fst2);
191  assert(RandEquivalent(*fst1, fst2, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
192  delete fst1;
193  }
194  }
195 }
196 
197 
198 // use TestConvertPair when the Weight can be constructed from
199 // a pair of floats.
200 template<class Weight, class Int> void TestConvertPair(bool invert) {
201  typedef ArcTpl<Weight> Arc;
202  typedef ArcTpl<CompactLatticeWeightTpl<Weight, Int> > CompactArc;
203  for(int i = 0; i < 2; i++) {
204  VectorFst<Arc> *fst = RandPairFst<Arc>();
205  /*std::cout << "FST before converting to compact-arc is:\n";
206  {
207  FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true);
208  fstprinter.Print(&std::cout, "standard output");
209  }*/
210  VectorFst<CompactArc> ofst;
211  ConvertLattice<Weight, Int>(*fst, &ofst, invert);
212 
213  /*std::cout << "FST after converting is:\n";
214  {
215  FstPrinter<CompactArc> fstprinter(ofst, NULL, NULL, NULL, false, true);
216  fstprinter.Print(&std::cout, "standard output");
217  }*/
218  VectorFst<Arc> origfst;
219  ConvertLattice<Weight, Int>(ofst, &origfst, invert);
220  /*std::cout << "FST after back conversion is:\n";
221  {
222  FstPrinter<Arc> fstprinter(origfst, NULL, NULL, NULL, false, true);
223  fstprinter.Print(&std::cout, "standard output");
224  }*/
225 
226  assert(RandEquivalent(*fst, origfst, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/));
227  delete fst;
228  }
229 }
230 
231 
232 // use TestConvertPair when the Weight can be constructed from
233 // a pair of floats.
234 template<class Weight, class Int> void TestScalePair(bool invert) {
235  std::vector<std::vector<double> > scale1 = DefaultLatticeScale(),
236  scale2 = DefaultLatticeScale();
237  // important that all these numbers exactly representable as floats..
238  // exact floating-point comparisons are used in LatticeWeight, and
239  // this exactness is being tested here.. this test will fail for
240  // other types of number.
241  if (kaldi::Rand() % 4 == 0) {
242  scale1[0][0] = 2.0;
243  scale2[0][0] = 0.5;
244  scale1[1][1] = 4.0;
245  scale2[1][1] = 0.25;
246  } else if (kaldi::Rand() % 3 == 0) {
247  // use that [1 0.25; 0 1] [ 1 -0.25; 0 1] is the unit matrix.
248  scale1[0][1] = 0.25;
249  scale2[0][1] = -0.25;
250  } else if (kaldi::Rand() % 2 == 0) {
251  scale1[1][0] = 0.25;
252  scale2[1][0] = -0.25;
253  }
254 
255 
256  typedef ArcTpl<Weight> Arc;
257  typedef ArcTpl<CompactLatticeWeightTpl<Weight, Int> > CompactArc;
258  for(int i = 0; i < 2; i++) {
259  VectorFst<Arc> *fst = RandPairFst<Arc>();
260  /*std::cout << "FST before converting to compact-arc is:\n";
261  {
262  FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true);
263  fstprinter.Print(&std::cout, "standard output");
264  }*/
265  VectorFst<CompactArc> ofst;
266  ConvertLattice<Weight, Int>(*fst, &ofst, invert);
267  ScaleLattice(scale1, &ofst);
268  /*std::cout << "FST after converting and scaling is:\n";
269  {
270  FstPrinter<CompactArc> fstprinter(ofst, NULL, NULL, NULL, false, true);
271  fstprinter.Print(&std::cout, "standard output");
272  }*/
273  VectorFst<Arc> origfst;
274  ConvertLattice<Weight, Int>(ofst, &origfst, invert);
275  ScaleLattice(scale2, &origfst);
276  /*std::cout << "FST after back conversion and scaling is:\n";
277  {
278  FstPrinter<Arc> fstprinter(origfst, NULL, NULL, NULL, false, true);
279  fstprinter.Print(&std::cout, "standard output");
280  }*/
281  // If RandEquivalent doesn't work, it could be due to a nasty issue related to the use
282  // of exact floating-point comparisons in the Plus function of LatticeWeight.
283  if (!RandEquivalent(*fst, origfst, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length-- max?*/)) {
284  std::cerr << "Warn, randequivalent returned false. Checking equivalence another way.\n";
285  assert(Equal(*fst, origfst));
286  }
287  delete fst;
288  }
289 }
290 
291 
292 
293 } // end namespace fst
294 
295 int main() {
296  using namespace fst;
297 
298  typedef ::int64 int64;
299  typedef ::uint64 uint64;
301  typedef ::uint32 uint32;
302 
303  {
305  for(int i = 0; i < 2; i++) {
306  bool invert = (i % 2);
307  TestConvert<TropicalWeight, int32>(invert);
308  TestConvertPair<LatticeWeight, int32>(invert);
309  TestConvertPair<LatticeWeight, size_t>(invert);
310  TestConvertPair<LexicographicWeight<TropicalWeight, TropicalWeight>, size_t>(invert);
311  TestScalePair<LatticeWeight, int32>(invert);
312  TestScalePair<LatticeWeight, size_t>(invert);
313  TestScalePair<LexicographicWeight<TropicalWeight, TropicalWeight>, size_t>(invert);
314  }
315  }
316  {
318  TestShortestPath<LatticeWeight, int32>();
319  TestConvert2<int32>();
320  for(int i = 0; i < 2; i++) {
321  bool invert = (i % 2);
322  TestConvertPair<LatticeWeight, int32>(invert);
323  TestConvertPair<LatticeWeight, size_t>(invert);
324  TestConvertPair<LexicographicWeight<TropicalWeight, TropicalWeight>, size_t>(invert);
325  TestScalePair<LatticeWeight, int32>(invert);
326  TestScalePair<LatticeWeight, size_t>(invert);
327  TestScalePair<LexicographicWeight<TropicalWeight, TropicalWeight>, size_t>(invert);
328  }
329  }
330  std::cout << "Tests succeeded\n";
331 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
kaldi::int32 int32
bool ApproxEqual(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2, float delta=kDelta)
void TestConvertPair(bool invert)
int main()
void TestScalePair(bool invert)
void ScaleLattice(const std::vector< std::vector< ScaleFloat > > &scale, MutableFst< ArcTpl< Weight > > *fst)
Scales the pairs of weights in LatticeWeight or CompactLatticeWeight by viewing the pair (a...
void ConvertLattice(const ExpandedFst< ArcTpl< Weight > > &ifst, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *ofst, bool invert)
Convert lattice from a normal FST to a CompactLattice FST.
void TestShortestPath()
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:45
LatticeWeightTpl< BaseFloat > LatticeWeight
void TestConvert2()
void TestConvert(bool invert)
std::vector< std::vector< double > > DefaultLatticeScale()
Returns a default 2x2 matrix scaling factor for LatticeWeight.