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 77 namespace fst { 78 79 // 80 // CONSTANT DEFINITIONS 81 // 82 83 // A representable float near .001 84 const 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)) 87 const uint64 kLeftSemiring = 0x0000000000000001ULL; 88 89 // For all a,b,c: Times(Plus(a,b), c) = Plus(Times(a,c), Times(b, c)) 90 const uint64 kRightSemiring = 0x0000000000000002ULL; 91 92 const uint64 kSemiring = kLeftSemiring | kRightSemiring; 93 94 // For all a,b: Times(a,b) = Times(b,a) 95 const uint64 kCommutative = 0x0000000000000004ULL; 96 97 // For all a: Plus(a, a) = a 98 const uint64 kIdempotent = 0x0000000000000008ULL; 99 100 // For all a,b: Plus(a,b) = a or Plus(a,b) = b 101 const uint64 kPath = 0x0000000000000010ULL; 102 103 104 // Determines direction of division. 105 enum 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 120 template <class W> 121 class NaturalLess { 122 public: 123 typedef W Weight; 124 NaturalLess()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 operator()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