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
174
175
176
177
178
179
|
// weight.h
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: [email protected] (Michael Riley)
//
// \file
// General weight set and associated semiring operation definitions.
//
// A semiring is specified by two binary operations Plus and Times and
// two designated elements Zero and One with the following properties:
// Plus: associative, commutative, and has Zero as its identity.
// Times: associative and has identity One, distributes w.r.t. Plus, and
// has Zero as an annihilator:
// Times(Zero(), a) == Times(a, Zero()) = Zero().
//
// A left semiring distributes on the left; a right semiring is
// similarly defined.
//
// A Weight class must have binary functions =Plus= and =Times= and
// static member functions =Zero()= and =One()= and these must form
// (at least) a left or right semiring.
//
// In addition, the following should be defined for a Weight:
// Member: predicate on set membership.
// NoWeight: static member function that returns an element that is
// not a set member; used to signal an error.
// >>: reads textual representation of a weight.
// <<: prints textual representation of a weight.
// Read(istream &strm): reads binary representation of a weight.
// Write(ostream &strm): writes binary representation of a weight.
// Hash: maps weight to size_t.
// ApproxEqual: approximate equality (for inexact weights)
// Quantize: quantizes wrt delta (for inexact weights)
// Divide: for all a,b,c s.t. Times(a, b) == c
// --> b' = Divide(c, a, DIVIDE_LEFT) if a left semiring, b'.Member()
// and Times(a, b') == c
// --> a' = Divide(c, b, DIVIDE_RIGHT) if a right semiring, a'.Member()
// and Times(a', b) == c
// --> b' = Divide(c, a) = Divide(c, a, DIVIDE_ANY) =
// Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a
// commutative semiring, b'.Member() and Times(a, b') = Times(b', a) = c
// ReverseWeight: the type of the corresponding reverse weight.
// Typically the same type as Weight for a (both left and right) semiring.
// For the left string semiring, it is the right string semiring.
// Reverse: a mapping from Weight to ReverseWeight s.t.
// --> Reverse(Reverse(a)) = a
// --> Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
// --> Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
// Typically the identity mapping in a (both left and right) semiring.
// In the left string semiring, it maps to the reverse string
// in the right string semiring.
// Properties: specifies additional properties that hold:
// LeftSemiring: indicates weights form a left semiring.
// RightSemiring: indicates weights form a right semiring.
// Commutative: for all a,b: Times(a,b) == Times(b,a)
// Idempotent: for all a: Plus(a, a) == a.
// Path: for all a, b: Plus(a, b) == a or Plus(a, b) == b.
#ifndef FST_LIB_WEIGHT_H__
#define FST_LIB_WEIGHT_H__
#include <cmath>
#include <cctype>
#include <iostream>
#include <sstream>
#include <fst/compat.h>
#include <fst/util.h>
namespace fst {
//
// CONSTANT DEFINITIONS
//
// A representable float near .001
const float kDelta = 1.0F/1024.0F;
// For all a,b,c: Times(c, Plus(a,b)) = Plus(Times(c,a), Times(c, b))
const uint64 kLeftSemiring = 0x0000000000000001ULL;
// For all a,b,c: Times(Plus(a,b), c) = Plus(Times(a,c), Times(b, c))
const uint64 kRightSemiring = 0x0000000000000002ULL;
const uint64 kSemiring = kLeftSemiring | kRightSemiring;
// For all a,b: Times(a,b) = Times(b,a)
const uint64 kCommutative = 0x0000000000000004ULL;
// For all a: Plus(a, a) = a
const uint64 kIdempotent = 0x0000000000000008ULL;
// For all a,b: Plus(a,b) = a or Plus(a,b) = b
const uint64 kPath = 0x0000000000000010ULL;
// Determines direction of division.
enum DivideType { DIVIDE_LEFT, // left division
DIVIDE_RIGHT, // right division
DIVIDE_ANY }; // division in a commutative semiring
// NATURAL ORDER
//
// By definition:
// a <= b iff a + b = a
// The natural order is a negative partial order iff the semiring is
// idempotent. It is trivially monotonic for plus. It is left
// (resp. right) monotonic for times iff the semiring is left
// (resp. right) distributive. It is a total order iff the semiring
// has the path property. See Mohri, "Semiring Framework and
// Algorithms for Shortest-Distance Problems", Journal of Automata,
// Languages and Combinatorics 7(3):321-350, 2002. We define the
// strict version of this order below.
template <class W>
class NaturalLess {
public:
typedef W Weight;
NaturalLess() {
if (!(W::Properties() & kIdempotent)) {
FSTERROR() << "NaturalLess: Weight type is not idempotent: "
<< W::Type();
}
}
bool operator()(const W &w1, const W &w2) const {
return (Plus(w1, w2) == w1) && w1 != w2;
}
};
// Power is the iterated product for arbitrary semirings such that
// Power(w, 0) is One() for the semiring, and
// Power(w, n) = Times(Power(w, n-1), w)
template <class W>
W Power(W w, size_t n) {
W result = W::One();
for (size_t i = 0; i < n; ++i) {
result = Times(result, w);
}
return result;
}
// General weight converter - raises error.
template <class W1, class W2>
struct WeightConvert {
W2 operator()(W1 w1) const {
FSTERROR() << "WeightConvert: can't convert weight from \""
<< W1::Type() << "\" to \"" << W2::Type();
return W2::NoWeight();
}
};
// Specialized weight converter to self.
template <class W>
struct WeightConvert<W, W> {
W operator()(W w) const { return w; }
};
} // namespace fst
#endif // FST_LIB_WEIGHT_H__
|