FST  openfst-1.7.2
OpenFst Library
partition.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 // Functions and classes to create a partition of states.
5 
6 #ifndef FST_PARTITION_H_
7 #define FST_PARTITION_H_
8 
9 #include <algorithm>
10 #include <vector>
11 
12 
13 #include <fst/queue.h>
14 
15 
16 namespace fst {
17 namespace internal {
18 
19 template <typename T>
21 
22 // Defines a partitioning of elements, used to represent equivalence classes
23 // for FST operations like minimization. T must be a signed integer type.
24 //
25 // The elements are numbered from 0 to num_elements - 1.
26 // Initialize(num_elements) sets up the class for a given number of elements.
27 // We maintain a partition of these elements into classes. The classes are also
28 // numbered from zero; you can add a class with AddClass(), or add them in bulk
29 // with AllocateClasses(num_classes). Initially the elements are not assigned
30 // to any class; you set up the initial mapping from elements to classes by
31 // calling Add(element_id, class_id). You can also move an element to a
32 // different class by calling Move(element_id, class_id).
33 //
34 // We also support a rather specialized interface that allows you to efficiently
35 // split classes in the Hopcroft minimization algorithm. This maintains a
36 // binary partition of each class. Let's call these, rather arbitrarily, the
37 // 'yes' subset and the 'no' subset of each class, and assume that by default,
38 // each element of a class is in its 'no' subset. When one calls
39 // SplitOn(element_id), element_id is moved to the 'yes' subset of its class.
40 // (If it was already in the 'yes' set, it just stays there). The aim is to
41 // enable (later) splitting the class in two in time no greater than the time
42 // already spent calling SplitOn() for that class. We keep a list of the classes
43 // which have nonempty 'yes' sets, as visited_classes_. When one calls
44 // FinalizeSplit(Queue *l), for each class in visited_classes_ whose 'yes'
45 // and 'no' sets are both nonempty, it will create a new class consisting of
46 // the smaller of the two subsets (and this class will be added to the queue),
47 // and the old class will now be the larger of the two subsets. This call also
48 // resets all the yes/no partitions so that everything is in the 'no' subsets.
49 //
50 // One cannot use the Move() function if SplitOn() has been called without
51 // a subsequent call to FinalizeSplit()
52 template <typename T>
53 class Partition {
54  public:
55  Partition() {}
56 
57  explicit Partition(T num_elements) { Initialize(num_elements); }
58 
59  // Creates an empty partition for num_elements. This means that the elements
60  // are not assigned to a class (i.e class_index = -1); you should set up the
61  // number of classes using AllocateClasses() or AddClass(), and allocate each
62  // element to a class by calling Add(element, class_id).
63  void Initialize(size_t num_elements) {
64  elements_.resize(num_elements);
65  classes_.reserve(num_elements);
66  classes_.clear();
67  yes_counter_ = 1;
68  }
69 
70  // Adds a class; returns new number of classes.
71  T AddClass() {
72  auto num_classes = classes_.size();
73  classes_.resize(num_classes + 1);
74  return num_classes;
75  }
76 
77  // Adds 'num_classes' new (empty) classes.
78  void AllocateClasses(T num_classes) {
79  classes_.resize(classes_.size() + num_classes);
80  }
81 
82  // Adds element_id to class_id. element_id should already have been allocated
83  // by calling Initialize(num_elements)---or the constructor taking
84  // num_elements---with num_elements > element_id. element_id must not
85  // currently be a member of any class; once elements have been added to a
86  // class, use the Move() method to move them from one class to another.
87  void Add(T element_id, T class_id) {
88  auto &this_element = elements_[element_id];
89  auto &this_class = classes_[class_id];
90  ++this_class.size;
91  // Adds the element to the 'no' subset of the class.
92  auto no_head = this_class.no_head;
93  if (no_head >= 0) elements_[no_head].prev_element = element_id;
94  this_class.no_head = element_id;
95  this_element.class_id = class_id;
96  // Adds to the 'no' subset of the class.
97  this_element.yes = 0;
98  this_element.next_element = no_head;
99  this_element.prev_element = -1;
100  }
101 
102  // Moves element_id from 'no' subset of its current class to 'no' subset of
103  // class class_id. This may not work correctly if you have called SplitOn()
104  // [for any element] and haven't subsequently called FinalizeSplit().
105  void Move(T element_id, T class_id) {
106  auto elements = &(elements_[0]);
107  auto &element = elements[element_id];
108  auto &old_class = classes_[element.class_id];
109  --old_class.size;
110  // Excises the element from the 'no' list of its old class, where it is
111  // assumed to be.
112  if (element.prev_element >= 0) {
113  elements[element.prev_element].next_element = element.next_element;
114  } else {
115  old_class.no_head = element.next_element;
116  }
117  if (element.next_element >= 0) {
118  elements[element.next_element].prev_element = element.prev_element;
119  }
120  // Adds to new class.
121  Add(element_id, class_id);
122  }
123 
124  // Moves element_id to the 'yes' subset of its class if it was in the 'no'
125  // subset, and marks the class as having been visited.
126  void SplitOn(T element_id) {
127  auto elements = &(elements_[0]);
128  auto &element = elements[element_id];
129  if (element.yes == yes_counter_) {
130  return; // Already in the 'yes' set; nothing to do.
131  }
132  auto class_id = element.class_id;
133  auto &this_class = classes_[class_id];
134  // Excises the element from the 'no' list of its class.
135  if (element.prev_element >= 0) {
136  elements[element.prev_element].next_element = element.next_element;
137  } else {
138  this_class.no_head = element.next_element;
139  }
140  if (element.next_element >= 0) {
141  elements[element.next_element].prev_element = element.prev_element;
142  }
143  // Adds the element to the 'yes' list.
144  if (this_class.yes_head >= 0) {
145  elements[this_class.yes_head].prev_element = element_id;
146  } else {
147  visited_classes_.push_back(class_id);
148  }
149  element.yes = yes_counter_;
150  element.next_element = this_class.yes_head;
151  element.prev_element = -1;
152  this_class.yes_head = element_id;
153  this_class.yes_size++;
154  }
155 
156  // This should be called after one has possibly called SplitOn for one or more
157  // elements, thus moving those elements to the 'yes' subset for their class.
158  // For each class that has a nontrivial split (i.e., it's not the case that
159  // all members are in the 'yes' or 'no' subset), this function creates a new
160  // class containing the smaller of the two subsets of elements, leaving the
161  // larger group of elements in the old class. The identifier of the new class
162  // will be added to the queue provided as the pointer L. This method then
163  // moves all elements to the 'no' subset of their class.
164  template <class Queue>
165  void FinalizeSplit(Queue *queue) {
166  for (const auto &visited_class : visited_classes_) {
167  const auto new_class = SplitRefine(visited_class);
168  if (new_class != -1 && queue) queue->Enqueue(new_class);
169  }
170  visited_classes_.clear();
171  // Incrementation sets all the 'yes' members of the elements to false.
172  ++yes_counter_;
173  }
174 
175  const T ClassId(T element_id) const { return elements_[element_id].class_id; }
176 
177  const size_t ClassSize(T class_id) const { return classes_[class_id].size; }
178 
179  const T NumClasses() const { return classes_.size(); }
180 
181  private:
182  friend class PartitionIterator<T>;
183 
184  // Information about a given element.
185  struct Element {
186  T class_id; // Class ID of this element.
187  T yes; // This is to be interpreted as a bool, true if it's in the
188  // 'yes' set of this class. The interpretation as bool is
189  // (yes == yes_counter_ ? true : false).
190  T next_element; // Next element in the 'no' list or 'yes' list of this
191  // class, whichever of the two we belong to (think of
192  // this as the 'next' in a doubly-linked list, although
193  // it is an index into the elements array). Negative
194  // values corresponds to null.
195  T prev_element; // Previous element in the 'no' or 'yes' doubly linked
196  // list. Negative values corresponds to null.
197  };
198 
199  // Information about a given class.
200  struct Class {
201  Class() : size(0), yes_size(0), no_head(-1), yes_head(-1) {}
202  T size; // Total number of elements in this class ('no' plus 'yes'
203  // subsets).
204  T yes_size; // Total number of elements of 'yes' subset of this class.
205  T no_head; // Index of head element of doubly-linked list in 'no' subset.
206  // Everything is in the 'no' subset until you call SplitOn().
207  // -1 means no element.
208  T yes_head; // Index of head element of doubly-linked list in 'yes' subset.
209  // -1 means no element.
210  };
211 
212  // This method, called from FinalizeSplit(), checks whether a class has to
213  // be split (a class will be split only if its 'yes' and 'no' subsets are
214  // both nonempty, but one can assume that since this function was called, the
215  // 'yes' subset is nonempty). It splits by taking the smaller subset and
216  // making it a new class, and leaving the larger subset of elements in the
217  // 'no' subset of the old class. It returns the new class if created, or -1
218  // if none was created.
219  T SplitRefine(T class_id) {
220  auto yes_size = classes_[class_id].yes_size;
221  auto size = classes_[class_id].size;
222  auto no_size = size - yes_size;
223  if (no_size == 0) {
224  // All members are in the 'yes' subset, so we don't have to create a new
225  // class, just move them all to the 'no' subset.
226  classes_[class_id].no_head = classes_[class_id].yes_head;
227  classes_[class_id].yes_head = -1;
228  classes_[class_id].yes_size = 0;
229  return -1;
230  } else {
231  auto new_class_id = classes_.size();
232  classes_.resize(classes_.size() + 1);
233  auto &old_class = classes_[class_id];
234  auto &new_class = classes_[new_class_id];
235  // The new_class will have the values from the constructor.
236  if (no_size < yes_size) {
237  // Moves the 'no' subset to new class ('no' subset).
238  new_class.no_head = old_class.no_head;
239  new_class.size = no_size;
240  // And makes the 'yes' subset of the old class ('no' subset).
241  old_class.no_head = old_class.yes_head;
242  old_class.yes_head = -1;
243  old_class.size = yes_size;
244  old_class.yes_size = 0;
245  } else {
246  // Moves the 'yes' subset to the new class (to the 'no' subset)
247  new_class.size = yes_size;
248  new_class.no_head = old_class.yes_head;
249  // Retains only the 'no' subset in the old class.
250  old_class.size = no_size;
251  old_class.yes_size = 0;
252  old_class.yes_head = -1;
253  }
254  auto elements = &(elements_[0]);
255  // Updates the 'class_id' of all the elements we moved.
256  for (auto e = new_class.no_head; e >= 0; e = elements[e].next_element) {
257  elements[e].class_id = new_class_id;
258  }
259  return new_class_id;
260  }
261  }
262 
263  // elements_[i] contains all info about the i'th element.
264  std::vector<Element> elements_;
265  // classes_[i] contains all info about the i'th class.
266  std::vector<Class> classes_;
267  // Set of visited classes to be used in split refine.
268  std::vector<T> visited_classes_;
269  // yes_counter_ is used in interpreting the 'yes' members of class Element.
270  // If element.yes == yes_counter_, we interpret that element as being in the
271  // 'yes' subset of its class. This allows us to, in effect, set all those
272  // bools to false at a stroke by incrementing yes_counter_.
273  T yes_counter_;
274 };
275 
276 // Iterates over members of the 'no' subset of a class in a partition. (When
277 // this is used, everything is in the 'no' subset).
278 template <typename T>
279 class PartitionIterator {
280  public:
281  using Element = typename Partition<T>::Element;
282 
283  PartitionIterator(const Partition<T> &partition, T class_id)
284  : partition_(partition),
285  element_id_(partition_.classes_[class_id].no_head),
286  class_id_(class_id) {}
287 
288  bool Done() { return element_id_ < 0; }
289 
290  const T Value() { return element_id_; }
291 
292  void Next() { element_id_ = partition_.elements_[element_id_].next_element; }
293 
294  void Reset() { element_id_ = partition_.classes_[class_id_].no_head; }
295 
296  private:
297  const Partition<T> &partition_;
298  T element_id_;
299  T class_id_;
300 };
301 
302 } // namespace internal
303 } // namespace fst
304 
305 #endif // FST_PARTITION_H_
const size_t ClassSize(T class_id) const
Definition: partition.h:177
void SplitOn(T element_id)
Definition: partition.h:126
void Move(T element_id, T class_id)
Definition: partition.h:105
void AllocateClasses(T num_classes)
Definition: partition.h:78
typename Partition< T >::Element Element
Definition: partition.h:281
const T NumClasses() const
Definition: partition.h:179
void Initialize(size_t num_elements)
Definition: partition.h:63
Partition(T num_elements)
Definition: partition.h:57
const T ClassId(T element_id) const
Definition: partition.h:175
void Add(T element_id, T class_id)
Definition: partition.h:87
PartitionIterator(const Partition< T > &partition, T class_id)
Definition: partition.h:283
void FinalizeSplit(Queue *queue)
Definition: partition.h:165