1 // arc-map.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 // Copyright 2005-2010 Google, Inc.
16 // Author: riley@google.com (Michael Riley)
17 //
18 // \file
19 // Class to map over/transform arcs e.g., change semirings or
20 // implement project/invert. Consider using when operation does
21 // not change the number of arcs (except possibly superfinal arcs).
22
23 #ifndef FST_LIB_ARC_MAP_H__
24 #define FST_LIB_ARC_MAP_H__
25
26 #include <unordered_map>
27 using std::tr1::unordered_map;
28 using std::tr1::unordered_multimap;
29 #include <string>
30 #include <utility>
31 using std::pair; using std::make_pair;
32
33 #include <fst/cache.h>
34 #include <fst/mutable-fst.h>
35
36
37 namespace fst {
38
39 // This determines how final weights are mapped.
40 enum MapFinalAction {
41 // A final weight is mapped into a final weight. An error
42 // is raised if this is not possible.
43 MAP_NO_SUPERFINAL,
44
45 // A final weight is mapped to an arc to the superfinal state
46 // when the result cannot be represented as a final weight.
47 // The superfinal state will be added only if it is needed.
48 MAP_ALLOW_SUPERFINAL,
49
50 // A final weight is mapped to an arc to the superfinal state
51 // unless the result can be represented as a final weight of weight
52 // Zero(). The superfinal state is always added (if the input is
53 // not the empty Fst).
54 MAP_REQUIRE_SUPERFINAL
55 };
56
57 // This determines how symbol tables are mapped.
58 enum MapSymbolsAction {
59 // Symbols should be cleared in the result by the map.
60 MAP_CLEAR_SYMBOLS,
61
62 // Symbols should be copied from the input FST by the map.
63 MAP_COPY_SYMBOLS,
64
65 // Symbols should not be modified in the result by the map itself.
66 // (They may set by the mapper).
67 MAP_NOOP_SYMBOLS
68 };
69
70 // ArcMapper Interface - class determinies how arcs and final weights
71 // are mapped. Useful for implementing operations that do not change
72 // the number of arcs (expect possibly superfinal arcs).
73 //
74 // class ArcMapper {
75 // public:
76 // typedef A FromArc;
77 // typedef B ToArc;
78 //
79 // // Maps an arc type A to arc type B.
80 // B operator()(const A &arc);
81 // // Specifies final action the mapper requires (see above).
82 // // The mapper will be passed final weights as arcs of the
83 // // form A(0, 0, weight, kNoStateId).
84 // MapFinalAction FinalAction() const;
85 // // Specifies input symbol table action the mapper requires (see above).
86 // MapSymbolsAction InputSymbolsAction() const;
87 // // Specifies output symbol table action the mapper requires (see above).
88 // MapSymbolsAction OutputSymbolsAction() const;
89 // // This specifies the known properties of an Fst mapped by this
90 // // mapper. It takes as argument the input Fst's known properties.
91 // uint64 Properties(uint64 props) const;
92 // };
93 //
94 // The ArcMap functions and classes below will use the FinalAction()
95 // method of the mapper to determine how to treat final weights,
96 // e.g. whether to add a superfinal state. They will use the Properties()
97 // method to set the result Fst properties.
98 //
99 // We include a various map versions below. One dimension of
100 // variation is whether the mapping mutates its input, writes to a
101 // new result Fst, or is an on-the-fly Fst. Another dimension is how
102 // we pass the mapper. We allow passing the mapper by pointer
103 // for cases that we need to change the state of the user's mapper.
104 // This is the case with the encode mapper, which is reused during
105 // decoding. We also include map versions that pass the mapper
106 // by value or const reference when this suffices.
107
108
109 // Maps an arc type A using a mapper function object C, passed
110 // by pointer. This version modifies its Fst input.
111 template<class A, class C>
ArcMap(MutableFst<A> * fst,C * mapper)112 void ArcMap(MutableFst<A> *fst, C* mapper) {
113 typedef typename A::StateId StateId;
114 typedef typename A::Weight Weight;
115
116 if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
117 fst->SetInputSymbols(0);
118
119 if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
120 fst->SetOutputSymbols(0);
121
122 if (fst->Start() == kNoStateId)
123 return;
124
125 uint64 props = fst->Properties(kFstProperties, false);
126
127 MapFinalAction final_action = mapper->FinalAction();
128 StateId superfinal = kNoStateId;
129 if (final_action == MAP_REQUIRE_SUPERFINAL) {
130 superfinal = fst->AddState();
131 fst->SetFinal(superfinal, Weight::One());
132 }
133
134 for (StateId s = 0; s < fst->NumStates(); ++s) {
135 for (MutableArcIterator< MutableFst<A> > aiter(fst, s);
136 !aiter.Done(); aiter.Next()) {
137 const A &arc = aiter.Value();
138 aiter.SetValue((*mapper)(arc));
139 }
140
141 switch (final_action) {
142 case MAP_NO_SUPERFINAL:
143 default: {
144 A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
145 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
146 FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc";
147 fst->SetProperties(kError, kError);
148 }
149
150 fst->SetFinal(s, final_arc.weight);
151 break;
152 }
153 case MAP_ALLOW_SUPERFINAL: {
154 if (s != superfinal) {
155 A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
156 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
157 // Add a superfinal state if not already done.
158 if (superfinal == kNoStateId) {
159 superfinal = fst->AddState();
160 fst->SetFinal(superfinal, Weight::One());
161 }
162 final_arc.nextstate = superfinal;
163 fst->AddArc(s, final_arc);
164 fst->SetFinal(s, Weight::Zero());
165 } else {
166 fst->SetFinal(s, final_arc.weight);
167 }
168 break;
169 }
170 }
171 case MAP_REQUIRE_SUPERFINAL: {
172 if (s != superfinal) {
173 A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId));
174 if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
175 final_arc.weight != Weight::Zero())
176 fst->AddArc(s, A(final_arc.ilabel, final_arc.olabel,
177 final_arc.weight, superfinal));
178 fst->SetFinal(s, Weight::Zero());
179 }
180 break;
181 }
182 }
183 }
184 fst->SetProperties(mapper->Properties(props), kFstProperties);
185 }
186
187
188 // Maps an arc type A using a mapper function object C, passed
189 // by value. This version modifies its Fst input.
190 template<class A, class C>
ArcMap(MutableFst<A> * fst,C mapper)191 void ArcMap(MutableFst<A> *fst, C mapper) {
192 ArcMap(fst, &mapper);
193 }
194
195
196 // Maps an arc type A to an arc type B using mapper function
197 // object C, passed by pointer. This version writes the mapped
198 // input Fst to an output MutableFst.
199 template<class A, class B, class C>
ArcMap(const Fst<A> & ifst,MutableFst<B> * ofst,C * mapper)200 void ArcMap(const Fst<A> &ifst, MutableFst<B> *ofst, C* mapper) {
201 typedef typename A::StateId StateId;
202 typedef typename A::Weight Weight;
203
204 ofst->DeleteStates();
205
206 if (mapper->InputSymbolsAction() == MAP_COPY_SYMBOLS)
207 ofst->SetInputSymbols(ifst.InputSymbols());
208 else if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
209 ofst->SetInputSymbols(0);
210
211 if (mapper->OutputSymbolsAction() == MAP_COPY_SYMBOLS)
212 ofst->SetOutputSymbols(ifst.OutputSymbols());
213 else if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
214 ofst->SetOutputSymbols(0);
215
216 uint64 iprops = ifst.Properties(kCopyProperties, false);
217
218 if (ifst.Start() == kNoStateId) {
219 if (iprops & kError) ofst->SetProperties(kError, kError);
220 return;
221 }
222
223 MapFinalAction final_action = mapper->FinalAction();
224 if (ifst.Properties(kExpanded, false)) {
225 ofst->ReserveStates(CountStates(ifst) +
226 final_action == MAP_NO_SUPERFINAL ? 0 : 1);
227 }
228
229 // Add all states.
230 for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next())
231 ofst->AddState();
232
233 StateId superfinal = kNoStateId;
234 if (final_action == MAP_REQUIRE_SUPERFINAL) {
235 superfinal = ofst->AddState();
236 ofst->SetFinal(superfinal, B::Weight::One());
237 }
238 for (StateIterator< Fst<A> > siter(ifst); !siter.Done(); siter.Next()) {
239 StateId s = siter.Value();
240 if (s == ifst.Start())
241 ofst->SetStart(s);
242
243 ofst->ReserveArcs(s, ifst.NumArcs(s));
244 for (ArcIterator< Fst<A> > aiter(ifst, s); !aiter.Done(); aiter.Next())
245 ofst->AddArc(s, (*mapper)(aiter.Value()));
246
247 switch (final_action) {
248 case MAP_NO_SUPERFINAL:
249 default: {
250 B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
251 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
252 FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc";
253 ofst->SetProperties(kError, kError);
254 }
255 ofst->SetFinal(s, final_arc.weight);
256 break;
257 }
258 case MAP_ALLOW_SUPERFINAL: {
259 B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
260 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
261 // Add a superfinal state if not already done.
262 if (superfinal == kNoStateId) {
263 superfinal = ofst->AddState();
264 ofst->SetFinal(superfinal, B::Weight::One());
265 }
266 final_arc.nextstate = superfinal;
267 ofst->AddArc(s, final_arc);
268 ofst->SetFinal(s, B::Weight::Zero());
269 } else {
270 ofst->SetFinal(s, final_arc.weight);
271 }
272 break;
273 }
274 case MAP_REQUIRE_SUPERFINAL: {
275 B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId));
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));
280 ofst->SetFinal(s, B::Weight::Zero());
281 break;
282 }
283 }
284 }
285 uint64 oprops = ofst->Properties(kFstProperties, false);
286 ofst->SetProperties(mapper->Properties(iprops) | oprops, kFstProperties);
287 }
288
289 // Maps an arc type A to an arc type B using mapper function
290 // object C, passed by value. This version writes the mapped input
291 // Fst to an output MutableFst.
292 template<class A, class B, class C>
ArcMap(const Fst<A> & ifst,MutableFst<B> * ofst,C mapper)293 void ArcMap(const Fst<A> &ifst, MutableFst<B> *ofst, C mapper) {
294 ArcMap(ifst, ofst, &mapper);
295 }
296
297
298 struct ArcMapFstOptions : public CacheOptions {
299 // ArcMapFst default caching behaviour is to do no caching. Most
300 // mappers are cheap and therefore we save memory by not doing
301 // caching.
ArcMapFstOptionsArcMapFstOptions302 ArcMapFstOptions() : CacheOptions(true, 0) {}
ArcMapFstOptionsArcMapFstOptions303 ArcMapFstOptions(const CacheOptions& opts) : CacheOptions(opts) {}
304 };
305
306
307 template <class A, class B, class C> class ArcMapFst;
308
309 // Implementation of delayed ArcMapFst.
310 template <class A, class B, class C>
311 class ArcMapFstImpl : public CacheImpl<B> {
312 public:
313 using FstImpl<B>::SetType;
314 using FstImpl<B>::SetProperties;
315 using FstImpl<B>::SetInputSymbols;
316 using FstImpl<B>::SetOutputSymbols;
317
318 using VectorFstBaseImpl<typename CacheImpl<B>::State>::NumStates;
319
320 using CacheImpl<B>::PushArc;
321 using CacheImpl<B>::HasArcs;
322 using CacheImpl<B>::HasFinal;
323 using CacheImpl<B>::HasStart;
324 using CacheImpl<B>::SetArcs;
325 using CacheImpl<B>::SetFinal;
326 using CacheImpl<B>::SetStart;
327
328 friend class StateIterator< ArcMapFst<A, B, C> >;
329
330 typedef B Arc;
331 typedef typename B::Weight Weight;
332 typedef typename B::StateId StateId;
333
ArcMapFstImpl(const Fst<A> & fst,const C & mapper,const ArcMapFstOptions & opts)334 ArcMapFstImpl(const Fst<A> &fst, const C &mapper,
335 const ArcMapFstOptions& opts)
336 : CacheImpl<B>(opts),
337 fst_(fst.Copy()),
338 mapper_(new C(mapper)),
339 own_mapper_(true),
340 superfinal_(kNoStateId),
341 nstates_(0) {
342 Init();
343 }
344
ArcMapFstImpl(const Fst<A> & fst,C * mapper,const ArcMapFstOptions & opts)345 ArcMapFstImpl(const Fst<A> &fst, C *mapper,
346 const ArcMapFstOptions& opts)
347 : CacheImpl<B>(opts),
348 fst_(fst.Copy()),
349 mapper_(mapper),
350 own_mapper_(false),
351 superfinal_(kNoStateId),
352 nstates_(0) {
353 Init();
354 }
355
ArcMapFstImpl(const ArcMapFstImpl<A,B,C> & impl)356 ArcMapFstImpl(const ArcMapFstImpl<A, B, C> &impl)
357 : CacheImpl<B>(impl),
358 fst_(impl.fst_->Copy(true)),
359 mapper_(new C(*impl.mapper_)),
360 own_mapper_(true),
361 superfinal_(kNoStateId),
362 nstates_(0) {
363 Init();
364 }
365
~ArcMapFstImpl()366 ~ArcMapFstImpl() {
367 delete fst_;
368 if (own_mapper_) delete mapper_;
369 }
370
Start()371 StateId Start() {
372 if (!HasStart())
373 SetStart(FindOState(fst_->Start()));
374 return CacheImpl<B>::Start();
375 }
376
Final(StateId s)377 Weight Final(StateId s) {
378 if (!HasFinal(s)) {
379 switch (final_action_) {
380 case MAP_NO_SUPERFINAL:
381 default: {
382 B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
383 kNoStateId));
384 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
385 FSTERROR() << "ArcMapFst: non-zero arc labels for superfinal arc";
386 SetProperties(kError, kError);
387 }
388 SetFinal(s, final_arc.weight);
389 break;
390 }
391 case MAP_ALLOW_SUPERFINAL: {
392 if (s == superfinal_) {
393 SetFinal(s, Weight::One());
394 } else {
395 B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
396 kNoStateId));
397 if (final_arc.ilabel == 0 && final_arc.olabel == 0)
398 SetFinal(s, final_arc.weight);
399 else
400 SetFinal(s, Weight::Zero());
401 }
402 break;
403 }
404 case MAP_REQUIRE_SUPERFINAL: {
405 SetFinal(s, s == superfinal_ ? Weight::One() : Weight::Zero());
406 break;
407 }
408 }
409 }
410 return CacheImpl<B>::Final(s);
411 }
412
NumArcs(StateId s)413 size_t NumArcs(StateId s) {
414 if (!HasArcs(s))
415 Expand(s);
416 return CacheImpl<B>::NumArcs(s);
417 }
418
NumInputEpsilons(StateId s)419 size_t NumInputEpsilons(StateId s) {
420 if (!HasArcs(s))
421 Expand(s);
422 return CacheImpl<B>::NumInputEpsilons(s);
423 }
424
NumOutputEpsilons(StateId s)425 size_t NumOutputEpsilons(StateId s) {
426 if (!HasArcs(s))
427 Expand(s);
428 return CacheImpl<B>::NumOutputEpsilons(s);
429 }
430
Properties()431 uint64 Properties() const { return Properties(kFstProperties); }
432
433 // Set error if found; return FST impl properties.
Properties(uint64 mask)434 uint64 Properties(uint64 mask) const {
435 if ((mask & kError) && (fst_->Properties(kError, false) ||
436 (mapper_->Properties(0) & kError)))
437 SetProperties(kError, kError);
438 return FstImpl<Arc>::Properties(mask);
439 }
440
InitArcIterator(StateId s,ArcIteratorData<B> * data)441 void InitArcIterator(StateId s, ArcIteratorData<B> *data) {
442 if (!HasArcs(s))
443 Expand(s);
444 CacheImpl<B>::InitArcIterator(s, data);
445 }
446
Expand(StateId s)447 void Expand(StateId s) {
448 // Add exiting arcs.
449 if (s == superfinal_) { SetArcs(s); return; }
450
451 for (ArcIterator< Fst<A> > aiter(*fst_, FindIState(s));
452 !aiter.Done(); aiter.Next()) {
453 A aarc(aiter.Value());
454 aarc.nextstate = FindOState(aarc.nextstate);
455 const B& barc = (*mapper_)(aarc);
456 PushArc(s, barc);
457 }
458
459 // Check for superfinal arcs.
460 if (!HasFinal(s) || Final(s) == Weight::Zero())
461 switch (final_action_) {
462 case MAP_NO_SUPERFINAL:
463 default:
464 break;
465 case MAP_ALLOW_SUPERFINAL: {
466 B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
467 kNoStateId));
468 if (final_arc.ilabel != 0 || final_arc.olabel != 0) {
469 if (superfinal_ == kNoStateId)
470 superfinal_ = nstates_++;
471 final_arc.nextstate = superfinal_;
472 PushArc(s, final_arc);
473 }
474 break;
475 }
476 case MAP_REQUIRE_SUPERFINAL: {
477 B final_arc = (*mapper_)(A(0, 0, fst_->Final(FindIState(s)),
478 kNoStateId));
479 if (final_arc.ilabel != 0 || final_arc.olabel != 0 ||
480 final_arc.weight != B::Weight::Zero())
481 PushArc(s, B(final_arc.ilabel, final_arc.olabel,
482 final_arc.weight, superfinal_));
483 break;
484 }
485 }
486 SetArcs(s);
487 }
488
489 private:
Init()490 void Init() {
491 SetType("map");
492
493 if (mapper_->InputSymbolsAction() == MAP_COPY_SYMBOLS)
494 SetInputSymbols(fst_->InputSymbols());
495 else if (mapper_->InputSymbolsAction() == MAP_CLEAR_SYMBOLS)
496 SetInputSymbols(0);
497
498 if (mapper_->OutputSymbolsAction() == MAP_COPY_SYMBOLS)
499 SetOutputSymbols(fst_->OutputSymbols());
500 else if (mapper_->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS)
501 SetOutputSymbols(0);
502
503 if (fst_->Start() == kNoStateId) {
504 final_action_ = MAP_NO_SUPERFINAL;
505 SetProperties(kNullProperties);
506 } else {
507 final_action_ = mapper_->FinalAction();
508 uint64 props = fst_->Properties(kCopyProperties, false);
509 SetProperties(mapper_->Properties(props));
510 if (final_action_ == MAP_REQUIRE_SUPERFINAL)
511 superfinal_ = 0;
512 }
513 }
514
515 // Maps from output state to input state.
FindIState(StateId s)516 StateId FindIState(StateId s) {
517 if (superfinal_ == kNoStateId || s < superfinal_)
518 return s;
519 else
520 return s - 1;
521 }
522
523 // Maps from input state to output state.
FindOState(StateId is)524 StateId FindOState(StateId is) {
525 StateId os;
526 if (superfinal_ == kNoStateId || is < superfinal_)
527 os = is;
528 else
529 os = is + 1;
530
531 if (os >= nstates_)
532 nstates_ = os + 1;
533
534 return os;
535 }
536
537
538 const Fst<A> *fst_;
539 C* mapper_;
540 bool own_mapper_;
541 MapFinalAction final_action_;
542
543 StateId superfinal_;
544 StateId nstates_;
545
546 void operator=(const ArcMapFstImpl<A, B, C> &); // disallow
547 };
548
549
550 // Maps an arc type A to an arc type B using Mapper function object
551 // C. This version is a delayed Fst.
552 template <class A, class B, class C>
553 class ArcMapFst : public ImplToFst< ArcMapFstImpl<A, B, C> > {
554 public:
555 friend class ArcIterator< ArcMapFst<A, B, C> >;
556 friend class StateIterator< ArcMapFst<A, B, C> >;
557
558 typedef B Arc;
559 typedef typename B::Weight Weight;
560 typedef typename B::StateId StateId;
561 typedef CacheState<B> State;
562 typedef ArcMapFstImpl<A, B, C> Impl;
563
ArcMapFst(const Fst<A> & fst,const C & mapper,const ArcMapFstOptions & opts)564 ArcMapFst(const Fst<A> &fst, const C &mapper, const ArcMapFstOptions& opts)
565 : ImplToFst<Impl>(new Impl(fst, mapper, opts)) {}
566
ArcMapFst(const Fst<A> & fst,C * mapper,const ArcMapFstOptions & opts)567 ArcMapFst(const Fst<A> &fst, C* mapper, const ArcMapFstOptions& opts)
568 : ImplToFst<Impl>(new Impl(fst, mapper, opts)) {}
569
ArcMapFst(const Fst<A> & fst,const C & mapper)570 ArcMapFst(const Fst<A> &fst, const C &mapper)
571 : ImplToFst<Impl>(new Impl(fst, mapper, ArcMapFstOptions())) {}
572
ArcMapFst(const Fst<A> & fst,C * mapper)573 ArcMapFst(const Fst<A> &fst, C* mapper)
574 : ImplToFst<Impl>(new Impl(fst, mapper, ArcMapFstOptions())) {}
575
576 // See Fst<>::Copy() for doc.
577 ArcMapFst(const ArcMapFst<A, B, C> &fst, bool safe = false)
578 : ImplToFst<Impl>(fst, safe) {}
579
580 // Get a copy of this ArcMapFst. See Fst<>::Copy() for further doc.
581 virtual ArcMapFst<A, B, C> *Copy(bool safe = false) const {
582 return new ArcMapFst<A, B, C>(*this, safe);
583 }
584
585 virtual inline void InitStateIterator(StateIteratorData<B> *data) const;
586
InitArcIterator(StateId s,ArcIteratorData<B> * data)587 virtual void InitArcIterator(StateId s, ArcIteratorData<B> *data) const {
588 GetImpl()->InitArcIterator(s, data);
589 }
590
591 private:
592 // Makes visible to friends.
GetImpl()593 Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }
594
595 void operator=(const ArcMapFst<A, B, C> &fst); // disallow
596 };
597
598
599 // Specialization for ArcMapFst.
600 template<class A, class B, class C>
601 class StateIterator< ArcMapFst<A, B, C> > : public StateIteratorBase<B> {
602 public:
603 typedef typename B::StateId StateId;
604
StateIterator(const ArcMapFst<A,B,C> & fst)605 explicit StateIterator(const ArcMapFst<A, B, C> &fst)
606 : impl_(fst.GetImpl()), siter_(*impl_->fst_), s_(0),
607 superfinal_(impl_->final_action_ == MAP_REQUIRE_SUPERFINAL)
608 { CheckSuperfinal(); }
609
Done()610 bool Done() const { return siter_.Done() && !superfinal_; }
611
Value()612 StateId Value() const { return s_; }
613
Next()614 void Next() {
615 ++s_;
616 if (!siter_.Done()) {
617 siter_.Next();
618 CheckSuperfinal();
619 }
620 else if (superfinal_)
621 superfinal_ = false;
622 }
623
Reset()624 void Reset() {
625 s_ = 0;
626 siter_.Reset();
627 superfinal_ = impl_->final_action_ == MAP_REQUIRE_SUPERFINAL;
628 CheckSuperfinal();
629 }
630
631 private:
632 // This allows base-class virtual access to non-virtual derived-
633 // class members of the same name. It makes the derived class more
634 // efficient to use but unsafe to further derive.
Done_()635 bool Done_() const { return Done(); }
Value_()636 StateId Value_() const { return Value(); }
Next_()637 void Next_() { Next(); }
Reset_()638 void Reset_() { Reset(); }
639
CheckSuperfinal()640 void CheckSuperfinal() {
641 if (impl_->final_action_ != MAP_ALLOW_SUPERFINAL || superfinal_)
642 return;
643 if (!siter_.Done()) {
644 B final_arc = (*impl_->mapper_)(A(0, 0, impl_->fst_->Final(s_),
645 kNoStateId));
646 if (final_arc.ilabel != 0 || final_arc.olabel != 0)
647 superfinal_ = true;
648 }
649 }
650
651 const ArcMapFstImpl<A, B, C> *impl_;
652 StateIterator< Fst<A> > siter_;
653 StateId s_;
654 bool superfinal_; // true if there is a superfinal state and not done
655
656 DISALLOW_COPY_AND_ASSIGN(StateIterator);
657 };
658
659
660 // Specialization for ArcMapFst.
661 template <class A, class B, class C>
662 class ArcIterator< ArcMapFst<A, B, C> >
663 : public CacheArcIterator< ArcMapFst<A, B, C> > {
664 public:
665 typedef typename A::StateId StateId;
666
ArcIterator(const ArcMapFst<A,B,C> & fst,StateId s)667 ArcIterator(const ArcMapFst<A, B, C> &fst, StateId s)
668 : CacheArcIterator< ArcMapFst<A, B, C> >(fst.GetImpl(), s) {
669 if (!fst.GetImpl()->HasArcs(s))
670 fst.GetImpl()->Expand(s);
671 }
672
673 private:
674 DISALLOW_COPY_AND_ASSIGN(ArcIterator);
675 };
676
677 template <class A, class B, class C> inline
InitStateIterator(StateIteratorData<B> * data)678 void ArcMapFst<A, B, C>::InitStateIterator(StateIteratorData<B> *data)
679 const {
680 data->base = new StateIterator< ArcMapFst<A, B, C> >(*this);
681 }
682
683
684 //
685 // Utility Mappers
686 //
687
688 // Mapper that returns its input.
689 template <class A>
690 struct IdentityArcMapper {
691 typedef A FromArc;
692 typedef A ToArc;
693
operatorIdentityArcMapper694 A operator()(const A &arc) const { return arc; }
695
FinalActionIdentityArcMapper696 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
697
InputSymbolsActionIdentityArcMapper698 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
699
OutputSymbolsActionIdentityArcMapper700 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
701
PropertiesIdentityArcMapper702 uint64 Properties(uint64 props) const { return props; }
703 };
704
705
706 // Mapper that returns its input with final states redirected to
707 // a single super-final state.
708 template <class A>
709 struct SuperFinalMapper {
710 typedef A FromArc;
711 typedef A ToArc;
712
operatorSuperFinalMapper713 A operator()(const A &arc) const { return arc; }
714
FinalActionSuperFinalMapper715 MapFinalAction FinalAction() const { return MAP_REQUIRE_SUPERFINAL; }
716
InputSymbolsActionSuperFinalMapper717 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
718
OutputSymbolsActionSuperFinalMapper719 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
720
PropertiesSuperFinalMapper721 uint64 Properties(uint64 props) const {
722 return props & kAddSuperFinalProperties;
723 }
724 };
725
726
727 // Mapper that leaves labels and nextstate unchanged and constructs a new weight
728 // from the underlying value of the arc weight. Requires that there is a
729 // WeightConvert class specialization that converts the weights.
730 template <class A, class B>
731 class WeightConvertMapper {
732 public:
733 typedef A FromArc;
734 typedef B ToArc;
735 typedef typename FromArc::Weight FromWeight;
736 typedef typename ToArc::Weight ToWeight;
737
operator()738 ToArc operator()(const FromArc &arc) const {
739 return ToArc(arc.ilabel, arc.olabel,
740 convert_weight_(arc.weight), arc.nextstate);
741 }
742
FinalAction()743 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
744
InputSymbolsAction()745 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
746
OutputSymbolsAction()747 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
748
Properties(uint64 props)749 uint64 Properties(uint64 props) const { return props; }
750
751 private:
752 WeightConvert<FromWeight, ToWeight> convert_weight_;
753 };
754
755 // Non-precision-changing weight conversions.
756 // Consider using more efficient Cast (fst.h) instead.
757 typedef WeightConvertMapper<StdArc, LogArc> StdToLogMapper;
758 typedef WeightConvertMapper<LogArc, StdArc> LogToStdMapper;
759
760 // Precision-changing weight conversions.
761 typedef WeightConvertMapper<StdArc, Log64Arc> StdToLog64Mapper;
762 typedef WeightConvertMapper<LogArc, Log64Arc> LogToLog64Mapper;
763 typedef WeightConvertMapper<Log64Arc, StdArc> Log64ToStdMapper;
764 typedef WeightConvertMapper<Log64Arc, LogArc> Log64ToLogMapper;
765
766 // Mapper from A to GallicArc<A>.
767 template <class A, StringType S = STRING_LEFT>
768 struct ToGallicMapper {
769 typedef A FromArc;
770 typedef GallicArc<A, S> ToArc;
771
772 typedef StringWeight<typename A::Label, S> SW;
773 typedef typename A::Weight AW;
774 typedef typename GallicArc<A, S>::Weight GW;
775
operatorToGallicMapper776 ToArc operator()(const A &arc) const {
777 // 'Super-final' arc.
778 if (arc.nextstate == kNoStateId && arc.weight != AW::Zero())
779 return ToArc(0, 0, GW(SW::One(), arc.weight), kNoStateId);
780 // 'Super-non-final' arc.
781 else if (arc.nextstate == kNoStateId)
782 return ToArc(0, 0, GW(SW::Zero(), arc.weight), kNoStateId);
783 // Epsilon label.
784 else if (arc.olabel == 0)
785 return ToArc(arc.ilabel, arc.ilabel,
786 GW(SW::One(), arc.weight), arc.nextstate);
787 // Regular label.
788 else
789 return ToArc(arc.ilabel, arc.ilabel,
790 GW(SW(arc.olabel), arc.weight), arc.nextstate);
791 }
792
FinalActionToGallicMapper793 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
794
InputSymbolsActionToGallicMapper795 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
796
OutputSymbolsActionToGallicMapper797 MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;}
798
PropertiesToGallicMapper799 uint64 Properties(uint64 props) const {
800 return ProjectProperties(props, true) & kWeightInvariantProperties;
801 }
802 };
803
804
805 // Mapper from GallicArc<A> to A.
806 template <class A, StringType S = STRING_LEFT>
807 struct FromGallicMapper {
808 typedef GallicArc<A, S> FromArc;
809 typedef A ToArc;
810
811 typedef typename A::Label Label;
812 typedef StringWeight<Label, S> SW;
813 typedef typename A::Weight AW;
814 typedef typename GallicArc<A, S>::Weight GW;
815
816 FromGallicMapper(Label superfinal_label = 0)
superfinal_label_FromGallicMapper817 : superfinal_label_(superfinal_label), error_(false) {}
818
operatorFromGallicMapper819 A operator()(const FromArc &arc) const {
820 // 'Super-non-final' arc.
821 if (arc.nextstate == kNoStateId && arc.weight == GW::Zero())
822 return A(arc.ilabel, 0, AW::Zero(), kNoStateId);
823
824 SW w1 = arc.weight.Value1();
825 AW w2 = arc.weight.Value2();
826 StringWeightIterator<Label, S> iter1(w1);
827
828 Label l = w1.Size() == 1 ? iter1.Value() : 0;
829
830 if (l == kStringInfinity || l == kStringBad ||
831 arc.ilabel != arc.olabel || w1.Size() > 1) {
832 FSTERROR() << "FromGallicMapper: unrepesentable weight";
833 error_ = true;
834 }
835
836 if (arc.ilabel == 0 && l != 0 && arc.nextstate == kNoStateId)
837 return A(superfinal_label_, l, w2, arc.nextstate);
838 else
839 return A(arc.ilabel, l, w2, arc.nextstate);
840 }
841
FinalActionFromGallicMapper842 MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; }
843
InputSymbolsActionFromGallicMapper844 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
845
OutputSymbolsActionFromGallicMapper846 MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;}
847
PropertiesFromGallicMapper848 uint64 Properties(uint64 inprops) const {
849 uint64 outprops = inprops & kOLabelInvariantProperties &
850 kWeightInvariantProperties & kAddSuperFinalProperties;
851 if (error_)
852 outprops |= kError;
853 return outprops;
854 }
855
856 private:
857 Label superfinal_label_;
858 mutable bool error_;
859 };
860
861
862 // Mapper from GallicArc<A> to A.
863 template <class A, StringType S = STRING_LEFT>
864 struct GallicToNewSymbolsMapper {
865 typedef GallicArc<A, S> FromArc;
866 typedef A ToArc;
867
868 typedef typename A::StateId StateId;
869 typedef typename A::Label Label;
870 typedef StringWeight<Label, S> SW;
871 typedef typename A::Weight AW;
872 typedef typename GallicArc<A, S>::Weight GW;
873
GallicToNewSymbolsMapperGallicToNewSymbolsMapper874 GallicToNewSymbolsMapper(MutableFst<ToArc> *fst)
875 : fst_(fst), lmax_(0), osymbols_(fst->OutputSymbols()),
876 isymbols_(0), error_(false) {
877 fst_->DeleteStates();
878 state_ = fst_->AddState();
879 fst_->SetStart(state_);
880 fst_->SetFinal(state_, AW::One());
881 if (osymbols_) {
882 string name = osymbols_->Name() + "_from_gallic";
883 fst_->SetInputSymbols(new SymbolTable(name));
884 isymbols_ = fst_->MutableInputSymbols();
885 isymbols_->AddSymbol(osymbols_->Find((int64) 0), 0);
886 } else {
887 fst_->SetInputSymbols(0);
888 }
889 }
890
operatorGallicToNewSymbolsMapper891 A operator()(const FromArc &arc) {
892 // 'Super-non-final' arc.
893 if (arc.nextstate == kNoStateId && arc.weight == GW::Zero())
894 return A(arc.ilabel, 0, AW::Zero(), kNoStateId);
895
896 SW w1 = arc.weight.Value1();
897 AW w2 = arc.weight.Value2();
898 Label l;
899
900 if (w1.Size() == 0) {
901 l = 0;
902 } else {
903 typename Map::iterator miter = map_.find(w1);
904 if (miter != map_.end()) {
905 l = (*miter).second;
906 } else {
907 l = ++lmax_;
908 map_.insert(pair<const SW, Label>(w1, l));
909 StringWeightIterator<Label, S> iter1(w1);
910 StateId n;
911 string s;
912 for(size_t i = 0, p = state_;
913 i < w1.Size();
914 ++i, iter1.Next(), p = n) {
915 n = i == w1.Size() - 1 ? state_ : fst_->AddState();
916 fst_->AddArc(p, ToArc(i ? 0 : l, iter1.Value(), AW::One(), n));
917 if (isymbols_) {
918 if (i) s = s + "_";
919 s = s + osymbols_->Find(iter1.Value());
920 }
921 }
922 if (isymbols_)
923 isymbols_->AddSymbol(s, l);
924 }
925 }
926
927 if (l == kStringInfinity || l == kStringBad || arc.ilabel != arc.olabel) {
928 FSTERROR() << "GallicToNewSymbolMapper: unrepesentable weight";
929 error_ = true;
930 }
931
932 return A(arc.ilabel, l, w2, arc.nextstate);
933 }
934
FinalActionGallicToNewSymbolsMapper935 MapFinalAction FinalAction() const { return MAP_ALLOW_SUPERFINAL; }
936
InputSymbolsActionGallicToNewSymbolsMapper937 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
938
OutputSymbolsActionGallicToNewSymbolsMapper939 MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; }
940
PropertiesGallicToNewSymbolsMapper941 uint64 Properties(uint64 inprops) const {
942 uint64 outprops = inprops & kOLabelInvariantProperties &
943 kWeightInvariantProperties & kAddSuperFinalProperties;
944 if (error_)
945 outprops |= kError;
946 return outprops;
947 }
948
949 private:
950 class StringKey {
951 public:
operatorGallicToNewSymbolsMapper952 size_t operator()(const SW &x) const {
953 return x.Hash();
954 }
955 };
956
957 typedef unordered_map<SW, Label, StringKey> Map;
958
959 MutableFst<ToArc> *fst_;
960 Map map_;
961 Label lmax_;
962 StateId state_;
963 const SymbolTable *osymbols_;
964 SymbolTable *isymbols_;
965 mutable bool error_;
966
967 DISALLOW_COPY_AND_ASSIGN(GallicToNewSymbolsMapper);
968 };
969
970
971 // Mapper to add a constant to all weights.
972 template <class A>
973 struct PlusMapper {
974 typedef A FromArc;
975 typedef A ToArc;
976 typedef typename A::Weight Weight;
977
PlusMapperPlusMapper978 explicit PlusMapper(Weight w) : weight_(w) {}
979
operatorPlusMapper980 A operator()(const A &arc) const {
981 if (arc.weight == Weight::Zero())
982 return arc;
983 Weight w = Plus(arc.weight, weight_);
984 return A(arc.ilabel, arc.olabel, w, arc.nextstate);
985 }
986
FinalActionPlusMapper987 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
988
InputSymbolsActionPlusMapper989 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
990
OutputSymbolsActionPlusMapper991 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
992
PropertiesPlusMapper993 uint64 Properties(uint64 props) const {
994 return props & kWeightInvariantProperties;
995 }
996
997 private:
998
999
1000
1001 Weight weight_;
1002 };
1003
1004
1005 // Mapper to (right) multiply a constant to all weights.
1006 template <class A>
1007 struct TimesMapper {
1008 typedef A FromArc;
1009 typedef A ToArc;
1010 typedef typename A::Weight Weight;
1011
TimesMapperTimesMapper1012 explicit TimesMapper(Weight w) : weight_(w) {}
1013
operatorTimesMapper1014 A operator()(const A &arc) const {
1015 if (arc.weight == Weight::Zero())
1016 return arc;
1017 Weight w = Times(arc.weight, weight_);
1018 return A(arc.ilabel, arc.olabel, w, arc.nextstate);
1019 }
1020
FinalActionTimesMapper1021 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
1022
InputSymbolsActionTimesMapper1023 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
1024
OutputSymbolsActionTimesMapper1025 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
1026
PropertiesTimesMapper1027 uint64 Properties(uint64 props) const {
1028 return props & kWeightInvariantProperties;
1029 }
1030
1031 private:
1032 Weight weight_;
1033 };
1034
1035
1036 // Mapper to reciprocate all non-Zero() weights.
1037 template <class A>
1038 struct InvertWeightMapper {
1039 typedef A FromArc;
1040 typedef A ToArc;
1041 typedef typename A::Weight Weight;
1042
operatorInvertWeightMapper1043 A operator()(const A &arc) const {
1044 if (arc.weight == Weight::Zero())
1045 return arc;
1046 Weight w = Divide(Weight::One(), arc.weight);
1047 return A(arc.ilabel, arc.olabel, w, arc.nextstate);
1048 }
1049
FinalActionInvertWeightMapper1050 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
1051
InputSymbolsActionInvertWeightMapper1052 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
1053
OutputSymbolsActionInvertWeightMapper1054 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
1055
PropertiesInvertWeightMapper1056 uint64 Properties(uint64 props) const {
1057 return props & kWeightInvariantProperties;
1058 }
1059 };
1060
1061
1062 // Mapper to map all non-Zero() weights to One().
1063 template <class A, class B = A>
1064 struct RmWeightMapper {
1065 typedef A FromArc;
1066 typedef B ToArc;
1067 typedef typename FromArc::Weight FromWeight;
1068 typedef typename ToArc::Weight ToWeight;
1069
operatorRmWeightMapper1070 B operator()(const A &arc) const {
1071 ToWeight w = arc.weight != FromWeight::Zero() ?
1072 ToWeight::One() : ToWeight::Zero();
1073 return B(arc.ilabel, arc.olabel, w, arc.nextstate);
1074 }
1075
FinalActionRmWeightMapper1076 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
1077
InputSymbolsActionRmWeightMapper1078 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
1079
OutputSymbolsActionRmWeightMapper1080 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
1081
PropertiesRmWeightMapper1082 uint64 Properties(uint64 props) const {
1083 return (props & kWeightInvariantProperties) | kUnweighted;
1084 }
1085 };
1086
1087
1088 // Mapper to quantize all weights.
1089 template <class A, class B = A>
1090 struct QuantizeMapper {
1091 typedef A FromArc;
1092 typedef B ToArc;
1093 typedef typename FromArc::Weight FromWeight;
1094 typedef typename ToArc::Weight ToWeight;
1095
QuantizeMapperQuantizeMapper1096 QuantizeMapper() : delta_(kDelta) {}
1097
QuantizeMapperQuantizeMapper1098 explicit QuantizeMapper(float d) : delta_(d) {}
1099
operatorQuantizeMapper1100 B operator()(const A &arc) const {
1101 ToWeight w = arc.weight.Quantize(delta_);
1102 return B(arc.ilabel, arc.olabel, w, arc.nextstate);
1103 }
1104
FinalActionQuantizeMapper1105 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
1106
InputSymbolsActionQuantizeMapper1107 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
1108
OutputSymbolsActionQuantizeMapper1109 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
1110
PropertiesQuantizeMapper1111 uint64 Properties(uint64 props) const {
1112 return props & kWeightInvariantProperties;
1113 }
1114
1115 private:
1116 float delta_;
1117 };
1118
1119
1120 // Mapper from A to B under the assumption:
1121 // B::Weight = A::Weight::ReverseWeight
1122 // B::Label == A::Label
1123 // B::StateId == A::StateId
1124 // The weight is reversed, while the label and nextstate preserved
1125 // in the mapping.
1126 template <class A, class B>
1127 struct ReverseWeightMapper {
1128 typedef A FromArc;
1129 typedef B ToArc;
1130
operatorReverseWeightMapper1131 B operator()(const A &arc) const {
1132 return B(arc.ilabel, arc.olabel, arc.weight.Reverse(), arc.nextstate);
1133 }
1134
FinalActionReverseWeightMapper1135 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
1136
InputSymbolsActionReverseWeightMapper1137 MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
1138
OutputSymbolsActionReverseWeightMapper1139 MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
1140
PropertiesReverseWeightMapper1141 uint64 Properties(uint64 props) const { return props; }
1142 };
1143
1144 } // namespace fst
1145
1146 #endif // FST_LIB_ARC_MAP_H__
1147