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