// doc/lattices.dox
  
  
  // Copyright 2009-2011 Microsoft Corporation
  //                2013 Johns Hopkins University (author: Daniel Povey)
  
  // 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 lattices Lattices in Kaldi
  
   \section lattices_intro Introduction
  
   A lattice is a representation of the alternative word-sequences that are "sufficiently likely" for
   a particular utterance.  In order to understand lattices properly you have to understand decoding
   graphs in the WFST framework (see \ref graph).
   In this section we summarize the issues relating to Kaldi lattices, and in the rest of this page
   we will explain them more precisely.  The reader may also want to read the paper
   <a href=https://sites.google.com/site/dpovey/2012_icassp_lattices.pdf?attredirects=0>
  "Generating exact lattices in the WFST framework", D. Povey, M. Hannemann et. al, ICASSP 2012 (submitted)</a>,
   which provides more context as to how our lattices relate to previously published algorithms.
   This page gives more focus to the programming aspects.
  
   There are two representations of lattices in Kaldi.
   The first representation is the Lattice type.  This is an FST whose weight type contains two
   floating point weights (the graph cost and the acoustic cost), whose input
   symbols are \ref transition_model_identifiers "transition-ids" (these are roughly like
   context-dependent HMM states), and whose output symbols typically represent words (in general,
   they represent whatever the output symbols on your decoding graph represented).
  
   The second representation of lattices is the CompactLattice type.  This contains essentially the same
   information as Lattice, but in a different form: it is an acceptor (meaning the input and
   output symbols are always identical), the input and output symbols represent words, and the
   sequence of transition-ids is included as part of the weights (note that OpenFst has a very general
   concept of weights; anything that satisfies the semiring axiom can be a weight).
   The weight type in CompactLattice
   contains a pair of floats and a sequence of integers (which represent transition-ids).
   We'll describe the semiring later.
  
   Since the Lattice and CompactLattice types both represent the same information, we have made
   them equivalent for I/O purposes in the sense that the mechanisms that read Lattice will
   also read CompactLattice, and vice versa.  For instance, if you use the type
   SequentialLatticeReader to read sets of lattices indexed by utterance-id, it will work
   the same whether it was actually a Lattice or a CompactLattice in the archive.
   However, we typically write lattices out as CompactLattice.  Many programs read as Lattice
   because
   To convert between lattice types, there is a function ConvertLattice()
    that you can use.
  
   The weights in both the CompactLattice and Lattice types contain two floats, which
   are interpreted as the graph cost and the acoustic cost respectively.  The graph cost
   is a sum of the LM cost, the (weighted) transition probabilities, and any pronunciation cost.  Since
   these are all mixed together, in order to do things like LM rescoring we typically first subtract
   the "old" LM cost and then add in the "new" LM cost, to avoid touching the other parts
   of the cost.  If we call these two floating point values (a,b), the semiring in Lattice
   is like the lexicographic semiring on (a+b, a-b) (see OpenFst documentation for explanation).
   That is, when we "add" (in the semiring)
   two of these pairs, we get the pair that has the lowest (graph + acoustic) cost; if they are the
   same we break ties using the difference (graph - acoustic).  This makes sense in terms of
   "taking the best path".  Actually, it only makes sense if the acoustic weights are appropriately
   scaled.  Our convention is to keep lattices externally (e.g. on disk) with the
   acoustic costs unscaled, and to apply
   the scale before any algorithm that compares the weights (and un-scale them again before
   we write the lattices out).
  
   The Lattice and CompactLattice types are used as data-structures to represent conventional lattices, and
   also to represent N-best lists.  The lattice generation algorithm we use has
   quite precise properties.  Let lattice-delta be a number (typically 10 or so).
   Our lattice generation algorithm ensures (modulo beam pruning) that every
   word-sequence whose best alignment has cost within lattice-delta of the best
   path is present in the lattice, and has the best possible alignment and weight.
   Also, each word-sequence must be present in the lattice only once.  We achieve this by
   first creating a state-level lattice and appropriately pruning it, and then
   determinizing it using a special semiring (or if you like, you can view this as
   a special determinization algorithm that handles non-functional FSTs by always
   picking the most likely alternative path).  We'll explain below below exactly
   how this works.
  
   We always ensure that for lattices that we write out to disk,
   each word-sequence has only one path through the lattice.  This is required for
   certain algorithms (such as LM rescoring) to work properly.  Being determinized
   (on the word labels, in the CompactLattice format) is a sufficient condition for this.
  
   We never attach symbol tables to FSTs in any Kaldi code.  In order to view
   archives containing lattices in their most natural form with actual words
   in them, we use scripts to do the conversion (an example is in egs/rm/s1/steps/decode_tri1_latgen.sh).
  
   \section lattices_lattice The Lattice type
  
   The Lattice type is just an FST templated on a particular semiring.
   In kaldi-lattice.h, we create a typedef:
  \verbatim
   typedef fst::VectorFst<LatticeArc> Lattice;
  \endverbatim
   where LatticeArc is the normal arc type templated on LatticeWeight:
  \verbatim
  typedef fst::ArcTpl<LatticeWeight> LatticeArc;
  \endverbatim
  LatticeWeight is again a typedef that instantiates the LatticeWeightTpl
  template using BaseFloat as the floating point type.
  \verbatim
  typedef fst::LatticeWeightTpl<BaseFloat> LatticeWeight;
  \endverbatim
  The template LatticeWeightTpl is something that we define in the
   fst namespace, in fstext/lattice-weight.h.
  It has some similarities to the lexicographic semiring, i.e. it is similar to
  the OpenFst type
  \verbatim
   LexicographicWeight<TropicalWeight, TropicalWeight>
  \endverbatim
  In both cases, addition (the semiring "plus" operation) is defined as taking
  the max, but the "max" is differently defined.  LexicographicWeight first compares
  the first element and uses the second to break
  ties.  LatticeWeight first compares the sum; tie-breaking is then done using the
  difference.  So a LatticeWeight with (a,b) is equivalent to a LexigraphicWeight
  with (a+b, a-b).  The basic intuition behind LatticeWeight is to preserve the
  semantics of taking the lowest-cost path (where the total cost is the graph plus
  acoustic cost), while separately "remembering" what the acoustic and graph cost were.
  In an ideal world, we might like to keep more information separate: for instance,
  the LM cost versus the transition-model cost versus the pronunciation-probability
  cost.  But this is not practical because this information is all mixed together in
  the decoding graph, and separating it out in the decoding graph would lead to a
  significant expansion in decoding-graph size.
  
  As mentioned previously, the input symbols in the Lattice represent transition-ids,
  and the output symbols represent words (or whatever symbol was on the output
  of your decoding graphs).
  
  When designing Kaldi we considered using the LexicographicWeight type instead of
  the LatticeWeight type, where the first element would be the (graph + acoustic)
  cost and the second element would be, say, just the acoustic cost.  We
  ultimately decided against this because while it might be slightly more
  efficient for some purposes, we felt it would be too confusing.
  
  Many algorithms on lattices (for instance, taking the best path, or pruning) are
  most efficient to do using the Lattice type rather than the CompactLattice type.  The issue
  is that with the CompactLattice type, the weights contain sequences of transition-ids,
  and operations like taking the best path will multiply weights together which
  corresponds to appending these sequences.  For many algorithms, this would take time quadratic
  in the length of the lattice in words.  As mentioned above, you can read a Lattice
  from an archive even if it contains a CompactLattice because the Holder type (LatticeHolder)
  does automatic conversion.  So the code:
  \verbatim
    SequentialLatticeReader lattice_reader(lats_rspecifier);
    for (; !lattice_reader.Done(); lattice_reader.Next()) {
       std::string key = lattice_reader.Key();
       Lattice lat = lattice_reader.Value();
       ...
    }
  \endverbatim
  would be valid even if the archive or script file specified in "lats_rspecifier"
  contained the CompactLattice format-- which it normally would, because that is how
  we normally write lattices.  An example of lattice type conversion is:
  \verbatim
    Lattice lat;
    // initialize lat.
    CompactLattice compact_lat;
    ConvertLattice(lat, &compact_lat);
  \endverbatim
  Conversion to the CompactLattice type involves a "factoring" operation, the function
  fst::Factor() (defined by us in fstext/factor.h), that identifies chains of states
  that can be combined into a single CompactLattice arc.
  A typical example of appying an OpenFst algorithm to a lattice is as follows
  (this code, modified from latbin/lattice-best-path.cc, finds the best path
  through a lattice):
  \verbatim
    Lattice lat;
    // initialize lat.
    Lattice best_path;
    fst::ShortestPath(lat, &best_path);
  \endverbatim
  
  
   \section lattices_compact Compact lattices (the CompactLattice type)
  
   Similarly to the Lattice type, CompactLattice is a typedef to a typical OpenFst
   template:
  \verbatim
   typedef fst::VectorFst<CompactLatticeArc> CompactLattice;
  \endverbatim
  The CompactLatticeArc type is a standard template for an Arc, templated on CompactLatticeWeight:
  \verbatim
   typedef fst::ArcTpl<CompactLatticeWeight> CompactLatticeArc;
  \endverbatim
  The CompactLatticeWeight type is a typedef as follows:
  \verbatim
   typedef fst::CompactLatticeWeightTpl<LatticeWeight, int32> CompactLatticeWeight;
  \endverbatim
  The template arguments are the underlying weight type (LatticeWeight), and an
  integer type (int32) that is used to store the sequences of transition-ids.
  Note that in Kaldi code (such as above), we tend to prefer to define concrete types,
  for understandability, whereas the OpenFst style is to define templates, and when coding inside the
  fst namespace we tend to follow this convention.  Thus, we define a template in the
  fst namespace and turn it into a fully-specified type (CompactLatticeWeight) in the
  kaldi namespace.
  
  The template arguments of CompactLatticeWeightTpl are an underlying weight (here,
  LatticeWeight) and an integer type (here, int32).  It contains two data members: a weight and
  a sequence of integers:
  \verbatim
  template<class WeightType, class IntType>
  class CompactLatticeWeightTpl {
     ...
   private:
    WeightType weight_;
    vector<IntType> string_;
  };
  \endverbatim
  These can be accessed using the member functions \ref fst::CompactLatticeWeightTpl::Weight() "Weight()"
  and \ref fst::CompactLatticeWeightTpl::String() "String()".  The semiring used by
  \ref fst::CompactLatticeWeightTpl "CompactLatticeWeightTpl" does not correspond to any
  semiring used in OpenFst, as far as we are aware.  Multiplication corresponds to multiplying
  the weights and appending the strings together.  When adding two CompactLatticeWeights,
  we first compare the weight component.  If one of the weights is "more" than the other one, we take that weight
  and its corresponding string.  If not (i.e. if the two weights are the same), we use an ordering
  on the strings to break ties.  The ordering if we use is to take the shortest string if
  they have different length, and otherwise use lexical order (we can't just use lexical order, or it
  would violate one of the semiring axioms which is distributivity of multiplication over
  addition).
  
  Note that we talked above about one of the weights being "more" than the other one, and we
  assumed that if neither is more than the other, then they are equal.  This is only true if there
  is a total order on the semiring, and this is a requirement on the weight component of
  the template (this requirement is fulfilled for LatticeWeight and TropicalWeight).
  The "OpenFst" way to access this ordering is using the template "NaturalLess", which given
  a and b, looks for whether (a+b) is equal to a or to b.  For efficiency reasons, we don't
  do it this way: we assume that there is a Compare() function defined on the weight type
  which returns -1, 0 or 1 depending on the comparison.  We have such a function defined
  for the LatticeWeightTpl template.  To enable CompactLatticeWeightTpl
  to be instantiated for TropicalWeight, which we do for testing purposes,
  we define an appropriate Compare function for that weight type.
  
  There is a reason why we define this perhaps rather strange looking semiring.  It relates
  to our idea of a lattice as containing the best path for any given word sequence.
  Suppose we had an arbitrary lattice (e.g., it might be a raw state-level lattice) and
  we represent it as a CompactLattice, which is an acceptor on word sequences with the
  transition-id sequences as part of the weights.  The semantics of WFSTs is that for
  any (input-symbol-sequence, output-symbol-sequence) pair, the weight that the WFST
  assigns is the sum of the weights of all paths that have that pair of symbol-sequences.
  In the current case, we are dealing with an acceptor so there is really only symbol-sequence
  (the word sequence).  The point is that when we sum the (weight, string) pairs
  in this semiring, we just get the single (weight, string) pair that
  has the best "weight component", i.e. the lowest cost.  If we were to remove
  epsilons and determinize, in this semiring, we would get a lattice that only had a
  single path for each word sequence, and that path would have the best possible
  cost for that word sequence.  This wouldn't be very efficient, so we actually use
  a specialized determinization algorithm that removes epsilons and that is optimized for this case, but it
  has the same effect as calling that the normal OpenFst RemoveEps() and Determinize() algorithms would.
  
   \section lattices_generation Lattice generation
  
  Command-line decoding programs that have 'latgen' in their names generate lattices.
  Currently most of these use LatticeFasterDecoder.  For purposes of exposition we will
  focus instead on LatticeSimpleDecoder, whose operation is simpler.
  This is defined in decoder/lattice-simple-decoder.h, and invoked by gmm-latgen-simple.cc.
  As the name suggests, LatticeSimpleDecoder is a lattice-generating decoder that is modified from SimpleDecoder.
  SimpleDecoder is a straightforwardly implemented Viterbi beam search algorithm with only a single
  tunable parameter: the pruning beam (see \ref decoders_simple).  LatticeSimpleDecoder has
  one more important tunable parameter: the lattice beam (or lattice-delta), which should typically be
  less than the pruning beam.
  The basic picture is that LatticeSimpleDecoder first produces a state-level lattice, and prunes
  it with the lattice-delta, and then at the end it runs a special determinization algorithm
  that results in only keeping the best path for each word sequence.
  
  In SimpleDecoder, there are reference-counted tracebacks.  In LatticeSimpleDecoder,
  a single traceback isn't enough because the lattice has a more complicated structure.
  In fact, it turned out to be more convenient to store <EM> forward </EM> instead of
  backward links.  We need to do more than just do reference counting in order to
  free un-needed links, because of the lattice-delta pruning; in fact there is no reference counting.
  
  The final objective of the pruning algorithm is as follows (call this the
  "naive" approach.
  Firstly, suppose that for each
  frame, for each state that was active on that frame we created a structure or token
  of some kind, and for each arc out of it (to a state that was not pruned), we
  create some kind of link record.  Let's use the word "token" for the structure
  that we create for a particular graph state at a particular frame, and "link" for
  the forward link from one token to another token (note: these links can be within
  a frame as well as across frames, due to epsilon arcs in the decoding graph).
  The simplest possible version of the pruning algorithm is:
  firstly, we decode up till the end of the file, keeping all the tokens and links
  that were active during decoding.
  When we have come to the end of the file we want to apply the lattice-delta beam,
  such that any state or arc that is not on a path that is within lattice-delta
  cost of the best path, will be pruned away.  This is fairly easy to do: for example,
  we could turn the state-level traceback into an FST and use OpenFst's \ref fst::Prune()
  "Prune()" algorithm.  Unfortunately this wouldn't be a very practical algorithm
  because we would soon run out of memory: on each frame there are typically
  many thousands of states active, and we can't afford to wait till the end of the
  utterance to prune them.
  
  Fortunately there is an efficient way to prune away these tokens without waiting
  until the end of the utterance.  Periodically (every 25 frames by default), we do
  a backward sweep from the current frame to the beginning.  In this backward
  sweep, we work out a "delta" quantity for each token.  The "delta" is the
  difference between the cost of the best path and the cost of the best path the
  token is on, and it can be computed in the backward sweep (the "forward"
  information that we need it already inside the token, and is static).  We can
  define an analogous "delta" quantity for the forward links.  Any time this
  "delta" exceeds the "lattice-delta" beam, we prune away the associated token or
  link.  For the tokens at the currently active frame, we set the "delta" to zero;
  we can prove that this is the right thing to do.  That is, with this algorithm
  we will only be pruning away things that we eventually would have pruned away anyway
  using the "naive" algorithm.
  
  It might seem on the face of it that our pruning algorithm would take time
  quadratic in the length of the utterance (because each 25 frames we visit the whole
  utterance up to the current point), but in fact it is more like linear,
  because we can detect when all the "delta" values of tokens for a particular
  frame have not changed, and we can stop going backward in time.  We expect that
  for very long utterances, we will normally prune backward for only a second or two.
  Even if it were not for this feature, the algorithm would be dominated by a linear-time
  component in practical cases, because the vast majority of tokens are deleted the
  first time they are visited by the algorithm.
  
  We note that there are a couple of complexities in our implementation of this.  One
  is that because we have forward links, while the pruning algorithm goes backward in
  time, there is a danger of "dangling" forward links being created when we delete()
  tokens, so we have to avoid delete()ing tokens until we have pruned the forward
  links from the previous frame.  The other issue is that we have to treat the
  final frame specially, because we need to take into account the final
  probabilities.
  
  
  \subsection lattices_generation_raw Getting the raw lattice, and converting it into the final form.
  
  When we have reached the end of the utterance, we produce the lattice in two phases.
  The first phase is to create the
  "raw lattice".  This is a state-level FST that is pruned using the lattice-delta
  but is not determinized, so it has many alternative paths corresponding to each
  word sequence.  Creation of the "raw lattice" is very trivial, and consists of
  taking our token and link structures and translating them into OpenFst
  structures.  If we are asked for the best path (e.g. for getting the transcript),
  we would just run OpenFst's ShortestPath algorithm on this raw lattice.  If we
  are asked for the lattice, there are two options.
  
  The first option is: the
  decoder supports outputting the raw state-level lattice directly (set --determinize-lattice=false);
  this is mostly useful if you are going to do acoustic rescoring with a system built with the
  same tree.  Afterwards you would probably want to determinize the lattice using the
  lattice-determinize program, before storing the lattices on disk for an extended time
  (as the raw state-level lattices are quite large).
  
  Let's assume instead that we're outputting
  the determinized lattice (the second option).  The determinized lattice is supposed to have only one
  path through it for every word sequence that is allowed in the original raw
  lattice.  We can achieve this by creating a CompactLattice, removing epsilons and
  determinizing, but this would be very inefficient.  Instead, we run a special
  determinization algorithm called \ref fst::DeterminizeLattice()
  "DeterminizeLattice()".  This algorithm does epsilon removal and
  determinization together.  In this respect it is similar to our algorithm \ref
  fst::DeterminizeStar() "DeterminizeStar()", but the \ref
  fst::DeterminizeLattice() "DeterminizeLattice()" algorithm uses data structures
  that are specifically optimized for this case.  The issue is the cost overhead of
  appending long strings of input symbols together (the sequences of symbols are only about as long
  as the maximum number of frames in a word, but this is quite long).  That is, if represented in the
  most naive way as vectors, adding a symbol to a list of N symbols and storing
  the result separately take time O(N).  Instead we use data structures that make
  it take constant time.  \ref fst::DeterminizeLattice()
  "DeterminizeLattice()" takes as input the Lattice format, since this is the
  most natural form for the input, and outputs in the CompactLattice format.  However,
  it should really be viewed as determinization of the CompactLattice format: that
  is, it preserves equivalence only when viewing it as an operation on a CompactLattice.
  
   \section lattices_archives Lattices in archives
  
   We normally store lattices in archives.  For general information about archives and
   Kaldi I/O mechanisms, see \ref io.  For a concrete example, a command line that
   generates lattices might be as follows:
  \verbatim
    gmm-latgen-simple --beam=13.0 --acoustic-scale=0.0625 exp/tri/1.mdl \
       exp/graph_tri/HCLG.fst ark:test_feats.ark "ark,t:|gzip -c > exp/lats_tri/1.lats.gz"
  \endverbatim
   After this, we could look at the lattice as follows:
  \verbatim
  gunzip -c exp/decode_tri2a_bg_latgen_eval92/7.lats.gz | \
    utils/int2sym.pl -f 3 data/words.txt | head
  444c0410
  0 1 <s> 5.27832,0,
  1 2 <UNK> 8.08116,1099.84,
  1 3 A 12.8737,8342.93,3_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_17_17_17_17_17_17_3\
  464_3596_3632_3_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_\
  1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_12_18_17_17_18562_18561_18604_18\
  603_18603_18618_604_603_603_638
  1 4 IF 10.2262,8096.64,3_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_17_17_17_13708_137\
  28_13806_12654_12670_12676_3_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1\
  _1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_1856\
  2 5 NOT 12.4568,10548.7,3_1_1_1_1_1_1_1_1_1_1_12_18_17_17_17_17_17_17_17_20_26\
  ...
  \endverbatim
  It might seem slightly disconcerting that the label \<UNK\> appears on
  a transition that has graph and acoustic scores but with no input labels
  (these would appear after the final comma, if they
  were present).  It must be appreciated that graph and acoustic scores and input-label
  sequences are only valid when summed (or appended) over entire paths through the
  FST.  There is no guarantee that they will be synchronized with respect to each other
  or with respect to the word labels.
  
  Lattices are normally stored in the CompactLattice format in the archive, and
  as mentioned before, we use the convention that the acoustic weights in the
  archive are unscaled, so for operations (such as pruning) that are sensitive
  to the acoustic weight, the corresponding command-line programs would take
  the --acoustic-scale option and would scale the acoustic weights prior to such
  operations (and un-scale them afterwards).
  
  \section lattices_operations Operations on lattices
  
  Here we discuss some operations that can be done on lattices, and their corresponding
  programs.
  
   \subsection lattices_operations_pruning Pruning lattices
  
   We can prune lattices using a specified pruning beam.  This will remove arcs and states that
   do not appear on a path that has a cost sufficiently close to the cost of the best path through the lattice.
   For each lattice, the program lattice-prune first scales the acoustic weights using a specified acoustic
   scale, then calls OpenFst's \ref fst::Prune() "Prune()" function, then reverses the
   scaling of acoustic weights.  An example command line is:
  \verbatim
   lattice-prune --acoustic-scale=0.1 --beam=5 ark:in.lats ark:out.lats
  \endverbatim
   Note: for efficiency, the pruning operation is done in the Lattice format, but we convert
   to CompactLattice before writing the lattice out.
  
   \subsection lattices_operations_best_path Computing the best path through a lattice
  
   The program lattice-best-path computes the best path through a lattice, and outputs
   the corresponding input-symbol sequence (alignment) and output-symbol sequence (transcription).
   As usual, the input and outputs are in the form of archives.  An example command line is:
  \verbatim
   lattice-best-path --acoustic-scale=0.1 ark:in.lats ark:out.tra ark:out.ali
  \endverbatim
  
   \subsection lattices_operations_nbest Computing the N-best hypotheses
  
   The program lattice-nbest computes the N best paths through the lattice (using
   OpenFst's \ref fst::ShortestPath() "ShortestPath()" function), and outputs
   the result as a lattice (a CompactLattice), but with a special structure.
   As documented for the \ref fst::ShortestPath() "ShortestPath()" function in
   OpenFst, the start state will have (up to) n arcs out of it, each one to the
   start of a separate path.  Note that these paths may share suffixes.
   An example command line is:
  \verbatim
   lattice-nbest --n=10 --acoustic-scale=0.1 ark:in.lats ark:out.nbest
  \endverbatim
  
   \subsection lattices_operations_lmrescore Language model rescoring
  
   Because the "graph part" (the first component) of LatticeWeight contains the
   language model score mixed together with the transition-model score and any
   pronunciation or silence probabilities, we can't just replace it with
   the new language model score or we would lose the transition probabilities
   and pronunciation probabilities.  Instead we have to first subtract the
   "old" LM probabilities and then add in the new LM probabilities.  The
   central operation in both of these phases is composition (there is some
   scaling of weights going on, also).  The command line for doing this
   is: first, to remove the old LM probabilities:
  \verbatim
   lattice-lmrescore --lm-scale=-1.0 ark:in.lats G_old.fst ark:nolm.lats
  \endverbatim
   and to add the new LM probabilities:
  \verbatim
   lattice-lmrescore --lm-scale=1.0 ark:nolm.lats G_new.fst ark:out.lats
  \endverbatim
  Note: the above examples are slightly simplified; actually you would have
  to "project" the G.fst FST's on the output to remove disambiguation symbols
  using `fstproject` with `--project_output=true`, see steps/lmrescore.sh for examples.
  Also there are other ways to do this; see
  the documentation for lattice-compose below.
  What the program \ref lattice-lmrescore.cc "lattice-lmrescore" does is this...
  actually, we will first first describe the simple version that is not exactly what
  happens.  Suppose that we are given an LM-scale S and a LM G.fst.
  We first multiply all the costs in G.fst by S.  Then for each lattice,
  we compose it on the right with G, lattice-determinize it (to keep only the
  best path through G for each word sequence) and write it out.  This would
  work fine for positive S, but for negative S it would be equivalent to taking
  the <EM> worst </EM> path through G, for each word sequence.  To fix this,
  we instead do it as follows.
  For each input lattice, we first
  scale the lattice's graph (or LM) costs by the inverse of S; we then compose
  on the right with G.fst; we run lattice-determinization (see above) on the resulting lattice
  which retains only the best path through the lattice for each word sequence;
  and we then scale the lattice's graph/LM scores by S.  This does the right
  thing for negative S.  This whole approach only makes sense if the input
  lattice has only a single path through it for each word sequence (e.g. if it
  was lattice determinized).  We assume that all lattices passed between programs
  have this property (this is why it is not a good idea to write out "raw" state-level
  lattices, unless you know what you are doing).
  
  Note that in order for the composition to work, this program needs to map G.fst
  from the tropical semiring into the LatticeWeight semiring.  It does this by
  putting the weights of G.fst into the first part of the weight (the "graph"
  part), and leaving the second part of the weight zero (in the semiring, this is
  1).  At the C++ level, this mapping is done using the MapFst mechanism of
  OpenFst, in which we define a Mapper class to map StdArc to LatticeArc, and then
  create an object of type MapFst which is evaluated on demand and converts G.fst
  to the LatticeWeight weight type.
  
   \subsection lattices_operations_scale Probability scaling
  
   It is possible to scale the probabilities on lattice weights using a general
   2x2 matrix.  The command-line program that does this is lattice-scale.
   An example command line is:
  \verbatim
   lattice-scale --acoustic-scale=0.1 --lm-scale=0.8 ark:in.lats ark:out.lats
  \endverbatim
   This is actually not a frequently used program, because we expect that normally the
   acoustic weights in archives should be unscaled;  programs that need to apply an acoustic
   scale generally accept an --acoustic-scale option.   Such programs generally apply the scale,
   do an operation (such as determinization or pruning) that is sensitive to it, and then apply
   the inverse of the scale.
   For most operations we do not
   want to scale the LM probabilities; however, it might sometimes be useful to do so, e.g.
   in discriminative training it might be useful to tune both the LM and acoustic scale.
   The lattice-scale program accepts the options --lm2acoustic-scale
   and --acoustic2lm-scale.  For instance, the program would add  --lm2acoustic-scale
   times the original LM part of the weight to the acoustic part of the new weight.  We include
   this mostly for completeness.
  
   \subsection lattices_union Lattice union
  
   The program lattice-union computes the union of two lattices (as with other programs,
   this program iterates over sets of lattices in archives).  The main envisaged use of
   this is in discriminative training (especially MMI), to ensure that the correct
   transcription is present in the denominator lattice.  An example command line is:
  \verbatim
   lattice-union ark:num_lats.ark ark:den_lats.ark ark:augmented_den_lats.ark
  \endverbatim
   This program calls OpenFst's Union() function, then lattice-determinizes to
   ensure there is only one path for each word sequence, then write the lattice out.
   There are actually not many situations where lattice union makes sense (e.g.
   it does not make much sense to do the union over lattices computed with different
   features or models).
  
   \subsection lattices_operations_compose Lattice composition
  
   The program lattice-compose works in several modes.  One composes lattices
   with other lattices.  This is done in the transducer form, i.e. viewing
   a lattice as a transducer from transition-ids to words.  It would typically
    be done after first projecting one of the sets of lattices on the output
   (to get a word to word transducer).  Typical usage might be:
  \verbatim
    lattice-project ark:1.lats ark:-  | \
      lattice-compose ark:- ark:2.lats ark:3.lats
  \endverbatim
   Now, 3.lats would have the sum of the scores in
   1.lats and 2.lats, on its paths.  You can accomplish the same thing in "one package"
   by using the program lattice-interp (see next section).
  
   Another mode is to compose a set of lattices with a fixed FST.
   The FST is converted dynamically into a lattice for this purpose;
   the FST weights are interpreted as the "graph part" of the lattice weights,
   i.e. as the first part of the tuple.  An example of the use of
   this is to convert a lattice to phones, and then compose with
   a lexicon to convert back to words, for example:
  \verbatim
   lattice-to-phone-lattice final.mdl ark:1.lats ark:- | \
     lattice-compose ark:- Ldet.fst ark:words.lats
  \endverbatim
   This is a simplified example; you'd do further processing
   to remove the original "graph scores" from the lattices and
   add back in the grammar and transition scores.  Also,
   Ldet.fst is a specially processed version of the lexicon:
   the lexicon with disambiguation symbols (but without the
   loop that converts \#0 to \#0 to pass through the language
   model disambiguation symbol), determinized and with the
   disambiguation symbols then removed.
  
   The mode described above can also be useful for language model
   rescoring; however, it also comes in a different version,
   illustrated below (this is useful for adding in LM scores to lattices, assuming
   we had removed the old LM scores):
  \verbatim
    lattice-compose --phi-label=13461 ark:1.lats G.fst ark:2.lats
  \endverbatim
   Here, G.fst would be the grammar including the special "backoff symbol"
   \#0 on the input side, and 13461 is the numeric label of the backoff symbol.
  This form of composition treats the backoff symbol as a failure transition
   (using OpenFst's PhiMatcher), which is only taken in case the
   requested label did not exist: thus, we treat G.fst as a backoff
   language model.  This form of composition is more exact than
   turning the \#0 into epsilon and compsoing normally, because it
   prevents us taking backoff arcs when a non-backoff arc exists
   (which amounts to a misinterpretation of the language model).
   Actually, what the program lattice-compose has to do is a little more
   complicated than just invoking Compose with OpenFst's PhiMatcher, because
   of the way final-probabilities are treated.  Because Compose doesn't use
   the matcher when computing final probabilities, we can fail to take the
   backoff arc when computing final probabilities.   Therefore the
   lattice-compose program has to modify the final probabilities
   by "following through" the phi arcs, before calling the composition
   algorithm.  Note that this problem would not exist if we had the end-of-sentence
   symbol as a label in G, but in some scripts we prefer to remove it.
  Note also that "phi composition" would not work properly in general, if
  the FST with phi's in it had epsilons on that same side.  Thus, it makes
  sense to remove epsilons from G first.
  
   \subsection lattices_operations_interp Lattice interpolation
  
   The program lattice-interp interpolates two sets of lattices together,
   with a scaling factor.  An example command line is:
  \verbatim
    lattice-interp --alpha=0.4 ark:1.lats ark:2.lats ark:3.lats
  \endverbatim
  which amounts to putting a weight of 0.4 on the scores of 1.lats and
  of 0.6 on the scores of 2.lats.  It keeps the alignments, if any, present
  in the first archive.  Note that this program will not output
  any lattice if the composition is empty because the two lattices
  had no paths in common, so the final archive may
  have "gaps" in it.  You have to build in some mechanism to produce
  output for such utterances, into your decoding scripts (e.g.
  see egs/rm/s3/steps/decode_combine.sh).  The behavior of this
  program can be simulated by combining the programs
  lattice-scale, lattice-project and lattice-compose.
  
   \subsection lattices_operations_phones Conversion of lattices to phones
  
    The program lattice-to-phone-lattice removes the word labels from the
   output side of a lattice and puts in their place phone labels.  These
   are worked out from the transition-ids on the input side.  Note that the phone labels are
   not exactly aligned with the phone boundaries (as a rule, FSTs have
   no real concept of alignment between input and output symbols).
   Typical usage is:
  \verbatim
    lattice-to-phones final.mdl ark:1.lats ark:phones.lats
  \endverbatim
  
   \subsection lattices_operations_project Lattice projection
  
    Projection is an FST operation that turns an FST into an acceptor, either
    by copying the output symbols to the input, or the input symbols to the output,
   so they are both the same.  The default for lattice-project is to copy the
   word labels to the input side (this is useful when doing interpolation
   of the scores of lattices).  An example is:
  \verbatim
    lattice-project ark:1.lats ark:- | \
       lattice-compose ark:- ark:2.lats ark:3.lats
  \endverbatim
  
   \subsection lattices_operations_equivalent Lattice equivalence testing
  
    The program lattice-equivalent is mostly useful as a debugging tool.  It
   tests the equivalence of sets of lattices.  It returns with exit status 0
   only if all pairs of lattices in two supplied tables (e.g. archives) are
   equivalent.  It uses a randomized equivalence testing algorithm to do this.
   A typical usage is:
  \verbatim
    lattice-equivalent ark:1.lats ark:2.lats || echo "Not equivalent!"
  \endverbatim
   Optional arguments include --num-paths (the number of paths used in the
   randomized testing algorithm) and --delta, the score difference at which
   scores are considered different for purposes of equivalence testing.
  
   \subsection lattices_operations_rmali Removing alignments from lattices
  
   The program lattice-rmali removes the alignment information (i.e. the
   transition-ids) from the input side of the lattices.  This is mainly useful
   if you will not need that information (e.g. you only need the lattices for
    language model rescoring), and you want to save disk space.  An example is:
  \verbatim
    lattice-rmali ark:in.lats ark:word.lats
  \endverbatim
  
   \subsection lattices_operations_boost Error boosting in lattices
  
   The program lattice-boost-ali is used in boosted MMI training.  It reads in
   a lattice and an alignment (both as tables, e.g. archives), and outputs the
   lattices with the language model scores (i.e. the graph part of the scores)
   boosted by the parameter b times the number of frame-level phone errors on that
   path.  Typical usage is:
  \verbatim
    lattice-boost-ali --silence-phones=1:2:3 --b=0.1 final.mdl ark:1.lats \
     ark:1.ali ark:boosted.lats
  \endverbatim
  The silence phones are treated specially: wherever they appear in the lattices,
  they are assigned zero error, i.e. they are not counted as errors
  (this behavior can be controlled with the --max-silence option).    Note that
  this special treatment of silence has been adopted from MPE training where it
  appeared to help; we have not investigated its exact effect on boosted MMI.
  
   \subsection lattices_operations_post Computing posteriors from lattices
  
    The program lattice-to-post computes, from a lattice, per-frame posterior
   probabilities of the transition-ids in the lattice.  This is done by a standard
   forward-backward type of algorithm.  Since, by convention, we store lattices
   without any acoustic scaling, it will normally be necessary to supply an
   acoustic scale to be used in the forward-backward algorithm.  It also accepts
   a language model scale, but the default (1.0) will often be most appropriate.
    An example of
   using this program is:
  \verbatim
    lattice-to-post --acoustic-scale=0.1 ark:1.lats ark:- | \
      gmm-acc-stats 10.mdl "$feats" ark:- 1.acc
  \endverbatim
  
   \subsection lattices_operations_det Determinization of lattices
  
    The program lattice-determinize implements lattice-determinization, which
   essentially consists of keeping, for each word-sequence in the lattice, only
   the best-scoring sequence of transition-ids.  In general this process is
   sensitive to the acoustic scale (because "best-scoring" depends on the scale),
   but if the lattice has previously been determinized and then has only been processed
   in a "word-level" way, i.e. each word-sequence still has only one transition-id
   sequence, then the acoustic scale doesn't matter.   The only time the acoustic
   scale is likely to matter is if you generate state-level lattices, e.g. you
   do lattice generation with --determinize-lattice=false.
   This program has other options, that are mostly related to what to do if
   determinization "blows up", i.e. exhausts memory, but in general you can just
   leave these at their default values.   These are mostly there because a previous
   version of the determinization tended to exhaust memory.
   You may want to set --prune=true if you want
   to do pruning as part of the same program, but be careful that this only makes sense
   if you have set the acoustic scale to an appropriate value; you might also want to
   set the --beam option in that case.
  
   A typical usage is:
  \verbatim
     lattice-determinize ark:1.lats ark:det.lats
  \endverbatim
  or:
  \verbatim
     lattice-determinize --acoustic-scale=0.08333 ark:state_level.lats ark:1.lats
  \endverbatim
   Note that lattices produced by lattice generation programs will be default already
   be determinized, so it only makes sense to do determinization if you have just done
   an operation like composition that makes lattices nondeterministic, or if you
   have given --determinize-lattice=false to the lattice generation program to create
   state-level lattices.
  
   \subsection lattices_operations_oracle Computing oracle WERs from lattices
  
   The program lattice-oracle takes two tables: the first of lattices, the second
   of transcriptions (C++ representation: vector<int32>), and outputs the oracle
   word-sequence of the lattices; it prints out the corresponding WERs in its
   logging output.  This is done by constructing an "edit-distance FST" and
   composing this with unweighted acceptors constructed from the lattice and
   from the reference.
  
    An example (this script fragment assumes the newer, s3-style script) is:
  \verbatim
   cat $data/text | \
    sed 's:<NOISE>::g' |  sed 's:<SPOKEN_NOISE>::g'  | \
    scripts/sym2int.pl --ignore-first-field $lang/words.txt | \
    lattice-oracle --word-symbol-table=$lang/words.txt  \
      "ark:gunzip -c $dir/lats.pruned.gz|" ark:- ark,t:$dir/oracle.tra \
      2>$dir/oracle.log
  \endverbatim
  
   \subsection lattices_operations_tprob Adding transition probabilities to lattices
  
   The program lattice-add-trans-probs adds in the (negated) transition probabilities  to the
   costs of a lattice.  This is useful in forms of lattice rescoring where the original
   "graph costs" are discarded and reconstructed from scratch.  A typical usage is:
  \verbatim
    lattice-add-trans-probs --transition-scale=1.0 --self-loop-scale=0.1 \
        final.mdl ark:1.lats ark:2.lats
  \endverbatim
    See \ref hmm_scale for more explanation about these scaling factors.
  
    \subsection lattices_operations_to_fst Converting lattices to FSTs
  
   The program lattice-to-fst converts an table of lattices into a table of
   FSTs, in the same format used by the code that compiles the training
    graphs.  The resulting FSTs will be weighted word acceptors (although
   in current use of this program we apply a scale of zero so there are
   actually no weights).  These may be used as input to the program
   compile-train-graphs-fsts to produce decoding graphs that only include
   the paths present in the lattice.  The main use of this is to do
   lattice rescoring across different models that don't share the same tree.
   An example of usage is:
  \verbatim
    lattice-to-fst --lm-scale=0.0 --acoustic-scale=0.0 ark:1.lats ark:1.words
  \endverbatim
  
  
   \subsection lattices_operations_copy Copying lattices
  
    The program lattice-copy simply copies a table (e.g. archive) of lattices.
   This is mostly useful if you want to view binary FSTs in text form.  For
   example:
  \verbatim
    lattice-copy ark:1.lats ark,t:- | head -50
  \endverbatim
  
    \section lattice_nbest N-best lists and best paths
  
    There are some situations (e.g. Viterbi training; rescoring with neural-net language
    models) where we don't want the lattice structure and want either the best path
    or the N best paths.  Our format for N-best lists is the same as for lattices,
    except for each utterance we have multiple FSTs (up to n, for some specified n).
   Suppose the utterance id's are uttA, uttB, and so on.  A normal Table of lattices
   (e.g. an archive) will contain a lattice for uttA, one for uttB, and so on.
   If we run the program
  \verbatim
    lattice-to-nbest --acoustic-scale=0.1 --n=10 ark:1.lats ark:1.nbest
  \endverbatim
   then the archive 1.nbest will contain lattices for uttA-1, uttA-2, ... uttA-2,
   for uttB-1 ... uttB-10, and so on.  Of course some of the utterances may not
   have that many N-best entries if the lattice did not contain that many distinct
   word sequences.  The program lattice-to-nbest needs the acoustic scale as this
   affects which paths would have the lowest score.
  
   For some purposes it will still be inconvenient to deal with an FST and
   we want an actual linear structure, e.g. just a sequence of words.  For this,
   we can use the following program:
  \verbatim
   nbest-to-linear ark:1.nbest ark:1.ali ark:1.words ark:1.lmscore ark:1.acscore
  \endverbatim
   This program reads in an archive of lattices, which must each be a linear FST,
   and outputs 4 archives, corresponding to the input symbol sequences, the output
   symbol sequences, and the acoustic and LM scores.   The format (assuming
   you write in text mode, e.g. with "ark,t:my_file") is as one would
   expect, e.g.:
  \verbatim
  # head 1.words
  utt-A-1 10243 432  436 10244
  utt-A-2 7890  420 10244
  ...
  \endverbatim
  Remember that Kaldi always deals with integer id's; you can convert to words
  using the symbol table and "utils/int2sym.pl -f 2-".  The reverse transformation
  can be accomplished with linear-to-nbest.
  
   A program that might also be useful is lattice-to-1best, which is not the same
   as lattice-to-nbest with --n=1, because it doesn't append "-1" to the utterance id.
   You can pipe the output of this into nbest-to-linear if you want the word sequences
   or something of that nature.  The program lattice-best-path takes in a lattice
   and outputs up to two archives, containing the word sequences and transition-id
   sequences.  This is there for historical reasons; the combination of lattice-to-1best
   and nbest-to-linear is cleaner and more consistent with the overall framework.
  
   \section lattices_times Times on lattices
  
   If you want the time information of the lattices explicitly (rather than having
   to count transition-ids), there is a function LatticeStateTimes (for Lattice),
   and CompactLatticeStateTimes (for CompactLattice), which will give you the time
   where each state is located (a number from 0 to the number of frames in the
   file).  Be careful that in general, the words are not synchronized with to the
   transition-ids, meaning that the transition-ids on an arc won't necessarily all
   belong to the word whose label is on that arc.  This means that the times you
   get from the lattice will (as far as the word labels are concerned) be inexact.
   The same is also true of the weights; these are also not synchronized with
   either the words or the transition-ids on a particular arc.  If you want exact
   times (e.g. for conversion to HTK lattices, or for sclite scoring), then you
   should run the program lattice-align-words.  This program only works if you
   built your system with word-position-dependent phones, and it requires certain
   command-line options to tell it which phones are in which position in the word.
   See egs/wsj/s3/run.sh for an example (search for align).  There is an
   alternative program, lattice-align-words-lexicon, that you can use if your
   system does not have word-position-dependent phones.
  
  
  */
  
  
  }