Go to the documentation of this file.
1 // lat/determinize-lattice-pruned.h
3 // Copyright 2009-2012 Microsoft Corporation
4 // 2012-2013 Johns Hopkins University (Author: Daniel Povey)
5 // 2014 Guoguo Chen
7 // See ../../COPYING for clarification regarding multiple authors
8 //
9 // Licensed under the Apache License, Version 2.0 (the "License");
10 // you may not use this file except in compliance with the License.
11 // You may obtain a copy of the License at
12 //
13 //
14 //
19 // See the Apache 2 License for the specific language governing permissions and
20 // limitations under the License.
24 #include <fst/fstlib.h>
25 #include <fst/fst-decl.h>
26 #include <algorithm>
27 #include <map>
28 #include <set>
29 #include <vector>
30 #include "fstext/lattice-weight.h"
31 #include "hmm/transition-model.h"
32 #include "itf/options-itf.h"
33 #include "lat/kaldi-lattice.h"
35 namespace fst {
41 // For example of usage, see
43 /*
44  DeterminizeLatticePruned implements a special form of determinization with
45  epsilon removal, optimized for a phase of lattice generation. This algorithm
46  also does pruning at the same time-- the combination is more efficient as it
47  somtimes prevents us from creating a lot of states that would later be pruned
48  away. This allows us to increase the lattice-beam and not have the algorithm
49  blow up. Also, because our algorithm processes states in order from those
50  that appear on high-scoring paths down to those that appear on low-scoring
51  paths, we can easily terminate the algorithm after a certain specified number
52  of states or arcs.
54  The input is an FST with weight-type BaseWeightType (usually a pair of floats,
55  with a lexicographical type of order, such as LatticeWeightTpl<float>).
56  Typically this would be a state-level lattice, with input symbols equal to
57  words, and output-symbols equal to p.d.f's (so like the inverse of HCLG). Imagine representing this as an
58  acceptor of type CompactLatticeWeightTpl<float>, in which the input/output
59  symbols are words, and the weights contain the original weights together with
60  strings (with zero or one symbol in them) containing the original output labels
61  (the p.d.f.'s). We determinize this using acceptor determinization with
62  epsilon removal. Remember (from lattice-weight.h) that
63  CompactLatticeWeightTpl has a special kind of semiring where we always take
64  the string corresponding to the best cost (of type BaseWeightType), and
65  discard the other. This corresponds to taking the best output-label sequence
66  (of p.d.f.'s) for each input-label sequence (of words). We couldn't use the
67  Gallic weight for this, or it would die as soon as it detected that the input
68  FST was non-functional. In our case, any acyclic FST (and many cyclic ones)
69  can be determinized.
70  We assume that there is a function
71  Compare(const BaseWeightType &a, const BaseWeightType &b)
72  that returns (-1, 0, 1) according to whether (a < b, a == b, a > b) in the
73  total order on the BaseWeightType... this information should be the
74  same as NaturalLess would give, but it's more efficient to do it this way.
75  You can define this for things like TropicalWeight if you need to instantiate
76  this class for that weight type.
78  We implement this determinization in a special way to make it efficient for
79  the types of FSTs that we will apply it to. One issue is that if we
80  explicitly represent the strings (in CompactLatticeWeightTpl) as vectors of
81  type vector<IntType>, the algorithm takes time quadratic in the length of
82  words (in states), because propagating each arc involves copying a whole
83  vector (of integers representing p.d.f.'s). Instead we use a hash structure
84  where each string is a pointer (Entry*), and uses a hash from (Entry*,
85  IntType), to the successor string (and a way to get the latest IntType and the
86  ancestor Entry*). [this is the class LatticeStringRepository].
88  Another issue is that rather than representing a determinized-state as a
89  collection of (state, weight), we represent it in a couple of reduced forms.
90  Suppose a determinized-state is a collection of (state, weight) pairs; call
91  this the "canonical representation". Note: these collections are always
92  normalized to remove any common weight and string part. Define end-states as
93  the subset of states that have an arc out of them with a label on, or are
94  final. If we represent a determinized-state a the set of just its (end-state,
95  weight) pairs, this will be a valid and more compact representation, and will
96  lead to a smaller set of determinized states (like early minimization). Call
97  this collection of (end-state, weight) pairs the "minimal representation". As
98  a mechanism to reduce compute, we can also consider another representation.
99  In the determinization algorithm, we start off with a set of (begin-state,
100  weight) pairs (where the "begin-states" are initial or have a label on the
101  transition into them), and the "canonical representation" consists of the
102  epsilon-closure of this set (i.e. follow epsilons). Call this set of
103  (begin-state, weight) pairs, appropriately normalized, the "initial
104  representation". If two initial representations are the same, the "canonical
105  representation" and hence the "minimal representation" will be the same. We
106  can use this to reduce compute. Note that if two initial representations are
107  different, this does not preclude the other representations from being the same.
109 */
113  float delta; // A small offset used to measure equality of weights.
114  int max_mem; // If >0, determinization will fail and return false
115  // when the algorithm's (approximate) memory consumption crosses this threshold.
116  int max_loop; // If >0, can be used to detect non-determinizable input
117  // (a case that wouldn't be caught by max_mem).
119  int max_arcs;
122  max_mem(-1),
123  max_loop(-1),
124  max_states(-1),
125  max_arcs(-1),
126  retry_cutoff(0.5) { }
128  opts->Register("delta", &delta, "Tolerance used in determinization");
129  opts->Register("max-mem", &max_mem, "Maximum approximate memory usage in "
130  "determinization (real usage might be many times this)");
131  opts->Register("max-arcs", &max_arcs, "Maximum number of arcs in "
132  "output FST (total, not per state");
133  opts->Register("max-states", &max_states, "Maximum number of arcs in output "
134  "FST (total, not per state");
135  opts->Register("max-loop", &max_loop, "Option used to detect a particular "
136  "type of determinization failure, typically due to invalid input "
137  "(e.g., negative-cost loops)");
138  opts->Register("retry-cutoff", &retry_cutoff, "Controls pruning un-determinized "
139  "lattice and retrying determinization: if effective-beam < "
140  "retry-cutoff * beam, we prune the raw lattice and retry. Avoids "
141  "ever getting empty output for long segments.");
142  }
143 };
146  // delta: a small offset used to measure equality of weights.
147  float delta;
148  // max_mem: if > 0, determinization will fail and return false when the
149  // algorithm's (approximate) memory consumption crosses this threshold.
150  int max_mem;
151  // phone_determinize: if true, do a first pass determinization on both phones
152  // and words.
154  // word_determinize: if true, do a second pass determinization on words only.
156  // minimize: if true, push and minimize after determinization.
157  bool minimize;
159  max_mem(50000000),
160  phone_determinize(true),
161  word_determinize(true),
162  minimize(false) {}
164  opts->Register("delta", &delta, "Tolerance used in determinization");
165  opts->Register("max-mem", &max_mem, "Maximum approximate memory usage in "
166  "determinization (real usage might be many times this).");
167  opts->Register("phone-determinize", &phone_determinize, "If true, do an "
168  "initial pass of determinization on both phones and words (see"
169  " also --word-determinize)");
170  opts->Register("word-determinize", &word_determinize, "If true, do a second "
171  "pass of determinization on words only (see also "
172  "--phone-determinize)");
173  opts->Register("minimize", &minimize, "If true, push and minimize after "
174  "determinization.");
175  }
176 };
189 template<class Weight>
191  const ExpandedFst<ArcTpl<Weight> > &ifst,
192  double prune,
193  MutableFst<ArcTpl<Weight> > *ofst,
197 /* This is a version of DeterminizeLattice with a slightly more "natural" output format,
198  where the output sequences are encoded using the CompactLatticeArcTpl template
199  (i.e. the sequences of output symbols are represented directly as strings The input
200  FST must be topologically sorted in order for the algorithm to work. For efficiency
201  it is recommended to sort the ilabel for the input FST as well.
202  Returns true on normal success, and false if it had to terminate the determinization
203  earlier than specified by the "prune" beam-- that is, if it terminated because
204  of the max_mem, max_loop or max_arcs constraints in the options.
205  CAUTION: if Lattice is the input, you need to Invert() before calling this,
206  so words are on the input side.
207 */
208 template<class Weight, class IntType>
210  const ExpandedFst<ArcTpl<Weight> >&ifst,
211  double prune,
212  MutableFst<ArcTpl<CompactLatticeWeightTpl<Weight, IntType> > > *ofst,
223 template<class Weight>
225  const kaldi::TransitionModel &trans_model,
226  MutableFst<ArcTpl<Weight> > *fst);
234 template<class Weight>
236  typename ArcTpl<Weight>::Label first_phone_label,
237  MutableFst<ArcTpl<Weight> > *fst);
254 template<class Weight, class IntType>
256  const kaldi::TransitionModel &trans_model,
257  const ExpandedFst<ArcTpl<Weight> > &ifst,
258  double prune,
259  MutableFst<ArcTpl<CompactLatticeWeightTpl<Weight, IntType> > > *ofst,
266 template<class Weight, class IntType>
268  const kaldi::TransitionModel &trans_model,
269  MutableFst<ArcTpl<Weight> > *ifst,
270  double prune,
271  MutableFst<ArcTpl<CompactLatticeWeightTpl<Weight, IntType> > > *ofst,
285  const kaldi::TransitionModel &trans_model,
286  MutableFst<kaldi::LatticeArc> *ifst,
287  double prune,
288  MutableFst<kaldi::CompactLatticeArc> *ofst,
294 } // end namespace fst
296 #endif
bool DeterminizeLatticePruned(const ExpandedFst< ArcTpl< Weight > > &ifst, double beam, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticePrunedOptions opts)
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
bool DeterminizeLatticePhonePruned(const kaldi::TransitionModel &trans_model, MutableFst< ArcTpl< Weight > > *ifst, double beam, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticePhonePrunedOptions opts)
"Destructive" version of DeterminizeLatticePhonePruned() where the input lattice might be changed...
virtual void Register(const std::string &name, bool *ptr, const std::string &doc)=0
fst::StdArc::Label Label
ArcTpl< Weight >::Label DeterminizeLatticeInsertPhones(const kaldi::TransitionModel &trans_model, MutableFst< ArcTpl< Weight > > *fst)
This function takes in lattices and inserts phones at phone boundaries.
bool DeterminizeLatticePhonePrunedWrapper(const kaldi::TransitionModel &trans_model, MutableFst< kaldi::LatticeArc > *ifst, double beam, MutableFst< kaldi::CompactLatticeArc > *ofst, DeterminizeLatticePhonePrunedOptions opts)
This function is a wrapper of DeterminizeLatticePhonePruned() that works for Lattice type FSTs...
void DeterminizeLatticeDeletePhones(typename ArcTpl< Weight >::Label first_phone_label, MutableFst< ArcTpl< Weight > > *fst)
This function takes in lattices and deletes "phones" from them.