determinize-lattice-pruned-test.cc
Go to the documentation of this file.
1 // lat/determinize-lattice-pruned-test.cc
2 
3 // Copyright 2009-2012 Microsoft Corporation
4 // 2012-2013 Johns Hopkins University (Author: Daniel Povey)
5 
6 // See ../../COPYING for clarification regarding multiple authors
7 //
8 // Licensed under the Apache License, Version 2.0 (the "License");
9 // you may not use this file except in compliance with the License.
10 // You may obtain a copy of the License at
11 //
12 // http://www.apache.org/licenses/LICENSE-2.0
13 //
14 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
16 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
17 // MERCHANTABLITY OR NON-INFRINGEMENT.
18 // See the Apache 2 License for the specific language governing permissions and
19 // limitations under the License.
20 
22 #include "fstext/lattice-utils.h"
23 #include "fstext/fst-test-utils.h"
24 #include "lat/kaldi-lattice.h"
25 #include "lat/lattice-functions.h"
26 
27 namespace fst {
28 // Caution: these tests are not as generic as you might think from all the
29 // templates in the code. They are basically only valid for LatticeArc.
30 // This is partly due to the fact that certain templates need to be instantiated
31 // in other .cc files in this directory.
32 
33 // test that determinization proceeds correctly on general
34 // FSTs (not guaranteed determinzable, but we use the
35 // max-states option to stop it getting out of control).
36 template<class Arc> void TestDeterminizeLatticePruned() {
37  typedef kaldi::int32 Int;
38  typedef typename Arc::Weight Weight;
39  typedef ArcTpl<CompactLatticeWeightTpl<Weight, Int> > CompactArc;
40 
41  for(int i = 0; i < 100; i++) {
42  RandFstOptions opts;
43  opts.n_states = 4;
44  opts.n_arcs = 10;
45  opts.n_final = 2;
46  opts.allow_empty = false;
47  opts.weight_multiplier = 0.5; // impt for the randomly generated weights
48  opts.acyclic = true;
49  // to be exactly representable in float,
50  // or this test fails because numerical differences can cause symmetry in
51  // weights to be broken, which causes the wrong path to be chosen as far
52  // as the string part is concerned.
53 
54  VectorFst<Arc> *fst = RandPairFst<Arc>(opts);
55 
56  bool sorted = TopSort(fst);
57  KALDI_ASSERT(sorted);
58 
59  ILabelCompare<Arc> ilabel_comp;
60  if (kaldi::Rand() % 2 == 0)
61  ArcSort(fst, ilabel_comp);
62 
63  std::cout << "FST before lattice-determinizing is:\n";
64  {
65  FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true, "\t");
66  fstprinter.Print(&std::cout, "standard output");
67  }
68  VectorFst<Arc> det_fst;
69  try {
71  lat_opts.max_mem = ((kaldi::Rand() % 2 == 0) ? 100 : 1000);
72  lat_opts.max_states = ((kaldi::Rand() % 2 == 0) ? -1 : 20);
73  lat_opts.max_arcs = ((kaldi::Rand() % 2 == 0) ? -1 : 30);
74  bool ans = DeterminizeLatticePruned<Weight>(*fst, 10.0, &det_fst, lat_opts);
75 
76  std::cout << "FST after lattice-determinizing is:\n";
77  {
78  FstPrinter<Arc> fstprinter(det_fst, NULL, NULL, NULL, false, true, "\t");
79  fstprinter.Print(&std::cout, "standard output");
80  }
81  KALDI_ASSERT(det_fst.Properties(kIDeterministic, true) & kIDeterministic);
82  // OK, now determinize it a different way and check equivalence.
83  // [note: it's not normal determinization, it's taking the best path
84  // for any input-symbol sequence....
85 
86 
87  VectorFst<Arc> pruned_fst(*fst);
88  if (pruned_fst.NumStates() != 0)
89  kaldi::PruneLattice(10.0, &pruned_fst);
90 
91  VectorFst<CompactArc> compact_pruned_fst, compact_pruned_det_fst;
92  ConvertLattice<Weight, Int>(pruned_fst, &compact_pruned_fst, false);
93  std::cout << "Compact pruned FST is:\n";
94  {
95  FstPrinter<CompactArc> fstprinter(compact_pruned_fst, NULL, NULL, NULL, false, true, "\t");
96  fstprinter.Print(&std::cout, "standard output");
97  }
98  ConvertLattice<Weight, Int>(det_fst, &compact_pruned_det_fst, false);
99 
100  std::cout << "Compact version of determinized FST is:\n";
101  {
102  FstPrinter<CompactArc> fstprinter(compact_pruned_det_fst, NULL, NULL, NULL, false, true, "\t");
103  fstprinter.Print(&std::cout, "standard output");
104  }
105 
106  if (ans)
107  KALDI_ASSERT(RandEquivalent(compact_pruned_det_fst, compact_pruned_fst, 5/*paths*/, 0.01/*delta*/, kaldi::Rand()/*seed*/, 100/*path length, max*/));
108  } catch (...) {
109  std::cout << "Failed to lattice-determinize this FST (probably not determinizable)\n";
110  }
111  delete fst;
112  }
113 }
114 
115 // test that determinization proceeds without crash on acyclic FSTs
116 // (guaranteed determinizable in this sense).
117 template<class Arc> void TestDeterminizeLatticePruned2() {
118  typedef typename Arc::Weight Weight;
119  RandFstOptions opts;
120  opts.acyclic = true;
121  for(int i = 0; i < 100; i++) {
122  VectorFst<Arc> *fst = RandPairFst<Arc>(opts);
123  std::cout << "FST before lattice-determinizing is:\n";
124  {
125  FstPrinter<Arc> fstprinter(*fst, NULL, NULL, NULL, false, true, "\t");
126  fstprinter.Print(&std::cout, "standard output");
127  }
128  VectorFst<Arc> ofst;
129  DeterminizeLatticePruned<Weight>(*fst, 10.0, &ofst);
130  std::cout << "FST after lattice-determinizing is:\n";
131  {
132  FstPrinter<Arc> fstprinter(ofst, NULL, NULL, NULL, false, true, "\t");
133  fstprinter.Print(&std::cout, "standard output");
134  }
135  delete fst;
136  }
137 }
138 
139 
140 } // end namespace fst
141 
142 int main() {
143  using namespace fst;
144  TestDeterminizeLatticePruned<kaldi::LatticeArc>();
145  TestDeterminizeLatticePruned2<kaldi::LatticeArc>();
146  std::cout << "Tests succeeded\n";
147 }
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
void TestDeterminizeLatticePruned()
float weight_multiplier
Definition: rand-fst.h:41
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:45
fst::StdArc::Weight Weight
bool PruneLattice(BaseFloat beam, LatType *lat)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:185
void TestDeterminizeLatticePruned2()