FST  openfst-1.7.2
OpenFst Library
pdt.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 // Common classes for PDT expansion/traversal.
5 
6 #ifndef FST_EXTENSIONS_PDT_PDT_H_
7 #define FST_EXTENSIONS_PDT_PDT_H_
8 
9 #include <map>
10 #include <set>
11 #include <unordered_map>
12 
13 #include <fst/compat.h>
14 #include <fst/log.h>
15 #include <fst/fst.h>
16 #include <fst/state-table.h>
17 
18 namespace fst {
19 
20 // Provides bijection between parenthesis stacks and signed integral stack IDs.
21 // Each stack ID is unique to each distinct stack. The open-close parenthesis
22 // label pairs are passed using the parens argument.
23 template <typename StackId, typename Label>
24 class PdtStack {
25  public:
26  // The stacks are stored in a tree. The nodes are stored in a vector. Each
27  // node represents the top of some stack and is identified by its position in
28  // the vector. Its' parent node represents the stack with the top popped and
29  // its children are stored in child_map_ and accessed by stack_id and label.
30  // The paren_id is
31  // the position in parens of the parenthesis for that node.
32  struct StackNode {
33  StackId parent_id;
34  size_t paren_id;
35 
36  StackNode(StackId p, size_t i) : parent_id(p), paren_id(i) {}
37  };
38 
39  explicit PdtStack(const std::vector<std::pair<Label, Label>> &parens)
40  : parens_(parens), min_paren_(kNoLabel), max_paren_(kNoLabel) {
41  for (size_t i = 0; i < parens.size(); ++i) {
42  const auto &pair = parens[i];
43  paren_map_[pair.first] = i;
44  paren_map_[pair.second] = i;
45  if (min_paren_ == kNoLabel || pair.first < min_paren_) {
46  min_paren_ = pair.first;
47  }
48  if (pair.second < min_paren_) min_paren_ = pair.second;
49  if (max_paren_ == kNoLabel || pair.first > max_paren_) {
50  max_paren_ = pair.first;
51  }
52  if (pair.second > max_paren_) max_paren_ = pair.second;
53  }
54  nodes_.push_back(StackNode(-1, -1)); // Tree root.
55  }
56 
57  // Returns stack ID given the current stack ID (0 if empty) and label read.
58  // Pushes onto the stack if the label is an open parenthesis, returning the
59  // new stack ID. Pops the stack if the label is a close parenthesis that
60  // matches the top of the stack, returning the parent stack ID. Returns -1 if
61  // label is an unmatched close parenthesis. Otherwise, returns the current
62  // stack ID.
63  StackId Find(StackId stack_id, Label label) {
64  if (min_paren_ == kNoLabel || label < min_paren_ || label > max_paren_) {
65  return stack_id; // Non-paren.
66  }
67  const auto it = paren_map_.find(label);
68  // Non-paren.
69  if (it == paren_map_.end()) return stack_id;
70  const auto paren_id = it->second;
71  // Open paren.
72  if (label == parens_[paren_id].first) {
73  auto &child_id = child_map_[std::make_pair(stack_id, label)];
74  if (child_id == 0) { // Child not found; pushes label.
75  child_id = nodes_.size();
76  nodes_.push_back(StackNode(stack_id, paren_id));
77  }
78  return child_id;
79  }
80  const auto &node = nodes_[stack_id];
81  // Matching close paren.
82  if (paren_id == node.paren_id) return node.parent_id;
83  // Non-matching close paren.
84  return -1;
85  }
86 
87  // Returns the stack ID obtained by popping the label at the top of the
88  // current stack ID.
89  StackId Pop(StackId stack_id) const { return nodes_[stack_id].parent_id; }
90 
91  // Returns the paren ID at the top of the stack.
92  ssize_t Top(StackId stack_id) const { return nodes_[stack_id].paren_id; }
93 
94  ssize_t ParenId(Label label) const {
95  const auto it = paren_map_.find(label);
96  if (it == paren_map_.end()) return -1; // Non-paren.
97  return it->second;
98  }
99 
100  private:
101  struct ChildHash {
102  size_t operator()(const std::pair<StackId, Label> &pair) const {
103  static constexpr size_t prime = 7853;
104  return static_cast<size_t>(pair.first) +
105  static_cast<size_t>(pair.second) * prime;
106  }
107  };
108 
109  std::vector<std::pair<Label, Label>> parens_;
110  std::vector<StackNode> nodes_;
111  std::unordered_map<Label, size_t> paren_map_;
112  // Child of stack node w.r.t label
113  std::unordered_map<std::pair<StackId, Label>, StackId, ChildHash> child_map_;
114  Label min_paren_;
115  Label max_paren_;
116 };
117 
118 // State tuple for PDT expansion.
119 template <typename S, typename K>
121  using StateId = S;
122  using StackId = K;
123 
126 
127  PdtStateTuple(StateId state_id = kNoStateId, StackId stack_id = -1)
128  : state_id(state_id), stack_id(stack_id) {}
129 };
130 
131 // Equality of PDT state tuples.
132 template <typename S, typename K>
133 inline bool operator==(const PdtStateTuple<S, K> &x,
134  const PdtStateTuple<S, K> &y) {
135  if (&x == &y) return true;
136  return x.state_id == y.state_id && x.stack_id == y.stack_id;
137 }
138 
139 // Hash function object for PDT state tuples
140 template <class T>
142  public:
143  size_t operator()(const T &tuple) const {
144  static constexpr auto prime = 7853;
145  return tuple.state_id + tuple.stack_id * prime;
146  }
147 };
148 
149 // Tuple to PDT state bijection.
150 template <class StateId, class StackId>
152  PdtStateTuple<StateId, StackId>,
153  PdtStateHash<PdtStateTuple<StateId, StackId>>> {
154  public:
156 
157  PdtStateTable(const PdtStateTable &other) {}
158 
159  private:
160  PdtStateTable &operator=(const PdtStateTable &) = delete;
161 };
162 
163 } // namespace fst
164 
165 #endif // FST_EXTENSIONS_PDT_PDT_H_
PdtStateTuple(StateId state_id=kNoStateId, StackId stack_id=-1)
Definition: pdt.h:127
constexpr int kNoLabel
Definition: fst.h:179
StackId stack_id
Definition: pdt.h:125
StackId parent_id
Definition: pdt.h:33
constexpr int kNoStateId
Definition: fst.h:180
StackNode(StackId p, size_t i)
Definition: pdt.h:36
bool operator==(const PdtStateTuple< S, K > &x, const PdtStateTuple< S, K > &y)
Definition: pdt.h:133
PdtStateTable(const PdtStateTable &other)
Definition: pdt.h:157
StackId Pop(StackId stack_id) const
Definition: pdt.h:89
ssize_t ParenId(Label label) const
Definition: pdt.h:94
StackId Find(StackId stack_id, Label label)
Definition: pdt.h:63
ssize_t Top(StackId stack_id) const
Definition: pdt.h:92
size_t operator()(const T &tuple) const
Definition: pdt.h:143
StateId state_id
Definition: pdt.h:124
PdtStack(const std::vector< std::pair< Label, Label >> &parens)
Definition: pdt.h:39