factor.h

Go to the documentation of this file.

// fstext/factor.h

// Copyright 2009-2011  Microsoft Corporation

// 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_FACTOR_H_
#define KALDI_FSTEXT_FACTOR_H_

/*
   This header declares the Factor function, which takes an FST and
   compresses it by detecting linear chains of states, and creating
   special input symbols that represent these chains.  It outputs enough
   information to be able to reconstruct the original sequences [i.e.
   the mapping between the new symbols, and sequences of the original
   symbols].  It ensures that the original symbols all have the same
   number as a corresponding "new" symbol representing a sequence of length
   one; this enables certain optimizations later on.
*/


#include <fst/fstlib.h>
#include <fst/fst-decl.h>
#include "util/const-integer-set.h"

namespace fst {


template<class Arc, class I>
void Factor(const Fst<Arc> &fst, MutableFst<Arc> *ofst,
            std::vector<std::vector<I> > *symbols);


template<class Arc>
void Factor(const Fst<Arc> &fst, MutableFst<Arc> *ofst1,
            MutableFst<Arc> *ofst2);



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


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


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


enum  StatePropertiesEnum
{ kStateFinal = 0x1,
  kStateInitial = 0x2,
  kStateArcsIn = 0x4,
  kStateMultipleArcsIn = 0x8,
  kStateArcsOut = 0x10,
  kStateMultipleArcsOut = 0x20,
  kStateOlabelsOut = 0x40,
  kStateIlabelsOut = 0x80 };

typedef unsigned char StatePropertiesType;

template<class Arc>
void GetStateProperties(const Fst<Arc> &fst,
                        typename Arc::StateId max_state,
                        std::vector<StatePropertiesType> *props);



template<class Arc>
class DfsOrderVisitor {
  // visitor class that gives the user the dfs order,
  // c.f. dfs-visit.h.  Used in factor-fst-impl.h
  typedef typename Arc::StateId StateId;
 public:
  DfsOrderVisitor(std::vector<StateId> *order): order_(order) { order->clear(); }
  void InitVisit(const Fst<Arc> &fst) {}
  bool InitState(StateId s, StateId) { order_->push_back(s); return true; }
  bool TreeArc(StateId, const Arc&) { return true; }
  bool BackArc(StateId, const Arc&) { return true; }
  bool ForwardOrCrossArc(StateId, const Arc&) { return true; }
  void FinishState(StateId, StateId, const Arc *) { }
  void FinishVisit() { }
 private:
  std::vector<StateId> *order_;
};



}  // namespace fst

#include "factor-inl.h"

#endif