lexicographic-weight.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2
1474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// lexicographic-weight.h 2474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 3474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// Licensed under the Apache License, Version 2.0 (the "License"); 4474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// you may not use this file except in compliance with the License. 5474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// You may obtain a copy of the License at 6474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// 7474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// http://www.apache.org/licenses/LICENSE-2.0 8474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// 9474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// Unless required by applicable law or agreed to in writing, software 10474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// distributed under the License is distributed on an "AS IS" BASIS, 11474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// See the License for the specific language governing permissions and 13474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// limitations under the License. 14474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// 15474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// Copyright 2005-2010 Google, Inc. 16474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// Author: rws@google.com (Richard Sproat) 17474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// 18474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// \file 19474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// Lexicographic weight set and associated semiring operation definitions. 20474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// 21474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// A lexicographic weight is a sequence of weights, each of which must have the 22474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// path property and Times() must be (strongly) cancellative 23474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// (for all a,b,c != Zero(): Times(c, a) = Times(c, b) => a = b, 24474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// Times(a, c) = Times(b, c) => a = b). 25474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// The + operation on two weights a and b is the lexicographically 26474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org// prior of a and b. 27474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 286fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org#ifndef FST_LIB_LEXICOGRAPHIC_WEIGHT_H__ 29d348b8d765c019ee7250075d663a83db00c65c08tomfinegan@chromium.org#define FST_LIB_LEXICOGRAPHIC_WEIGHT_H__ 30474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 31474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#include <string> 32474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 33474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#include <fst/pair-weight.h> 34474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#include <fst/weight.h> 35474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 36474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 37474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgnamespace fst { 38474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 39474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgtemplate<class W1, class W2> 40474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgclass LexicographicWeight : public PairWeight<W1, W2> { 41474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org public: 42474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org using PairWeight<W1, W2>::Value1; 43474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org using PairWeight<W1, W2>::Value2; 44474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org using PairWeight<W1, W2>::SetValue1; 45fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org using PairWeight<W1, W2>::SetValue2; 46fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org using PairWeight<W1, W2>::Zero; 47fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org using PairWeight<W1, W2>::One; 48fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org using PairWeight<W1, W2>::NoWeight; 49fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org using PairWeight<W1, W2>::Quantize; 50fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org using PairWeight<W1, W2>::Reverse; 51fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org 52fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org typedef LexicographicWeight<typename W1::ReverseWeight, 53fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org typename W2::ReverseWeight> 54fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org ReverseWeight; 55474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 56474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org LexicographicWeight() {} 57474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 58474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org LexicographicWeight(const PairWeight<W1, W2>& w) 59474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org : PairWeight<W1, W2>(w) {} 60474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 61474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org LexicographicWeight(W1 w1, W2 w2) : PairWeight<W1, W2>(w1, w2) { 62474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org uint64 props = kPath; 63474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if ((W1::Properties() & props) != props) { 64474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org FSTERROR() << "LexicographicWeight must " 65474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org << "have the path property: " << W1::Type(); 66fa43a22c16ae2b81f2532c907fb9eb2c1cd2a373fgalligan@chromium.org SetValue1(W1::NoWeight()); 67474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 68474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if ((W2::Properties() & props) != props) { 69474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org FSTERROR() << "LexicographicWeight must " 70474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org << "have the path property: " << W2::Type(); 71474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org SetValue2(W2::NoWeight()); 72474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 73474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 74474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 75474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const LexicographicWeight<W1, W2> &Zero() { 76474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const LexicographicWeight<W1, W2> zero(PairWeight<W1, W2>::Zero()); 77474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return zero; 78474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 79474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 80474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const LexicographicWeight<W1, W2> &One() { 81474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const LexicographicWeight<W1, W2> one(PairWeight<W1, W2>::One()); 82474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return one; 83474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 84474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 85474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const LexicographicWeight<W1, W2> &NoWeight() { 86474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const LexicographicWeight<W1, W2> no_weight( 87474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org PairWeight<W1, W2>::NoWeight()); 88ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org return no_weight; 89474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 90474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 91474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const string &Type() { 92474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static const string type = W1::Type() + "_LT_" + W2::Type(); 93474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return type; 94474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 95474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 96474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org bool Member() const { 97474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (!Value1().Member() || !Value2().Member()) return false; 98474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org // Lexicographic weights cannot mix zeroes and non-zeroes. 99474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (Value1() == W1::Zero() && Value2() == W2::Zero()) return true; 100474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (Value1() != W1::Zero() && Value2() != W2::Zero()) return true; 101474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return false; 102474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org } 103474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 104474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org LexicographicWeight<W1, W2> Quantize(float delta = kDelta) const { 105ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org return PairWeight<W1, W2>::Quantize(); 106ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org } 107167514562bbce1eb0566271d6cb41d90d2b5ffa0hclam@chromium.org 108474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org ReverseWeight Reverse() const { 109474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return PairWeight<W1, W2>::Reverse(); 110ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org } 111474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 112474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org static uint64 Properties() { 113474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org uint64 props1 = W1::Properties(); 114474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org uint64 props2 = W2::Properties(); 115ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org return props1 & props2 & (kLeftSemiring | kRightSemiring | kPath | 116474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org kIdempotent | kCommutative); 117ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org } 118474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org}; 119ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org 120474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgtemplate <class W1, class W2> 121474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orginline LexicographicWeight<W1, W2> Plus(const LexicographicWeight<W1, W2> &w, 122474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org const LexicographicWeight<W1, W2> &v) { 123474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (!w.Member() || !v.Member()) 124474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return LexicographicWeight<W1, W2>::NoWeight(); 125474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org NaturalLess<W1> less1; 126474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org NaturalLess<W2> less2; 127474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (less1(w.Value1(), v.Value1())) return w; 128474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (less1(v.Value1(), w.Value1())) return v; 129474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (less2(w.Value2(), v.Value2())) return w; 130474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org if (less2(v.Value2(), w.Value2())) return v; 131474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return w; 132474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 133474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 134474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgtemplate <class W1, class W2> 1355c1d3b27608a3f3f6028c069b9bf066a4de474b6hclam@chromium.orginline LexicographicWeight<W1, W2> Times(const LexicographicWeight<W1, W2> &w, 136474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org const LexicographicWeight<W1, W2> &v) { 137474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return LexicographicWeight<W1, W2>(Times(w.Value1(), v.Value1()), 138474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org Times(w.Value2(), v.Value2())); 139474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 140474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 141ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.orgtemplate <class W1, class W2> 142474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orginline LexicographicWeight<W1, W2> Divide(const LexicographicWeight<W1, W2> &w, 143474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org const LexicographicWeight<W1, W2> &v, 144474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org DivideType typ = DIVIDE_ANY) { 145474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org return LexicographicWeight<W1, W2>(Divide(w.Value1(), v.Value1(), typ), 146474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org Divide(w.Value2(), v.Value2(), typ)); 147ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org} 148474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 149ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org} // namespace fst 150474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 151ed759d81a39febed3a8a395386639d54307504aagrunell@chromium.org#endif // FST_LIB_LEXICOGRAPHIC_WEIGHT_H__ 152474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org