1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// power-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: allauzen@google.com (Cyril Allauzen) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Cartesian power weight semiring operation definitions. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_POWER_WEIGHT_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_POWER_WEIGHT_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/tuple-weight.h> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/weight.h> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Cartesian power semiring: W ^ n 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Forms: 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - a left semimodule when W is a left semiring, 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - a right semimodule when W is a right semiring, 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - a bisemimodule when W is a semiring, 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// the free semimodule of rank n over W 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The Times operation is overloaded to provide the 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// left and right scalar products. 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W, unsigned int n> 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass PowerWeight : public TupleWeight<W, n> { 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using TupleWeight<W, n>::Zero; 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using TupleWeight<W, n>::One; 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using TupleWeight<W, n>::NoWeight; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using TupleWeight<W, n>::Quantize; 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using TupleWeight<W, n>::Reverse; 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef PowerWeight<typename W::ReverseWeight, n> ReverseWeight; 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight() {} 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight(const TupleWeight<W, n> &w) : TupleWeight<W, n>(w) {} 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson template <class Iterator> 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight(Iterator begin, Iterator end) : TupleWeight<W, n>(begin, end) {} 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const PowerWeight<W, n> &Zero() { 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const PowerWeight<W, n> zero(TupleWeight<W, n>::Zero()); 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return zero; 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const PowerWeight<W, n> &One() { 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const PowerWeight<W, n> one(TupleWeight<W, n>::One()); 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return one; 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const PowerWeight<W, n> &NoWeight() { 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const PowerWeight<W, n> no_weight(TupleWeight<W, n>::NoWeight()); 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return no_weight; 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static const string &Type() { 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static string type; 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (type.empty()) { 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson string power; 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Int64ToStr(n, &power); 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson type = W::Type() + "_^" + power; 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return type; 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static uint64 Properties() { 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props = W::Properties(); 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return props & (kLeftSemiring | kRightSemiring | 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kCommutative | kIdempotent); 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight<W, n> Quantize(float delta = kDelta) const { 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return TupleWeight<W, n>::Quantize(delta); 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReverseWeight Reverse() const { 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return TupleWeight<W, n>::Reverse(); 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Semiring plus operation 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W, unsigned int n> 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline PowerWeight<W, n> Plus(const PowerWeight<W, n> &w1, 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const PowerWeight<W, n> &w2) { 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight<W, n> w; 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < n; ++i) 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w.SetValue(i, Plus(w1.Value(i), w2.Value(i))); 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w; 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Semiring times operation 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W, unsigned int n> 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline PowerWeight<W, n> Times(const PowerWeight<W, n> &w1, 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const PowerWeight<W, n> &w2) { 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight<W, n> w; 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < n; ++i) 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w.SetValue(i, Times(w1.Value(i), w2.Value(i))); 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w; 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Semiring divide operation 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W, unsigned int n> 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline PowerWeight<W, n> Divide(const PowerWeight<W, n> &w1, 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const PowerWeight<W, n> &w2, 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DivideType type = DIVIDE_ANY) { 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight<W, n> w; 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < n; ++i) 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w.SetValue(i, Divide(w1.Value(i), w2.Value(i), type)); 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w; 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Semimodule left scalar product 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W, unsigned int n> 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline PowerWeight<W, n> Times(const W &s, const PowerWeight<W, n> &w) { 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight<W, n> sw; 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < n; ++i) 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson sw.SetValue(i, Times(s, w.Value(i))); 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w; 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Semimodule right scalar product 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W, unsigned int n> 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline PowerWeight<W, n> Times(const PowerWeight<W, n> &w, const W &s) { 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PowerWeight<W, n> ws; 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < n; ++i) 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ws.SetValue(i, Times(w.Value(i), s)); 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w; 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Semimodule dot product 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class W, unsigned int n> 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsoninline W DotProduct(const PowerWeight<W, n> &w1, 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const PowerWeight<W, n> &w2) { 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson W w = W::Zero(); 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < n; ++i) 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson w = Plus(w, Times(w1.Value(i), w2.Value(i))); 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return w; 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_POWER_WEIGHT_H__ 160