summaryrefslogtreecommitdiff
path: root/kaldi_io/src/tools/openfst/include/fst/test-properties.h
diff options
context:
space:
mode:
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/test-properties.h')
-rw-r--r--kaldi_io/src/tools/openfst/include/fst/test-properties.h250
1 files changed, 0 insertions, 250 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/test-properties.h b/kaldi_io/src/tools/openfst/include/fst/test-properties.h
deleted file mode 100644
index 80af593..0000000
--- a/kaldi_io/src/tools/openfst/include/fst/test-properties.h
+++ /dev/null
@@ -1,250 +0,0 @@
-// test-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: [email protected] (Michael Riley)
-//
-// \file
-// Functions to manipulate and test property bits
-
-#ifndef FST_LIB_TEST_PROPERTIES_H__
-#define FST_LIB_TEST_PROPERTIES_H__
-
-#include <tr1/unordered_set>
-using std::tr1::unordered_set;
-using std::tr1::unordered_multiset;
-
-#include <fst/dfs-visit.h>
-#include <fst/connect.h>
-
-
-DECLARE_bool(fst_verify_properties);
-
-namespace fst {
-
-// For a binary property, the bit is always returned set.
-// For a trinary (i.e. two-bit) property, both bits are
-// returned set iff either corresponding input bit is set.
-inline uint64 KnownProperties(uint64 props) {
- return kBinaryProperties | (props & kTrinaryProperties) |
- ((props & kPosTrinaryProperties) << 1) |
- ((props & kNegTrinaryProperties) >> 1);
-}
-
-// Tests compatibility between two sets of properties
-inline bool CompatProperties(uint64 props1, uint64 props2) {
- uint64 known_props1 = KnownProperties(props1);
- uint64 known_props2 = KnownProperties(props2);
- uint64 known_props = known_props1 & known_props2;
- uint64 incompat_props = (props1 & known_props) ^ (props2 & known_props);
- if (incompat_props) {
- uint64 prop = 1;
- for (int i = 0; i < 64; ++i, prop <<= 1)
- if (prop & incompat_props)
- LOG(ERROR) << "CompatProperties: mismatch: " << PropertyNames[i]
- << ": props1 = " << (props1 & prop ? "true" : "false")
- << ", props2 = " << (props2 & prop ? "true" : "false");
- return false;
- } else {
- return true;
- }
-}
-
-// Computes FST property values defined in properties.h. The value of
-// each property indicated in the mask will be determined and returned
-// (these will never be unknown here). In the course of determining
-// the properties specifically requested in the mask, certain other
-// properties may be determined (those with little additional expense)
-// and their values will be returned as well. The complete set of
-// known properties (whether true or false) determined by this
-// operation will be assigned to the the value pointed to by KNOWN.
-// If 'use_stored' is true, pre-computed FST properties may be used
-// when possible. This routine is seldom called directly; instead it
-// is used to implement fst.Properties(mask, true).
-template<class Arc>
-uint64 ComputeProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known,
- bool use_stored) {
- typedef typename Arc::Label Label;
- typedef typename Arc::Weight Weight;
- typedef typename Arc::StateId StateId;
-
- uint64 fst_props = fst.Properties(kFstProperties, false); // Fst-stored
-
- // Check stored FST properties first if allowed.
- if (use_stored) {
- uint64 known_props = KnownProperties(fst_props);
- // If FST contains required info, return it.
- if ((known_props & mask) == mask) {
- *known = known_props;
- return fst_props;
- }
- }
-
- // Compute (trinary) properties explicitly.
-
- // Initialize with binary properties (already known).
- uint64 comp_props = fst_props & kBinaryProperties;
-
- // Compute these trinary properties with a DFS. We compute only those
- // that need a DFS here, since we otherwise would like to avoid a DFS
- // since its stack could grow large.
- uint64 dfs_props = kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
- kAccessible | kNotAccessible |
- kCoAccessible | kNotCoAccessible;
- if (mask & dfs_props) {
- SccVisitor<Arc> scc_visitor(&comp_props);
- DfsVisit(fst, &scc_visitor);
- }
-
- // Compute any remaining trinary properties via a state and arcs iterations
- if (mask & ~(kBinaryProperties | dfs_props)) {
- comp_props |= kAcceptor | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
- kILabelSorted | kOLabelSorted | kUnweighted | kTopSorted | kString;
- if (mask & (kIDeterministic | kNonIDeterministic))
- comp_props |= kIDeterministic;
- if (mask & (kODeterministic | kNonODeterministic))
- comp_props |= kODeterministic;
-
- unordered_set<Label> *ilabels = 0;
- unordered_set<Label> *olabels = 0;
-
- StateId nfinal = 0;
- for (StateIterator< Fst<Arc> > siter(fst);
- !siter.Done();
- siter.Next()) {
- StateId s = siter.Value();
-
- Arc prev_arc;
- // Create these only if we need to
- if (mask & (kIDeterministic | kNonIDeterministic))
- ilabels = new unordered_set<Label>;
- if (mask & (kODeterministic | kNonODeterministic))
- olabels = new unordered_set<Label>;
-
- bool first_arc = true;
- for (ArcIterator< Fst<Arc> > aiter(fst, s);
- !aiter.Done();
- aiter.Next()) {
- const Arc &arc =aiter.Value();
-
- if (ilabels && ilabels->find(arc.ilabel) != ilabels->end()) {
- comp_props |= kNonIDeterministic;
- comp_props &= ~kIDeterministic;
- }
- if (olabels && olabels->find(arc.olabel) != olabels->end()) {
- comp_props |= kNonODeterministic;
- comp_props &= ~kODeterministic;
- }
- if (arc.ilabel != arc.olabel) {
- comp_props |= kNotAcceptor;
- comp_props &= ~kAcceptor;
- }
- if (arc.ilabel == 0 && arc.olabel == 0) {
- comp_props |= kEpsilons;
- comp_props &= ~kNoEpsilons;
- }
- if (arc.ilabel == 0) {
- comp_props |= kIEpsilons;
- comp_props &= ~kNoIEpsilons;
- }
- if (arc.olabel == 0) {
- comp_props |= kOEpsilons;
- comp_props &= ~kNoOEpsilons;
- }
- if (!first_arc) {
- if (arc.ilabel < prev_arc.ilabel) {
- comp_props |= kNotILabelSorted;
- comp_props &= ~kILabelSorted;
- }
- if (arc.olabel < prev_arc.olabel) {
- comp_props |= kNotOLabelSorted;
- comp_props &= ~kOLabelSorted;
- }
- }
- if (arc.weight != Weight::One() && arc.weight != Weight::Zero()) {
- comp_props |= kWeighted;
- comp_props &= ~kUnweighted;
- }
- if (arc.nextstate <= s) {
- comp_props |= kNotTopSorted;
- comp_props &= ~kTopSorted;
- }
- if (arc.nextstate != s + 1) {
- comp_props |= kNotString;
- comp_props &= ~kString;
- }
- prev_arc = arc;
- first_arc = false;
- if (ilabels)
- ilabels->insert(arc.ilabel);
- if (olabels)
- olabels->insert(arc.olabel);
- }
-
- if (nfinal > 0) { // final state not last
- comp_props |= kNotString;
- comp_props &= ~kString;
- }
-
- Weight final = fst.Final(s);
-
- if (final != Weight::Zero()) { // final state
- if (final != Weight::One()) {
- comp_props |= kWeighted;
- comp_props &= ~kUnweighted;
- }
- ++nfinal;
- } else { // non-final state
- if (fst.NumArcs(s) != 1) {
- comp_props |= kNotString;
- comp_props &= ~kString;
- }
- }
-
- delete ilabels;
- delete olabels;
- }
-
- if (fst.Start() != kNoStateId && fst.Start() != 0) {
- comp_props |= kNotString;
- comp_props &= ~kString;
- }
- }
-
- *known = KnownProperties(comp_props);
- return comp_props;
-}
-
-// This is a wrapper around ComputeProperties that will cause a fatal
-// error if the stored properties and the computed properties are
-// incompatible when 'FLAGS_fst_verify_properties' is true. This
-// routine is seldom called directly; instead it is used to implement
-// fst.Properties(mask, true).
-template<class Arc>
-uint64 TestProperties(const Fst<Arc> &fst, uint64 mask, uint64 *known) {
- if (FLAGS_fst_verify_properties) {
- uint64 stored_props = fst.Properties(kFstProperties, false);
- uint64 computed_props = ComputeProperties(fst, mask, known, false);
- if (!CompatProperties(stored_props, computed_props))
- LOG(FATAL) << "TestProperties: stored Fst properties incorrect"
- << " (stored: props1, computed: props2)";
- return computed_props;
- } else {
- return ComputeProperties(fst, mask, known, true);
- }
-}
-
-} // namespace fst
-
-#endif // FST_LIB_TEST_PROPERTIES_H__
Powered by cgit, Themed by Ted Yin.