Home | History | Annotate | Download | only in fst 
      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 (at) 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 
     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 
    120 template <class W1, class W2>
    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>
    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