diff options
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/properties.h')
| -rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/properties.h | 460 |
1 files changed, 0 insertions, 460 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/properties.h b/kaldi_io/src/tools/openfst/include/fst/properties.h deleted file mode 100644 index 8fab16f..0000000 --- a/kaldi_io/src/tools/openfst/include/fst/properties.h +++ /dev/null @@ -1,460 +0,0 @@ -// properties.h - -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// Copyright 2005-2010 Google, Inc. -// Author: Michael Riley <riley@google.com> -// \file -// FST property bits. - -#ifndef FST_LIB_PROPERTIES_H__ -#define FST_LIB_PROPERTIES_H__ - -#include <sys/types.h> -#include <vector> -using std::vector; - -#include <fst/compat.h> - -namespace fst { - -// The property bits here assert facts about an FST. If individual -// bits are added, then the composite properties below, the property -// functions and property names in properties.cc, and -// TestProperties() in test-properties.h should be updated. - -// -// BINARY PROPERTIES -// -// For each property below, there is a single bit. If it is set, -// the property is true. If it is not set, the property is false. -// - -// The Fst is an ExpandedFst -const uint64 kExpanded = 0x0000000000000001ULL; - -// The Fst is a MutableFst -const uint64 kMutable = 0x0000000000000002ULL; - -// An error was detected while constructing/using the FST -const uint64 kError = 0x0000000000000004ULL; - -// -// TRINARY PROPERTIES -// -// For each of these properties below there is a pair of property bits -// - one positive and one negative. If the positive bit is set, the -// property is true. If the negative bit is set, the property is -// false. If neither is set, the property has unknown value. Both -// should never be simultaneously set. The individual positive and -// negative bit pairs should be adjacent with the positive bit -// at an odd and lower position. - -// ilabel == olabel for each arc -const uint64 kAcceptor = 0x0000000000010000ULL; -// ilabel != olabel for some arc -const uint64 kNotAcceptor = 0x0000000000020000ULL; - -// ilabels unique leaving each state -const uint64 kIDeterministic = 0x0000000000040000ULL; -// ilabels not unique leaving some state -const uint64 kNonIDeterministic = 0x0000000000080000ULL; - -// olabels unique leaving each state -const uint64 kODeterministic = 0x0000000000100000ULL; -// olabels not unique leaving some state -const uint64 kNonODeterministic = 0x0000000000200000ULL; - -// FST has input/output epsilons -const uint64 kEpsilons = 0x0000000000400000ULL; -// FST has no input/output epsilons -const uint64 kNoEpsilons = 0x0000000000800000ULL; - -// FST has input epsilons -const uint64 kIEpsilons = 0x0000000001000000ULL; -// FST has no input epsilons -const uint64 kNoIEpsilons = 0x0000000002000000ULL; - -// FST has output epsilons -const uint64 kOEpsilons = 0x0000000004000000ULL; -// FST has no output epsilons -const uint64 kNoOEpsilons = 0x0000000008000000ULL; - -// ilabels sorted wrt < for each state -const uint64 kILabelSorted = 0x0000000010000000ULL; -// ilabels not sorted wrt < for some state -const uint64 kNotILabelSorted = 0x0000000020000000ULL; - -// olabels sorted wrt < for each state -const uint64 kOLabelSorted = 0x0000000040000000ULL; -// olabels not sorted wrt < for some state -const uint64 kNotOLabelSorted = 0x0000000080000000ULL; - -// Non-trivial arc or final weights -const uint64 kWeighted = 0x0000000100000000ULL; -// Only trivial arc and final weights -const uint64 kUnweighted = 0x0000000200000000ULL; - -// FST has cycles -const uint64 kCyclic = 0x0000000400000000ULL; -// FST has no cycles -const uint64 kAcyclic = 0x0000000800000000ULL; - -// FST has cycles containing the initial state -const uint64 kInitialCyclic = 0x0000001000000000ULL; -// FST has no cycles containing the initial state -const uint64 kInitialAcyclic = 0x0000002000000000ULL; - -// FST is topologically sorted -const uint64 kTopSorted = 0x0000004000000000ULL; -// FST is not topologically sorted -const uint64 kNotTopSorted = 0x0000008000000000ULL; - -// All states reachable from the initial state -const uint64 kAccessible = 0x0000010000000000ULL; -// Not all states reachable from the initial state -const uint64 kNotAccessible = 0x0000020000000000ULL; - -// All states can reach a final state -const uint64 kCoAccessible = 0x0000040000000000ULL; -// Not all states can reach a final state -const uint64 kNotCoAccessible = 0x0000080000000000ULL; - -// If NumStates() > 0, then state 0 is initial, state NumStates()-1 is -// final, there is a transition from each non-final state i to -// state i+1, and there are no other transitions. -const uint64 kString = 0x0000100000000000ULL; - -// Not a string FST -const uint64 kNotString = 0x0000200000000000ULL; - -// -// COMPOSITE PROPERTIES -// - -// Properties of an empty machine -const uint64 kNullProperties - = kAcceptor | kIDeterministic | kODeterministic | kNoEpsilons | - kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted | - kUnweighted | kAcyclic | kInitialAcyclic | kTopSorted | - kAccessible | kCoAccessible | kString; - -// Properties that are preserved when an FST is copied -const uint64 kCopyProperties - = kError | kAcceptor | kNotAcceptor | kIDeterministic | kNonIDeterministic | - kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons | - kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons | - kILabelSorted | kNotILabelSorted | kOLabelSorted | - kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic | - kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted | - kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible | - kString | kNotString; - -// Properites that are intrinsic to the FST -const uint64 kIntrinsicProperties - = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic | - kNonIDeterministic | kODeterministic | kNonODeterministic | - kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | - kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted | - kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic | - kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted | - kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible | - kString | kNotString; - -// Properites that are (potentially) extrinsic to the FST -const uint64 kExtrinsicProperties = kError; - -// Properties that are preserved when an FST start state is set -const uint64 kSetStartProperties - = kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | - kIDeterministic | kNonIDeterministic | kODeterministic | - kNonODeterministic | kEpsilons | kNoEpsilons | kIEpsilons | - kNoIEpsilons | kOEpsilons | kNoOEpsilons | kILabelSorted | - kNotILabelSorted | kOLabelSorted | kNotOLabelSorted | kWeighted | - kUnweighted | kCyclic | kAcyclic | kTopSorted | kNotTopSorted | - kCoAccessible | kNotCoAccessible; - -// Properties that are preserved when an FST final weight is set -const uint64 kSetFinalProperties - = kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | - kIDeterministic | kNonIDeterministic | kODeterministic | - kNonODeterministic | kEpsilons | kNoEpsilons | kIEpsilons | - kNoIEpsilons | kOEpsilons | kNoOEpsilons | kILabelSorted | - kNotILabelSorted | kOLabelSorted | kNotOLabelSorted | kCyclic | - kAcyclic | kInitialCyclic | kInitialAcyclic | kTopSorted | - kNotTopSorted | kAccessible | kNotAccessible; - -// Properties that are preserved when an FST state is added -const uint64 kAddStateProperties - = kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | - kIDeterministic | kNonIDeterministic | kODeterministic | - kNonODeterministic | kEpsilons | kNoEpsilons | kIEpsilons | - kNoIEpsilons | kOEpsilons | kNoOEpsilons | kILabelSorted | - kNotILabelSorted | kOLabelSorted | kNotOLabelSorted | kWeighted | - kUnweighted | kCyclic | kAcyclic | kInitialCyclic | - kInitialAcyclic | kTopSorted | kNotTopSorted | kNotAccessible | - kNotCoAccessible | kNotString; - -// Properties that are preserved when an FST arc is added -const uint64 kAddArcProperties = kExpanded | kMutable | kError | kNotAcceptor | - kNonIDeterministic | kNonODeterministic | kEpsilons | kIEpsilons | - kOEpsilons | kNotILabelSorted | kNotOLabelSorted | kWeighted | - kCyclic | kInitialCyclic | kNotTopSorted | kAccessible | kCoAccessible; - -// Properties that are preserved when an FST arc is set -const uint64 kSetArcProperties = kExpanded | kMutable | kError; - -// Properties that are preserved when FST states are deleted -const uint64 kDeleteStatesProperties - = kExpanded | kMutable | kError | kAcceptor | kIDeterministic | - kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons | - kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic | - kInitialAcyclic | kTopSorted; - -// Properties that are preserved when FST arcs are deleted -const uint64 kDeleteArcsProperties - = kExpanded | kMutable | kError | kAcceptor | kIDeterministic | - kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons | - kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic | - kInitialAcyclic | kTopSorted | kNotAccessible | kNotCoAccessible; - -// Properties that are preserved when an FST's states are reordered -const uint64 kStateSortProperties = kExpanded | kMutable | kError | kAcceptor | - kNotAcceptor | kIDeterministic | kNonIDeterministic | - kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons | - kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons | - kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted - | kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | - kInitialAcyclic | kAccessible | kNotAccessible | kCoAccessible | - kNotCoAccessible; - -// Properties that are preserved when an FST's arcs are reordered -const uint64 kArcSortProperties = - kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic | - kNonIDeterministic | kODeterministic | kNonODeterministic | - kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | - kNoOEpsilons | kWeighted | kUnweighted | kCyclic | kAcyclic | - kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted | - kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible | - kString | kNotString; - -// Properties that are preserved when an FST's input labels are changed. -const uint64 kILabelInvariantProperties = - kExpanded | kMutable | kError | kODeterministic | kNonODeterministic | - kOEpsilons | kNoOEpsilons | kOLabelSorted | kNotOLabelSorted | - kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | - kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible | - kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString; - -// Properties that are preserved when an FST's output labels are changed. -const uint64 kOLabelInvariantProperties = - kExpanded | kMutable | kError | kIDeterministic | kNonIDeterministic | - kIEpsilons | kNoIEpsilons | kILabelSorted | kNotILabelSorted | - kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | - kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible | - kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString; - -// Properties that are preserved when an FST's weights are changed. -// This assumes that the set of states that are non-final is not changed. -const uint64 kWeightInvariantProperties = - kExpanded | kMutable | kError | kAcceptor | kNotAcceptor | kIDeterministic | - kNonIDeterministic | kODeterministic | kNonODeterministic | - kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | - kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted | - kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic | - kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible | - kNotCoAccessible | kString | kNotString; - -// Properties that are preserved when a superfinal state is added -// and an FSTs final weights are directed to it via new transitions. -const uint64 kAddSuperFinalProperties = kExpanded | kMutable | kError | - kAcceptor | kNotAcceptor | kNonIDeterministic | kNonODeterministic | - kEpsilons | kIEpsilons | kOEpsilons | kNotILabelSorted | kNotOLabelSorted | - kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | - kInitialAcyclic | kNotTopSorted | kNotAccessible | kCoAccessible | - kNotCoAccessible | kNotString; - -// Properties that are preserved when a superfinal state is removed -// and the epsilon transitions directed to it are made final weights. -const uint64 kRmSuperFinalProperties = kExpanded | kMutable | kError | - kAcceptor | kNotAcceptor | kIDeterministic | kODeterministic | - kNoEpsilons | kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted | - kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | - kInitialAcyclic | kTopSorted | kAccessible | kCoAccessible | - kNotCoAccessible | kString; - -// All binary properties -const uint64 kBinaryProperties = 0x0000000000000007ULL; - -// All trinary properties -const uint64 kTrinaryProperties = 0x00003fffffff0000ULL; - -// -// COMPUTED PROPERTIES -// - -// 1st bit of trinary properties -const uint64 kPosTrinaryProperties = - kTrinaryProperties & 0x5555555555555555ULL; - -// 2nd bit of trinary properties -const uint64 kNegTrinaryProperties = - kTrinaryProperties & 0xaaaaaaaaaaaaaaaaULL; - -// All properties -const uint64 kFstProperties = kBinaryProperties | kTrinaryProperties; - -// -// PROPERTY FUNCTIONS and STRING NAMES (defined in properties.cc) -// - -// Below are functions for getting property bit vectors when executing -// mutating fst operations. -inline uint64 SetStartProperties(uint64 inprops); -template <typename Weight> -uint64 SetFinalProperties(uint64 inprops, Weight old_weight, - Weight new_weight); -inline uint64 AddStateProperties(uint64 inprops); -template <typename A> -uint64 AddArcProperties(uint64 inprops, typename A::StateId s, const A &arc, - const A *prev_arc); -inline uint64 DeleteStatesProperties(uint64 inprops); -inline uint64 DeleteAllStatesProperties(uint64 inprops, uint64 staticProps); -inline uint64 DeleteArcsProperties(uint64 inprops); - -uint64 ClosureProperties(uint64 inprops, bool star, bool delayed = false); -uint64 ComplementProperties(uint64 inprops); -uint64 ComposeProperties(uint64 inprops1, uint64 inprops2); -uint64 ConcatProperties(uint64 inprops1, uint64 inprops2, - bool delayed = false); -uint64 DeterminizeProperties(uint64 inprops, bool has_subsequential_label); -uint64 FactorWeightProperties(uint64 inprops); -uint64 InvertProperties(uint64 inprops); -uint64 ProjectProperties(uint64 inprops, bool project_input); -uint64 RandGenProperties(uint64 inprops, bool weighted); -uint64 RelabelProperties(uint64 inprops); -uint64 ReplaceProperties(const vector<uint64>& inprops, - ssize_t root, - bool epsilon_on_replace, - bool no_empty_fst); -uint64 ReverseProperties(uint64 inprops); -uint64 ReweightProperties(uint64 inprops); -uint64 RmEpsilonProperties(uint64 inprops, bool delayed = false); -uint64 ShortestPathProperties(uint64 props); -uint64 SynchronizeProperties(uint64 inprops); -uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed = false); - -// Definitions of inlined functions. - -uint64 SetStartProperties(uint64 inprops) { - uint64 outprops = inprops & kSetStartProperties; - if (inprops & kAcyclic) { - outprops |= kInitialAcyclic; - } - return outprops; -} - -uint64 AddStateProperties(uint64 inprops) { - return inprops & kAddStateProperties; -} - -uint64 DeleteStatesProperties(uint64 inprops) { - return inprops & kDeleteStatesProperties; -} - -uint64 DeleteAllStatesProperties(uint64 inprops, uint64 staticprops) { - uint64 outprops = inprops & kError; - return outprops | kNullProperties | staticprops; -} - -uint64 DeleteArcsProperties(uint64 inprops) { - return inprops & kDeleteArcsProperties; -} - -// Definitions of template functions. - -// -template <typename Weight> -uint64 SetFinalProperties(uint64 inprops, Weight old_weight, - Weight new_weight) { - uint64 outprops = inprops; - if (old_weight != Weight::Zero() && old_weight != Weight::One()) { - outprops &= ~kWeighted; - } - if (new_weight != Weight::Zero() && new_weight != Weight::One()) { - outprops |= kWeighted; - outprops &= ~kUnweighted; - } - outprops &= kSetFinalProperties | kWeighted | kUnweighted; - return outprops; -} - -/// Gets the properties for the MutableFst::AddArc method. -/// -/// \param inprops the current properties of the fst -/// \param s the id of the state to which an arc is being added -/// \param arc the arc being added to the state with the specified id -/// \param prev_arc the previously-added (or "last") arc of state s, or NULL if -/// s currently has no arcs -template <typename A> -uint64 AddArcProperties(uint64 inprops, typename A::StateId s, - const A &arc, const A *prev_arc) { - uint64 outprops = inprops; - if (arc.ilabel != arc.olabel) { - outprops |= kNotAcceptor; - outprops &= ~kAcceptor; - } - if (arc.ilabel == 0) { - outprops |= kIEpsilons; - outprops &= ~kNoIEpsilons; - if (arc.olabel == 0) { - outprops |= kEpsilons; - outprops &= ~kNoEpsilons; - } - } - if (arc.olabel == 0) { - outprops |= kOEpsilons; - outprops &= ~kNoOEpsilons; - } - if (prev_arc != 0) { - if (prev_arc->ilabel > arc.ilabel) { - outprops |= kNotILabelSorted; - outprops &= ~kILabelSorted; - } - if (prev_arc->olabel > arc.olabel) { - outprops |= kNotOLabelSorted; - outprops &= ~kOLabelSorted; - } - } - if (arc.weight != A::Weight::Zero() && arc.weight != A::Weight::One()) { - outprops |= kWeighted; - outprops &= ~kUnweighted; - } - if (arc.nextstate <= s) { - outprops |= kNotTopSorted; - outprops &= ~kTopSorted; - } - outprops &= kAddArcProperties | kAcceptor | - kNoEpsilons | kNoIEpsilons | kNoOEpsilons | - kILabelSorted | kOLabelSorted | kUnweighted | kTopSorted; - if (outprops & kTopSorted) { - outprops |= kAcyclic | kInitialAcyclic; - } - return outprops; -} - -extern const char *PropertyNames[]; - -} // namespace fst - -#endif // FST_LIB_PROPERTIES_H__ |