FST  openfst-1.7.2
OpenFst Library
reverse.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 // Reverses an MPDT.
5 
6 #ifndef FST_EXTENSIONS_MPDT_REVERSE_H_
7 #define FST_EXTENSIONS_MPDT_REVERSE_H_
8 
9 #include <limits>
10 #include <vector>
11 
12 #include <fst/mutable-fst.h>
13 #include <fst/relabel.h>
14 #include <fst/reverse.h>
15 
16 namespace fst {
17 
18 // Reverses a multi-stack pushdown transducer (MPDT) encoded as an FST.
19 template <class Arc, class RevArc>
20 void Reverse(
21  const Fst<Arc> &ifst,
22  const std::vector<std::pair<typename Arc::Label, typename Arc::Label>>
23  &parens,
24  std::vector<typename Arc::Label> *assignments, MutableFst<RevArc> *ofst) {
25  using Label = typename Arc::Label;
26  // Reverses FST component.
27  Reverse(ifst, ofst);
28  // Exchanges open and close parenthesis pairs.
29  std::vector<std::pair<Label, Label>> relabel_pairs;
30  relabel_pairs.reserve(2 * parens.size());
31  for (const auto &pair : parens) {
32  relabel_pairs.emplace_back(pair.first, pair.second);
33  relabel_pairs.emplace_back(pair.second, pair.first);
34  }
35  Relabel(ofst, relabel_pairs, relabel_pairs);
36  // Computes new bounds for the stack assignments.
37  Label max_level = -1;
38  Label min_level = std::numeric_limits<Label>::max();
39  for (const auto assignment : *assignments) {
40  if (assignment < min_level) {
41  min_level = assignment;
42  } else if (assignment > max_level) {
43  max_level = assignment;
44  }
45  }
46  // Actually reverses stack assignments.
47  for (auto &assignment : *assignments) {
48  assignment = (max_level - assignment) + min_level;
49  }
50 }
51 
52 } // namespace fst
53 
54 #endif // FST_EXTENSIONS_MPDT_REVERSE_H_
void Relabel(MutableFst< Arc > *fst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &ipairs, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &opairs)
Definition: relabel.h:29
void Reverse(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, std::vector< typename Arc::Label > *assignments, MutableFst< RevArc > *ofst)
Definition: reverse.h:20