1// weight.h
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15//
16// \file
17// General weight set and associated semiring operation definitions.
18//
19// A semiring is specified by two binary operations Plus and Times and
20// two designated elements Zero and One with the following properties:
21//   Plus: associative, commutative, and has Zero as its identity.
22//   Times: associative and has identity One, distributes w.r.t. Plus, and
23//     has Zero as an annihilator:
24//          Times(Zero(), a) == Times(a, Zero()) = Zero().
25//
26//  A left semiring distributes on the left; a right semiring is
27//  similarly defined.
28//
29// A Weight class is required to be (at least) a left or right semiring.
30//
31// In addition, the following should be defined for a Weight:
32//   Member: predicate on set membership.
33//   >>: reads textual representation of a weight.
34//   <<: prints textual representation of a weight.
35//   Read(istream &): reads binary representation of a weight.
36//   Write(ostrem &): writes binary representation of a weight.
37//   Hash: maps weight to ssize_t.
38//   ApproxEqual: approximate equality (for inexact weights)
39//   Quantize: quantizes wrt delta (for inexact weights)
40//   Divide: for all a,b,c s.t. Times(a, b) == c
41//     --> b = Divide(c, a, DIVIDE_LEFT) if a left semiring and b.Member()
42//     --> a = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a.Member()
43//     --> b = Divide(c, a)
44//           = Divide(c, a, DIVIDE_ANY)
45//           = Divide(c, a, DIVIDE_LEFT)
46//           = Divide(c, a, DIVIDE_RIGHT) if a commutative semiring
47//   ReverseWeight: the type of the corresponding reverse weight.
48//     Typically the same type as Weight for a (both left and right) semiring.
49//     For the left string semiring, it is the right string semiring.
50//   Reverse: a mapping from Weight to ReverseWeight s.t.
51//     --> Reverse(Reverse(a)) = a
52//     --> Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
53//     --> Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
54//     Typically the identity mapping in a (both left and right) semiring.
55//     In the left string semiring, it maps to the reverse string
56//     in the right string semiring.
57//   Properties: specifies additional properties that hold:
58//      LeftSemiring: indicates weights form a left semiring.
59//      RightSemiring: indicates weights form a right semiring.
60//      TimesCommutative: for all a,b: Times(a,b) == Times(b,a)
61//      Idempotent: for all a: Plus(a, a) == a.
62//      Path Property: for all a, b: Plus(a, b) == a or Plus(a, b) == b.
63
64
65#ifndef FST_LIB_WEIGHT_H__
66#define FST_LIB_WEIGHT_H__
67
68#include <cctype>
69#include <cmath>
70#include <iostream>
71#include <sstream>
72
73#include "fst/lib/compat.h"
74
75#include "fst/lib/util.h"
76
77namespace fst {
78
79//
80// CONSTANT DEFINITIONS
81//
82
83// A representable float near .001
84const float kDelta =                   1.0F/1024.0F;
85
86// For all a,b,c: Times(c, Plus(a,b)) = Plus(Times(c,a), Times(c, b))
87const uint64 kLeftSemiring =           0x0000000000000001ULL;
88
89// For all a,b,c: Times(Plus(a,b), c) = Plus(Times(a,c), Times(b, c))
90const uint64 kRightSemiring =          0x0000000000000002ULL;
91
92const uint64 kSemiring = kLeftSemiring | kRightSemiring;
93
94// For all a,b: Times(a,b) = Times(b,a)
95const uint64 kCommutative =       0x0000000000000004ULL;
96
97// For all a: Plus(a, a) = a
98const uint64 kIdempotent =             0x0000000000000008ULL;
99
100// For all a,b: Plus(a,b) = a or Plus(a,b) = b
101const uint64 kPath =                   0x0000000000000010ULL;
102
103
104// Determines direction of division.
105enum DivideType { DIVIDE_LEFT,   // left division
106                  DIVIDE_RIGHT,  // right division
107                  DIVIDE_ANY };  // division in a commutative semiring
108
109// NATURAL ORDER
110//
111// By definition:
112//                 a <= b iff a + b = a
113// The natural order is a monotonic and negative partial order iff the
114// semiring is idempotent and (left and right) distributive. It is a
115// total order iff the semiring has the path property. See Mohri,
116// "Semiring Framework and Algorithms for Shortest-Distance Problems",
117// Journal of Automata, Languages and Combinatorics 7(3):321-350,
118// 2002. We define the strict version of this order below.
119
120template <class W>
121class NaturalLess {
122 public:
123  typedef W Weight;
124
125  NaturalLess() {
126    uint64 props = kIdempotent | kLeftSemiring | kRightSemiring;
127    if ((W::Properties() & props) != props)
128      LOG(ERROR) << "NaturalLess: Weight type is not idempotent and "
129                 << "(left and right) distributive: " << W::Type();
130  }
131
132  bool operator()(const W &w1, const W &w2) const {
133    return (Plus(w1, w2) == w1) && w1 != w2;
134  }
135};
136
137}  // namespace fst;
138
139#endif  // FST_LIB_WEIGHT_H__
140