FST  openfst-1.8.2.post1
OpenFst Library
reverse.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Reverses an MPDT.
19 
20 #ifndef FST_EXTENSIONS_MPDT_REVERSE_H_
21 #define FST_EXTENSIONS_MPDT_REVERSE_H_
22 
23 #include <limits>
24 #include <vector>
25 
26 #include <fst/mutable-fst.h>
27 #include <fst/relabel.h>
28 #include <fst/reverse.h>
29 
30 namespace fst {
31 
32 // Reverses a multi-stack pushdown transducer (MPDT) encoded as an FST.
33 template <class Arc, class RevArc>
34 void Reverse(
35  const Fst<Arc> &ifst,
36  const std::vector<std::pair<typename Arc::Label, typename Arc::Label>>
37  &parens,
38  std::vector<typename Arc::Label> *assignments, MutableFst<RevArc> *ofst) {
39  using Label = typename Arc::Label;
40  // Reverses FST component.
41  Reverse(ifst, ofst);
42  // Exchanges open and close parenthesis pairs.
43  std::vector<std::pair<Label, Label>> relabel_pairs;
44  relabel_pairs.reserve(2 * parens.size());
45  for (const auto &pair : parens) {
46  relabel_pairs.emplace_back(pair.first, pair.second);
47  relabel_pairs.emplace_back(pair.second, pair.first);
48  }
49  Relabel(ofst, relabel_pairs, relabel_pairs);
50  // Computes new bounds for the stack assignments.
51  Label max_level = -1;
52  Label min_level = std::numeric_limits<Label>::max();
53  for (const auto assignment : *assignments) {
54  if (assignment < min_level) {
55  min_level = assignment;
56  } else if (assignment > max_level) {
57  max_level = assignment;
58  }
59  }
60  // Actually reverses stack assignments.
61  for (auto &assignment : *assignments) {
62  assignment = (max_level - assignment) + min_level;
63  }
64 }
65 
66 } // namespace fst
67 
68 #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:42
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:34