fstext-utils.h

Go to the documentation of this file.

// fstext/fstext-utils.h

// Copyright 2009-2011  Microsoft Corporation
//           2012-2013  Johns Hopkins University (Author: Daniel Povey)
//                2013  Guoguo Chen
//                2014  Telepoint Global Hosting Service, LLC. (Author: David Snyder)

// See ../../COPYING for clarification regarding multiple authors
//
// 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
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

#ifndef KALDI_FSTEXT_FSTEXT_UTILS_H_
#define KALDI_FSTEXT_FSTEXT_UTILS_H_
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <fst/fstlib.h>
#include <fst/fst-decl.h>
#include "fstext/determinize-star.h"
#include "fstext/remove-eps-local.h"
#include "base/kaldi-common.h" // for error reporting macros.
#include "util/text-utils.h" // for SplitStringToVector
#include "fst/script/print-impl.h"

namespace fst {

template<class Arc>
typename Arc::Label HighestNumberedOutputSymbol(const Fst<Arc> &fst);

template<class Arc>
typename Arc::Label HighestNumberedInputSymbol(const Fst<Arc> &fst);

template<class Arc>
typename Arc::StateId NumArcs(const ExpandedFst<Arc> &fst);

template<class Arc, class I>
void GetInputSymbols(const Fst<Arc> &fst,
                     bool include_eps,
                     std::vector<I> *symbols);

template<class Arc, class I>
void GetOutputSymbols(const Fst<Arc> &fst,
                      bool include_eps,
                      std::vector<I> *symbols);

template<class Arc>
void ClearSymbols(bool clear_input,
                  bool clear_output,
                  MutableFst<Arc> *fst);

template<class I>
void GetSymbols(const SymbolTable &symtab,
                bool include_eps,
                std::vector<I> *syms_out);



inline
void DeterminizeStarInLog(VectorFst<StdArc> *fst, float delta = kDelta, bool *debug_ptr = NULL,
                          int max_states = -1);


// e.g. of using this function: PushInLog<REWEIGHT_TO_INITIAL>(fst, kPushWeights|kPushLabels);

template<ReweightType rtype> // == REWEIGHT_TO_{INITIAL, FINAL}
void PushInLog(VectorFst<StdArc> *fst, uint32 ptype, float delta = kDelta) {

  // PushInLog pushes the FST
  // and returns a new pushed FST (labels and weights pushed to the left).
  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>;  // Want to determinize in log semiring.
  Cast(*fst, fst_log);
  VectorFst<StdArc> tmp;
  *fst = tmp;  // free up memory.
  VectorFst<LogArc> *fst_pushed_log = new VectorFst<LogArc>;
  Push<LogArc, rtype>(*fst_log, fst_pushed_log, ptype, delta);
  Cast(*fst_pushed_log, fst);
  delete fst_log;
  delete fst_pushed_log;
}

// Minimizes after encoding; applicable to all FSTs.  It is like what you get
// from the Minimize() function, except it will not push the weights, or the
// symbols.  This is better for our recipes, as we avoid ever pushing the
// weights.  However, it will only minimize optimally if your graphs are such
// that the symbols are as far to the left as they can go, and the weights
// in combinable paths are the same... hard to formalize this, but it's something
// that is satisified by our normal FSTs.
template<class Arc>
void MinimizeEncoded(VectorFst<Arc> *fst, float delta = kDelta) {

  Map(fst, QuantizeMapper<Arc>(delta));
  EncodeMapper<Arc> encoder(kEncodeLabels | kEncodeWeights, ENCODE);
  Encode(fst, &encoder);
  internal::AcceptorMinimize(fst);
  Decode(fst, encoder);
}


template<class Arc, class I>
bool GetLinearSymbolSequence(const Fst<Arc> &fst,
                             std::vector<I> *isymbols_out,
                             std::vector<I> *osymbols_out,
                             typename Arc::Weight *tot_weight_out);


template<class Arc>
void ConvertNbestToVector(const Fst<Arc> &fst,
                          std::vector<VectorFst<Arc> > *fsts_out);


template<class Arc>
void NbestAsFsts(const Fst<Arc> &fst,
                 size_t n,
                 std::vector<VectorFst<Arc> > *fsts_out);




template<class Arc, class I>
void MakeLinearAcceptor(const std::vector<I> &labels, MutableFst<Arc> *ofst);



template<class Arc, class I>
void MakeLinearAcceptorWithAlternatives(const std::vector<std::vector<I> > &labels,
                                        MutableFst<Arc> *ofst);



template<class Arc>
void SafeDeterminizeWrapper(MutableFst<Arc> *ifst, MutableFst<Arc> *ofst, float delta = kDelta);


template<class Arc>
void SafeDeterminizeMinimizeWrapper(MutableFst<Arc> *ifst, VectorFst<Arc> *ofst, float delta = kDelta);


void SafeDeterminizeMinimizeWrapperInLog(VectorFst<StdArc> *ifst, VectorFst<StdArc> *ofst, float delta = kDelta);



template<class Arc, class I>
void RemoveSomeInputSymbols(const std::vector<I> &to_remove,
                            MutableFst<Arc> *fst);

// MapInputSymbols will replace any input symbol i that is between 0 and
// symbol_map.size()-1, with symbol_map[i].  It removes the input symbol
// table of the FST.
template<class Arc, class I>
void MapInputSymbols(const std::vector<I> &symbol_map,
                     MutableFst<Arc> *fst);


template<class Arc>
void RemoveWeights(MutableFst<Arc> *fst);




template<class Arc>
bool PrecedingInputSymbolsAreSame(bool start_is_epsilon, const Fst<Arc> &fst);


template<class Arc, class F>
bool PrecedingInputSymbolsAreSameClass(bool start_is_epsilon, const Fst<Arc> &fst, const F &f);


template<class Arc>
bool FollowingInputSymbolsAreSame(bool end_is_epsilon, const Fst<Arc> &fst);


template<class Arc, class F>
bool FollowingInputSymbolsAreSameClass(bool end_is_epsilon, const Fst<Arc> &fst, const F &f);


template<class Arc>
void MakePrecedingInputSymbolsSame(bool start_is_epsilon, MutableFst<Arc> *fst);


template<class Arc, class F>
void MakePrecedingInputSymbolsSameClass(bool start_is_epsilon, MutableFst<Arc> *fst, const F &f);


template<class Arc>
void MakeFollowingInputSymbolsSame(bool end_is_epsilon, MutableFst<Arc> *fst);

template<class Arc, class F>
void MakeFollowingInputSymbolsSameClass(bool end_is_epsilon, MutableFst<Arc> *fst, const F &f);







template<class Arc>
VectorFst<Arc>* MakeLoopFst(const std::vector<const ExpandedFst<Arc> *> &fsts);


template<class Arc>
void ApplyProbabilityScale(float scale, MutableFst<Arc> *fst);





template<class Arc>
bool EqualAlign(const Fst<Arc> &ifst, typename Arc::StateId length,
                int rand_seed, MutableFst<Arc> *ofst, int num_retries = 10);



// RemoveUselessArcs removes arcs such that there is no input symbol
// sequence for which the best path through the FST would contain
// those arcs [for these purposes, epsilon is not treated as a real symbol].
// This is mainly geared towards decoding-graph FSTs which may contain
// transitions that have less likely words on them that would never be
// taken.  We do not claim that this algorithm removes all such arcs;
// it just does the best job it can.
// Only works for tropical (not log) semiring as it uses
// NaturalLess.
template<class Arc>
void RemoveUselessArcs(MutableFst<Arc> *fst);


// PhiCompose is a version of composition where
// the right hand FST (fst2) is treated as a backoff
// LM, with the phi symbol (e.g. #0) treated as a
// "failure transition", only taken when we don't
// have a match for the requested symbol.
template<class Arc>
void PhiCompose(const Fst<Arc> &fst1,
                const Fst<Arc> &fst2,
                typename Arc::Label phi_label,
                MutableFst<Arc> *fst);

// PropagateFinal propagates final-probs through
// "phi" transitions (note that here, phi_label may
// be epsilon if you want).  If you have a backoff LM
// with special symbols ("phi") on the backoff arcs
// instead of epsilon, you may use PhiCompose to compose
// with it, but this won't do the right thing w.r.t.
// final probabilities.  You should first call PropagateFinal
// on the FST with phi's i it (fst2 in PhiCompose above),
// to fix this.  If a state does not have a final-prob,
// but has a phi transition, it makes the state's final-prob
// (phi-prob * final-prob-of-dest-state), and does this
// recursively i.e. follows phi transitions on the dest state
// first.  It behaves as if there were a super-final state
// with a special symbol leading to it, from each currently
// final state.  Note that this may not behave as desired
// if there are epsilons in your FST; it might be better
// to remove those before calling this function.

template<class Arc>
void PropagateFinal(typename Arc::Label phi_label,
                    MutableFst<Arc> *fst);

// PhiCompose is a version of composition where
// the right hand FST (fst2) has speciall "rho transitions"
// which are taken whenever no normal transition matches; these
// transitions will be rewritten with whatever symbol was on
// the first FST.
template<class Arc>
void RhoCompose(const Fst<Arc> &fst1,
                const Fst<Arc> &fst2,
                typename Arc::Label rho_label,
                MutableFst<Arc> *fst);



template<class Arc>
bool IsStochasticFst(const Fst<Arc> &fst,
                     float delta = kDelta,  // kDelta = 1.0/1024.0 by default.
                     typename Arc::Weight *min_sum = NULL,
                     typename Arc::Weight *max_sum = NULL);




// IsStochasticFstInLog makes sure it's stochastic after casting to log.
inline bool IsStochasticFstInLog(const Fst<StdArc> &fst,
                                 float delta = kDelta,  // kDelta = 1.0/1024.0 by default.
                                 StdArc::Weight *min_sum = NULL,
                                 StdArc::Weight *max_sum = NULL);


} // end namespace fst


#include "fstext/fstext-utils-inl.h"

#endif