FST  openfst-1.7.1
OpenFst Library
lexicographic-weight.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Lexicographic weight set and associated semiring operation definitions.
5 //
6 // A lexicographic weight is a sequence of weights, each of which must have the
7 // path property and Times() must be (strongly) cancellative
8 // (for all a,b,c != Zero(): Times(c, a) = Times(c, b) => a = b,
9 // Times(a, c) = Times(b, c) => a = b).
10 // The + operation on two weights a and b is the lexicographically
11 // prior of a and b.
12 
13 #ifndef FST_LEXICOGRAPHIC_WEIGHT_H_
14 #define FST_LEXICOGRAPHIC_WEIGHT_H_
15 
16 #include <cstdlib>
17 
18 #include <string>
19 
20 #include <fst/log.h>
21 
22 #include <fst/pair-weight.h>
23 #include <fst/weight.h>
24 
25 
26 namespace fst {
27 
28 template <class W1, class W2>
29 class LexicographicWeight : public PairWeight<W1, W2> {
30  public:
31  using ReverseWeight = LexicographicWeight<typename W1::ReverseWeight,
32  typename W2::ReverseWeight>;
33 
43 
45 
47  : PairWeight<W1, W2>(w) {}
48 
49  LexicographicWeight(W1 w1, W2 w2) : PairWeight<W1, W2>(w1, w2) {
50  if ((W1::Properties() & kPath) != kPath) {
51  FSTERROR() << "LexicographicWeight must "
52  << "have the path property: " << W1::Type();
53  SetValue1(W1::NoWeight());
54  }
55  if ((W2::Properties() & kPath) != kPath) {
56  FSTERROR() << "LexicographicWeight must "
57  << "have the path property: " << W2::Type();
58  SetValue2(W2::NoWeight());
59  }
60  }
61 
62  static const LexicographicWeight &Zero() {
63  static const LexicographicWeight zero(PairWeight<W1, W2>::Zero());
64  return zero;
65  }
66 
67  static const LexicographicWeight &One() {
68  static const LexicographicWeight one(PairWeight<W1, W2>::One());
69  return one;
70  }
71 
72  static const LexicographicWeight &NoWeight() {
73  static const LexicographicWeight no_weight(PairWeight<W1, W2>::NoWeight());
74  return no_weight;
75  }
76 
77  static const string &Type() {
78  static const string *const type =
79  new string(W1::Type() + "_LT_" + W2::Type());
80  return *type;
81  }
82 
83  bool Member() const {
84  if (!Value1().Member() || !Value2().Member()) return false;
85  // Lexicographic weights cannot mix zeroes and non-zeroes.
86  if (Value1() == W1::Zero() && Value2() == W2::Zero()) return true;
87  if (Value1() != W1::Zero() && Value2() != W2::Zero()) return true;
88  return false;
89  }
90 
91  LexicographicWeight Quantize(float delta = kDelta) const {
93  }
94 
97  }
98 
99  static constexpr uint64 Properties() {
100  return W1::Properties() & W2::Properties() &
102  kCommutative);
103  }
104 };
105 
106 template <class W1, class W2>
108  const LexicographicWeight<W1, W2> &v) {
109  if (!w.Member() || !v.Member()) {
111  }
112  NaturalLess<W1> less1;
113  NaturalLess<W2> less2;
114  if (less1(w.Value1(), v.Value1())) return w;
115  if (less1(v.Value1(), w.Value1())) return v;
116  if (less2(w.Value2(), v.Value2())) return w;
117  if (less2(v.Value2(), w.Value2())) return v;
118  return w;
119 }
120 
121 template <class W1, class W2>
123  const LexicographicWeight<W1, W2> &v) {
125  Times(w.Value2(), v.Value2()));
126 }
127 
128 template <class W1, class W2>
131  DivideType typ = DIVIDE_ANY) {
132  return LexicographicWeight<W1, W2>(Divide(w.Value1(), v.Value1(), typ),
133  Divide(w.Value2(), v.Value2(), typ));
134 }
135 
136 // This function object generates weights by calling the underlying generators
137 // for the templated weight types, like all other pair weight types. However,
138 // for lexicographic weights, we cannot generate zeroes for the two subweights
139 // separately: weights are members iff both members are zero or both members
140 // are non-zero. This is intended primarily for testing.
141 template <class W1, class W2>
143  public:
147 
148  explicit WeightGenerate(bool allow_zero = true,
149  size_t num_random_weights = kNumRandomWeights)
150  : generator1_(false, num_random_weights),
151  generator2_(false, num_random_weights), allow_zero_(allow_zero),
152  num_random_weights_(num_random_weights) {}
153 
154  Weight operator()() const {
155  if (allow_zero_) {
156  const int n = rand() % (num_random_weights_ + 1); // NOLINT
157  if (n == num_random_weights_) return Weight(W1::Zero(), W2::Zero());
158  }
159  return Weight(generator1_(), generator2_());
160  }
161 
162  private:
163  const Generate1 generator1_;
164  const Generate2 generator2_;
165  // Permits Zero() and zero divisors.
166  const bool allow_zero_;
167  // The number of alternative random weights.
168  const size_t num_random_weights_;
169 };
170 
171 } // namespace fst
172 
173 #endif // FST_LEXICOGRAPHIC_WEIGHT_H_
LexicographicWeight(const PairWeight< W1, W2 > &w)
LexicographicWeight< typename W1::ReverseWeight, typename W2::ReverseWeight > ReverseWeight
ExpectationWeight< X1, X2 > Divide(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2, DivideType typ=DIVIDE_ANY)
uint64_t uint64
Definition: types.h:32
constexpr uint64 kRightSemiring
Definition: weight.h:115
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
const W2 & Value2() const
Definition: pair-weight.h:78
constexpr uint64 kCommutative
Definition: weight.h:120
constexpr uint64 kLeftSemiring
Definition: weight.h:112
static constexpr uint64 Properties()
WeightGenerate(bool allow_zero=true, size_t num_random_weights=kNumRandomWeights)
void SetValue2(const W2 &weight)
Definition: pair-weight.h:82
#define FSTERROR()
Definition: util.h:35
static const LexicographicWeight & One()
static const LexicographicWeight & Zero()
LexicographicWeight Quantize(float delta=kDelta) const
constexpr uint64 kIdempotent
Definition: weight.h:123
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
ReverseWeight Reverse() const
static const string & Type()
constexpr uint64 kPath
Definition: weight.h:126
static const LexicographicWeight & NoWeight()
constexpr size_t kNumRandomWeights
Definition: weight.h:130
DivideType
Definition: weight.h:142
constexpr float kDelta
Definition: weight.h:109
void SetValue1(const W1 &weight)
Definition: pair-weight.h:80
const W1 & Value1() const
Definition: pair-weight.h:76