encode.h revision a8a167d6883e4acee42619e0bbfd811984f6e94d
1// encode.h 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14// 15// 16// \file 17// Class to encode and decoder an fst. 18 19#ifndef FST_LIB_ENCODE_H__ 20#define FST_LIB_ENCODE_H__ 21 22#include "fst/lib/map.h" 23#include "fst/lib/rmfinalepsilon.h" 24 25namespace fst { 26 27static const uint32 kEncodeLabels = 0x00001; 28static const uint32 kEncodeWeights = 0x00002; 29 30enum EncodeType { ENCODE = 1, DECODE = 2 }; 31 32// Identifies stream data as an encode table (and its endianity) 33static const int32 kEncodeMagicNumber = 2129983209; 34 35 36// The following class encapsulates implementation details for the 37// encoding and decoding of label/weight tuples used for encoding 38// and decoding of Fsts. The EncodeTable is bidirectional. I.E it 39// stores both the Tuple of encode labels and weights to a unique 40// label, and the reverse. 41template <class A> class EncodeTable { 42 public: 43 typedef typename A::Label Label; 44 typedef typename A::Weight Weight; 45 46 // Encoded data consists of arc input/output labels and arc weight 47 struct Tuple { 48 Tuple() {} 49 Tuple(Label ilabel_, Label olabel_, Weight weight_) 50 : ilabel(ilabel_), olabel(olabel_), weight(weight_) {} 51 Tuple(const Tuple& tuple) 52 : ilabel(tuple.ilabel), olabel(tuple.olabel), weight(tuple.weight) {} 53 54 Label ilabel; 55 Label olabel; 56 Weight weight; 57 }; 58 59 // Comparison object for hashing EncodeTable Tuple(s). 60 class TupleEqual { 61 public: 62 bool operator()(const Tuple* x, const Tuple* y) const { 63 return (x->ilabel == y->ilabel && 64 x->olabel == y->olabel && 65 x->weight == y->weight); 66 } 67 }; 68 69 // Hash function for EncodeTabe Tuples. Based on the encode flags 70 // we either hash the labels, weights or compbination of them. 71 class TupleKey { 72 static const int kPrime = 7853; 73 public: 74 TupleKey() 75 : encode_flags_(kEncodeLabels | kEncodeWeights) {} 76 77 TupleKey(const TupleKey& key) 78 : encode_flags_(key.encode_flags_) {} 79 80 explicit TupleKey(uint32 encode_flags) 81 : encode_flags_(encode_flags) {} 82 83 size_t operator()(const Tuple* x) const { 84 int lshift = x->ilabel % kPrime; 85 int rshift = sizeof(size_t) - lshift; 86 size_t hash = x->ilabel << lshift; 87 if (encode_flags_ & kEncodeLabels) hash ^= x->olabel >> rshift; 88 if (encode_flags_ & kEncodeWeights) hash ^= x->weight.Hash(); 89 return hash; 90 } 91 92 private: 93 int32 encode_flags_; 94 }; 95 96 typedef std::unordered_map<const Tuple*, Label, TupleKey, TupleEqual> EncodeHash; 97 98 explicit EncodeTable(uint32 encode_flags) 99 : flags_(encode_flags), 100 encode_hash_(1024, TupleKey(encode_flags)) {} 101 102 ~EncodeTable() { 103 for (size_t i = 0; i < encode_tuples_.size(); ++i) { 104 delete encode_tuples_[i]; 105 } 106 } 107 108 // Given an arc encode either input/ouptut labels or input/costs or both 109 Label Encode(const A &arc) { 110 const Tuple tuple(arc.ilabel, 111 flags_ & kEncodeLabels ? arc.olabel : 0, 112 flags_ & kEncodeWeights ? arc.weight : Weight::One()); 113 typename EncodeHash::const_iterator it = encode_hash_.find(&tuple); 114 if (it == encode_hash_.end()) { 115 encode_tuples_.push_back(new Tuple(tuple)); 116 encode_hash_[encode_tuples_.back()] = encode_tuples_.size(); 117 return encode_tuples_.size(); 118 } else { 119 return it->second; 120 } 121 } 122 123 // Given an encode arc Label decode back to input/output labels and costs 124 const Tuple* Decode(Label key) { 125 return key <= (Label)encode_tuples_.size() ? encode_tuples_[key - 1] : 0; 126 } 127 128 bool Write(ostream &strm, const string &source) const { 129 WriteType(strm, kEncodeMagicNumber); 130 WriteType(strm, flags_); 131 int64 size = encode_tuples_.size(); 132 WriteType(strm, size); 133 for (size_t i = 0; i < size; ++i) { 134 const Tuple* tuple = encode_tuples_[i]; 135 WriteType(strm, tuple->ilabel); 136 WriteType(strm, tuple->olabel); 137 tuple->weight.Write(strm); 138 } 139 strm.flush(); 140 if (!strm) 141 LOG(ERROR) << "EncodeTable::Write: write failed: " << source; 142 return strm; 143 } 144 145 bool Read(istream &strm, const string &source) { 146 encode_tuples_.clear(); 147 encode_hash_.clear(); 148 int32 magic_number = 0; 149 ReadType(strm, &magic_number); 150 if (magic_number != kEncodeMagicNumber) { 151 LOG(ERROR) << "EncodeTable::Read: Bad encode table header: " << source; 152 return false; 153 } 154 ReadType(strm, &flags_); 155 int64 size; 156 ReadType(strm, &size); 157 if (!strm) { 158 LOG(ERROR) << "EncodeTable::Read: read failed: " << source; 159 return false; 160 } 161 for (size_t i = 0; i < size; ++i) { 162 Tuple* tuple = new Tuple(); 163 ReadType(strm, &tuple->ilabel); 164 ReadType(strm, &tuple->olabel); 165 tuple->weight.Read(strm); 166 encode_tuples_.push_back(tuple); 167 encode_hash_[encode_tuples_.back()] = encode_tuples_.size(); 168 } 169 if (!strm) 170 LOG(ERROR) << "EncodeTable::Read: read failed: " << source; 171 return strm; 172 } 173 174 uint32 flags() const { return flags_; } 175 private: 176 uint32 flags_; 177 vector<Tuple*> encode_tuples_; 178 EncodeHash encode_hash_; 179 180 DISALLOW_EVIL_CONSTRUCTORS(EncodeTable); 181}; 182 183 184// A mapper to encode/decode weighted transducers. Encoding of an 185// Fst is useful for performing classical determinization or minimization 186// on a weighted transducer by treating it as an unweighted acceptor over 187// encoded labels. 188// 189// The Encode mapper stores the encoding in a local hash table (EncodeTable) 190// This table is shared (and reference counted) between the encoder and 191// decoder. A decoder has read only access to the EncodeTable. 192// 193// The EncodeMapper allows on the fly encoding of the machine. As the 194// EncodeTable is generated the same table may by used to decode the machine 195// on the fly. For example in the following sequence of operations 196// 197// Encode -> Determinize -> Decode 198// 199// we will use the encoding table generated during the encode step in the 200// decode, even though the encoding is not complete. 201// 202template <class A> class EncodeMapper { 203 typedef typename A::Weight Weight; 204 typedef typename A::Label Label; 205 public: 206 EncodeMapper(uint32 flags, EncodeType type) 207 : ref_count_(1), flags_(flags), type_(type), 208 table_(new EncodeTable<A>(flags)) {} 209 210 EncodeMapper(const EncodeMapper& mapper) 211 : ref_count_(mapper.ref_count_ + 1), 212 flags_(mapper.flags_), 213 type_(mapper.type_), 214 table_(mapper.table_) { } 215 216 // Copy constructor but setting the type, typically to DECODE 217 EncodeMapper(const EncodeMapper& mapper, EncodeType type) 218 : ref_count_(mapper.ref_count_ + 1), 219 flags_(mapper.flags_), 220 type_(type), 221 table_(mapper.table_) { } 222 223 ~EncodeMapper() { 224 if (--ref_count_ == 0) delete table_; 225 } 226 227 A operator()(const A &arc) { 228 if (type_ == ENCODE) { // labels and/or weights to single label 229 if ((arc.nextstate == kNoStateId && !(flags_ & kEncodeWeights)) || 230 (arc.nextstate == kNoStateId && (flags_ & kEncodeWeights) && 231 arc.weight == Weight::Zero())) { 232 return arc; 233 } else { 234 Label label = table_->Encode(arc); 235 return A(label, 236 flags_ & kEncodeLabels ? label : arc.olabel, 237 flags_ & kEncodeWeights ? Weight::One() : arc.weight, 238 arc.nextstate); 239 } 240 } else { 241 if (arc.nextstate == kNoStateId) { 242 return arc; 243 } else { 244 const typename EncodeTable<A>::Tuple* tuple = 245 table_->Decode(arc.ilabel); 246 return A(tuple->ilabel, 247 flags_ & kEncodeLabels ? tuple->olabel : arc.olabel, 248 flags_ & kEncodeWeights ? tuple->weight : arc.weight, 249 arc.nextstate);; 250 } 251 } 252 } 253 254 uint64 Properties(uint64 props) { 255 uint64 mask = kFstProperties; 256 if (flags_ & kEncodeLabels) 257 mask &= kILabelInvariantProperties & kOLabelInvariantProperties; 258 if (flags_ & kEncodeWeights) 259 mask &= kILabelInvariantProperties & kWeightInvariantProperties & 260 (type_ == ENCODE ? kAddSuperFinalProperties : 261 kRmSuperFinalProperties); 262 return props & mask; 263 } 264 265 266 MapFinalAction FinalAction() const { 267 return (type_ == ENCODE && (flags_ & kEncodeWeights)) ? 268 MAP_REQUIRE_SUPERFINAL : MAP_NO_SUPERFINAL; 269 } 270 271 uint32 flags() const { return flags_; } 272 EncodeType type() const { return type_; } 273 274 bool Write(ostream &strm, const string& source) { 275 return table_->Write(strm, source); 276 } 277 278 bool Write(const string& filename) { 279 ofstream strm(filename.c_str()); 280 if (!strm) { 281 LOG(ERROR) << "EncodeMap: Can't open file: " << filename; 282 return false; 283 } 284 return Write(strm, filename); 285 } 286 287 static EncodeMapper<A> *Read(istream &strm, 288 const string& source, EncodeType type) { 289 EncodeTable<A> *table = new EncodeTable<A>(0); 290 bool r = table->Read(strm, source); 291 return r ? new EncodeMapper(table->flags(), type, table) : 0; 292 } 293 294 static EncodeMapper<A> *Read(const string& filename, EncodeType type) { 295 ifstream strm(filename.c_str()); 296 if (!strm) { 297 LOG(ERROR) << "EncodeMap: Can't open file: " << filename; 298 return false; 299 } 300 return Read(strm, filename, type); 301 } 302 303 private: 304 uint32 ref_count_; 305 uint32 flags_; 306 EncodeType type_; 307 EncodeTable<A>* table_; 308 309 explicit EncodeMapper(uint32 flags, EncodeType type, EncodeTable<A> *table) 310 : ref_count_(1), flags_(flags), type_(type), table_(table) {} 311 void operator=(const EncodeMapper &); // Disallow. 312}; 313 314 315// Complexity: O(nstates + narcs) 316template<class A> inline 317void Encode(MutableFst<A> *fst, EncodeMapper<A>* mapper) { 318 Map(fst, mapper); 319} 320 321 322template<class A> inline 323void Decode(MutableFst<A>* fst, const EncodeMapper<A>& mapper) { 324 Map(fst, EncodeMapper<A>(mapper, DECODE)); 325 RmFinalEpsilon(fst); 326} 327 328 329// On the fly label and/or weight encoding of input Fst 330// 331// Complexity: 332// - Constructor: O(1) 333// - Traversal: O(nstates_visited + narcs_visited), assuming constant 334// time to visit an input state or arc. 335template <class A> 336class EncodeFst : public MapFst<A, A, EncodeMapper<A> > { 337 public: 338 typedef A Arc; 339 typedef EncodeMapper<A> C; 340 341 EncodeFst(const Fst<A> &fst, EncodeMapper<A>* encoder) 342 : MapFst<A, A, C>(fst, encoder, MapFstOptions()) {} 343 344 EncodeFst(const Fst<A> &fst, const EncodeMapper<A>& encoder) 345 : MapFst<A, A, C>(fst, encoder, MapFstOptions()) {} 346 347 EncodeFst(const EncodeFst<A> &fst) 348 : MapFst<A, A, C>(fst) {} 349 350 virtual EncodeFst<A> *Copy() const { return new EncodeFst(*this); } 351}; 352 353 354// On the fly label and/or weight encoding of input Fst 355// 356// Complexity: 357// - Constructor: O(1) 358// - Traversal: O(nstates_visited + narcs_visited), assuming constant 359// time to visit an input state or arc. 360template <class A> 361class DecodeFst : public MapFst<A, A, EncodeMapper<A> > { 362 public: 363 typedef A Arc; 364 typedef EncodeMapper<A> C; 365 366 DecodeFst(const Fst<A> &fst, const EncodeMapper<A>& encoder) 367 : MapFst<A, A, C>(fst, 368 EncodeMapper<A>(encoder, DECODE), 369 MapFstOptions()) {} 370 371 DecodeFst(const EncodeFst<A> &fst) 372 : MapFst<A, A, C>(fst) {} 373 374 virtual DecodeFst<A> *Copy() const { return new DecodeFst(*this); } 375}; 376 377 378// Specialization for EncodeFst. 379template <class A> 380class StateIterator< EncodeFst<A> > 381 : public StateIterator< MapFst<A, A, EncodeMapper<A> > > { 382 public: 383 explicit StateIterator(const EncodeFst<A> &fst) 384 : StateIterator< MapFst<A, A, EncodeMapper<A> > >(fst) {} 385}; 386 387 388// Specialization for EncodeFst. 389template <class A> 390class ArcIterator< EncodeFst<A> > 391 : public ArcIterator< MapFst<A, A, EncodeMapper<A> > > { 392 public: 393 ArcIterator(const EncodeFst<A> &fst, typename A::StateId s) 394 : ArcIterator< MapFst<A, A, EncodeMapper<A> > >(fst, s) {} 395}; 396 397 398// Specialization for DecodeFst. 399template <class A> 400class StateIterator< DecodeFst<A> > 401 : public StateIterator< MapFst<A, A, EncodeMapper<A> > > { 402 public: 403 explicit StateIterator(const DecodeFst<A> &fst) 404 : StateIterator< MapFst<A, A, EncodeMapper<A> > >(fst) {} 405}; 406 407 408// Specialization for DecodeFst. 409template <class A> 410class ArcIterator< DecodeFst<A> > 411 : public ArcIterator< MapFst<A, A, EncodeMapper<A> > > { 412 public: 413 ArcIterator(const DecodeFst<A> &fst, typename A::StateId s) 414 : ArcIterator< MapFst<A, A, EncodeMapper<A> > >(fst, s) {} 415}; 416 417 418// Useful aliases when using StdArc. 419typedef EncodeFst<StdArc> StdEncodeFst; 420 421typedef DecodeFst<StdArc> StdDecodeFst; 422 423} 424 425#endif // FST_LIB_ENCODE_H__ 426