FST  openfst-1.7.2
OpenFst Library
compose.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Compose an MPDT and an FST.
5 
6 #ifndef FST_EXTENSIONS_MPDT_COMPOSE_H_
7 #define FST_EXTENSIONS_MPDT_COMPOSE_H_
8 
9 #include <list>
10 
13 #include <fst/compose.h>
14 
15 namespace fst {
16 
17 template <class Filter>
19  public:
20  using FST1 = typename Filter::FST1;
21  using FST2 = typename Filter::FST2;
22  using Arc = typename Filter::Arc;
23  using Label = typename Arc::Label;
24  using StateId = typename Arc::StateId;
25  using Weight = typename Arc::Weight;
26 
27  using Matcher1 = typename Filter::Matcher1;
28  using Matcher2 = typename Filter::Matcher2;
29 
30  using StackId = StateId;
32  using FilterState1 = typename Filter::FilterState;
35 
36  MPdtParenFilter(const FST1 &fst1, const FST2 &fst2,
37  Matcher1 *matcher1 = nullptr, Matcher2 *matcher2 = nullptr,
38  const std::vector<std::pair<Label, Label>> *parens = nullptr,
39  const std::vector<Label> *assignments = nullptr,
40  bool expand = false, bool keep_parens = true)
41  : filter_(fst1, fst2, matcher1, matcher2),
42  parens_(parens ? *parens : std::vector<std::pair<Label, Label>>()),
43  assignments_(assignments ? *assignments : std::vector<Label>()),
44  expand_(expand),
45  keep_parens_(keep_parens),
46  fs_(FilterState::NoState()),
47  stack_(parens_, assignments_),
48  paren_id_(-1) {
49  if (parens) {
50  for (const auto &pair : *parens) {
51  parens_.push_back(pair);
52  GetMatcher1()->AddOpenParen(pair.first);
53  GetMatcher2()->AddOpenParen(pair.first);
54  if (!expand_) {
55  GetMatcher1()->AddCloseParen(pair.second);
56  GetMatcher2()->AddCloseParen(pair.second);
57  }
58  }
59  }
60  }
61 
62  MPdtParenFilter(const MPdtParenFilter &filter, bool safe = false)
63  : filter_(filter.filter_, safe),
64  parens_(filter.parens_),
65  expand_(filter.expand_),
66  keep_parens_(filter.keep_parens_),
67  fs_(FilterState::NoState()),
68  stack_(filter.parens_, filter.assignments_),
69  paren_id_(-1) {}
70 
71  FilterState Start() const {
72  return FilterState(filter_.Start(), FilterState2(0));
73  }
74 
75  void SetState(StateId s1, StateId s2, const FilterState &fs) {
76  fs_ = fs;
77  filter_.SetState(s1, s2, fs_.GetState1());
78  if (!expand_) return;
79  const auto paren_id = stack_.Top(fs.GetState2().GetState());
80  if (paren_id != paren_id_) {
81  if (paren_id_ != -1) {
82  GetMatcher1()->RemoveCloseParen(parens_[paren_id_].second);
83  GetMatcher2()->RemoveCloseParen(parens_[paren_id_].second);
84  }
85  paren_id_ = paren_id;
86  if (paren_id_ != -1) {
87  GetMatcher1()->AddCloseParen(parens_[paren_id_].second);
88  GetMatcher2()->AddCloseParen(parens_[paren_id_].second);
89  }
90  }
91  }
92 
93  FilterState FilterArc(Arc *arc1, Arc *arc2) const {
94  const auto fs1 = filter_.FilterArc(arc1, arc2);
95  const auto &fs2 = fs_.GetState2();
96  if (fs1 == FilterState1::NoState()) return FilterState::NoState();
97  if (arc1->olabel == kNoLabel && arc2->ilabel) { // arc2 parentheses.
98  if (keep_parens_) {
99  arc1->ilabel = arc2->ilabel;
100  } else if (arc2->ilabel) {
101  arc2->olabel = arc1->ilabel;
102  }
103  return FilterParen(arc2->ilabel, fs1, fs2);
104  } else if (arc2->ilabel == kNoLabel && arc1->olabel) { // arc1 parentheses
105  if (keep_parens_) {
106  arc2->olabel = arc1->olabel;
107  } else {
108  arc1->ilabel = arc2->olabel;
109  }
110  return FilterParen(arc1->olabel, fs1, fs2);
111  } else {
112  return FilterState(fs1, fs2);
113  }
114  }
115 
116  void FilterFinal(Weight *w1, Weight *w2) const {
117  if (fs_.GetState2().GetState() != 0) *w1 = Weight::Zero();
118  filter_.FilterFinal(w1, w2);
119  }
120 
121  // Returns respective matchers; ownership stays with filter.
122 
123  Matcher1 *GetMatcher1() { return filter_.GetMatcher1(); }
124 
125  Matcher2 *GetMatcher2() { return filter_.GetMatcher2(); }
126 
127  uint64 Properties(uint64 iprops) const {
128  const auto oprops = filter_.Properties(iprops);
130  }
131 
132  private:
133  const FilterState FilterParen(Label label, const FilterState1 &fs1,
134  const FilterState2 &fs2) const {
135  if (!expand_) return FilterState(fs1, fs2);
136  const auto stack_id = stack_.Find(fs2.GetState(), label);
137  if (stack_id < 0) {
138  return FilterState::NoState();
139  } else {
140  return FilterState(fs1, FilterState2(stack_id));
141  }
142  }
143 
144  Filter filter_;
145  std::vector<std::pair<Label, Label>> parens_;
146  std::vector<Label> assignments_;
147  bool expand_; // Expands to FST?
148  bool keep_parens_; // Retains parentheses in output?
149  FilterState fs_; // Current filter state.
150  mutable ParenStack stack_;
151  ssize_t paren_id_;
152 };
153 
154 // Class to setup composition options for MPDT composition. Default is to take
155 // the MPDT as the first composition argument.
156 template <class Arc, bool left_pdt = true>
158  : public ComposeFstOptions<Arc, ParenMatcher<Fst<Arc>>,
159  MPdtParenFilter<AltSequenceComposeFilter<
160  ParenMatcher<Fst<Arc>> >> > {
161  public:
162  using Label = typename Arc::Label;
165 
169 
171  const std::vector<std::pair<Label, Label>> &parens,
172  const std::vector<typename Arc::Label> &assignments,
173  const Fst<Arc> &ifst2, bool expand = false,
174  bool keep_parens = true) {
175  matcher1 = new MPdtMatcher(ifst1, MATCH_OUTPUT, kParenList);
176  matcher2 = new MPdtMatcher(ifst2, MATCH_INPUT, kParenLoop);
177  filter = new MPdtFilter(ifst1, ifst2, matcher1, matcher2, &parens,
178  &assignments, expand, keep_parens);
179  }
180 };
181 
182 // Class to setup composition options for PDT with FST composition.
183 // Specialization is for the FST as the first composition argument.
184 template <class Arc>
186  : public ComposeFstOptions<
187  Arc, ParenMatcher<Fst<Arc>>,
188  MPdtParenFilter<SequenceComposeFilter<ParenMatcher<Fst<Arc>> >> > {
189  public:
190  using Label = typename Arc::Label;
193 
197 
198  MPdtComposeFstOptions(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
199  const std::vector<std::pair<Label, Label>> &parens,
200  const std::vector<typename Arc::Label> &assignments,
201  bool expand = false, bool keep_parens = true) {
202  matcher1 = new MPdtMatcher(ifst1, MATCH_OUTPUT, kParenLoop);
203  matcher2 = new MPdtMatcher(ifst2, MATCH_INPUT, kParenList);
204  filter = new MPdtFilter(ifst1, ifst2, matcher1, matcher2, &parens,
205  &assignments, expand, keep_parens);
206  }
207 };
208 
210  bool connect; // Connect output?
211  PdtComposeFilter filter_type; // Which pre-defined filter to use.
212 
213  explicit MPdtComposeOptions(bool connect = true,
214  PdtComposeFilter filter_type = PAREN_FILTER)
215  : connect(connect), filter_type(filter_type) {}
216 };
217 
218 // Composes multi-pushdown transducer (MPDT) encoded as an FST (1st arg) and an
219 // FST (2nd arg) with the result also an MPDT encoded as an FST (3rd arg). In
220 // theMPDTs, some transitions are labeled with open or close parentheses (and
221 // associated with a stack). To be interpreted as an MPDT, the parents on each
222 // stack must balance on a path (see MPdtExpand()). The open-close parenthesis
223 // label pairs are passed using the parens arguments, and the stack assignments
224 // are passed using the assignments argument.
225 template <class Arc>
226 void Compose(
227  const Fst<Arc> &ifst1,
228  const std::vector<std::pair<typename Arc::Label, typename Arc::Label>>
229  &parens,
230  const std::vector<typename Arc::Label> &assignments, const Fst<Arc> &ifst2,
231  MutableFst<Arc> *ofst,
232  const MPdtComposeOptions &opts = MPdtComposeOptions()) {
233  bool expand = opts.filter_type != PAREN_FILTER;
234  bool keep_parens = opts.filter_type != EXPAND_FILTER;
235  MPdtComposeFstOptions<Arc, true> copts(ifst1, parens, assignments, ifst2,
236  expand, keep_parens);
237  copts.gc_limit = 0;
238  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
239  if (opts.connect) Connect(ofst);
240 }
241 
242 // Composes an FST (1st arg) and a multi-pushdown transducer (MPDT) encoded as
243 // an FST (2nd arg) with the result also an MPDT encoded as an FST (3rd arg).
244 // In the MPDTs, some transitions are labeled with open or close parentheses
245 // (and associated with a stack). To be interpreted as an MPDT, the parents on
246 // each stack must balance on a path (see MPdtExpand()). The open-close
247 // parenthesis label pairs are passed using the parens arguments, and the stack
248 // assignments are passed using the assignments argument.
249 template <class Arc>
250 void Compose(
251  const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
252  const std::vector<std::pair<typename Arc::Label, typename Arc::Label>>
253  &parens,
254  const std::vector<typename Arc::Label> &assignments, MutableFst<Arc> *ofst,
255  const MPdtComposeOptions &opts = MPdtComposeOptions()) {
256  bool expand = opts.filter_type != PAREN_FILTER;
257  bool keep_parens = opts.filter_type != EXPAND_FILTER;
258  MPdtComposeFstOptions<Arc, false> copts(ifst1, ifst2, parens, assignments,
259  expand, keep_parens);
260  copts.gc_limit = 0;
261  *ofst = ComposeFst<Arc>(ifst1, ifst2, copts);
262  if (opts.connect) Connect(ofst);
263 }
264 
265 } // namespace fst
266 
267 #endif // FST_EXTENSIONS_MPDT_COMPOSE_H_
MPdtComposeFstOptions(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, const std::vector< std::pair< Label, Label >> &parens, const std::vector< typename Arc::Label > &assignments, bool expand=false, bool keep_parens=true)
Definition: compose.h:198
typename SequenceComposeFilter< ParenMatcher< Fst< Arc > > >::Arc Arc
Definition: compose.h:22
constexpr int kNoLabel
Definition: fst.h:179
MPdtComposeOptions(bool connect=true, PdtComposeFilter filter_type=PAREN_FILTER)
Definition: compose.h:213
uint64_t uint64
Definition: types.h:32
typename SequenceComposeFilter< ParenMatcher< Fst< Arc > > >::Matcher1 Matcher1
Definition: compose.h:27
Matcher1 * GetMatcher1()
Definition: compose.h:123
ssize_t Top(StackId stack_id) const
Definition: mpdt.h:125
MPdtParenFilter(const MPdtParenFilter &filter, bool safe=false)
Definition: compose.h:62
MPdtComposeFstOptions(const Fst< Arc > &ifst1, const std::vector< std::pair< Label, Label >> &parens, const std::vector< typename Arc::Label > &assignments, const Fst< Arc > &ifst2, bool expand=false, bool keep_parens=true)
Definition: compose.h:170
IntegerFilterState< StackId > FilterState2
Definition: compose.h:33
uint64 Properties(uint64 iprops) const
Definition: compose.h:127
PdtComposeFilter
Definition: compose.h:436
void FilterFinal(Weight *w1, Weight *w2) const
Definition: compose.h:116
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
typename SequenceComposeFilter< ParenMatcher< Fst< Arc > > >::Matcher2 Matcher2
Definition: compose.h:28
typename SequenceComposeFilter< ParenMatcher< Fst< Arc > > >::FilterState FilterState1
Definition: compose.h:32
FilterState FilterArc(Arc *arc1, Arc *arc2) const
Definition: compose.h:93
const FS2 & GetState2() const
Definition: filter-state.h:164
typename SequenceComposeFilter< ParenMatcher< Fst< Arc > > >::FST2 FST2
Definition: compose.h:21
void Compose(const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const ComposeOptions &opts=ComposeOptions())
Definition: compose.h:981
constexpr uint32 kParenList
Definition: compose.h:17
MPdtParenFilter(const FST1 &fst1, const FST2 &fst2, Matcher1 *matcher1=nullptr, Matcher2 *matcher2=nullptr, const std::vector< std::pair< Label, Label >> *parens=nullptr, const std::vector< Label > *assignments=nullptr, bool expand=false, bool keep_parens=true)
Definition: compose.h:36
void SetState(StateId s1, StateId s2, const FilterState &fs)
Definition: compose.h:75
FilterState Start() const
Definition: compose.h:71
constexpr uint64 kOLabelInvariantProperties
Definition: properties.h:245
typename Arc::Label Label
Definition: compose.h:162
PairFilterState< FilterState1, FilterState2 > FilterState
Definition: compose.h:34
PdtComposeFilter filter_type
Definition: compose.h:211
Matcher2 * GetMatcher2()
Definition: compose.h:125
constexpr uint32 kParenLoop
Definition: compose.h:20
typename SequenceComposeFilter< ParenMatcher< Fst< Arc > > >::FST1 FST1
Definition: compose.h:20
constexpr uint64 kILabelInvariantProperties
Definition: properties.h:236
size_t gc_limit
Definition: cache.h:29
const FS1 & GetState1() const
Definition: filter-state.h:162
StackId Find(StackId stack_id, Label label)
Definition: mpdt.h:306