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
37namespace fst {
38
39template<class W1, class W2>
40class 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
56  LexicographicWeight() {}
57
58  LexicographicWeight(const PairWeight<W1, W2>& w)
59      : PairWeight<W1, W2>(w) {}
60
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
75  static const LexicographicWeight<W1, W2> &Zero() {
76    static const LexicographicWeight<W1, W2> zero(PairWeight<W1, W2>::Zero());
77    return zero;
78  }
79
80  static const LexicographicWeight<W1, W2> &One() {
81    static const LexicographicWeight<W1, W2> one(PairWeight<W1, W2>::One());
82    return one;
83  }
84
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
91  static const string &Type() {
92    static const string type = W1::Type() + "_LT_" + W2::Type();
93    return type;
94  }
95
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
108  ReverseWeight Reverse() const {
109    return PairWeight<W1, W2>::Reverse();
110  }
111
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
120template <class W1, class W2>
121inline 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
134template <class W1, class W2>
135inline 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
141template <class W1, class W2>
142inline 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