1 // lexicographic-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 // Copyright 2005-2010 Google, Inc.
16 // Author: rws@google.com (Richard Sproat)
17 //
18 // \file
19 // Lexicographic weight set and associated semiring operation definitions.
20 //
21 // A lexicographic weight is a sequence of weights, each of which must have the
22 // path property and Times() must be (strongly) cancellative
23 // (for all a,b,c != Zero(): Times(c, a) = Times(c, b) => a = b,
24 // Times(a, c) = Times(b, c) => a = b).
25 // The + operation on two weights a and b is the lexicographically
26 // prior of a and b.
27
28 #ifndef FST_LIB_LEXICOGRAPHIC_WEIGHT_H__
29 #define FST_LIB_LEXICOGRAPHIC_WEIGHT_H__
30
31 #include <string>
32
33 #include <fst/pair-weight.h>
34 #include <fst/weight.h>
35
36
37 namespace fst {
38
39 template<class W1, class W2>
40 class LexicographicWeight : public PairWeight<W1, W2> {
41 public:
42 using PairWeight<W1, W2>::Value1;
43 using PairWeight<W1, W2>::Value2;
44 using PairWeight<W1, W2>::SetValue1;
45 using PairWeight<W1, W2>::SetValue2;
46 using PairWeight<W1, W2>::Zero;
47 using PairWeight<W1, W2>::One;
48 using PairWeight<W1, W2>::NoWeight;
49 using PairWeight<W1, W2>::Quantize;
50 using PairWeight<W1, W2>::Reverse;
51
52 typedef LexicographicWeight<typename W1::ReverseWeight,
53 typename W2::ReverseWeight>
54 ReverseWeight;
55
LexicographicWeight()56 LexicographicWeight() {}
57
LexicographicWeight(const PairWeight<W1,W2> & w)58 LexicographicWeight(const PairWeight<W1, W2>& w)
59 : PairWeight<W1, W2>(w) {}
60
LexicographicWeight(W1 w1,W2 w2)61 LexicographicWeight(W1 w1, W2 w2) : PairWeight<W1, W2>(w1, w2) {
62 uint64 props = kPath;
63 if ((W1::Properties() & props) != props) {
64 FSTERROR() << "LexicographicWeight must "
65 << "have the path property: " << W1::Type();
66 SetValue1(W1::NoWeight());
67 }
68 if ((W2::Properties() & props) != props) {
69 FSTERROR() << "LexicographicWeight must "
70 << "have the path property: " << W2::Type();
71 SetValue2(W2::NoWeight());
72 }
73 }
74
Zero()75 static const LexicographicWeight<W1, W2> &Zero() {
76 static const LexicographicWeight<W1, W2> zero(PairWeight<W1, W2>::Zero());
77 return zero;
78 }
79
One()80 static const LexicographicWeight<W1, W2> &One() {
81 static const LexicographicWeight<W1, W2> one(PairWeight<W1, W2>::One());
82 return one;
83 }
84
NoWeight()85 static const LexicographicWeight<W1, W2> &NoWeight() {
86 static const LexicographicWeight<W1, W2> no_weight(
87 PairWeight<W1, W2>::NoWeight());
88 return no_weight;
89 }
90
Type()91 static const string &Type() {
92 static const string type = W1::Type() + "_LT_" + W2::Type();
93 return type;
94 }
95
Member()96 bool Member() const {
97 if (!Value1().Member() || !Value2().Member()) return false;
98 // Lexicographic weights cannot mix zeroes and non-zeroes.
99 if (Value1() == W1::Zero() && Value2() == W2::Zero()) return true;
100 if (Value1() != W1::Zero() && Value2() != W2::Zero()) return true;
101 return false;
102 }
103
104 LexicographicWeight<W1, W2> Quantize(float delta = kDelta) const {
105 return PairWeight<W1, W2>::Quantize();
106 }
107
Reverse()108 ReverseWeight Reverse() const {
109 return PairWeight<W1, W2>::Reverse();
110 }
111
Properties()112 static uint64 Properties() {
113 uint64 props1 = W1::Properties();
114 uint64 props2 = W2::Properties();
115 return props1 & props2 & (kLeftSemiring | kRightSemiring | kPath |
116 kIdempotent | kCommutative);
117 }
118 };
119
120 template <class W1, class W2>
Plus(const LexicographicWeight<W1,W2> & w,const LexicographicWeight<W1,W2> & v)121 inline LexicographicWeight<W1, W2> Plus(const LexicographicWeight<W1, W2> &w,
122 const LexicographicWeight<W1, W2> &v) {
123 if (!w.Member() || !v.Member())
124 return LexicographicWeight<W1, W2>::NoWeight();
125 NaturalLess<W1> less1;
126 NaturalLess<W2> less2;
127 if (less1(w.Value1(), v.Value1())) return w;
128 if (less1(v.Value1(), w.Value1())) return v;
129 if (less2(w.Value2(), v.Value2())) return w;
130 if (less2(v.Value2(), w.Value2())) return v;
131 return w;
132 }
133
134 template <class W1, class W2>
Times(const LexicographicWeight<W1,W2> & w,const LexicographicWeight<W1,W2> & v)135 inline LexicographicWeight<W1, W2> Times(const LexicographicWeight<W1, W2> &w,
136 const LexicographicWeight<W1, W2> &v) {
137 return LexicographicWeight<W1, W2>(Times(w.Value1(), v.Value1()),
138 Times(w.Value2(), v.Value2()));
139 }
140
141 template <class W1, class W2>
142 inline LexicographicWeight<W1, W2> Divide(const LexicographicWeight<W1, W2> &w,
143 const LexicographicWeight<W1, W2> &v,
144 DivideType typ = DIVIDE_ANY) {
145 return LexicographicWeight<W1, W2>(Divide(w.Value1(), v.Value1(), typ),
146 Divide(w.Value2(), v.Value2(), typ));
147 }
148
149 } // namespace fst
150
151 #endif // FST_LIB_LEXICOGRAPHIC_WEIGHT_H__
152