determinize-star.h
Go to the documentation of this file.
1 // fstext/determinize-star.h
2 
3 // Copyright 2009-2011 Microsoft Corporation
4 // 2014 Guoguo Chen
5 // 2015 Hainan Xu
6 
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 // http://www.apache.org/licenses/LICENSE-2.0
14 //
15 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
17 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
18 // MERCHANTABLITY OR NON-INFRINGEMENT.
19 // See the Apache 2 License for the specific language governing permissions and
20 // limitations under the License.
21 
22 #ifndef KALDI_FSTEXT_DETERMINIZE_STAR_H_
23 #define KALDI_FSTEXT_DETERMINIZE_STAR_H_
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 <stdexcept> // this algorithm uses exceptions
31 
32 namespace fst {
33 
36 
37 
38 // For example of usage, see test-determinize-star.cc
39 
40 /*
41  DeterminizeStar implements determinization with epsilon removal, which we
42  distinguish with a star.
43 
44  We define a determinized* FST as one in which no state has more than one
45  transition with the same input-label. Epsilon input labels are not allowed
46  except starting from states that have exactly one arc exiting them (and are
47  not final). [In the normal definition of determinized, epsilon-input labels
48  are not allowed at all, whereas in Mohri's definition, epsilons are treated
49  as ordinary symbols]. The determinized* definition is intended to simulate
50  the effect of allowing strings of output symbols at each state.
51 
52  The algorithm implemented here takes an Fst<Arc>, and a pointer to a
53  MutableFst<Arc> where it puts its output. The weight type is assumed to be a
54  float-weight. It does epsilon removal and determinization.
55  This algorithm may fail if the input has epsilon cycles under
56  certain circumstances (i.e. the semiring is non-idempotent, e.g. the log
57  semiring, or there are negative cost epsilon cycles).
58 
59  This implementation is much less fancy than the one in fst/determinize.h, and
60  does not have an "on-demand" version.
61 
62  The algorithm is a fairly normal determinization algorithm. We keep in
63  memory the subsets of states, together with their leftover strings and their
64  weights. The only difference is we detect input epsilon transitions and
65  treat them "specially".
66 */
67 
68 
69 // This algorithm will be slightly faster if you sort the input fst on input label.
70 
88 template<class F>
89 bool DeterminizeStar(F &ifst, MutableFst<typename F::Arc> *ofst,
90  float delta = kDelta,
91  bool *debug_ptr = NULL,
92  int max_states = -1,
93  bool allow_partial = false);
94 
95 
96 
97 /* This is a version of DeterminizeStar with a slightly more "natural" output format,
98  where the output sequences are encoded using the GallicArc (i.e. the output symbols
99  are strings.
100  If max_states is positive, it will stop determinization and throw an
101  exception as soon as the max-states is reached. This can be useful in test.
102  If allow_partial is true, the algorithm will output partial results when the
103  specified max_states is reached (when larger than zero), instead of throwing
104  out an error.
105 
106  Caution, the return status is un-intuitive: this function will return false if
107  determinization completed normally, and true if it was stopped early by
108  reaching the 'max-states' limit, and a partial FST was generated.
109 */
110 template<class F>
111 bool DeterminizeStar(F &ifst, MutableFst<GallicArc<typename F::Arc> > *ofst,
112  float delta = kDelta, bool *debug_ptr = NULL,
113  int max_states = -1,
114  bool allow_partial = false);
115 
116 
118 
119 } // end namespace fst
120 
122 
123 #endif
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
bool DeterminizeStar(F &ifst, MutableFst< typename F::Arc > *ofst, float delta, bool *debug_ptr, int max_states, bool allow_partial)
This function implements the normal version of DeterminizeStar, in which the output strings are repre...