1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// lexicographic-weight.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: rws@google.com (Richard Sproat) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Lexicographic weight set and associated semiring operation definitions. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A lexicographic weight is a sequence of weights, each of which must have the 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// path property and Times() must be (strongly) cancellative 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (for all a,b,c != Zero(): Times(c, a) = Times(c, b) => a = b, 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Times(a, c) = Times(b, c) => a = b). 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The + operation on two weights a and b is the lexicographically 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// prior of a and b. 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_LEXICOGRAPHIC_WEIGHT_H__ 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_LEXICOGRAPHIC_WEIGHT_H__ 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <string> 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/pair-weight.h> 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/weight.h> 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class W1, class W2> 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass LexicographicWeight : public PairWeight<W1, W2> { 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::Value1; 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::Value2; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::SetValue1; 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::SetValue2; 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::Zero; 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::One; 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::NoWeight; 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::Quantize; 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using PairWeight<W1, W2>::Reverse; 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef LexicographicWeight<typename W1::ReverseWeight, 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename W2::ReverseWeight> 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReverseWeight; 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LexicographicWeight() {} 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LexicographicWeight(const PairWeight<W1, W2>& w) 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : PairWeight<W1, W2>(w) {} 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LexicographicWeight(W1 w1, W2 w2) : PairWeight<W1, W2>(w1, w2) { 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props = kPath; 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((W1::Properties() & props) != props) { 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "LexicographicWeight must " 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "have the path property: " << W1::Type(); 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetValue1(W1::NoWeight()); 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((W2::Properties() & props) != props) { 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "LexicographicWeight must " 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << "have the path property: " << W2::Type(); 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetValue2(W2::NoWeight()); 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const LexicographicWeight<W1, W2> &Zero() { 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const LexicographicWeight<W1, W2> zero(PairWeight<W1, W2>::Zero()); 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return zero; 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const LexicographicWeight<W1, W2> &One() { 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const LexicographicWeight<W1, W2> one(PairWeight<W1, W2>::One()); 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return one; 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const LexicographicWeight<W1, W2> &NoWeight() { 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const LexicographicWeight<W1, W2> no_weight( 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PairWeight<W1, W2>::NoWeight()); 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return no_weight; 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const string &Type() { 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const string type = W1::Type() + "_LT_" + W2::Type(); 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return type; 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Member() const { 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!Value1().Member() || !Value2().Member()) return false; 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Lexicographic weights cannot mix zeroes and non-zeroes. 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Value1() == W1::Zero() && Value2() == W2::Zero()) return true; 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Value1() != W1::Zero() && Value2() != W2::Zero()) return true; 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return false; 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LexicographicWeight<W1, W2> Quantize(float delta = kDelta) const { 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return PairWeight<W1, W2>::Quantize(); 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReverseWeight Reverse() const { 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return PairWeight<W1, W2>::Reverse(); 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static uint64 Properties() { 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props1 = W1::Properties(); 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props2 = W2::Properties(); 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return props1 & props2 & (kLeftSemiring | kRightSemiring | kPath | 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kIdempotent | kCommutative); 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W1, class W2> 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline LexicographicWeight<W1, W2> Plus(const LexicographicWeight<W1, W2> &w, 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const LexicographicWeight<W1, W2> &v) { 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!w.Member() || !v.Member()) 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return LexicographicWeight<W1, W2>::NoWeight(); 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalLess<W1> less1; 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalLess<W2> less2; 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (less1(w.Value1(), v.Value1())) return w; 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (less1(v.Value1(), w.Value1())) return v; 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (less2(w.Value2(), v.Value2())) return w; 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (less2(v.Value2(), w.Value2())) return v; 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w; 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W1, class W2> 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline LexicographicWeight<W1, W2> Times(const LexicographicWeight<W1, W2> &w, 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const LexicographicWeight<W1, W2> &v) { 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return LexicographicWeight<W1, W2>(Times(w.Value1(), v.Value1()), 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Times(w.Value2(), v.Value2())); 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W1, class W2> 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline LexicographicWeight<W1, W2> Divide(const LexicographicWeight<W1, W2> &w, 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const LexicographicWeight<W1, W2> &v, 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DivideType typ = DIVIDE_ANY) { 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return LexicographicWeight<W1, W2>(Divide(w.Value1(), v.Value1(), typ), 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Divide(w.Value2(), v.Value2(), typ)); 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_LEXICOGRAPHIC_WEIGHT_H__ 152