1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// invert.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: riley@google.com (Michael Riley) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Functions and classes to invert an Fst. 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_INVERT_H__ 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_INVERT_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arc-map.h> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/mutable-fst.h> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Mapper to implement inversion of an arc. 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> struct InvertMapper { 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson InvertMapper() {} 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A operator()(const A &arc) { 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return A(arc.olabel, arc.ilabel, arc.weight, arc.nextstate); 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MapSymbolsAction InputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; } 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;} 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 Properties(uint64 props) { return InvertProperties(props); } 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Inverts the transduction corresponding to an FST by exchanging the 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST's input and output labels. This version modifies its input. 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Complexity: 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Time: O(V + E) 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Space: O(1) 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// where V = # of states and E = # of arcs. 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> inline 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid Invert(MutableFst<Arc> *fst) { 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SymbolTable *input = fst->InputSymbols() ? fst->InputSymbols()->Copy() : 0; 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SymbolTable *output = fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : 0; 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcMap(fst, InvertMapper<Arc>()); 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetInputSymbols(output); 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst->SetOutputSymbols(input); 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete input; 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete output; 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Inverts the transduction corresponding to an FST by exchanging the 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST's input and output labels. This version is a delayed Fst. 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Complexity: 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Time: O(v + e) 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// - Space: O(1) 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// where v = # of states visited, e = # of arcs visited. Constant 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// time and to visit an input state or arc is assumed and exclusive 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// of caching. 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass InvertFst : public ArcMapFst<A, A, InvertMapper<A> > { 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef InvertMapper<A> C; 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef ArcMapFstImpl< A, A, InvertMapper<A> > Impl; 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using ImplToFst<Impl>::GetImpl; 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit InvertFst(const Fst<A> &fst) : ArcMapFst<A, A, C>(fst, C()) { 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetImpl()->SetOutputSymbols(fst.InputSymbols()); 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson GetImpl()->SetInputSymbols(fst.OutputSymbols()); 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // See Fst<>::Copy() for doc. 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson InvertFst(const InvertFst<A> &fst, bool safe = false) 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ArcMapFst<A, A, C>(fst, safe) {} 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Get a copy of this InvertFst. See Fst<>::Copy() for further doc. 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual InvertFst<A> *Copy(bool safe = false) const { 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return new InvertFst(*this, safe); 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specialization for InvertFst. 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StateIterator< InvertFst<A> > 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public StateIterator< ArcMapFst<A, A, InvertMapper<A> > > { 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson explicit StateIterator(const InvertFst<A> &fst) 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : StateIterator< ArcMapFst<A, A, InvertMapper<A> > >(fst) {} 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specialization for InvertFst. 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A> 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ArcIterator< InvertFst<A> > 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : public ArcIterator< ArcMapFst<A, A, InvertMapper<A> > > { 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcIterator(const InvertFst<A> &fst, typename A::StateId s) 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : ArcIterator< ArcMapFst<A, A, InvertMapper<A> > >(fst, s) {} 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Useful alias when using StdArc. 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef InvertFst<StdArc> StdInvertFst; 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_INVERT_H__ 126