/usr/include/fst/state-map.h is in libfst-dev 1.5.3+r3-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 | // See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Class to map over/transform states e.g., sort transitions.
//
// Consider using when operation does not change the number of states.
#ifndef FST_LIB_STATE_MAP_H_
#define FST_LIB_STATE_MAP_H_
#include <algorithm>
#include <string>
#include <unordered_map>
#include <utility>
#include <fst/arc-map.h>
#include <fst/cache.h>
#include <fst/mutable-fst.h>
namespace fst {
// StateMapper Interface - class determinies how states are mapped.
// Useful for implementing operations that do not change the number of states.
//
// class StateMapper {
// public:
// typedef A FromArc;
// typedef B ToArc;
//
// // Typical constructor
// StateMapper(const Fst<A> &fst);
// // Required copy constructor that allows updating Fst argument;
// // pass only if relevant and changed.
// StateMapper(const StateMapper &mapper, const Fst<A> *fst = 0);
//
// // Specifies initial state of result
// B::StateId Start() const;
// // Specifies state's final weight in result
// B::Weight Final(B::StateId s) const;
//
// // These methods iterate through a state's arcs in result
// // Specifies state to iterate over
// void SetState(B::StateId s);
// // End of arcs?
// bool Done() const;
// // Current arc
// const B &Value() const;
// // Advance to next arc (when !Done)
// void Next();
//
// // Specifies input symbol table action the mapper requires (see above).
// MapSymbolsAction InputSymbolsAction() const;
// // Specifies output symbol table action the mapper requires (see above).
// MapSymbolsAction OutputSymbolsAction() const;
// // This specifies the known properties of an Fst mapped by this
// // mapper. It takes as argument the input Fst's known properties.
// uint64 Properties(uint64 props) const;
// };
//
// We include a various state map versions below. One dimension of
// variation is whether the mapping mutates its input, writes to a
// new result Fst, or is an on-the-fly Fst. Another dimension is how
// we pass the mapper. We allow passing the mapper by pointer
// for cases that we need to change the state of the user's mapper.
// We also include map versions that pass the mapper
// by value or const reference when this suffices.
// Maps an arc type A using a mapper function object C, passed
// by pointer. This version modifies its Fst input.
template <class A, class C>
void StateMap(MutableFst<A> *fst, C *mapper) {
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
fst->SetInputSymbols(0);
if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
fst->SetOutputSymbols(0);
if (fst->Start() == kNoStateId) return;
uint64 props = fst->Properties(kFstProperties, false);
fst->SetStart(mapper->Start());
for (StateId s = 0; s < fst->NumStates(); ++s) {
mapper->SetState(s);
fst->DeleteArcs(s);
for (; !mapper->Done(); mapper->Next()) fst->AddArc(s, mapper->Value());
fst->SetFinal(s, mapper->Final(s));
}
fst->SetProperties(mapper->Properties(props), kFstProperties);
}
// Maps an arc type A using a mapper function object C, passed
// by value. This version modifies its Fst input.
template <class A, class C>
void StateMap(MutableFst<A> *fst, C mapper) {
StateMap(fst, &mapper);
}
// Maps an arc type A to an arc type B using mapper function
// object C, passed by pointer. This version writes the mapped
// input Fst to an output MutableFst.
template <class A, class B, class C>
void StateMap(const Fst<A> &ifst, MutableFst<B> *ofst, C *mapper) {
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
ofst->DeleteStates();
if (mapper->InputSymbolsAction() == MAP_COPY_SYMBOLS)
ofst->SetInputSymbols(ifst.InputSymbols());
else if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
ofst->SetInputSymbols(0);
if (mapper->OutputSymbolsAction() == MAP_COPY_SYMBOLS)
ofst->SetOutputSymbols(ifst.OutputSymbols());
else if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
ofst->SetOutputSymbols(0);
uint64 iprops = ifst.Properties(kCopyProperties, false);
if (ifst.Start() == kNoStateId) {
if (iprops & kError) ofst->SetProperties(kError, kError);
return;
}
// Add all states.
if (ifst.Properties(kExpanded, false)) ofst->ReserveStates(CountStates(ifst));
for (StateIterator<Fst<A>> siter(ifst); !siter.Done(); siter.Next())
ofst->AddState();
ofst->SetStart(mapper->Start());
for (StateIterator<Fst<A>> siter(ifst); !siter.Done(); siter.Next()) {
StateId s = siter.Value();
mapper->SetState(s);
for (; !mapper->Done(); mapper->Next()) ofst->AddArc(s, mapper->Value());
ofst->SetFinal(s, mapper->Final(s));
}
uint64 oprops = ofst->Properties(kFstProperties, false);
ofst->SetProperties(mapper->Properties(iprops) | oprops, kFstProperties);
}
// Maps an arc type A to an arc type B using mapper function
// object C, passed by value. This version writes the mapped input
// Fst to an output MutableFst.
template <class A, class B, class C>
void StateMap(const Fst<A> &ifst, MutableFst<B> *ofst, C mapper) {
StateMap(ifst, ofst, &mapper);
}
typedef CacheOptions StateMapFstOptions;
template <class A, class B, class C>
class StateMapFst;
// Implementation of delayed StateMapFst.
template <class A, class B, class C>
class StateMapFstImpl : public CacheImpl<B> {
public:
using FstImpl<B>::SetType;
using FstImpl<B>::SetProperties;
using FstImpl<B>::SetInputSymbols;
using FstImpl<B>::SetOutputSymbols;
using CacheImpl<B>::PushArc;
using CacheImpl<B>::HasArcs;
using CacheImpl<B>::HasFinal;
using CacheImpl<B>::HasStart;
using CacheImpl<B>::SetArcs;
using CacheImpl<B>::SetFinal;
using CacheImpl<B>::SetStart;
friend class StateIterator<StateMapFst<A, B, C>>;
typedef B Arc;
typedef typename B::Weight Weight;
typedef typename B::StateId StateId;
StateMapFstImpl(const Fst<A> &fst, const C &mapper,
const StateMapFstOptions &opts)
: CacheImpl<B>(opts),
fst_(fst.Copy()),
mapper_(new C(mapper, fst_)),
own_mapper_(true) {
Init();
}
StateMapFstImpl(const Fst<A> &fst, C *mapper, const StateMapFstOptions &opts)
: CacheImpl<B>(opts),
fst_(fst.Copy()),
mapper_(mapper),
own_mapper_(false) {
Init();
}
StateMapFstImpl(const StateMapFstImpl<A, B, C> &impl)
: CacheImpl<B>(impl),
fst_(impl.fst_->Copy(true)),
mapper_(new C(*impl.mapper_, fst_)),
own_mapper_(true) {
Init();
}
~StateMapFstImpl() override {
delete fst_;
if (own_mapper_) delete mapper_;
}
StateId Start() {
if (!HasStart()) SetStart(mapper_->Start());
return CacheImpl<B>::Start();
}
Weight Final(StateId s) {
if (!HasFinal(s)) SetFinal(s, mapper_->Final(s));
return CacheImpl<B>::Final(s);
}
size_t NumArcs(StateId s) {
if (!HasArcs(s)) Expand(s);
return CacheImpl<B>::NumArcs(s);
}
size_t NumInputEpsilons(StateId s) {
if (!HasArcs(s)) Expand(s);
return CacheImpl<B>::NumInputEpsilons(s);
}
size_t NumOutputEpsilons(StateId s) {
if (!HasArcs(s)) Expand(s);
return CacheImpl<B>::NumOutputEpsilons(s);
}
void InitStateIterator(StateIteratorData<A> *data) const {
fst_->InitStateIterator(data);
}
void InitArcIterator(StateId s, ArcIteratorData<B> *data) {
if (!HasArcs(s)) Expand(s);
CacheImpl<B>::InitArcIterator(s, data);
}
uint64 Properties() const override { return Properties(kFstProperties); }
// Set error if found; return FST impl properties.
uint64 Properties(uint64 mask) const override {
if ((mask & kError) &&
(fst_->Properties(kError, false) || (mapper_->Properties(0) & kError)))
SetProperties(kError, kError);
return FstImpl<Arc>::Properties(mask);
}
void Expand(StateId s) {
// Add exiting arcs.
for (mapper_->SetState(s); !mapper_->Done(); mapper_->Next())
PushArc(s, mapper_->Value());
SetArcs(s);
}
const Fst<A> &GetFst() const { return *fst_; }
private:
void Init() {
SetType("statemap");
if (mapper_->InputSymbolsAction() == MAP_COPY_SYMBOLS)
SetInputSymbols(fst_->InputSymbols());
else if (mapper_->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
SetInputSymbols(0);
if (mapper_->OutputSymbolsAction() == MAP_COPY_SYMBOLS)
SetOutputSymbols(fst_->OutputSymbols());
else if (mapper_->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
SetOutputSymbols(0);
uint64 props = fst_->Properties(kCopyProperties, false);
SetProperties(mapper_->Properties(props));
}
const Fst<A> *fst_;
C *mapper_;
bool own_mapper_;
void operator=(const StateMapFstImpl<A, B, C> &); // disallow
};
// Maps an arc type A to an arc type B using Mapper function object
// C. This version is a delayed Fst.
template <class A, class B, class C>
class StateMapFst : public ImplToFst<StateMapFstImpl<A, B, C>> {
public:
friend class ArcIterator<StateMapFst<A, B, C>>;
typedef B Arc;
typedef typename B::Weight Weight;
typedef typename B::StateId StateId;
typedef DefaultCacheStore<B> Store;
typedef typename Store::State State;
typedef StateMapFstImpl<A, B, C> Impl;
StateMapFst(const Fst<A> &fst, const C &mapper,
const StateMapFstOptions &opts)
: ImplToFst<Impl>(std::make_shared<Impl>(fst, mapper, opts)) {}
StateMapFst(const Fst<A> &fst, C *mapper, const StateMapFstOptions &opts)
: ImplToFst<Impl>(std::make_shared<Impl>(fst, mapper, opts)) {}
StateMapFst(const Fst<A> &fst, const C &mapper)
: ImplToFst<Impl>(
std::make_shared<Impl>(fst, mapper, StateMapFstOptions())) {}
StateMapFst(const Fst<A> &fst, C *mapper)
: ImplToFst<Impl>(
std::make_shared<Impl>(fst, mapper, StateMapFstOptions())) {}
// See Fst<>::Copy() for doc.
StateMapFst(const StateMapFst<A, B, C> &fst, bool safe = false)
: ImplToFst<Impl>(fst, safe) {}
// Get a copy of this StateMapFst. See Fst<>::Copy() for further doc.
StateMapFst<A, B, C> *Copy(bool safe = false) const override {
return new StateMapFst<A, B, C>(*this, safe);
}
void InitStateIterator(StateIteratorData<A> *data) const override {
GetImpl()->InitStateIterator(data);
}
void InitArcIterator(StateId s, ArcIteratorData<B> *data) const override {
GetMutableImpl()->InitArcIterator(s, data);
}
protected:
using ImplToFst<Impl>::GetImpl;
using ImplToFst<Impl>::GetMutableImpl;
private:
void operator=(const StateMapFst<A, B, C> &fst); // disallow
};
// Specialization for StateMapFst.
template <class A, class B, class C>
class ArcIterator<StateMapFst<A, B, C>>
: public CacheArcIterator<StateMapFst<A, B, C>> {
public:
typedef typename A::StateId StateId;
ArcIterator(const StateMapFst<A, B, C> &fst, StateId s)
: CacheArcIterator<StateMapFst<A, B, C>>(fst.GetMutableImpl(), s) {
if (!fst.GetImpl()->HasArcs(s)) fst.GetMutableImpl()->Expand(s);
}
private:
DISALLOW_COPY_AND_ASSIGN(ArcIterator);
};
//
// Utility Mappers
//
// Mapper that returns its input.
template <class A>
class IdentityStateMapper {
public:
typedef A FromArc;
typedef A ToArc;
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
explicit IdentityStateMapper(const Fst<A> &fst) : fst_(fst), aiter_(0) {}
// Allows updating Fst argument; pass only if changed.
IdentityStateMapper(const IdentityStateMapper<A> &mapper,
const Fst<A> *fst = 0)
: fst_(fst ? *fst : mapper.fst_), aiter_(0) {}
~IdentityStateMapper() { delete aiter_; }
StateId Start() const { return fst_.Start(); }
Weight Final(StateId s) const { return fst_.Final(s); }
void SetState(StateId s) {
if (aiter_) delete aiter_;
aiter_ = new ArcIterator<Fst<A>>(fst_, s);
}
bool Done() const { return aiter_->Done(); }
const A &Value() const { return aiter_->Value(); }
void Next() { aiter_->Next(); }
MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
uint64 Properties(uint64 props) const { return props; }
private:
const Fst<A> &fst_;
ArcIterator<Fst<A>> *aiter_;
};
template <class A>
class ArcSumMapper {
public:
typedef A FromArc;
typedef A ToArc;
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
explicit ArcSumMapper(const Fst<A> &fst) : fst_(fst), i_(0) {}
// Allows updating Fst argument; pass only if changed.
ArcSumMapper(const ArcSumMapper<A> &mapper, const Fst<A> *fst = 0)
: fst_(fst ? *fst : mapper.fst_), i_(0) {}
StateId Start() const { return fst_.Start(); }
Weight Final(StateId s) const { return fst_.Final(s); }
void SetState(StateId s) {
i_ = 0;
arcs_.clear();
arcs_.reserve(fst_.NumArcs(s));
for (ArcIterator<Fst<A>> aiter(fst_, s); !aiter.Done(); aiter.Next())
arcs_.push_back(aiter.Value());
// First sorts the exiting arcs by input label, output label
// and destination state and then sums weights of arcs with
// the same input label, output label, and destination state.
std::sort(arcs_.begin(), arcs_.end(), comp_);
size_t narcs = 0;
for (size_t i = 0; i < arcs_.size(); ++i) {
if (narcs > 0 && equal_(arcs_[i], arcs_[narcs - 1])) {
arcs_[narcs - 1].weight =
Plus(arcs_[narcs - 1].weight, arcs_[i].weight);
} else {
arcs_[narcs++] = arcs_[i];
}
}
arcs_.resize(narcs);
}
bool Done() const { return i_ >= arcs_.size(); }
const A &Value() const { return arcs_[i_]; }
void Next() { ++i_; }
MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
uint64 Properties(uint64 props) const {
return props & kArcSortProperties & kDeleteArcsProperties &
kWeightInvariantProperties;
}
private:
struct Compare {
bool operator()(const A &x, const A &y) const {
if (x.ilabel < y.ilabel) return true;
if (x.ilabel > y.ilabel) return false;
if (x.olabel < y.olabel) return true;
if (x.olabel > y.olabel) return false;
if (x.nextstate < y.nextstate) return true;
if (x.nextstate > y.nextstate) return false;
return false;
}
};
struct Equal {
bool operator()(const A &x, const A &y) {
return (x.ilabel == y.ilabel && x.olabel == y.olabel &&
x.nextstate == y.nextstate);
}
};
const Fst<A> &fst_;
Compare comp_;
Equal equal_;
std::vector<A> arcs_;
ssize_t i_; // current arc position
void operator=(const ArcSumMapper<A> &); // disallow
};
template <class A>
class ArcUniqueMapper {
public:
typedef A FromArc;
typedef A ToArc;
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
explicit ArcUniqueMapper(const Fst<A> &fst) : fst_(fst), i_(0) {}
// Allows updating Fst argument; pass only if changed.
ArcUniqueMapper(const ArcUniqueMapper<A> &mapper, const Fst<A> *fst = 0)
: fst_(fst ? *fst : mapper.fst_), i_(0) {}
StateId Start() const { return fst_.Start(); }
Weight Final(StateId s) const { return fst_.Final(s); }
void SetState(StateId s) {
i_ = 0;
arcs_.clear();
arcs_.reserve(fst_.NumArcs(s));
for (ArcIterator<Fst<A>> aiter(fst_, s); !aiter.Done(); aiter.Next())
arcs_.push_back(aiter.Value());
// First sorts the exiting arcs by input label, output label
// and destination state and then uniques identical arcs
std::sort(arcs_.begin(), arcs_.end(), comp_);
arcs_.erase(std::unique(arcs_.begin(), arcs_.end(), equal_), arcs_.end());
}
bool Done() const { return i_ >= arcs_.size(); }
const A &Value() const { return arcs_[i_]; }
void Next() { ++i_; }
MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
uint64 Properties(uint64 props) const {
return props & kArcSortProperties & kDeleteArcsProperties;
}
private:
struct Compare {
bool operator()(const A &x, const A &y) const {
if (x.ilabel < y.ilabel) return true;
if (x.ilabel > y.ilabel) return false;
if (x.olabel < y.olabel) return true;
if (x.olabel > y.olabel) return false;
if (x.nextstate < y.nextstate) return true;
if (x.nextstate > y.nextstate) return false;
return false;
}
};
struct Equal {
bool operator()(const A &x, const A &y) const {
return (x.ilabel == y.ilabel && x.olabel == y.olabel &&
x.nextstate == y.nextstate && x.weight == y.weight);
}
};
const Fst<A> &fst_;
Compare comp_;
Equal equal_;
std::vector<A> arcs_;
ssize_t i_; // current arc position
void operator=(const ArcUniqueMapper<A> &); // disallow
};
} // namespace fst
#endif // FST_LIB_STATE_MAP_H_
|