// doc/fst_algo.dox


// 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.

namespace kaldi {

/**
   \page fst_algo Finite State Transducer algorithms

 Here we describe the FST algorithms in the Kaldi toolkit that are new or
 different than the the ones in OpenFst (we use the OpenFst code itself
 for many algorithms).  These algorithms are 
 in the directory fstext/, and the corresponding command-line programs,
 where they exist, are in fstbin/.  This code uses the OpenFst library.
 We will only describe here the algorithms that are actually used 
 in our current recipes.
 
  \section fst_algo_det Determinization

 We use a different determinization algorithm from the one in OpenFst.  We
 distinguish this with the name DeterminizeStar(); the corresponding command-line
 program is named fstdeterminizestar.  Our determinization algorithm is actually
 closer to the standard FST determinization algorithm than the one in OpenFst,
 in that it does epsilon removal along with determinization (thus, like
 many other FST algorithms, we do not consider epsilon to be a "real symbol".
  
 Our determinization algorithm has a different way of handling what happens 
 when a transition in the initial determinized output has more than one output
 symbol on it.  The OpenFst determinization algorithm uses a
 function called FactorWeights that moves around the output symbols (encoded
 as weights) around while maintaining equivalence, in order to ensure that
 no arc has more than one (encoded) output symbol; it does not introduce new states with epsilon
 symbols on their input, which is the most "obvious" thing to do.  However, the
 FactorWeights algorithm can fail for the output of DeterminizeStar, because
 there can be cycles with more outputs than states on the cycle (this is not
 possible for the output of the normal Determinize algorithm, because it does not do
 epsilon removal).  Instead, whenever we encounter a link with more than one
 output symbols, we create a chain with a sufficient number of intermediate
 states to accommodate all the output symbols.  The weight and input symbol
 go on the first link of this chain.  The output of our DeterminizeStar 
 algorithm is deterministic according to the definitions OpenFst uses,
 i.e. treating epsilons as a normal symbols.  Its output does have epsilons
 on the input side, which is against the normal definition of
 determinism, but this is to be viewed as an encoding mechanism for allowing
 more than one output symbol on a link, and in any case it only happens
 in quite specific circumstances (an epsilon arc is always the only
 arc out of a state).

 One other difference is that our program fstdeterminizestar does not require
 the input FST to have its output symbols encoded as weights.
 
 \subsection fst_algo_det_debug Debugging determinization

 In general debugging determinization is quite hard, because when a process
 takes a long time it's hard to tell whether ever terminate.  The program
 fstdeterminizestar has the feature that if you send it a signal with
 "kill -SIGUSR1 \<its processid\>", it will stop and print out some
 information that can be useful for debugging the determinization.

  \subsection fst_algo_det_log Determinization in the log semiring

 We supply a function DeterminizeInLog() which casts an Fst in the
 normal (tropical) semiring to the log semiring before determinizing, and
 then converts back.  This is the form of determinization used in our
 algorithms, as it preserves stochasticity (see \ref fst_algo_stochastic).

 \section fst_algo_eps Removing epsilons

 We supply an epsilon-removal algorithm called RemoveEpsLocal() that is
 guaranteed to never blow up the FST, but on the other hand is not guaranteed
 to remove all epsilons.  Essentially it removes whatever epsilons it
 can easily remove without making the graph larger.  There is no optimality
 guaranteed here, as this is a hard problem.  The RemoveEpsLocal() function
 has slightly different behaviour from OpenFst's RemoveEps() function, because
 it will combine two arcs if one has an input epsilon and one an output epsilon.
 The function RemoveEpsLocal() preserves FST equivalence.

 There is also a function RemoveEpsLocalSpecial() that preserves equivalence
 in the tropical semiring while preserving stochasticity in the log semiring
 (for more on stochasticity see next section).  This appears to be a case
 where the usefulness of the semiring formalism breaks down a little bit, as
 we have to consider two semirings simultaneously.  

 
 \section fst_algo_stochastic Preserving stochasticity and testing it

 We define a stochastic FST as an FST in which, in the FST's semiring the sum of
 the weights of the arcs out of any given state (plus the final-weight) equals
 one (in the semiring).  This concept is most useful and natural in the log
 semiring; essentially, a stochastic FST is one where the sum of the weights out
 of a given arc is one (e.g. a properly normalized HMM would correspond to 
 a stochastic FST).  

 The function IsStochasticFst() tests stochasticity.  Optionally it can output
 minimum and maximum weights, to inform the user of the extent to which the
 FST fails to be stochastic.  The command-line version of this is fstisstochastic.
 We aim for most of the FST algorithms we use to preserve stochasticity, in the
 sense that they will produce stochastic outputs given stochastic inputs.  For
 non-stochastic inputs, we aim that the minimum and maximum range of the weights
 will not get larger.  By default the program isstochasticfst will test stochasticity
 after casting to the log semiring, as this is the most useful case (you can stop this
 by supplying the option --test-in-log=false).

 In order to preserve stochasticity, the FSTs that we compose with have to have
 certain properties.  These should apply to L, C and H.  Consider L, for example.
 We require that for any linear FST corresponding to a path through G, call this
 FST F, the product L o F must be stochastic.  This basically means that L
 have properly normalized pronunciation probabilities.  The actual property formally
 required may be a little stronger than this (this relates to ensuring that
 the probabilities appear at the "right time").  In practice we verify stochasticity
 by running the program isstochasticfst for each stage of graph creation.

 \section fst_algo_minimization Minimization

 We use the minimization algorithm supplied by OpenFst, but we apply a patch
 before compiling OpenFst so that minimization can be applied to non-deterministic
 FSTs.  The reason for this is so that we can remove disambiguation symbols before
 minimizing, which is more optimal (it allows minimization to combine more states).
 The patch fixes data-structure related issues; fundamentally, OpenFst's minimization
 algorithm is applicable to non-deterministic FSTs.  We supply a command-line program called
 fstminimizeencoded that minimizes FSTs after encoding weights and output symbols
 as part of the input symbols (so the FST becomes an acceptor).  This is the same
 thing the fstminimize program does except that it does not do weight pushing.  This
 is desirable for us because the way we ensure stochasticity entails avoiding any
 weight pushing.  
 
 \section fst_algo_composition  Composition

 For the most part we use OpenFst's own composition algorithms, but we do
 make use of a function TableCompose(), and a corresponding command-line program
 fsttablecompose, which is a more efficient composition algorithm for certain
 common cases.  It uses the "Matcher" concept of OpenFst; a Matcher is a kind
 of helper class used during composition that performs lookup on the arcs out of
 a state to find any arcs with a particular input or output symbol.  The normal
 matcher that OpenFst uses is SortedMatcher, which relies on arcs being sorted
 on the relevant label, and does a binary search.  TableMatcher detects 
 cases where it would be efficient to build a table indexed by label, and for
 those states it avoids the overhead of binary search.  This leads to a
 speedup when composing with things like lexicons that have a very high
 out-degree.

 \section fst_algo_disambig Adding and removing disambiguation symbols

 Our FST recipes (like other transducer-based recipes) rely on 
 disambiguation symbols.  In the normal recipes, these
 are added to the input side of the lexicon FST (L) to make it determizable.
 We also add disambiguation symbols to G and C (see \ref graph_disambig).
 Whenever we do a composition and the FST on the right has disambiguation
 symbols on its input, we (in theory) add to each state in the left-hand
 FST a self-loop for each of the disambiguation symbols, which has that
 symbol on both its input and output.  Note that the actual integer symbols
 id's for the disambiguation symbols on the left and right may not be the same.  
 For instance, we have a special symbol \#0 in G (where epsilon would normally
 be).  The symbol-id for this would generally be the highest-numbered word
 plus one.  But when we want to pass this symbol through L, we need a symbol
 in L's input symbol table (which mainly contains phones), to represent \#0.
 We have a function AddSelfLoops() that takes a mutable FST and 
 two vectors of labels (a label is an integer id for a symbol).  The vectors 
 are the same size, and represent corresponding input and output labels for
 the disambiguation symbols.  This function adds self-loops to each final
 state and each state with non-epsilon output symbols on at least one arc
 out of it.
 
 We remove disambiguation symbols with the function DeleteISymbols(), accessible
 on the command line with the program fstrmsymbols.



*/


}