1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// rational.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: riley@google.com (Michael Riley) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An Fst implementation and base interface for delayed unions, 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// concatenations and closures. 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_RATIONAL_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_RATIONAL_H__ 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <algorithm> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <string> 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/mutable-fst.h> 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/replace.h> 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/test-properties.h> 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef CacheOptions RationalFstOptions; 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This specifies whether to add the empty string. 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonenum ClosureType { CLOSURE_STAR = 0, // T* -> add the empty string 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson CLOSURE_PLUS = 1 }; // T+ -> don't add the empty string 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> class RationalFst; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> void Union(RationalFst<A> *fst1, const Fst<A> &fst2); 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> void Concat(RationalFst<A> *fst1, const Fst<A> &fst2); 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> void Concat(const Fst<A> &fst1, RationalFst<A> *fst2); 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> void Closure(RationalFst<A> *fst, ClosureType closure_type); 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Implementation class for delayed unions, concatenations and closures. 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class A> 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass RationalFstImpl : public FstImpl<A> { 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetType; 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetProperties; 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::WriteHeader; 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetInputSymbols; 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using FstImpl<A>::SetOutputSymbols; 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::Weight Weight; 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::Label Label; 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit RationalFstImpl(const RationalFstOptions &opts) 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : nonterminals_(0), 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson replace_(0), 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson replace_options_(opts, 0) { 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetType("rational"); 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(pair<Label, const Fst<A>*>(0, 0)); 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RationalFstImpl(const RationalFstImpl<A> &impl) 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : rfst_(impl.rfst_), 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nonterminals_(impl.nonterminals_), 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson replace_(impl.replace_ ? impl.replace_->Copy(true) : 0), 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson replace_options_(impl.replace_options_) { 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetType("rational"); 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.reserve(impl.fst_tuples_.size()); 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < impl.fst_tuples_.size(); ++i) 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(impl.fst_tuples_[i].first, 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson impl.fst_tuples_[i].second 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ? impl.fst_tuples_[i].second->Copy(true) 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : 0)); 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual ~RationalFstImpl() { 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (size_t i = 0; i < fst_tuples_.size(); ++i) 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (fst_tuples_[i].second) 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete fst_tuples_[i].second; 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (replace_) 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete replace_; 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Start() { return Replace()->Start(); } 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight Final(StateId s) { return Replace()->Final(s); } 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t NumArcs(StateId s) { return Replace()->NumArcs(s); } 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t NumInputEpsilons(StateId s) { 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return Replace()->NumInputEpsilons(s); 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_t NumOutputEpsilons(StateId s) { 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return Replace()->NumOutputEpsilons(s); 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 Properties() const { return Properties(kFstProperties); } 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Set error if found; return FST impl properties. 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 Properties(uint64 mask) const { 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((mask & kError) && Replace()->Properties(kError, false)) 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(kError, kError); 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return FstImpl<Arc>::Properties(mask); 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Implementation of UnionFst(fst1,fst2) 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void InitUnion(const Fst<A> &fst1, const Fst<A> &fst2) { 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (replace_) 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete replace_; 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props1 = fst1.Properties(kFstProperties, false); 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props2 = fst2.Properties(kFstProperties, false); 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetInputSymbols(fst1.InputSymbols()); 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetOutputSymbols(fst1.OutputSymbols()); 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetStart(0); 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetFinal(1, Weight::One()); 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetInputSymbols(fst1.InputSymbols()); 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetOutputSymbols(fst1.OutputSymbols()); 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nonterminals_ = 2; 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddArc(0, A(0, -1, Weight::One(), 1)); 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddArc(0, A(0, -2, Weight::One(), 1)); 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(-1, fst1.Copy())); 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(-2, fst2.Copy())); 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(UnionProperties(props1, props2, true), kCopyProperties); 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Implementation of ConcatFst(fst1,fst2) 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void InitConcat(const Fst<A> &fst1, const Fst<A> &fst2) { 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (replace_) 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete replace_; 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props1 = fst1.Properties(kFstProperties, false); 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props2 = fst2.Properties(kFstProperties, false); 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetInputSymbols(fst1.InputSymbols()); 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetOutputSymbols(fst1.OutputSymbols()); 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetStart(0); 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetFinal(2, Weight::One()); 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetInputSymbols(fst1.InputSymbols()); 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetOutputSymbols(fst1.OutputSymbols()); 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nonterminals_ = 2; 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddArc(0, A(0, -1, Weight::One(), 1)); 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddArc(1, A(0, -2, Weight::One(), 2)); 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(-1, fst1.Copy())); 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(-2, fst2.Copy())); 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(ConcatProperties(props1, props2, true), kCopyProperties); 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Implementation of ClosureFst(fst, closure_type) 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void InitClosure(const Fst<A> &fst, ClosureType closure_type) { 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (replace_) 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete replace_; 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props = fst.Properties(kFstProperties, false); 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetInputSymbols(fst.InputSymbols()); 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetOutputSymbols(fst.OutputSymbols()); 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (closure_type == CLOSURE_STAR) { 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetStart(0); 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetFinal(0, Weight::One()); 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddArc(0, A(0, -1, Weight::One(), 0)); 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddState(); 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetStart(0); 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetFinal(1, Weight::One()); 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddArc(0, A(0, -1, Weight::One(), 1)); 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.AddArc(1, A(0, 0, Weight::One(), 0)); 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetInputSymbols(fst.InputSymbols()); 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson rfst_.SetOutputSymbols(fst.OutputSymbols()); 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(-1, fst.Copy())); 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson nonterminals_ = 1; 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true), 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kCopyProperties); 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Implementation of Union(Fst &, RationalFst *) 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void AddUnion(const Fst<A> &fst) { 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (replace_) 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete replace_; 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props1 = FstImpl<A>::Properties(); 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props2 = fst.Properties(kFstProperties, false); 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<A> afst; 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.AddState(); 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.AddState(); 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.SetStart(0); 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.SetFinal(1, Weight::One()); 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++nonterminals_; 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1)); 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Union(&rfst_, afst); 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(-nonterminals_, fst.Copy())); 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(UnionProperties(props1, props2, true), kCopyProperties); 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Implementation of Concat(Fst &, RationalFst *) 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void AddConcat(const Fst<A> &fst, bool append) { 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (replace_) 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete replace_; 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props1 = FstImpl<A>::Properties(); 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props2 = fst.Properties(kFstProperties, false); 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<A> afst; 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.AddState(); 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.AddState(); 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.SetStart(0); 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.SetFinal(1, Weight::One()); 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++nonterminals_; 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1)); 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (append) 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(&rfst_, afst); 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Concat(afst, &rfst_); 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_.push_back(make_pair(-nonterminals_, fst.Copy())); 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(ConcatProperties(props1, props2, true), kCopyProperties); 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Implementation of Closure(RationalFst *, closure_type) 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void AddClosure(ClosureType closure_type) { 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (replace_) 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete replace_; 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props = FstImpl<A>::Properties(); 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Closure(&rfst_, closure_type); 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true), 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kCopyProperties); 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Returns the underlying ReplaceFst. 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReplaceFst<A> *Replace() const { 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!replace_) { 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst_tuples_[0].second = rfst_.Copy(); 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson replace_ = new ReplaceFst<A>(fst_tuples_, replace_options_); 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return replace_; 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VectorFst<A> rfst_; // rational topology machine; uses neg. nonterminals 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Label nonterminals_; // # of nonterminals used 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Contains the nonterminals and their corresponding FSTs. 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable vector<pair<Label, const Fst<A>*> > fst_tuples_; 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable ReplaceFst<A> *replace_; // Underlying ReplaceFst 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ReplaceFstOptions<A> replace_options_; // Options for creating 'replace_' 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const RationalFstImpl<A> &impl); // disallow 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Parent class for the delayed rational operations - delayed union, 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// concatenation, and closure. 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This class attaches interface to implementation and handles 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// reference counting, delegating most methods to ImplToFst. 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass RationalFst : public ImplToFst< RationalFstImpl<A> > { 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend class StateIterator< RationalFst<A> >; 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend class ArcIterator< RationalFst<A> >; 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend void Union<>(RationalFst<A> *fst1, const Fst<A> &fst2); 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend void Concat<>(RationalFst<A> *fst1, const Fst<A> &fst2); 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend void Concat<>(const Fst<A> &fst1, RationalFst<A> *fst2); 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson friend void Closure<>(RationalFst<A> *fst, ClosureType closure_type); 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef RationalFstImpl<A> Impl; 279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void InitStateIterator(StateIteratorData<A> *data) const { 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetImpl()->Replace()->InitStateIterator(data); 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetImpl()->Replace()->InitArcIterator(s, data); 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson protected: 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RationalFst() 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ImplToFst<Impl>(new Impl(RationalFstOptions())) {} 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit RationalFst(const RationalFstOptions &opts) 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ImplToFst<Impl>(new Impl(opts)) {} 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // See Fst<>::Copy() for doc. 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson RationalFst(const RationalFst<A> &fst , bool safe = false) 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ImplToFst<Impl>(fst, safe) {} 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Makes visible to friends. 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); } 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void operator=(const RationalFst<A> &fst); // disallow 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specialization for RationalFst. 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StateIterator< RationalFst<A> > 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public StateIterator< ReplaceFst<A> > { 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit StateIterator(const RationalFst<A> &fst) 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : StateIterator< ReplaceFst<A> >(*(fst.GetImpl()->Replace())) {} 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specialization for RationalFst. 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ArcIterator< RationalFst<A> > 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public CacheArcIterator< ReplaceFst<A> > { 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcIterator(const RationalFst<A> &fst, StateId s) 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ArcIterator< ReplaceFst<A> >(*(fst.GetImpl()->Replace()), s) {} 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_RATIONAL_H__ 331