FST  openfst-1.7.3
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 #include <string>
18 
19 #include <fst/log.h>
20 
21 #include <fst/pair-weight.h>
22 #include <fst/weight.h>
23 
24 
25 namespace fst {
26 
27 template <class W1, class W2>
28 class LexicographicWeight : public PairWeight<W1, W2> {
29  public:
30  using ReverseWeight = LexicographicWeight<typename W1::ReverseWeight,
31  typename W2::ReverseWeight>;
32 
42 
44 
46  : PairWeight<W1, W2>(w) {}
47 
48  LexicographicWeight(W1 w1, W2 w2) : PairWeight<W1, W2>(w1, w2) {
49  if ((W1::Properties() & kPath) != kPath) {
50  FSTERROR() << "LexicographicWeight must "
51  << "have the path property: " << W1::Type();
52  SetValue1(W1::NoWeight());
53  }
54  if ((W2::Properties() & kPath) != kPath) {
55  FSTERROR() << "LexicographicWeight must "
56  << "have the path property: " << W2::Type();
57  SetValue2(W2::NoWeight());
58  }
59  }
60 
61  static const LexicographicWeight &Zero() {
62  static const LexicographicWeight zero(PairWeight<W1, W2>::Zero());
63  return zero;
64  }
65 
66  static const LexicographicWeight &One() {
67  static const LexicographicWeight one(PairWeight<W1, W2>::One());
68  return one;
69  }
70 
71  static const LexicographicWeight &NoWeight() {
72  static const LexicographicWeight no_weight(PairWeight<W1, W2>::NoWeight());
73  return no_weight;
74  }
75 
76  static const std::string &Type() {
77  static const std::string *const type =
78  new std::string(W1::Type() + "_LT_" + W2::Type());
79  return *type;
80  }
81 
82  bool Member() const {
83  if (!Value1().Member() || !Value2().Member()) return false;
84  // Lexicographic weights cannot mix zeroes and non-zeroes.
85  if (Value1() == W1::Zero() && Value2() == W2::Zero()) return true;
86  if (Value1() != W1::Zero() && Value2() != W2::Zero()) return true;
87  return false;
88  }
89 
90  LexicographicWeight Quantize(float delta = kDelta) const {
92  }
93 
96  }
97 
98  static constexpr uint64 Properties() {
99  return W1::Properties() & W2::Properties() &
101  kCommutative);
102  }
103 };
104 
105 template <class W1, class W2>
107  const LexicographicWeight<W1, W2> &v) {
108  if (!w.Member() || !v.Member()) {
110  }
111  NaturalLess<W1> less1;
112  NaturalLess<W2> less2;
113  if (less1(w.Value1(), v.Value1())) return w;
114  if (less1(v.Value1(), w.Value1())) return v;
115  if (less2(w.Value2(), v.Value2())) return w;
116  if (less2(v.Value2(), w.Value2())) return v;
117  return w;
118 }
119 
120 template <class W1, class W2>
122  const LexicographicWeight<W1, W2> &v) {
124  Times(w.Value2(), v.Value2()));
125 }
126 
127 template <class W1, class W2>
130  DivideType typ = DIVIDE_ANY) {
131  return LexicographicWeight<W1, W2>(Divide(w.Value1(), v.Value1(), typ),
132  Divide(w.Value2(), v.Value2(), typ));
133 }
134 
135 // This function object generates weights by calling the underlying generators
136 // for the templated weight types, like all other pair weight types. However,
137 // for lexicographic weights, we cannot generate zeroes for the two subweights
138 // separately: weights are members iff both members are zero or both members
139 // are non-zero. This is intended primarily for testing.
140 template <class W1, class W2>
142  public:
146 
147  explicit WeightGenerate(bool allow_zero = true,
148  size_t num_random_weights = kNumRandomWeights)
149  : generator1_(false, num_random_weights),
150  generator2_(false, num_random_weights), allow_zero_(allow_zero),
151  num_random_weights_(num_random_weights) {}
152 
153  Weight operator()() const {
154  if (allow_zero_) {
155  const int n = rand() % (num_random_weights_ + 1); // NOLINT
156  if (n == num_random_weights_) return Weight(W1::Zero(), W2::Zero());
157  }
158  return Weight(generator1_(), generator2_());
159  }
160 
161  private:
162  const Generate1 generator1_;
163  const Generate2 generator2_;
164  // Permits Zero() and zero divisors.
165  const bool allow_zero_;
166  // The number of alternative random weights.
167  const size_t num_random_weights_;
168 };
169 
170 } // namespace fst
171 
172 #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
static const std::string & Type()
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
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