accumulator.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2
14fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// accumulator.h 24fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 34fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// Licensed under the Apache License, Version 2.0 (the "License"); 44fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// you may not use this file except in compliance with the License. 54fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// You may obtain a copy of the License at 64fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// 74fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// http://www.apache.org/licenses/LICENSE-2.0 84fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// 94fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// Unless required by applicable law or agreed to in writing, software 104fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// distributed under the License is distributed on an "AS IS" BASIS, 114fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// See the License for the specific language governing permissions and 134fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// limitations under the License. 144fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// 154fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// Copyright 2005-2010 Google, Inc. 164fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// Author: riley@google.com (Michael Riley) 174fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// 184fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// \file 194fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// Classes to accumulate arc weights. Useful for weight lookahead. 204fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 214fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#ifndef FST_LIB_ACCUMULATOR_H__ 224fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#define FST_LIB_ACCUMULATOR_H__ 234fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 244fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <algorithm> 254fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <functional> 264fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <unordered_map> 274fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorusing std::tr1::unordered_map; 284fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorusing std::tr1::unordered_multimap; 294fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <vector> 304fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorusing std::vector; 314fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 324fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <fst/arcfilter.h> 334fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <fst/arcsort.h> 344fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <fst/dfs-visit.h> 3542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman#include <fst/expanded-fst.h> 364fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor#include <fst/replace.h> 374fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 384fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregornamespace fst { 394fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 404fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// This class accumulates arc weights using the semiring Plus(). 414fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregortemplate <class A> 424fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorclass DefaultAccumulator { 434fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor public: 444fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef A Arc; 454fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename A::StateId StateId; 464fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename A::Weight Weight; 474fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 484fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor DefaultAccumulator() {} 494fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 504fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor DefaultAccumulator(const DefaultAccumulator<A> &acc) {} 514fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 524fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void Init(const Fst<A>& fst, bool copy = false) {} 534fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 548419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor void SetState(StateId) {} 554fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 568419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor Weight Sum(Weight w, Weight v) { 578419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor return Plus(w, v); 586c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor } 594fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 604fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor template <class ArcIterator> 614fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, 624fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t end) { 638419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor Weight sum = w; 644fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor aiter->Seek(begin); 654fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for (ssize_t pos = begin; pos < end; aiter->Next(), ++pos) 664fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor sum = Plus(sum, aiter->Value().weight); 674fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return sum; 684fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 694fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 704fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor bool Error() const { return false; } 714fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 724fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor private: 734fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void operator=(const DefaultAccumulator<A> &); // Disallow 744fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor}; 754fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 764fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 774fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// This class accumulates arc weights using the log semiring Plus() 784fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// assuming an arc weight has a WeightConvert specialization to 794fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// and from log64 weights. 804fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregortemplate <class A> 814fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorclass LogAccumulator { 824fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor public: 834fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef A Arc; 844fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename A::StateId StateId; 854fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename A::Weight Weight; 864fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 8742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman LogAccumulator() {} 8842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 8942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman LogAccumulator(const LogAccumulator<A> &acc) {} 9042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 9142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman void Init(const Fst<A>& fst, bool copy = false) {} 9242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 9342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman void SetState(StateId) {} 9442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 9542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman Weight Sum(Weight w, Weight v) { 9642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return LogPlus(w, v); 9742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 9842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 9942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman template <class ArcIterator> 10042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, 10142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman ssize_t end) { 10242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman Weight sum = w; 10342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman aiter->Seek(begin); 10442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman for (ssize_t pos = begin; pos < end; aiter->Next(), ++pos) 10542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman sum = LogPlus(sum, aiter->Value().weight); 10642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return sum; 10742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 10842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 10942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman bool Error() const { return false; } 11042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 11142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman private: 11242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double LogPosExp(double x) { return log(1.0F + exp(-x)); } 11342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 11442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman Weight LogPlus(Weight w, Weight v) { 11542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double f1 = to_log_weight_(w).Value(); 11642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double f2 = to_log_weight_(v).Value(); 11742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman if (f1 > f2) 11842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return to_weight_(f2 - LogPosExp(f1 - f2)); 11942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman else 12042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return to_weight_(f1 - LogPosExp(f2 - f1)); 12142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 12242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 12342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman WeightConvert<Weight, Log64Weight> to_log_weight_; 12442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman WeightConvert<Log64Weight, Weight> to_weight_; 12542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 12642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman void operator=(const LogAccumulator<A> &); // Disallow 12742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman}; 12842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 12942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 13042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman// Stores shareable data for fast log accumulator copies. 13142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedmanclass FastLogAccumulatorData { 13242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman public: 13342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman FastLogAccumulatorData() {} 13442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 13542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman vector<double> *Weights() { return &weights_; } 13642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman vector<ssize_t> *WeightPositions() { return &weight_positions_; } 13742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double *WeightEnd() { return &(weights_[weights_.size() - 1]); }; 13842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman int RefCount() const { return ref_count_.count(); } 13942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman int IncrRefCount() { return ref_count_.Incr(); } 14042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman int DecrRefCount() { return ref_count_.Decr(); } 14142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 14242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman private: 14342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman // Cummulative weight per state for all states s.t. # of arcs > 14442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman // arc_limit_ with arcs in order. Special first element per state 14542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman // being Log64Weight::Zero(); 14642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman vector<double> weights_; 14742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman // Maps from state to corresponding beginning weight position in 1484fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // weights_. Position -1 means no pre-computed weights for that 1494fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // state. 1504fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor vector<ssize_t> weight_positions_; 1514fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor RefCounter ref_count_; // Reference count. 1524fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 1534fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor DISALLOW_COPY_AND_ASSIGN(FastLogAccumulatorData); 1544fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor}; 1554fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 1564fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 1574fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// This class accumulates arc weights using the log semiring Plus() 15842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman// assuming an arc weight has a WeightConvert specialization to and 15942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman// from log64 weights. The member function Init(fst) has to be called 16042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman// to setup pre-computed weight information. 16142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedmantemplate <class A> 16242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedmanclass FastLogAccumulator { 16342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman public: 16442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman typedef A Arc; 16542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman typedef typename A::StateId StateId; 16642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman typedef typename A::Weight Weight; 1674fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 1684fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor explicit FastLogAccumulator(ssize_t arc_limit = 20, ssize_t arc_period = 10) 1694fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor : arc_limit_(arc_limit), 1704fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor arc_period_(arc_period), 1714fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor data_(new FastLogAccumulatorData()), 1724fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_(false) {} 1734fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 1744fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor FastLogAccumulator(const FastLogAccumulator<A> &acc) 17542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman : arc_limit_(acc.arc_limit_), 1764fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor arc_period_(acc.arc_period_), 1774fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor data_(acc.data_), 1784fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_(acc.error_) { 17948d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman data_->IncrRefCount(); 18048d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman } 18148d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman 1823d4a7c9bf856774fb43d724a3353c5a24297f866Eli Friedman ~FastLogAccumulator() { 1833d4a7c9bf856774fb43d724a3353c5a24297f866Eli Friedman if (!data_->DecrRefCount()) 1843d4a7c9bf856774fb43d724a3353c5a24297f866Eli Friedman delete data_; 1853d4a7c9bf856774fb43d724a3353c5a24297f866Eli Friedman } 1863d4a7c9bf856774fb43d724a3353c5a24297f866Eli Friedman 18748d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman void SetState(StateId s) { 18848d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman vector<double> &weights = *data_->Weights(); 18942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman vector<ssize_t> &weight_positions = *data_->WeightPositions(); 19042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 19142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman if (weight_positions.size() <= s) { 19242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman FSTERROR() << "FastLogAccumulator::SetState: invalid state id."; 19342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman error_ = true; 19442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return; 19542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 19642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 19742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman ssize_t pos = weight_positions[s]; 19842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman if (pos >= 0) 19942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman state_weights_ = &(weights[pos]); 20042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman else 20142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman state_weights_ = 0; 20242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 20342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 20442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman Weight Sum(Weight w, Weight v) { 20542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return LogPlus(w, v); 20642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 20742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 20842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman template <class ArcIterator> 20942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, 21042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman ssize_t end) { 21142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman if (error_) return Weight::NoWeight(); 21242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman Weight sum = w; 21342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman // Finds begin and end of pre-stored weights 21442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman ssize_t index_begin = -1, index_end = -1; 21542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman ssize_t stored_begin = end, stored_end = end; 21642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman if (state_weights_ != 0) { 2174fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor index_begin = begin > 0 ? (begin - 1)/ arc_period_ + 1 : 0; 2184fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor index_end = end / arc_period_; 2194fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor stored_begin = index_begin * arc_period_; 2204fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor stored_end = index_end * arc_period_; 2214fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2224fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // Computes sum before pre-stored weights 2234fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (begin < stored_begin) { 2244fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t pos_end = min(stored_begin, end); 22564f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor aiter->Seek(begin); 22664f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor for (ssize_t pos = begin; pos < pos_end; aiter->Next(), ++pos) 22764f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor sum = LogPlus(sum, aiter->Value().weight); 22864f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor } 22964f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor // Computes sum between pre-stored weights 23064f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor if (stored_begin < stored_end) { 23164f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor sum = LogPlus(sum, LogMinus(state_weights_[index_end], 23264f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor state_weights_[index_begin])); 2334fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2344fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // Computes sum after pre-stored weights 2354fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (stored_end < end) { 2364fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t pos_start = max(stored_begin, stored_end); 2374fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor aiter->Seek(pos_start); 2384fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for (ssize_t pos = pos_start; pos < end; aiter->Next(), ++pos) 2394fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor sum = LogPlus(sum, aiter->Value().weight); 2404fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2414fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return sum; 2424fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2434fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 2444fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor template <class F> 2454fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void Init(const F &fst, bool copy = false) { 2464fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (copy) 24742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return; 24842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman vector<double> &weights = *data_->Weights(); 24942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman vector<ssize_t> &weight_positions = *data_->WeightPositions(); 2504fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (!weights.empty() || arc_limit_ < arc_period_) { 2514fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor FSTERROR() << "FastLogAccumulator: initialization error."; 2524fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_ = true; 2534fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return; 2544fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2554fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weight_positions.reserve(CountStates(fst)); 2564fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 2574fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t weight_position = 0; 2584fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for(StateIterator<F> siter(fst); !siter.Done(); siter.Next()) { 2594fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor StateId s = siter.Value(); 2604fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (fst.NumArcs(s) >= arc_limit_) { 26142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double sum = FloatLimits<double>::kPosInfinity; 26242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman weight_positions.push_back(weight_position); 26342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman weights.push_back(sum); 2644fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ++weight_position; 2654fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t narcs = 0; 2664fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for(ArcIterator<F> aiter(fst, s); !aiter.Done(); aiter.Next()) { 2674fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor const A &arc = aiter.Value(); 2684fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor sum = LogPlus(sum, arc.weight); 2694fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // Stores cumulative weight distribution per arc_period_. 2704fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (++narcs % arc_period_ == 0) { 2714fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights.push_back(sum); 2724fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ++weight_position; 2734fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2744fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 27542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } else { 27642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman weight_positions.push_back(-1); 27742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 27842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 2794fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2804fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 2814fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor bool Error() const { return error_; } 2824fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 2834fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor private: 2844fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double LogPosExp(double x) { 2854fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return x == FloatLimits<double>::kPosInfinity ? 2864fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 0.0 : log(1.0F + exp(-x)); 2874fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2884fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 2894fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double LogMinusExp(double x) { 2904fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return x == FloatLimits<double>::kPosInfinity ? 29148d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman 0.0 : log(1.0F - exp(-x)); 2924fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 2934fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 2944fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight LogPlus(Weight w, Weight v) { 2954fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double f1 = to_log_weight_(w).Value(); 29642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double f2 = to_log_weight_(v).Value(); 29742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman if (f1 > f2) 29842f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return to_weight_(f2 - LogPosExp(f1 - f2)); 29942f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman else 30042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return to_weight_(f1 - LogPosExp(f2 - f1)); 30142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman } 30242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 3034fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double LogPlus(double f1, Weight v) { 30442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double f2 = to_log_weight_(v).Value(); 30542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman if (f1 == FloatLimits<double>::kPosInfinity) 30642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman return f2; 3074fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor else if (f1 > f2) 3086620a628b0a02c78741b8f31790d4c1186aa4038Douglas Gregor return f2 - LogPosExp(f1 - f2); 3096620a628b0a02c78741b8f31790d4c1186aa4038Douglas Gregor else 3104fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return f1 - LogPosExp(f2 - f1); 3114fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 3124fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3134fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight LogMinus(double f1, double f2) { 3144fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (f1 >= f2) { 3154fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor FSTERROR() << "FastLogAcumulator::LogMinus: f1 >= f2 with f1 = " << f1 3164fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor << " and f2 = " << f2; 3174fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_ = true; 3184fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return Weight::NoWeight(); 3194fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 3204fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (f2 == FloatLimits<double>::kPosInfinity) 3216620a628b0a02c78741b8f31790d4c1186aa4038Douglas Gregor return to_weight_(f1); 3224fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor else 3234fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return to_weight_(f1 - LogMinusExp(f2 - f1)); 3244fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 3254fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3264fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor WeightConvert<Weight, Log64Weight> to_log_weight_; 3274fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor WeightConvert<Log64Weight, Weight> to_weight_; 3284fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3294fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t arc_limit_; // Minimum # of arcs to pre-compute state 3304fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t arc_period_; // Save cumulative weights per 'arc_period_'. 33142f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman bool init_; // Cumulative weights initialized? 33242f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman FastLogAccumulatorData *data_; 33342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman double *state_weights_; 33442f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman bool error_; 33542f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman 33642f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman void operator=(const FastLogAccumulator<A> &); // Disallow 3374fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor}; 3384fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3394fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3404fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// Stores shareable data for cache log accumulator copies. 3414fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// All copies share the same cache. 3424fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregortemplate <class A> 3434fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorclass CacheLogAccumulatorData { 3444fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor public: 3454fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef A Arc; 3464fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename A::StateId StateId; 3474fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename A::Weight Weight; 3484fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3494fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor CacheLogAccumulatorData(bool gc, size_t gc_limit) 3504fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor : cache_gc_(gc), cache_limit_(gc_limit), cache_size_(0) {} 3514fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3524fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ~CacheLogAccumulatorData() { 3534fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for(typename unordered_map<StateId, CacheState>::iterator it = cache_.begin(); 3544fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor it != cache_.end(); 3554fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ++it) 3566620a628b0a02c78741b8f31790d4c1186aa4038Douglas Gregor delete it->second.weights; 3574fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 3584fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3594fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor bool CacheDisabled() const { return cache_gc_ && cache_limit_ == 0; } 3606620a628b0a02c78741b8f31790d4c1186aa4038Douglas Gregor 3614fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor vector<double> *GetWeights(StateId s) { 3624fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typename unordered_map<StateId, CacheState>::iterator it = cache_.find(s); 3634fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (it != cache_.end()) { 3644fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor it->second.recent = true; 3654fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return it->second.weights; 3664fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } else { 3676620a628b0a02c78741b8f31790d4c1186aa4038Douglas Gregor return 0; 3684fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 3694fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 3704fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3714fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void AddWeights(StateId s, vector<double> *weights) { 3724fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (cache_gc_ && cache_size_ >= cache_limit_) 37342f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman GC(false); 3744fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor cache_.insert(make_pair(s, CacheState(weights, true))); 3754fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (cache_gc_) 3764fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor cache_size_ += weights->capacity() * sizeof(double); 3774fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 3784fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3794fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor int RefCount() const { return ref_count_.count(); } 3804fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor int IncrRefCount() { return ref_count_.Incr(); } 3814fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor int DecrRefCount() { return ref_count_.Decr(); } 38248d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman 3834fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor private: 3844fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // Cached information for a given state. 3854fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor struct CacheState { 3864fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor vector<double>* weights; // Accumulated weights for this state. 38742f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman bool recent; // Has this state been accessed since last GC? 3884fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3894fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor CacheState(vector<double> *w, bool r) : weights(w), recent(r) {} 39042f42c0dd5cf71fbfc6fa282d03079a902f6e342Eli Friedman }; 3914fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 3924fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // Garbage collect: Delete from cache states that have not been 3934fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // accessed since the last GC ('free_recent = false') until 3944fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // 'cache_size_' is 2/3 of 'cache_limit_'. If it does not free enough 3954fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // memory, start deleting recently accessed states. 3964fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void GC(bool free_recent) { 3974fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor size_t cache_target = (2 * cache_limit_)/3 + 1; 3984fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typename unordered_map<StateId, CacheState>::iterator it = cache_.begin(); 3994fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor while (it != cache_.end() && cache_size_ > cache_target) { 4004fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor CacheState &cs = it->second; 4014fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (free_recent || !cs.recent) { 4024fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor cache_size_ -= cs.weights->capacity() * sizeof(double); 4034fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor delete cs.weights; 40448d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman cache_.erase(it++); 4054fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } else { 4064fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor cs.recent = false; 4074fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ++it; 4084fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4094fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4104fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (!free_recent && cache_size_ > cache_target) 4114fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor GC(true); 4124fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4134fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4148419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor unordered_map<StateId, CacheState> cache_; // Cache 4158419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor bool cache_gc_; // Enable garbage collection 4168419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor size_t cache_limit_; // # of bytes cached 4178419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor size_t cache_size_; // # of bytes allowed before GC 4184fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor RefCounter ref_count_; 4194fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 42048d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman DISALLOW_COPY_AND_ASSIGN(CacheLogAccumulatorData); 4214fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor}; 4224fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4234fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// This class accumulates arc weights using the log semiring Plus() 4244fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// has a WeightConvert specialization to and from log64 weights. It 4254fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// is similar to the FastLogAccumator. However here, the accumulated 4264fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// weights are pre-computed and stored only for the states that are 4278419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor// visited. The member function Init(fst) has to be called to setup 4288419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor// this accumulator. 4298419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregortemplate <class A> 4308419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregorclass CacheLogAccumulator { 4318419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor public: 4328419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor typedef A Arc; 4338419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor typedef typename A::StateId StateId; 4348419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor typedef typename A::Weight Weight; 4358419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor 4368419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor explicit CacheLogAccumulator(ssize_t arc_limit = 10, bool gc = false, 4378419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor size_t gc_limit = 10 * 1024 * 1024) 4388419fa3af97208eb00f0cd6c62354ce4ff986677Douglas Gregor : arc_limit_(arc_limit), fst_(0), data_( 4396c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor new CacheLogAccumulatorData<A>(gc, gc_limit)), s_(kNoStateId), 4406c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor error_(false) {} 4416c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor 4426c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor CacheLogAccumulator(const CacheLogAccumulator<A> &acc) 4436c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor : arc_limit_(acc.arc_limit_), fst_(acc.fst_ ? acc.fst_->Copy() : 0), 4446c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor data_(acc.data_), s_(kNoStateId), error_(acc.error_) { 4456c9c94053132e5ca0655124b70f1c386a332e71dDouglas Gregor data_->IncrRefCount(); 4464fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4474fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4484fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ~CacheLogAccumulator() { 4494fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (fst_) 4504fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor delete fst_; 4514fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (!data_->DecrRefCount()) 4524fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor delete data_; 4534fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4544fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4554fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor // Arg 'arc_limit' specifies minimum # of arcs to pre-compute state. 4564fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void Init(const Fst<A> &fst, bool copy = false) { 4574fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (copy) { 4584fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor delete fst_; 4594fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } else if (fst_) { 4604fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor FSTERROR() << "CacheLogAccumulator: initialization error."; 4614fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_ = true; 4624fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return; 4634fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4644fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor fst_ = fst.Copy(); 4654fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4664fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4674fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void SetState(StateId s, int depth = 0) { 4684fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (s == s_) 4694fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return; 4704fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor s_ = s; 4714fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4724fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (data_->CacheDisabled() || error_) { 4734fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_ = 0; 4744fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return; 4754fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4764fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4774fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (!fst_) { 4784fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor FSTERROR() << "CacheLogAccumulator::SetState: incorrectly initialized."; 4794fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_ = true; 4804fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_ = 0; 4814fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return; 4824fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4834fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4844fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_ = data_->GetWeights(s); 4854fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if ((weights_ == 0) && (fst_->NumArcs(s) >= arc_limit_)) { 4864fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_ = new vector<double>; 4874fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_->reserve(fst_->NumArcs(s) + 1); 4884fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_->push_back(FloatLimits<double>::kPosInfinity); 4894fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor data_->AddWeights(s, weights_); 4904fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4914fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 49264f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor 4934fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight Sum(Weight w, Weight v) { 49464f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor return LogPlus(w, v); 4954fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 4964fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 4974fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor template <class Iterator> 4984fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight Sum(Weight w, Iterator *aiter, ssize_t begin, 4994fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t end) { 5004fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (weights_ == 0) { 5014fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight sum = w; 5024fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor aiter->Seek(begin); 5034fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for (ssize_t pos = begin; pos < end; aiter->Next(), ++pos) 5044fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor sum = LogPlus(sum, aiter->Value().weight); 5054fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return sum; 5064fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } else { 5074fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (weights_->size() <= end) 5084fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for (aiter->Seek(weights_->size() - 1); 5094fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_->size() <= end; 5104fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor aiter->Next()) 5114fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_->push_back(LogPlus(weights_->back(), 5124fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor aiter->Value().weight)); 5134fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return LogPlus(w, LogMinus((*weights_)[end], (*weights_)[begin])); 5144fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5154fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5164fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5174fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor template <class Iterator> 51848d14a222276fad5279e994d1a062f36ae6fcbceEli Friedman size_t LowerBound(double w, Iterator *aiter) { 5194fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (weights_ != 0) { 52064f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor return lower_bound(weights_->begin() + 1, 5214fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor weights_->end(), 5224fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor w, 5234fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor std::greater<double>()) 5244fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor - weights_->begin() - 1; 5254fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } else { 5264fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor size_t n = 0; 5274fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double x = FloatLimits<double>::kPosInfinity; 5284fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for(aiter->Reset(); !aiter->Done(); aiter->Next(), ++n) { 5294fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor x = LogPlus(x, aiter->Value().weight); 5304fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (x < w) break; 53164f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor } 53264f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor return n; 53364f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor } 5344fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5354fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5364fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor bool Error() const { return error_; } 5374fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5384fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor private: 5394fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double LogPosExp(double x) { 5404fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return x == FloatLimits<double>::kPosInfinity ? 5414fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 0.0 : log(1.0F + exp(-x)); 5424fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5434fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5444fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double LogMinusExp(double x) { 5454fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return x == FloatLimits<double>::kPosInfinity ? 5464fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 0.0 : log(1.0F - exp(-x)); 5474fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5484fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5494fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight LogPlus(Weight w, Weight v) { 5504fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double f1 = to_log_weight_(w).Value(); 5514fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double f2 = to_log_weight_(v).Value(); 5524fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (f1 > f2) 5534fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return to_weight_(f2 - LogPosExp(f1 - f2)); 55464f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor else 5554fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return to_weight_(f1 - LogPosExp(f2 - f1)); 5564fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 55764f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor 55864f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor double LogPlus(double f1, Weight v) { 5594fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor double f2 = to_log_weight_(v).Value(); 5604fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (f1 == FloatLimits<double>::kPosInfinity) 56164f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor return f2; 5624fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor else if (f1 > f2) 5634fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return f2 - LogPosExp(f1 - f2); 56464f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor else 5654fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return f1 - LogPosExp(f2 - f1); 5664fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5674fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5684fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Weight LogMinus(double f1, double f2) { 56964f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor if (f1 >= f2) { 5704fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor FSTERROR() << "CacheLogAcumulator::LogMinus: f1 >= f2 with f1 = " << f1 5714fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor << " and f2 = " << f2; 5724fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_ = true; 5734fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return Weight::NoWeight(); 5744fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5754fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (f2 == FloatLimits<double>::kPosInfinity) 5764fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return to_weight_(f1); 5774fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor else 5784fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return to_weight_(f1 - LogMinusExp(f2 - f1)); 5794fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 5804fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5814fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor WeightConvert<Weight, Log64Weight> to_log_weight_; 5824fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor WeightConvert<Log64Weight, Weight> to_weight_; 5834fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5844fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ssize_t arc_limit_; // Minimum # of arcs to cache a state 58564f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor vector<double> *weights_; // Accumulated weights for cur. state 58664f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor const Fst<A>* fst_; // Input fst 5874fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor CacheLogAccumulatorData<A> *data_; // Cache data 5884fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor StateId s_; // Current state 5894fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor bool error_; 5904fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5914fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void operator=(const CacheLogAccumulator<A> &); // Disallow 59264f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor}; 5934fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 5944fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 59564f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor// Stores shareable data for replace accumulator copies. 5964fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregortemplate <class Accumulator, class T> 5974fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorclass ReplaceAccumulatorData { 5984fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor public: 5994fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename Accumulator::Arc Arc; 6004fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename Arc::StateId StateId; 6014fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename Arc::Label Label; 60264f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor typedef T StateTable; 6034fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename T::StateTuple StateTuple; 60464f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor 6054fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ReplaceAccumulatorData() : state_table_(0) {} 6064fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6074fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ReplaceAccumulatorData(const vector<Accumulator*> &accumulators) 6084fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor : state_table_(0), accumulators_(accumulators) {} 6094fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6104fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ~ReplaceAccumulatorData() { 6114fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for (size_t i = 0; i < fst_array_.size(); ++i) 6124fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor delete fst_array_[i]; 6134fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for (size_t i = 0; i < accumulators_.size(); ++i) 6144fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor delete accumulators_[i]; 6154fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 6164fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6174fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor void Init(const vector<pair<Label, const Fst<Arc>*> > &fst_tuples, 6184fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor const StateTable *state_table) { 6194fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor state_table_ = state_table; 6204fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor accumulators_.resize(fst_tuples.size()); 6214fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor for (size_t i = 0; i < accumulators_.size(); ++i) { 6224fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (!accumulators_[i]) 6234fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor accumulators_[i] = new Accumulator; 6244fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor accumulators_[i]->Init(*(fst_tuples[i].second)); 6254fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor fst_array_.push_back(fst_tuples[i].second->Copy()); 6264fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 6274fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 6284fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6294fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor const StateTuple &GetTuple(StateId s) const { 6304fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor return state_table_->Tuple(s); 6314fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor } 6324fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6334fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor Accumulator *GetAccumulator(size_t i) { return accumulators_[i]; } 6344fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6354fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor const Fst<Arc> *GetFst(size_t i) const { return fst_array_[i]; } 6364fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6374fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor int RefCount() const { return ref_count_.count(); } 6384fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor int IncrRefCount() { return ref_count_.Incr(); } 6394fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor int DecrRefCount() { return ref_count_.Decr(); } 6404fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6414fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor private: 6424fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor const T * state_table_; 6434fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor vector<Accumulator*> accumulators_; 6444fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor vector<const Fst<Arc>*> fst_array_; 6454fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor RefCounter ref_count_; 6464fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6474fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor DISALLOW_COPY_AND_ASSIGN(ReplaceAccumulatorData); 6484fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor}; 6494fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6504fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// This class accumulates weights in a ReplaceFst. The 'Init' method 6514fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// takes as input the argument used to build the ReplaceFst and the 6524fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// ReplaceFst state table. It uses accumulators of type 'Accumulator' 6534fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor// in the underlying FSTs. 6544fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregortemplate <class Accumulator, 6554fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor class T = DefaultReplaceStateTable<typename Accumulator::Arc> > 6564fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregorclass ReplaceAccumulator { 6574fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor public: 6584fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename Accumulator::Arc Arc; 6594fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename Arc::StateId StateId; 6604fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename Arc::Label Label; 6614fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename Arc::Weight Weight; 6624fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef T StateTable; 6634fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor typedef typename T::StateTuple StateTuple; 6644fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6654fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ReplaceAccumulator() 6664fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor : init_(false), data_(new ReplaceAccumulatorData<Accumulator, T>()), 6674fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_(false) {} 6684fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6694fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ReplaceAccumulator(const vector<Accumulator*> &accumulators) 6704fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor : init_(false), 6714fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor data_(new ReplaceAccumulatorData<Accumulator, T>(accumulators)), 6724fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor error_(false) {} 6734fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6744fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ReplaceAccumulator(const ReplaceAccumulator<Accumulator, T> &acc) 6754fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor : init_(acc.init_), data_(acc.data_), error_(acc.error_) { 6764fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (!init_) 67764f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor FSTERROR() << "ReplaceAccumulator: can't copy unintialized accumulator"; 6784fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor data_->IncrRefCount(); 67964f650062fbe5e2bc6fb6d341c46a2ec0284694fDouglas Gregor } 6804fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor 6814fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor ~ReplaceAccumulator() { 6824fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor if (!data_->DecrRefCount()) 6834fe0c8e9c76b96e7aff21696a40dacc09d0237bcDouglas Gregor delete data_; 684 } 685 686 // Does not take ownership of the state table, the state table 687 // is own by the ReplaceFst 688 void Init(const vector<pair<Label, const Fst<Arc>*> > &fst_tuples, 689 const StateTable *state_table) { 690 init_ = true; 691 data_->Init(fst_tuples, state_table); 692 } 693 694 void SetState(StateId s) { 695 if (!init_) { 696 FSTERROR() << "ReplaceAccumulator::SetState: incorrectly initialized."; 697 error_ = true; 698 return; 699 } 700 StateTuple tuple = data_->GetTuple(s); 701 fst_id_ = tuple.fst_id - 1; // Replace FST ID is 1-based 702 data_->GetAccumulator(fst_id_)->SetState(tuple.fst_state); 703 if ((tuple.prefix_id != 0) && 704 (data_->GetFst(fst_id_)->Final(tuple.fst_state) != Weight::Zero())) { 705 offset_ = 1; 706 offset_weight_ = data_->GetFst(fst_id_)->Final(tuple.fst_state); 707 } else { 708 offset_ = 0; 709 offset_weight_ = Weight::Zero(); 710 } 711 } 712 713 Weight Sum(Weight w, Weight v) { 714 if (error_) return Weight::NoWeight(); 715 return data_->GetAccumulator(fst_id_)->Sum(w, v); 716 } 717 718 template <class ArcIterator> 719 Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, 720 ssize_t end) { 721 if (error_) return Weight::NoWeight(); 722 Weight sum = begin == end ? Weight::Zero() 723 : data_->GetAccumulator(fst_id_)->Sum( 724 w, aiter, begin ? begin - offset_ : 0, end - offset_); 725 if (begin == 0 && end != 0 && offset_ > 0) 726 sum = Sum(offset_weight_, sum); 727 return sum; 728 } 729 730 bool Error() const { return error_; } 731 732 private: 733 bool init_; 734 ReplaceAccumulatorData<Accumulator, T> *data_; 735 Label fst_id_; 736 size_t offset_; 737 Weight offset_weight_; 738 bool error_; 739 740 void operator=(const ReplaceAccumulator<Accumulator, T> &); // Disallow 741}; 742 743} // namespace fst 744 745#endif // FST_LIB_ACCUMULATOR_H__ 746