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, 460 insertions, 0 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/properties.h b/kaldi_io/src/tools/openfst/include/fst/properties.h new file mode 100644 index 0000000..8fab16f --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/properties.h @@ -0,0 +1,460 @@ +// 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__ |