FST  openfst-1.8.3
OpenFst Library
lexicographic-weight.h
Go to the documentation of this file.
1 // Copyright 2005-2024 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Lexicographic weight set and associated semiring operation definitions.
19 //
20 // A lexicographic weight is a sequence of weights, each of which must have the
21 // path property and Times() must be (strongly) cancellative
22 // (for all a,b,c != Zero(): Times(c, a) = Times(c, b) => a = b,
23 // Times(a, c) = Times(b, c) => a = b).
24 // The + operation on two weights a and b is the lexicographically
25 // prior of a and b.
26 
27 #ifndef FST_LEXICOGRAPHIC_WEIGHT_H_
28 #define FST_LEXICOGRAPHIC_WEIGHT_H_
29 
30 #include <cstddef>
31 #include <cstdint>
32 #include <random>
33 #include <string>
34 
35 #include <fst/log.h>
36 #include <fst/pair-weight.h>
37 #include <fst/weight.h>
38 
39 namespace fst {
40 
41 template <class W1, class W2>
42 class LexicographicWeight : public PairWeight<W1, W2> {
43  public:
44  static_assert(IsPath<W1>::value, "W1 must have path property.");
45  static_assert(IsPath<W2>::value, "W2 must have path property.");
46 
47  using ReverseWeight = LexicographicWeight<typename W1::ReverseWeight,
48  typename W2::ReverseWeight>;
49 
59 
60  LexicographicWeight() = default;
61 
63  : PairWeight<W1, W2>(w) {}
64 
65  LexicographicWeight(W1 w1, W2 w2) : PairWeight<W1, W2>(w1, w2) {}
66 
67  static const LexicographicWeight &Zero() {
68  static const LexicographicWeight zero(PairWeight<W1, W2>::Zero());
69  return zero;
70  }
71 
72  static const LexicographicWeight &One() {
73  static const LexicographicWeight one(PairWeight<W1, W2>::One());
74  return one;
75  }
76 
77  static const LexicographicWeight &NoWeight() {
78  static const LexicographicWeight no_weight(PairWeight<W1, W2>::NoWeight());
79  return no_weight;
80  }
81 
82  static const std::string &Type() {
83  static const std::string *const type =
84  new std::string(W1::Type() + "_LT_" + W2::Type());
85  return *type;
86  }
87 
88  bool Member() const {
89  if (!Value1().Member() || !Value2().Member()) return false;
90  // Lexicographic weights cannot mix zeroes and non-zeroes.
91  if (Value1() == W1::Zero() && Value2() == W2::Zero()) return true;
92  if (Value1() != W1::Zero() && Value2() != W2::Zero()) return true;
93  return false;
94  }
95 
96  LexicographicWeight Quantize(float delta = kDelta) const {
98  }
99 
102  }
103 
104  static constexpr uint64_t Properties() {
105  return W1::Properties() & W2::Properties() &
107  kCommutative);
108  }
109 };
110 
111 template <class W1, class W2>
113  const LexicographicWeight<W1, W2> &v) {
114  if (!w.Member() || !v.Member()) {
116  }
117  NaturalLess<W1> less1;
118  NaturalLess<W2> less2;
119  if (less1(w.Value1(), v.Value1())) return w;
120  if (less1(v.Value1(), w.Value1())) return v;
121  if (less2(w.Value2(), v.Value2())) return w;
122  if (less2(v.Value2(), w.Value2())) return v;
123  return w;
124 }
125 
126 template <class W1, class W2>
128  const LexicographicWeight<W1, W2> &v) {
130  Times(w.Value2(), v.Value2()));
131 }
132 
133 template <class W1, class W2>
136  DivideType typ = DIVIDE_ANY) {
137  return LexicographicWeight<W1, W2>(Divide(w.Value1(), v.Value1(), typ),
138  Divide(w.Value2(), v.Value2(), typ));
139 }
140 
141 // This function object generates weights by calling the underlying generators
142 // for the templated weight types, like all other pair weight types. However,
143 // for lexicographic weights, we cannot generate zeroes for the two subweights
144 // separately: weights are members iff both members are zero or both members
145 // are non-zero. This is intended primarily for testing.
146 template <class W1, class W2>
148  public:
152 
153  explicit WeightGenerate(uint64_t seed = std::random_device()(),
154  bool allow_zero = true,
155  size_t num_random_weights = kNumRandomWeights)
156  : rand_(seed),
157  allow_zero_(allow_zero),
158  num_random_weights_(num_random_weights),
159  generator1_(seed, false, num_random_weights),
160  generator2_(seed, false, num_random_weights) {}
161 
162  Weight operator()() const {
163  if (allow_zero_) {
164  const int sample =
165  std::uniform_int_distribution<>(0, num_random_weights_)(rand_);
166  if (sample == num_random_weights_) return Weight(W1::Zero(), W2::Zero());
167  }
168  return Weight(generator1_(), generator2_());
169  }
170 
171  private:
172  mutable std::mt19937_64 rand_;
173  const bool allow_zero_;
174  const size_t num_random_weights_;
175  const Generate1 generator1_;
176  const Generate2 generator2_;
177 };
178 
179 } // namespace fst
180 
181 #endif // FST_LEXICOGRAPHIC_WEIGHT_H_
LexicographicWeight(const PairWeight< W1, W2 > &w)
static constexpr uint64_t Properties()
LexicographicWeight< typename W1::ReverseWeight, typename W2::ReverseWeight > ReverseWeight
ErrorWeight Plus(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:61
static const std::string & Type()
ErrorWeight Times(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:64
const W2 & Value2() const
Definition: pair-weight.h:95
constexpr uint64_t kIdempotent
Definition: weight.h:147
constexpr uint64_t kRightSemiring
Definition: weight.h:139
WeightGenerate(uint64_t seed=std::random_device()(), bool allow_zero=true, size_t num_random_weights=kNumRandomWeights)
static const LexicographicWeight & One()
static const LexicographicWeight & Zero()
constexpr uint64_t kCommutative
Definition: weight.h:144
LexicographicWeight Quantize(float delta=kDelta) const
ReverseWeight Reverse() const
constexpr uint64_t kPath
Definition: weight.h:150
static const LexicographicWeight & NoWeight()
ErrorWeight Divide(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:67
constexpr size_t kNumRandomWeights
Definition: weight.h:154
DivideType
Definition: weight.h:165
constexpr uint64_t kLeftSemiring
Definition: weight.h:136
constexpr float kDelta
Definition: weight.h:133
std::bool_constant<(W::Properties()&kPath)!=0 > IsPath
Definition: weight.h:162
const W1 & Value1() const
Definition: pair-weight.h:93