FST  openfst-1.7.2
OpenFst Library
properties.cc
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 for updating property bits for various FST operations and
5 // string names of the properties.
6 
7 #include <fst/properties.h>
8 
9 #include <stddef.h>
10 #include <vector>
11 
12 namespace fst {
13 
14 // These functions determine the properties associated with the FST result of
15 // various finite-state operations. The property arguments correspond to the
16 // operation's FST arguments. The properties returned assume the operation
17 // modifies its first argument. Bitwise-and this result with kCopyProperties for
18 // the case when a new (possibly delayed) FST is instead constructed.
19 
20 // Properties for a concatenatively-closed FST.
21 uint64 ClosureProperties(uint64 inprops, bool, bool delayed) {
22  auto outprops = (kError | kAcceptor | kUnweighted | kAccessible) & inprops;
23  if (inprops & kUnweighted) outprops |= kUnweightedCycles;
24  if (!delayed) {
25  outprops |=
27  inprops;
28  }
29  if (!delayed || inprops & kAccessible) {
33  if ((inprops & kWeighted) && (inprops & kAccessible) &&
34  (inprops & kCoAccessible)) {
35  outprops |= kWeightedCycles;
36  }
37  }
38  return outprops;
39 }
40 
41 // Properties for a complemented FST.
43  auto outprops = kAcceptor | kUnweighted | kUnweightedCycles | kNoEpsilons |
46  outprops |=
48  if (inprops & kAccessible) {
50  }
51  return outprops;
52 }
53 
54 // Properties for a composed FST.
55 uint64 ComposeProperties(uint64 inprops1, uint64 inprops2) {
56  auto outprops = kError & (inprops1 | inprops2);
57  if (inprops1 & kAcceptor && inprops2 & kAcceptor) {
58  outprops |= kAcceptor | kAccessible;
59  outprops |= (kNoEpsilons | kNoIEpsilons | kNoOEpsilons | kAcyclic |
61  inprops1 & inprops2;
62  if (kNoIEpsilons & inprops1 & inprops2) {
63  outprops |= (kIDeterministic | kODeterministic) & inprops1 & inprops2;
64  }
65  } else {
66  outprops |= kAccessible;
67  outprops |= (kAcceptor | kNoIEpsilons | kAcyclic | kInitialAcyclic) &
68  inprops1 & inprops2;
69  if (kNoIEpsilons & inprops1 & inprops2) {
70  outprops |= kIDeterministic & inprops1 & inprops2;
71  }
72  }
73  return outprops;
74 }
75 
76 // Properties for a concatenated FST.
77 uint64 ConcatProperties(uint64 inprops1, uint64 inprops2, bool delayed) {
78  auto outprops = (kAcceptor | kUnweighted | kUnweightedCycles | kAcyclic) &
79  inprops1 & inprops2;
80  outprops |= kError & (inprops1 | inprops2);
81  const bool empty1 = delayed; // Can the first FST be the empty machine?
82  const bool empty2 = delayed; // Can the second FST be the empty machine?
83  if (!delayed) {
84  outprops |= (kExpanded | kMutable | kNotTopSorted | kNotString) & inprops1;
85  outprops |= (kNotTopSorted | kNotString) & inprops2;
86  }
87  if (!empty1) outprops |= (kInitialAcyclic | kInitialCyclic) & inprops1;
88  if (!delayed || inprops1 & kAccessible) {
93  inprops1;
94  }
95  if ((inprops1 & (kAccessible | kCoAccessible)) ==
96  (kAccessible | kCoAccessible) &&
97  !empty1) {
98  outprops |= kAccessible & inprops2;
99  if (!empty2) outprops |= kCoAccessible & inprops2;
100  if (!delayed || inprops2 & kAccessible) {
105  inprops2;
106  }
107  }
108  return outprops;
109 }
110 
111 // Properties for a determinized FST.
112 uint64 DeterminizeProperties(uint64 inprops, bool has_subsequential_label,
113  bool distinct_psubsequential_labels) {
114  auto outprops = kAccessible;
115  if ((kAcceptor & inprops) ||
116  ((kNoIEpsilons & inprops) && distinct_psubsequential_labels) ||
117  (has_subsequential_label && distinct_psubsequential_labels)) {
118  outprops |= kIDeterministic;
119  }
120  outprops |= (kError | kAcceptor | kAcyclic | kInitialAcyclic | kCoAccessible |
121  kString) &
122  inprops;
123  if ((inprops & kNoIEpsilons) && distinct_psubsequential_labels) {
124  outprops |= kNoEpsilons & inprops;
125  }
126  if (inprops & kAccessible) {
127  outprops |= (kIEpsilons | kOEpsilons | kCyclic) & inprops;
128  }
129  if (inprops & kAcceptor) outprops |= (kNoIEpsilons | kNoOEpsilons) & inprops;
130  if ((inprops & kNoIEpsilons) && has_subsequential_label) {
131  outprops |= kNoIEpsilons;
132  }
133  return outprops;
134 }
135 
136 // Properties for factored weight FST.
138  auto outprops = (kExpanded | kMutable | kError | kAcceptor | kAcyclic |
140  inprops;
141  if (inprops & kAccessible) {
145  inprops;
146  }
147  return outprops;
148 }
149 
150 // Properties for an inverted FST.
152  auto outprops = (kExpanded | kMutable | kError | kAcceptor | kNotAcceptor |
158  inprops;
159  if (kIDeterministic & inprops) outprops |= kODeterministic;
160  if (kNonIDeterministic & inprops) outprops |= kNonODeterministic;
161  if (kODeterministic & inprops) outprops |= kIDeterministic;
162  if (kNonODeterministic & inprops) outprops |= kNonIDeterministic;
163 
164  if (kIEpsilons & inprops) outprops |= kOEpsilons;
165  if (kNoIEpsilons & inprops) outprops |= kNoOEpsilons;
166  if (kOEpsilons & inprops) outprops |= kIEpsilons;
167  if (kNoOEpsilons & inprops) outprops |= kNoIEpsilons;
168 
169  if (kILabelSorted & inprops) outprops |= kOLabelSorted;
170  if (kNotILabelSorted & inprops) outprops |= kNotOLabelSorted;
171  if (kOLabelSorted & inprops) outprops |= kILabelSorted;
172  if (kNotOLabelSorted & inprops) outprops |= kNotILabelSorted;
173  return outprops;
174 }
175 
176 // Properties for a projected FST.
177 uint64 ProjectProperties(uint64 inprops, bool project_input) {
178  auto outprops = kAcceptor;
179  outprops |= (kExpanded | kMutable | kError | kWeighted | kUnweighted |
184  inprops;
185  if (project_input) {
188  inprops;
189 
190  if (kIDeterministic & inprops) outprops |= kODeterministic;
191  if (kNonIDeterministic & inprops) outprops |= kNonODeterministic;
192 
193  if (kIEpsilons & inprops) outprops |= kOEpsilons | kEpsilons;
194  if (kNoIEpsilons & inprops) outprops |= kNoOEpsilons | kNoEpsilons;
195 
196  if (kILabelSorted & inprops) outprops |= kOLabelSorted;
197  if (kNotILabelSorted & inprops) outprops |= kNotOLabelSorted;
198  } else {
201  inprops;
202 
203  if (kODeterministic & inprops) outprops |= kIDeterministic;
204  if (kNonODeterministic & inprops) outprops |= kNonIDeterministic;
205 
206  if (kOEpsilons & inprops) outprops |= kIEpsilons | kEpsilons;
207  if (kNoOEpsilons & inprops) outprops |= kNoIEpsilons | kNoEpsilons;
208 
209  if (kOLabelSorted & inprops) outprops |= kILabelSorted;
210  if (kNotOLabelSorted & inprops) outprops |= kNotILabelSorted;
211  }
212  return outprops;
213 }
214 
215 // Properties for a randgen FST.
216 uint64 RandGenProperties(uint64 inprops, bool weighted) {
218  outprops |= inprops & kError;
219  if (weighted) {
220  outprops |= kTopSorted;
221  outprops |=
224  inprops;
225  } else {
226  outprops |= kUnweighted;
227  outprops |= (kAcceptor | kILabelSorted | kOLabelSorted) & inprops;
228  }
229  return outprops;
230 }
231 
232 // Properties for a replace FST.
233 uint64 ReplaceProperties(const std::vector<uint64>& inprops, size_t root,
234  bool epsilon_on_call, bool epsilon_on_return,
235  bool out_epsilon_on_call, bool out_epsilon_on_return,
236  bool replace_transducer, bool no_empty_fsts,
237  bool all_ilabel_sorted, bool all_olabel_sorted,
238  bool all_negative_or_dense) {
239  if (inprops.empty()) return kNullProperties;
240  uint64 outprops = 0;
241  for (auto inprop : inprops) outprops |= kError & inprop;
242  uint64 access_props = no_empty_fsts ? kAccessible | kCoAccessible : 0;
243  for (auto inprop : inprops) {
244  access_props &= (inprop & (kAccessible | kCoAccessible));
245  }
246  if (access_props == (kAccessible | kCoAccessible)) {
247  outprops |= access_props;
248  if (inprops[root] & kInitialCyclic) outprops |= kInitialCyclic;
249  uint64 props = 0;
250  bool string = true;
251  for (auto inprop : inprops) {
252  if (replace_transducer) props |= kNotAcceptor & inprop;
255  kCyclic | kNotTopSorted | kNotString) & inprop;
256  if (!(inprop & kString)) string = false;
257  }
258  outprops |= props;
259  if (string) outprops |= kString;
260  }
261  bool acceptor = !replace_transducer;
262  bool ideterministic = !epsilon_on_call && epsilon_on_return;
263  bool no_iepsilons = !epsilon_on_call && !epsilon_on_return;
264  bool acyclic = true;
265  bool unweighted = true;
266  for (size_t i = 0; i < inprops.size(); ++i) {
267  if (!(inprops[i] & kAcceptor)) acceptor = false;
268  if (!(inprops[i] & kIDeterministic)) ideterministic = false;
269  if (!(inprops[i] & kNoIEpsilons)) no_iepsilons = false;
270  if (!(inprops[i] & kAcyclic)) acyclic = false;
271  if (!(inprops[i] & kUnweighted)) unweighted = false;
272  if (i != root && !(inprops[i] & kNoIEpsilons)) ideterministic = false;
273  }
274  if (acceptor) outprops |= kAcceptor;
275  if (ideterministic) outprops |= kIDeterministic;
276  if (no_iepsilons) outprops |= kNoIEpsilons;
277  if (acyclic) outprops |= kAcyclic;
278  if (unweighted) outprops |= kUnweighted;
279  if (inprops[root] & kInitialAcyclic) outprops |= kInitialAcyclic;
280  // We assume that all terminals are positive. The resulting ReplaceFst is
281  // known to be kILabelSorted when: (1) all sub-FSTs are kILabelSorted, (2) the
282  // input label of the return arc is epsilon, and (3) one of the 3 following
283  // conditions is satisfied:
284  //
285  // 1. the input label of the call arc is not epsilon
286  // 2. all non-terminals are negative, or
287  // 3. all non-terninals are positive and form a dense range containing 1.
288  if (all_ilabel_sorted && epsilon_on_return &&
289  (!epsilon_on_call || all_negative_or_dense)) {
290  outprops |= kILabelSorted;
291  }
292  // Similarly, the resulting ReplaceFst is known to be kOLabelSorted when: (1)
293  // all sub-FSTs are kOLabelSorted, (2) the output label of the return arc is
294  // epsilon, and (3) one of the 3 following conditions is satisfied:
295  //
296  // 1. the output label of the call arc is not epsilon
297  // 2. all non-terminals are negative, or
298  // 3. all non-terninals are positive and form a dense range containing 1.
299  if (all_olabel_sorted && out_epsilon_on_return &&
300  (!out_epsilon_on_call || all_negative_or_dense)) {
301  outprops |= kOLabelSorted;
302  }
303  return outprops;
304 }
305 
306 // Properties for a relabeled FST.
308  static constexpr auto outprops =
314  return outprops & inprops;
315 }
316 
317 // Properties for a reversed FST (the superinitial state limits this set).
318 uint64 ReverseProperties(uint64 inprops, bool has_superinitial) {
319  auto outprops = (kExpanded | kMutable | kError | kAcceptor | kNotAcceptor |
322  inprops;
323  if (has_superinitial) outprops |= kWeighted & inprops;
324  return outprops;
325 }
326 
327 // Properties for re-weighted FST.
329  auto outprops = inprops & kWeightInvariantProperties;
330  outprops = outprops & ~kCoAccessible;
331  return outprops;
332 }
333 
334 // Properties for an epsilon-removed FST.
335 uint64 RmEpsilonProperties(uint64 inprops, bool delayed) {
336  auto outprops = kNoEpsilons;
337  outprops |= (kError | kAcceptor | kAcyclic | kInitialAcyclic) & inprops;
338  if (inprops & kAcceptor) outprops |= kNoIEpsilons | kNoOEpsilons;
339  if (!delayed) {
340  outprops |= kExpanded | kMutable;
341  outprops |= kTopSorted & inprops;
342  }
343  if (!delayed || inprops & kAccessible) outprops |= kNotAcceptor & inprops;
344  return outprops;
345 }
346 
347 // Properties for shortest path. This function computes how the properties of
348 // the output of shortest path need to be updated, given that 'props' is already
349 // known.
351  auto outprops =
353  if (!tree) outprops |= kCoAccessible;
354  return outprops;
355 }
356 
357 // Properties for a synchronized FST.
359  auto outprops = (kError | kAcceptor | kAcyclic | kAccessible | kCoAccessible |
361  inprops;
362  if (inprops & kAccessible) {
363  outprops |= (kCyclic | kNotCoAccessible | kWeighted | kWeightedCycles) &
364  inprops;
365  }
366  return outprops;
367 }
368 
369 // Properties for a unioned FST.
370 uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed) {
371  auto outprops =
373  inprops1 & inprops2;
374  outprops |= kError & (inprops1 | inprops2);
375  outprops |= kInitialAcyclic;
376  bool empty1 = delayed; // Can the first FST be the empty machine?
377  bool empty2 = delayed; // Can the second FST be the empty machine?
378  if (!delayed) {
379  outprops |= (kExpanded | kMutable | kNotTopSorted) & inprops1;
380  outprops |= kNotTopSorted & inprops2;
381  }
382  if (!empty1 && !empty2) {
383  outprops |= kEpsilons | kIEpsilons | kOEpsilons;
384  outprops |= kCoAccessible & inprops1 & inprops2;
385  }
386  // Note kNotCoAccessible does not hold because of kInitialAcyclic option.
387  if (!delayed || inprops1 & kAccessible) {
388  outprops |=
392  inprops1;
393  }
394  if (!delayed || inprops2 & kAccessible) {
399  inprops2;
400  }
401  return outprops;
402 }
403 
404 // Property string names (indexed by bit position).
405 const char* PropertyNames[] = {
406  // Binary.
407  "expanded", "mutable", "error", "", "", "", "", "", "", "", "", "", "", "",
408  "", "",
409  // Ternary.
410  "acceptor", "not acceptor", "input deterministic",
411  "non input deterministic", "output deterministic",
412  "non output deterministic", "input/output epsilons",
413  "no input/output epsilons", "input epsilons", "no input epsilons",
414  "output epsilons", "no output epsilons", "input label sorted",
415  "not input label sorted", "output label sorted", "not output label sorted",
416  "weighted", "unweighted", "cyclic", "acyclic", "cyclic at initial state",
417  "acyclic at initial state", "top sorted", "not top sorted", "accessible",
418  "not accessible", "coaccessible", "not coaccessible", "string",
419  "not string", "weighted cycles", "unweighted cycles"};
420 
421 } // namespace fst
uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed=false)
Definition: properties.cc:370
constexpr uint64 kNoEpsilons
Definition: properties.h:62
constexpr uint64 kInitialCyclic
Definition: properties.h:95
constexpr uint64 kNotAccessible
Definition: properties.h:107
constexpr uint64 kInitialAcyclic
Definition: properties.h:97
constexpr uint64 kNotOLabelSorted
Definition: properties.h:82
uint64_t uint64
Definition: types.h:32
uint64 ComposeProperties(uint64 inprops1, uint64 inprops2)
Definition: properties.cc:55
constexpr uint64 kNotCoAccessible
Definition: properties.h:112
constexpr uint64 kUnweightedCycles
Definition: properties.h:126
uint64 ClosureProperties(uint64 inprops, bool star, bool delayed=false)
Definition: properties.cc:21
uint64 ReplaceProperties(const std::vector< uint64 > &inprops, size_t root, bool epsilon_on_call, bool epsilon_on_return, bool out_epsilon_on_call, bool out_epsilon_on_return, bool replace_transducer, bool no_empty_fst, bool all_ilabel_sorted, bool all_olabel_sorted, bool all_negative_or_dense)
Definition: properties.cc:233
constexpr uint64 kILabelSorted
Definition: properties.h:75
constexpr uint64 kTopSorted
Definition: properties.h:100
constexpr uint64 kWeightedCycles
Definition: properties.h:123
constexpr uint64 kNotILabelSorted
Definition: properties.h:77
constexpr uint64 kNonIDeterministic
Definition: properties.h:52
constexpr uint64 kExpanded
Definition: properties.h:27
uint64 RandGenProperties(uint64 inprops, bool weighted)
Definition: properties.cc:216
uint64 ReweightProperties(uint64 inprops)
Definition: properties.cc:328
constexpr uint64 kEpsilons
Definition: properties.h:60
uint64 RelabelProperties(uint64 inprops)
Definition: properties.cc:307
constexpr uint64 kUnweighted
Definition: properties.h:87
uint64 ProjectProperties(uint64 inprops, bool project_input)
Definition: properties.cc:177
uint64 ComplementProperties(uint64 inprops)
Definition: properties.cc:42
const char * PropertyNames[]
Definition: properties.cc:405
constexpr uint64 kNonODeterministic
Definition: properties.h:57
constexpr uint64 kNotString
Definition: properties.h:120
constexpr uint64 kOLabelSorted
Definition: properties.h:80
constexpr uint64 kIEpsilons
Definition: properties.h:65
constexpr uint64 kIDeterministic
Definition: properties.h:50
uint64 ReverseProperties(uint64 inprops, bool has_superinitial)
Definition: properties.cc:318
constexpr uint64 kAcceptor
Definition: properties.h:45
uint64 SynchronizeProperties(uint64 inprops)
Definition: properties.cc:358
uint64 RmEpsilonProperties(uint64 inprops, bool delayed=false)
Definition: properties.cc:335
constexpr uint64 kNoOEpsilons
Definition: properties.h:72
constexpr uint64 kString
Definition: properties.h:117
constexpr uint64 kWeightInvariantProperties
Definition: properties.h:255
constexpr uint64 kCoAccessible
Definition: properties.h:110
constexpr uint64 kNotAcceptor
Definition: properties.h:47
constexpr uint64 kAcyclic
Definition: properties.h:92
uint64 ConcatProperties(uint64 inprops1, uint64 inprops2, bool delayed=false)
Definition: properties.cc:77
constexpr uint64 kWeighted
Definition: properties.h:85
uint64 DeterminizeProperties(uint64 inprops, bool has_subsequential_label, bool distinct_psubsequential_labels)
Definition: properties.cc:112
constexpr uint64 kError
Definition: properties.h:33
constexpr uint64 kNullProperties
Definition: properties.h:131
constexpr uint64 kNotTopSorted
Definition: properties.h:102
uint64 ShortestPathProperties(uint64 props, bool tree=false)
Definition: properties.cc:350
constexpr uint64 kMutable
Definition: properties.h:30
constexpr uint64 kODeterministic
Definition: properties.h:55
constexpr uint64 kOEpsilons
Definition: properties.h:70
constexpr uint64 kAccessible
Definition: properties.h:105
uint64 InvertProperties(uint64 inprops)
Definition: properties.cc:151
uint64 FactorWeightProperties(uint64 inprops)
Definition: properties.cc:137
constexpr uint64 kNoIEpsilons
Definition: properties.h:67
constexpr uint64 kCyclic
Definition: properties.h:90