22 #ifndef FST_ARC_MAP_H_ 23 #define FST_ARC_MAP_H_ 29 #include <type_traits> 45 #include <unordered_map> 119 template <
class A,
class C>
123 using Weight =
typename FromArc::Weight;
132 const auto final_action = mapper->FinalAction();
140 const auto state = siter.Value();
142 !aiter.Done(); aiter.Next()) {
143 const auto &arc = aiter.Value();
144 aiter.SetValue((*mapper)(arc));
146 switch (final_action) {
150 const auto final_arc = (*mapper)(arc);
151 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
152 FSTERROR() <<
"ArcMap: Non-zero arc labels for superfinal arc";
155 fst->
SetFinal(state, final_arc.weight);
159 if (state != superfinal) {
161 auto final_arc = (*mapper)(arc);
162 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
168 final_arc.nextstate = superfinal;
169 fst->
AddArc(state, std::move(final_arc));
170 fst->
SetFinal(state, Weight::Zero());
172 fst->
SetFinal(state, final_arc.weight);
178 if (state != superfinal) {
180 const auto final_arc = (*mapper)(arc);
181 if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
182 final_arc.weight != Weight::Zero()) {
183 fst->
AddArc(state, ToArc(final_arc.ilabel, final_arc.olabel,
184 final_arc.weight, superfinal));
186 fst->
SetFinal(state, Weight::Zero());
197 template <
class A,
class C>
205 template <
class A,
class B,
class C>
208 using StateId =
typename FromArc::StateId;
225 const auto final_action = mapper->FinalAction();
240 StateId s = siter.Value();
245 ofst->
AddArc(s, (*mapper)(aiter.Value()));
247 switch (final_action) {
251 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
252 FSTERROR() <<
"ArcMap: Non-zero arc labels for superfinal arc";
255 ofst->
SetFinal(s, final_arc.weight);
260 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
266 final_arc.nextstate = superfinal;
267 ofst->
AddArc(s, std::move(final_arc));
268 ofst->
SetFinal(s, B::Weight::Zero());
270 ofst->
SetFinal(s, final_arc.weight);
276 if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
277 final_arc.weight != B::Weight::Zero()) {
278 ofst->
AddArc(s, B(final_arc.ilabel, final_arc.olabel,
279 final_arc.weight, superfinal));
281 ofst->
SetFinal(s, B::Weight::Zero());
293 template <
class A,
class B,
class C>
295 ArcMap(ifst, ofst, &mapper);
306 template <
class A,
class B,
class C>
312 template <
class A,
class B,
class C>
339 mapper_(new C(mapper)),
358 fst_(impl.fst_->Copy(true)),
359 mapper_(new C(*impl.mapper_)),
367 if (own_mapper_)
delete mapper_;
371 if (!HasStart()) SetStart(FindOState(fst_->Start()));
377 switch (final_action_) {
380 const auto final_arc =
381 (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
kNoStateId));
382 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
383 FSTERROR() <<
"ArcMapFst: Non-zero arc labels for superfinal arc";
386 SetFinal(s, final_arc.weight);
390 if (s == superfinal_) {
393 const auto final_arc =
394 (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
kNoStateId));
395 if (final_arc.ilabel == 0 && final_arc.olabel == 0) {
396 SetFinal(s, final_arc.weight);
398 SetFinal(s, Weight::Zero());
404 SetFinal(s, s == superfinal_ ? Weight::One() : Weight::Zero());
413 if (!HasArcs(s))
Expand(s);
418 if (!HasArcs(s))
Expand(s);
423 if (!HasArcs(s))
Expand(s);
431 if ((mask &
kError) && (fst_->Properties(kError,
false) ||
432 (mapper_->Properties(0) &
kError))) {
433 SetProperties(kError, kError);
439 if (!HasArcs(s))
Expand(s);
445 if (s == superfinal_) {
451 auto aarc = aiter.Value();
452 aarc.nextstate = FindOState(aarc.nextstate);
453 PushArc(s, (*mapper_)(aarc));
457 if (!HasFinal(s) ||
Final(s) == Weight::Zero()) {
458 switch (final_action_) {
464 (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
kNoStateId));
465 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
466 if (superfinal_ ==
kNoStateId) superfinal_ = nstates_++;
467 final_arc.nextstate = superfinal_;
468 PushArc(s, std::move(final_arc));
473 const auto final_arc =
474 (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
kNoStateId));
475 if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
476 final_arc.weight != B::Weight::Zero()) {
477 EmplaceArc(s, final_arc.ilabel, final_arc.olabel, final_arc.weight,
491 SetInputSymbols(fst_->InputSymbols());
493 SetInputSymbols(
nullptr);
496 SetOutputSymbols(fst_->OutputSymbols());
498 SetOutputSymbols(
nullptr);
504 final_action_ = mapper_->FinalAction();
506 SetProperties(mapper_->Properties(props));
513 if (superfinal_ ==
kNoStateId || s < superfinal_) {
523 if (!(superfinal_ ==
kNoStateId || is < superfinal_)) ++os;
524 if (os >= nstates_) nstates_ = os + 1;
528 std::unique_ptr<const Fst<A>> fst_;
530 const bool own_mapper_;
540 template <
class A,
class B,
class C>
574 GetMutableImpl()->InitArcIterator(s, data);
588 template <
class A,
class B,
class C>
594 : impl_(fst.GetImpl()),
595 siter_(*impl_->fst_),
601 bool Done() const final {
return siter_.Done() && !superfinal_; }
607 if (!siter_.Done()) {
610 }
else if (superfinal_) {
623 void CheckSuperfinal() {
625 if (!siter_.Done()) {
626 const auto final_arc =
627 (*impl_->mapper_)(A(0, 0, impl_->fst_->Final(s_),
kNoStateId));
628 if (final_arc.ilabel != 0 || final_arc.olabel != 0) superfinal_ =
true;
639 template <
class A,
class B,
class C>
651 template <
class A,
class B,
class C>
654 data->
base = std::make_unique<StateIterator<ArcMapFst<A, B, C>>>(*this);
659 template <
class ArcMapper>
661 ->
ArcMapFst<
typename ArcMapper::FromArc,
typename ArcMapper::ToArc,
665 template <
class ArcMapper>
667 ->
ArcMapFst<
typename ArcMapper::FromArc,
typename ArcMapper::ToArc,
691 constexpr uint64_t
Properties(uint64_t props)
const {
return props; }
702 return ToArc(0, arc.olabel, arc.weight, arc.nextstate);
728 return ToArc(arc.ilabel, 0, arc.weight, arc.nextstate);
753 using Label =
typename FromArc::Label;
758 : final_label_(final_label) {}
762 if (arc.nextstate ==
kNoStateId && arc.weight != Weight::Zero()) {
782 if (final_label_ == 0) {
791 const Label final_label_;
798 template <
class A,
class B,
809 : convert_weight_(c) {}
812 return ToArc(arc.ilabel, arc.olabel, convert_weight_(arc.weight),
826 constexpr uint64_t
Properties(uint64_t props)
const {
return props; }
850 template <
class A, GallicType G = GALLIC_LEFT>
857 using AW =
typename FromArc::Weight;
862 if (arc.nextstate ==
kNoStateId && arc.weight != AW::Zero()) {
868 }
else if (arc.olabel == 0) {
869 return ToArc(arc.ilabel, arc.ilabel,
GW(SW::One(), arc.weight),
873 return ToArc(arc.ilabel, arc.ilabel,
GW(
SW(arc.olabel), arc.weight),
894 template <
class A, GallicType G = GALLIC_LEFT>
900 using Label =
typename ToArc::Label;
901 using AW =
typename ToArc::Weight;
905 : superfinal_label_(superfinal_label), error_(false) {}
913 AW weight = AW::Zero();
915 FSTERROR() <<
"FromGallicMapper: Unrepresentable weight: " << arc.
weight 916 <<
" for arc with ilabel = " << arc.
ilabel 917 <<
", olabel = " << arc.
olabel 941 if (error_) outprops |=
kError;
946 template <GallicType GT>
948 typename A::Weight *weight,
typename A::Label *label) {
950 const GW &w1 = gallic_weight.
Value1();
951 const AW &w2 = gallic_weight.
Value2();
952 typename GW::Iterator iter1(w1);
953 const Label l = w1.Size() == 1 ? iter1.Value() : 0;
961 typename A::Weight *weight,
typename A::Label *label) {
962 if (gallic_weight.Size() > 1)
return false;
963 if (gallic_weight.Size() == 0) {
965 *weight = A::Weight::Zero();
968 return Extract<GALLIC_RESTRICT>(gallic_weight.Back(), weight, label);
971 const Label superfinal_label_;
976 template <
class A, GallicType G = GALLIC_LEFT>
982 using Label =
typename ToArc::Label;
984 using AW =
typename ToArc::Weight;
991 osymbols_(fst->OutputSymbols()),
994 fst_->DeleteStates();
995 state_ = fst_->AddState();
996 fst_->SetStart(state_);
997 fst_->SetFinal(state_);
999 std::string name = osymbols_->Name() +
"_from_gallic";
1001 isymbols_ = fst_->MutableInputSymbols();
1002 const int64_t zero = 0;
1003 isymbols_->AddSymbol(osymbols_->Find(zero), 0);
1005 fst_->SetInputSymbols(
nullptr);
1017 if (w1.
Size() == 0) {
1019 }
else if (
auto [it, inserted] = map_.emplace(w1,
kNoLabel); !inserted) {
1027 for (
size_t i = 0, p = state_; i < w1.
Size(); ++i, iter1.
Next(), p = n) {
1028 n = i == w1.
Size() - 1 ? state_ : fst_->AddState();
1029 fst_->AddArc(p,
ToArc(i ? 0 : l, iter1.
Value(), n));
1032 s = s + osymbols_->Find(iter1.
Value());
1035 if (isymbols_) isymbols_->AddSymbol(s, l);
1038 FSTERROR() <<
"GallicToNewSymbolMapper: Unrepresentable weight: " << l;
1057 if (error_) outprops |=
kError;
1064 size_t operator()(
const SW &x)
const {
return x.
Hash(); }
1067 using Map = std::unordered_map<SW, Label, StringKey>;
1075 mutable bool error_;
1092 if (arc.weight == Weight::Zero())
return arc;
1093 return ToArc(arc.ilabel, arc.olabel,
Plus(arc.weight, weight_),
1126 if (arc.weight == Weight::Zero())
return arc;
1127 return ToArc(arc.ilabel, arc.olabel,
Times(arc.weight, weight_),
1164 return ToArc(arc.ilabel, arc.olabel,
Power(arc.weight, power_),
1183 const double power_;
1195 if (arc.weight == Weight::Zero())
return arc;
1196 return ToArc(arc.ilabel, arc.olabel,
Divide(Weight::One(), arc.weight),
1216 template <
class A,
class B = A>
1226 arc.ilabel, arc.olabel,
1227 arc.weight != FromWeight::Zero() ? ToWeight::One() : ToWeight::Zero(),
1247 template <
class A,
class B = A>
1260 return ToArc(arc.ilabel, arc.olabel, arc.weight.Quantize(delta_),
1289 template <
class A,
class B>
1294 static_assert(std::is_same_v<
typename ToArc::Weight,
1295 typename FromArc::Weight::ReverseWeight>,
1296 "ToArc::Weight must be FromArc::Weight::ReverseWeight");
1297 static_assert(std::is_same_v<typename ToArc::Label, typename FromArc::Label>,
1298 "ToArc::Label must be FromArc::Label");
1300 std::is_same_v<typename ToArc::StateId, typename FromArc::StateId>,
1301 "ToArc::StateId must be FromArc::StateId");
1304 return ToArc(arc.ilabel, arc.olabel, arc.weight.Reverse(), arc.nextstate);
1317 constexpr uint64_t
Properties(uint64_t props)
const {
return props; }
1322 #endif // FST_ARC_MAP_H_
constexpr MapSymbolsAction InputSymbolsAction() const
ToArc operator()(const FromArc &arc) const
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
ArcMapFstImpl(const ArcMapFstImpl< A, B, C > &impl)
void ArcMap(MutableFst< A > *fst, C *mapper)
StateId Value() const final
constexpr MapSymbolsAction InputSymbolsAction() const
constexpr SuperFinalMapper(Label final_label=0)
typename FromArc::Weight Weight
constexpr MapSymbolsAction InputSymbolsAction() const
GallicToNewSymbolsMapper(MutableFst< ToArc > *fst)
constexpr uint64_t kWeightInvariantProperties
uint64_t Properties(uint64_t props) const
typename Store::State State
virtual uint64_t Properties(uint64_t mask, bool test) const =0
constexpr uint64_t kOEpsilons
ToArc operator()(const FromArc &arc) const
constexpr MapFinalAction FinalAction() const
constexpr MapSymbolsAction InputSymbolsAction() const
constexpr MapSymbolsAction OutputSymbolsAction() const
ToArc operator()(const FromArc &arc) const
ErrorWeight Plus(const ErrorWeight &, const ErrorWeight &)
ArcMapFst(const Fst< typename ArcMapper::FromArc > &, const ArcMapper &) -> ArcMapFst< typename ArcMapper::FromArc, typename ArcMapper::ToArc, ArcMapper >
constexpr MapSymbolsAction InputSymbolsAction() const
virtual size_t NumArcs(StateId) const =0
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr MapSymbolsAction OutputSymbolsAction() const
typename ToArc::Weight ToWeight
constexpr uint64_t Properties(uint64_t props) const
const Label & Value() const
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr ToArc operator()(const FromArc &arc) const
constexpr ToArc operator()(const FromArc &arc) const
constexpr MapFinalAction FinalAction() const
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
constexpr ToArc operator()(const FromArc &arc) const
typename FromArc::Weight Weight
ArcMapFstImpl(const Fst< A > &fst, const C &mapper, const ArcMapFstOptions &opts)
constexpr MapFinalAction FinalAction() const
ErrorWeight Times(const ErrorWeight &, const ErrorWeight &)
void InitStateIterator(StateIteratorData< B > *data) const override
typename FromArc::Label Label
ToArc operator()(const FromArc &arc) const
constexpr uint64_t kError
typename ToArc::Weight ToWeight
constexpr MapFinalAction FinalAction() const
virtual void SetInputSymbols(const SymbolTable *isyms)=0
typename FromArc::Weight Weight
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr uint64_t Properties(uint64_t props) const
size_t NumArcs(StateId s)
constexpr MapSymbolsAction OutputSymbolsAction() const
virtual Weight Final(StateId) const =0
typename ToArc::Weight GW
constexpr MapFinalAction FinalAction() const
constexpr MapFinalAction FinalAction() const
virtual void SetStart(StateId)=0
constexpr uint64_t Properties(uint64_t props) const
ToArc operator()(const FromArc &arc) const
ssize_t NumArcs(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
ArcMapFst(const Fst< A > &fst, const C &mapper=C(), const ArcMapFstOptions &opts=ArcMapFstOptions())
ArcMapFstImpl(const Fst< A > &fst, C *mapper, const ArcMapFstOptions &opts)
ToArc operator()(const FromArc &arc)
uint64_t Properties(uint64_t props) const
size_t NumInputEpsilons(StateId s)
typename FromArc::Weight Weight
uint64_t Properties(uint64_t inprops) const
constexpr MapFinalAction FinalAction() const
constexpr uint64_t Properties(uint64_t props) const
FromGallicMapper(Label superfinal_label=0)
ToArc operator()(const FromArc &arc) const
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr MapSymbolsAction InputSymbolsAction() const
constexpr MapFinalAction FinalAction() const
constexpr TimesMapper(Weight weight)
typename B::StateId StateId
ToArc operator()(const FromArc &arc) const
virtual void ReserveArcs(StateId, size_t)
typename Arc::Weight Weight
ArcMapFst(const Fst< A > &fst, C *mapper, const ArcMapFstOptions &opts=ArcMapFstOptions())
typename Arc::Weight Weight
constexpr PlusMapper(Weight weight)
constexpr int kStringInfinity
constexpr MapSymbolsAction OutputSymbolsAction() const
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
typename FromArc::Weight Weight
StateIterator(const ArcMapFst< A, B, C > &fst)
constexpr uint64_t kOLabelSorted
constexpr uint64_t kCopyProperties
constexpr uint64_t Properties(uint64_t props) const
virtual void SetProperties(uint64_t props, uint64_t mask)=0
typename FirstCacheStore< VectorCacheStore< CacheState< Arc > > >::State State
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr WeightConvertMapper(const Converter &c=Converter())
constexpr MapSymbolsAction InputSymbolsAction() const
size_t NumOutputEpsilons(StateId s)
constexpr MapSymbolsAction InputSymbolsAction() const
virtual StateId Start() const =0
std::unique_ptr< StateIteratorBase< Arc > > base
constexpr uint64_t kOLabelInvariantProperties
constexpr uint64_t Properties(uint64_t props) const
ArcMapFst * Copy(bool safe=false) const override
constexpr uint64_t kNullProperties
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr uint64_t kIEpsilons
typename ToArc::StateId StateId
typename FromArc::Weight GW
typename FromArc::Weight GW
typename ToArc::Weight AW
constexpr uint64_t Properties(uint64_t props) const
virtual std::optional< StateId > NumStatesIfKnown() const
constexpr uint64_t kILabelInvariantProperties
typename A::StateId StateId
constexpr MapFinalAction FinalAction() const
constexpr uint64_t kILabelSorted
typename Arc::StateId StateId
constexpr uint64_t kFstProperties
virtual void AddArc(StateId, const Arc &)=0
constexpr uint64_t kUnweighted
ArcMapFst(const ArcMapFst &fst, bool safe=false)
constexpr MapFinalAction FinalAction() const
typename FromArc::Weight FromWeight
virtual const SymbolTable * InputSymbols() const =0
ArcIterator(const ArcMapFst< A, B, C > &fst, StateId s)
uint64_t Properties() const override
void InitArcIterator(StateId s, ArcIteratorData< B > *data) const override
constexpr MapFinalAction FinalAction() const
typename ToArc::Label Label
ErrorWeight Divide(const ErrorWeight &, const ErrorWeight &)
virtual StateId AddState()=0
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr MapSymbolsAction InputSymbolsAction() const
typename ToArc::Label Label
virtual void ReserveStates(size_t)
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
uint64_t Properties(uint64_t mask) const override
virtual void DeleteStates(const std::vector< StateId > &)=0
typename Arc::StateId StateId
constexpr MapSymbolsAction InputSymbolsAction() const
constexpr MapSymbolsAction InputSymbolsAction() const
uint64_t ProjectProperties(uint64_t inprops, bool project_input)
virtual void SetOutputSymbols(const SymbolTable *osyms)=0
constexpr MapFinalAction FinalAction() const
typename FromArc::Weight AW
void Expand(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, const std::vector< typename Arc::Label > &assignments, MutableFst< Arc > *ofst, const MPdtExpandOptions &opts)
void Extract(FarReader< Arc > &reader, int32_t generate_sources, const std::string &keys, std::string_view key_separator, std::string_view range_delimiter, std::string_view source_prefix, std::string_view source_suffix)
ToArc operator()(const FromArc &arc) const
constexpr MapFinalAction FinalAction() const
constexpr TropicalWeightTpl< T > Power(const TropicalWeightTpl< T > &w, V n)
typename FromArc::Weight FromWeight
internal::ArcMapFstImpl< A, B, C > * GetMutableImpl() const
constexpr uint64_t Properties(uint64_t props) const
ArcMapFstOptions(const CacheOptions &opts)
constexpr ToArc operator()(const FromArc &arc) const
uint64_t Properties(uint64_t inprops) const
constexpr MapFinalAction FinalAction() const
~ArcMapFstImpl() override
constexpr uint64_t Properties(uint64_t props) const
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr uint64_t Properties(uint64_t props) const
constexpr MapSymbolsAction OutputSymbolsAction() const
constexpr MapSymbolsAction InputSymbolsAction() const
constexpr uint64_t kSetArcProperties
constexpr MapSymbolsAction InputSymbolsAction() const
constexpr MapSymbolsAction InputSymbolsAction() const
constexpr MapSymbolsAction OutputSymbolsAction() const
PowerMapper(double power)
ToArc operator()(const FromArc &arc) const
void InitArcIterator(StateId s, ArcIteratorData< B > *data)
constexpr uint64_t kAddSuperFinalProperties
const internal::ArcMapFstImpl< A, B, C > * GetImpl() const
const StringWeight< Label, GallicStringType(G)> & Value1() const
typename ToArc::Weight AW
typename ToArc::Weight ToWeight
virtual const SymbolTable * OutputSymbols() const =0
typename FromArc::Weight FromWeight