```/* <![CDATA[ */
function get_sym_list(){return [["Macro","xm",[["FST_LIB_WEIGHT_H__",73]]],["Class","xc",[["NaturalLess",131]]],["Namespace","xn",[["fst",85]]],["Enum","xe",[["DivideType",113]]],["Struct","xs",[["WeightConvert",163],["WeightConvert",173]]],["Typedef","xt",[["Weight",133]]],["Function","xf",[["NaturalLess",135],["Power",153],["operator ()",142],["operator ()",164],["operator ()",174]]]];} /* ]]> */1// weight.h
2
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
8//
9// Unless required by applicable law or agreed to in writing, software
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
14//
17//
18// \file
19// General weight set and associated semiring operation definitions.
20//
21// A semiring is specified by two binary operations Plus and Times and
22// two designated elements Zero and One with the following properties:
23//   Plus: associative, commutative, and has Zero as its identity.
24//   Times: associative and has identity One, distributes w.r.t. Plus, and
25//     has Zero as an annihilator:
26//          Times(Zero(), a) == Times(a, Zero()) = Zero().
27//
28//  A left semiring distributes on the left; a right semiring is
29//  similarly defined.
30//
31// A Weight class must have binary functions =Plus= and =Times= and
32// static member functions =Zero()= and =One()= and these must form
33// (at least) a left or right semiring.
34//
35// In addition, the following should be defined for a Weight:
36//   Member: predicate on set membership.
37//   NoWeight: static member function that returns an element that is
38//      not a set member; used to signal an error.
39//   >>: reads textual representation of a weight.
40//   <<: prints textual representation of a weight.
42//   Write(ostream &strm): writes binary representation of a weight.
43//   Hash: maps weight to size_t.
44//   ApproxEqual: approximate equality (for inexact weights)
45//   Quantize: quantizes wrt delta (for inexact weights)
46//   Divide: for all a,b,c s.t. Times(a, b) == c
47//     --> b' = Divide(c, a, DIVIDE_LEFT) if a left semiring, b'.Member()
48//      and Times(a, b') == c
49//     --> a' = Divide(c, b, DIVIDE_RIGHT) if a right semiring, a'.Member()
50//      and Times(a', b) == c
51//     --> b' = Divide(c, a) = Divide(c, a, DIVIDE_ANY) =
52//      Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a
53//      commutative semiring, b'.Member() and Times(a, b') = Times(b', a) = c
54//   ReverseWeight: the type of the corresponding reverse weight.
55//     Typically the same type as Weight for a (both left and right) semiring.
56//     For the left string semiring, it is the right string semiring.
57//   Reverse: a mapping from Weight to ReverseWeight s.t.
58//     --> Reverse(Reverse(a)) = a
59//     --> Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
60//     --> Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
61//     Typically the identity mapping in a (both left and right) semiring.
62//     In the left string semiring, it maps to the reverse string
63//     in the right string semiring.
64//   Properties: specifies additional properties that hold:
65//      LeftSemiring: indicates weights form a left semiring.
66//      RightSemiring: indicates weights form a right semiring.
67//      Commutative: for all a,b: Times(a,b) == Times(b,a)
68//      Idempotent: for all a: Plus(a, a) == a.
69//      Path: for all a, b: Plus(a, b) == a or Plus(a, b) == b.
70
71
72#ifndef FST_LIB_WEIGHT_H__
73#define FST_LIB_WEIGHT_H__
74
75#include <cmath>
76#include <cctype>
77#include <iostream>
78#include <sstream>
79
80#include <fst/compat.h>
81
82#include <fst/util.h>
83
84
85namespace fst {
86
87//
88// CONSTANT DEFINITIONS
89//
90
91// A representable float near .001
92const float kDelta =                   1.0F/1024.0F;
93
94// For all a,b,c: Times(c, Plus(a,b)) = Plus(Times(c,a), Times(c, b))
95const uint64 kLeftSemiring =           0x0000000000000001ULL;
96
97// For all a,b,c: Times(Plus(a,b), c) = Plus(Times(a,c), Times(b, c))
98const uint64 kRightSemiring =          0x0000000000000002ULL;
99
100const uint64 kSemiring = kLeftSemiring | kRightSemiring;
101
102// For all a,b: Times(a,b) = Times(b,a)
103const uint64 kCommutative =       0x0000000000000004ULL;
104
105// For all a: Plus(a, a) = a
106const uint64 kIdempotent =             0x0000000000000008ULL;
107
108// For all a,b: Plus(a,b) = a or Plus(a,b) = b
109const uint64 kPath =                   0x0000000000000010ULL;
110
111
112// Determines direction of division.
113enum DivideType { DIVIDE_LEFT,   // left division
114                  DIVIDE_RIGHT,  // right division
115                  DIVIDE_ANY };  // division in a commutative semiring
116
117// NATURAL ORDER
118//
119// By definition:
120//                 a <= b iff a + b = a
121// The natural order is a negative partial order iff the semiring is
122// idempotent. It is trivially monotonic for plus. It is left
123// (resp. right) monotonic for times iff the semiring is left
124// (resp. right) distributive. It is a total order iff the semiring
125// has the path property. See Mohri, "Semiring Framework and
126// Algorithms for Shortest-Distance Problems", Journal of Automata,
127// Languages and Combinatorics 7(3):321-350, 2002. We define the
128// strict version of this order below.
129
130template <class W>
131class NaturalLess {
132 public:
133  typedef W Weight;
134
135  NaturalLess() {
136    if (!(W::Properties() & kIdempotent)) {
137      FSTERROR() << "NaturalLess: Weight type is not idempotent: "
138                 << W::Type();
139    }
140  }
141
142  bool operator()(const W &w1, const W &w2) const {
143    return (Plus(w1, w2) == w1) && w1 != w2;
144  }
145};
146
147
148// Power is the iterated product for arbitrary semirings such that
149// Power(w, 0) is One() for the semiring, and
150// Power(w, n) = Times(Power(w, n-1), w)
151
152template <class W>
153W Power(W w, size_t n) {
154  W result = W::One();
155  for (size_t i = 0; i < n; ++i) {
156    result = Times(result, w);
157  }
158  return result;
159}
160
161// General weight converter - raises error.
162template <class W1, class W2>
163struct WeightConvert {
164  W2 operator()(W1 w1) const {
165    FSTERROR() << "WeightConvert: can't convert weight from \""
166               << W1::Type() << "\" to \"" << W2::Type();
167    return W2::NoWeight();
168  }
169};
170
171// Specialized weight converter to self.
172template <class W>
173struct WeightConvert<W, W> {
174  W operator()(W w) const { return w; }
175};
176
177}  // namespace fst
178
179#endif  // FST_LIB_WEIGHT_H__
180```