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) const {
  24     return ToArc(arc.olabel, arc.ilabel, arc.weight, arc.nextstate);
  25   }
  26
  27   constexpr MapFinalAction FinalAction() const {
  28      return MAP_NO_SUPERFINAL;
  29   }
  30
  31   constexpr MapSymbolsAction InputSymbolsAction() const {
  32     return MAP_CLEAR_SYMBOLS;
  33   }
  34
  35   constexpr MapSymbolsAction OutputSymbolsAction() const {
  36     return MAP_CLEAR_SYMBOLS;
  37   }
  38
  39   uint64 Properties(uint64 props) const {
  40     return InvertProperties(props);
  41   }
  42 };
  43
  44 // Inverts the transduction corresponding to an FST by exchanging the
  45 // FST's input and output labels.
  46 //
  47 // Complexity:
  48 //
  49 //   Time: O(V + E)
  50 //   Space: O(1)
  51 //
  52 // where V is the number of states and E is the number of arcs.
  53 template <class Arc>
  54 inline void Invert(const Fst<Arc> &ifst, MutableFst<Arc> *ofst) {
  55   std::unique_ptr<SymbolTable> input(
  56       ifst.InputSymbols() ? ifst.InputSymbols()->Copy() : nullptr);
  57   std::unique_ptr<SymbolTable> output(
  58       ifst.OutputSymbols() ? ifst.OutputSymbols()->Copy() : nullptr);
  59   ArcMap(ifst, ofst, InvertMapper<Arc>());
  60   ofst->SetInputSymbols(output.get());
  61   ofst->SetOutputSymbols(input.get());
  62 }
  63
  64 // Destructive variant of the above.
  65 template <class Arc>
  66 inline void Invert(MutableFst<Arc> *fst) {
  67   std::unique_ptr<SymbolTable> input(
  68       fst->InputSymbols() ? fst->InputSymbols()->Copy() : nullptr);
  69   std::unique_ptr<SymbolTable> output(
  70       fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : nullptr);
  71   ArcMap(fst, InvertMapper<Arc>());
  72   fst->SetInputSymbols(output.get());
  73   fst->SetOutputSymbols(input.get());
  74 }
  75
  76 // Inverts the transduction corresponding to an FST by exchanging the
  77 // FST's input and output labels. This version is a delayed FST.
  78 //
  79 // Complexity:
  80 //
  81 //   Time: O(v + e)
  82 //   Space: O(1)
  83 //
  84 // where v is the number of states visited and e is the number of arcs visited.
  85 // Constant time and to visit an input state or arc is assumed and exclusive of
  86 // caching.
  87 template <class A>
  88 class InvertFst : public ArcMapFst<A, A, InvertMapper<A>> {
  89  public:
  90   using Arc = A;
  91
  92   using Mapper = InvertMapper<Arc>;
  93   using Impl = internal::ArcMapFstImpl<A, A, InvertMapper<A>>;
  94
  95   explicit InvertFst(const Fst<Arc> &fst)
  96       : ArcMapFst<Arc, Arc, Mapper>(fst, Mapper()) {
  97     GetMutableImpl()->SetOutputSymbols(fst.InputSymbols());
  98     GetMutableImpl()->SetInputSymbols(fst.OutputSymbols());
  99   }
 100
 101   // See Fst<>::Copy() for doc.
 102   InvertFst(const InvertFst<Arc> &fst, bool safe = false)
 103       : ArcMapFst<Arc, Arc, Mapper>(fst, safe) {}
 104
 105   // Get a copy of this InvertFst. See Fst<>::Copy() for further doc.
 106   InvertFst<Arc> *Copy(bool safe = false) const override {
 107     return new InvertFst(*this, safe);
 108   }
 109
 110  private:
 111   using ImplToFst<Impl>::GetMutableImpl;
 112 };
 113
 114 // Specialization for InvertFst.
 115 template <class Arc>
 116 class StateIterator<InvertFst<Arc>>
 117     : public StateIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>> {
 118  public:
 119   explicit StateIterator(const InvertFst<Arc> &fst)
 120       : StateIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>>(fst) {}
 121 };
 122
 123 // Specialization for InvertFst.
 124 template <class Arc>
 125 class ArcIterator<InvertFst<Arc>>
 126     : public ArcIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>> {
 127  public:
 128   using StateId = typename Arc::StateId;
 129
 130   ArcIterator(const InvertFst<Arc> &fst, StateId s)
 131       : ArcIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>>(fst, s) {}
 132 };
 133
 134 // Useful alias when using StdArc.
 135 using StdInvertFst = InvertFst<StdArc>;
 136
 137 }  // namespace fst
 138
 139 #endif  // FST_INVERT_H_