src/include/fst/invert.h

   1 // See www.openfst.org for extensive documentation on this weighted
   2 // finite-state transducer library.
   3 //
   4 // Functions and classes to invert an FST.
   5
   6 #ifndef FST_INVERT_H_
   7 #define FST_INVERT_H_
   8
   9 #include <fst/arc-map.h>
  10 #include <fst/mutable-fst.h>
  11
  12
  13 namespace fst {
  14
  15 // Mapper to implement inversion of an arc.
  16 template <class A>
  17 struct InvertMapper {
  18   using FromArc = A;
  19   using ToArc = A;
  20
  21   InvertMapper() {}
  22
  23   ToArc operator()(const FromArc &arc) {
  24     return ToArc(arc.olabel, arc.ilabel, arc.weight, arc.nextstate);
  25   }
  26
  27   MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
  28
  29   MapSymbolsAction InputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; }
  30
  31   MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; }
  32
  33   uint64 Properties(uint64 props) { return InvertProperties(props); }
  34 };
  35
  36 // Inverts the transduction corresponding to an FST by exchanging the
  37 // FST's input and output labels. This version modifies its input.
  38 //
  39 // Complexity:
  40 //
  41 //   Time: O(V + E)
  42 //   Space: O(1)
  43 //
  44 // where V is the number of states and E is the number of arcs.
  45 template <class Arc>
  46 inline void Invert(MutableFst<Arc> *fst) {
  47   std::unique_ptr<SymbolTable> input(
  48       fst->InputSymbols() ? fst->InputSymbols()->Copy() : nullptr);
  49   std::unique_ptr<SymbolTable> output(
  50       fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : nullptr);
  51   ArcMap(fst, InvertMapper<Arc>());
  52   fst->SetInputSymbols(output.get());
  53   fst->SetOutputSymbols(input.get());
  54 }
  55
  56 // Inverts the transduction corresponding to an FST by exchanging the
  57 // FST's input and output labels. This version is a delayed FST.
  58 //
  59 // Complexity:
  60 //
  61 //   Time: O(v + e)
  62 //   Space: O(1)
  63 //
  64 // where v is the number of states visited and e is the number of arcs visited.
  65 // Constant time and to visit an input state or arc is assumed and exclusive of
  66 // caching.
  67 template <class A>
  68 class InvertFst : public ArcMapFst<A, A, InvertMapper<A>> {
  69  public:
  70   using Arc = A;
  71
  72   using Mapper = InvertMapper<Arc>;
  73   using Impl = internal::ArcMapFstImpl<A, A, InvertMapper<A>>;
  74
  75   explicit InvertFst(const Fst<Arc> &fst)
  76       : ArcMapFst<Arc, Arc, Mapper>(fst, Mapper()) {
  77     GetMutableImpl()->SetOutputSymbols(fst.InputSymbols());
  78     GetMutableImpl()->SetInputSymbols(fst.OutputSymbols());
  79   }
  80
  81   // See Fst<>::Copy() for doc.
  82   InvertFst(const InvertFst<Arc> &fst, bool safe = false)
  83       : ArcMapFst<Arc, Arc, Mapper>(fst, safe) {}
  84
  85   // Get a copy of this InvertFst. See Fst<>::Copy() for further doc.
  86   InvertFst<Arc> *Copy(bool safe = false) const override {
  87     return new InvertFst(*this, safe);
  88   }
  89
  90  private:
  91   using ImplToFst<Impl>::GetMutableImpl;
  92 };
  93
  94 // Specialization for InvertFst.
  95 template <class Arc>
  96 class StateIterator<InvertFst<Arc>>
  97     : public StateIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>> {
  98  public:
  99   explicit StateIterator(const InvertFst<Arc> &fst)
 100       : StateIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>>(fst) {}
 101 };
 102
 103 // Specialization for InvertFst.
 104 template <class Arc>
 105 class ArcIterator<InvertFst<Arc>>
 106     : public ArcIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>> {
 107  public:
 108   using StateId = typename Arc::StateId;
 109
 110   ArcIterator(const InvertFst<Arc> &fst, StateId s)
 111       : ArcIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>>(fst, s) {}
 112 };
 113
 114 // Useful alias when using StdArc.
 115 using StdInvertFst = InvertFst<StdArc>;
 116
 117 }  // namespace fst
 118
 119 #endif  // FST_INVERT_H_