FunASR/runtime/onnxruntime/third_party/kaldi/decoder/lattice-incremental-decoder.h

// decoder/lattice-incremental-decoder.h

// Copyright      2019  Zhehuai Chen, 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.

#ifndef KALDI_DECODER_LATTICE_INCREMENTAL_DECODER_H_
#define KALDI_DECODER_LATTICE_INCREMENTAL_DECODER_H_

#include "util/stl-utils.h"
#include "util/hash-list.h"
#include "fst/fstlib.h"
#include "itf/decodable-itf.h"
#include "fstext/fstext-lib.h"
#include "lat/determinize-lattice-pruned.h"
#include "lat/kaldi-lattice.h"
#include "decoder/grammar-fst.h"
#include "decoder/lattice-faster-decoder.h"

namespace kaldi {
/**
   The normal decoder, lattice-faster-decoder.h, sometimes has an issue when
   doing real-time applications with long utterances, that each time you get the
   lattice the lattice determinization can take a considerable amount of time;
   this introduces latency.  This version of the decoder spreads the work of
   lattice determinization out throughout the decoding process.

   NOTE:

   Please see https://www.danielpovey.com/files/ *TBD* .pdf for a technical
   explanation of what is going on here.

   GLOSSARY OF TERMS:
      chunk: We do the determinization on chunks of frames; these
          may coincide with the chunks on which the user calls
          AdvanceDecoding().  The basic idea is to extract chunks
          of the raw lattice and determinize them individually, but
          it gets much more complicated than that.  The chunks
          should normally be at least as long as a word (let's say,
          at least 20 frames), or the overhead of this algorithm
          might become excessive and affect RTF.

      raw lattice chunk: A chunk of raw (i.e. undeterminized) lattice
          that we will determinize.  In the paper this corresponds
          to the FST B that is described in Section 5.2.

      token_label, state_label / token-label, state-label:

          In the paper these are both referred to as `state labels` (these are
          special, large integer id's that refer to states in the undeterminized
          lattice and in the the determinized lattice); but we use two separate
          terms here, for more clarity, when referring to the undeterminized
          vs. determinized lattice.

           token_label conceptually refers to states in the
           raw lattice, but we don't materialize the entire
           raw lattice as a physical FST and and these tokens
           are actually tokens (template type Token) held by
           the decoder

           state_label when used in this code refers specifically
           to labels that identify states in the determinized
           lattice (i.e. state indexes in lat_).

       token-final state
          A state in a raw lattice or in a determinized chunk that has an arc
          entering it that has a `token-label` on it (as defined above).
          These states will have nonzero final-probs.

       redeterminized-non-splice-state, aka ns_redet:
         A redeterminized state which is not also a splice state;
         refer to the paper for explanation.  In the already-determinized
         part this means a redeterminized state which is not final.

       canonical appended lattice:  This is the appended compact lattice
         that we conceptually have (i.e. what we described in the paper).
         The difference from the "actual appended lattice" stored
         in LatticeIncrementalDeterminizer::clat_ is that the
         actual appended lattice has all its final-arcs replaced with
         final-probs, and we keep the real final-arcs "on the side" in a
         separate data structure.  The final-probs in clat_ aren't
         necessarily related to the costs on the final-arcs; instead
         they can have arbitrary values passed in by the user (e.g.
         if we want to include final-probs).  This means that the
         clat_ can be returned without modification to the user who wants
         a partially determinized result.

       final-arc:  An arc in the canonical appended CompactLattice which
         goes to a final-state.  These arcs will have `state-labels` as
         their labels.

 */
struct LatticeIncrementalDecoderConfig {
  // All the configuration values until det_opts are the same as in
  // LatticeFasterDecoder.  For clarity we repeat them rather than inheriting.
  BaseFloat beam;
  int32 max_active;
  int32 min_active;
  BaseFloat lattice_beam;
  int32 prune_interval;
  BaseFloat beam_delta; // has nothing to do with beam_ratio
  BaseFloat hash_ratio;
  BaseFloat prune_scale; // Note: we don't make this configurable on the command line,
                         // it's not a very important parameter.  It affects the
                         // algorithm that prunes the tokens as we go.
  // Most of the options inside det_opts are not actually queried by the
  // LatticeIncrementalDecoder class itself, but by the code that calls it, for
  // example in the function DecodeUtteranceLatticeIncremental.
  fst::DeterminizeLatticePhonePrunedOptions det_opts;

  // The configuration values from this point on are specific to the
  // incremental determinization.  See where they are registered for
  // explanation.
  // Caution: these are only inspected in UpdateLatticeDeterminization().
  // If you call
  int32 determinize_max_delay;
  int32 determinize_min_chunk_size;
  int32 determinize_max_active;


  LatticeIncrementalDecoderConfig()
      : beam(16.0),
        max_active(std::numeric_limits<int32>::max()),
        min_active(200),
        lattice_beam(10.0),
        prune_interval(25),
        beam_delta(0.5),
        hash_ratio(2.0),
        prune_scale(0.01),
        determinize_max_delay(60),
        determinize_min_chunk_size(20),
        determinize_max_active(200) {
    det_opts.minimize = false;
  }
  void Register(OptionsItf *opts) {
    det_opts.Register(opts);
    opts->Register("beam", &beam, "Decoding beam.  Larger->slower, more accurate.");
    opts->Register("max-active", &max_active,
                   "Decoder max active states.  Larger->slower; "
                   "more accurate");
    opts->Register("min-active", &min_active, "Decoder minimum #active states.");
    opts->Register("lattice-beam", &lattice_beam,
                   "Lattice generation beam.  Larger->slower, "
                   "and deeper lattices");
    opts->Register("prune-interval", &prune_interval,
                   "Interval (in frames) at "
                   "which to prune tokens");
    opts->Register("beam-delta", &beam_delta,
                   "Increment used in decoding-- this "
                   "parameter is obscure and relates to a speedup in the way the "
                   "max-active constraint is applied.  Larger is more accurate.");
    opts->Register("hash-ratio", &hash_ratio,
                   "Setting used in decoder to "
                   "control hash behavior");
    opts->Register("determinize-max-delay", &determinize_max_delay,
                   "Maximum frames of delay between decoding a frame and "
                   "determinizing it");
    opts->Register("determinize-min-chunk-size", &determinize_min_chunk_size,
                   "Minimum chunk size used in determinization");
    opts->Register("determinize-max-active", &determinize_max_active,
                   "Maximum number of active tokens to update determinization");

  }
  void Check() const {
    if (!(beam > 0.0 && max_active > 1 && lattice_beam > 0.0 &&
          min_active <= max_active && prune_interval > 0 &&
          beam_delta > 0.0 && hash_ratio >= 1.0 &&
          prune_scale > 0.0 && prune_scale < 1.0 &&
          determinize_max_delay > determinize_min_chunk_size &&
          determinize_min_chunk_size > 0 &&
          determinize_max_active >= 0))
        KALDI_ERR << "Invalid options given to decoder";
    /* Minimization of the chunks is not compatible withour algorithm (or at
       least, would require additional complexity to implement.) */
    if (det_opts.minimize || !det_opts.word_determinize)
      KALDI_ERR << "Invalid determinization options given to decoder.";
  }
};



/**
   This class is used inside LatticeIncrementalDecoderTpl; it handles
   some of the details of incremental determinization.
   https://www.danielpovey.com/files/ *TBD*.pdf for the paper.

*/
class LatticeIncrementalDeterminizer {
 public:
  using Label = typename LatticeArc::Label;  /* Actualy the same labels appear
                                                in both lattice and compact
                                                lattice, so we don't use the
                                                specific type all the time but
                                                just say 'Label' */
  LatticeIncrementalDeterminizer(
      const TransitionInformation &trans_model,
      const LatticeIncrementalDecoderConfig &config):
      trans_model_(trans_model), config_(config) { }

  // Resets the lattice determinization data for new utterance
  void Init();

  // Returns the current determinized lattice.
  const CompactLattice &GetDeterminizedLattice() const { return clat_; }

  /**
     Starts the process of creating a raw lattice chunk.  (Search the glossary
     for "raw lattice chunk").  This just sets up the initial states and
     redeterminized-states in the chunk.  Relates to sec. 5.2 in the paper,
     specifically the initial-state i and the redeterminized-states.

     After calling this, the caller would add the remaining arcs and states
     to `olat` and then call AcceptRawLatticeChunk() with the result.

        @param [out] olat    The lattice to be (partially) created

        @param [out] token_label2state  This function outputs to here
                a map from `token-label` to the state we created for
                it in *olat.  See glossary for `token-label`.
                The keys actually correspond to the .nextstate fields
                in the arcs in final_arcs_; values are states in `olat`.
                See the last bullet point before Sec. 5.3 in the paper.
  */
  void InitializeRawLatticeChunk(
      Lattice *olat,
      unordered_map<Label, LatticeArc::StateId> *token_label2state);

  /**
     This function accepts the raw FST (state-level lattice) corresponding to a
     single chunk of the lattice, determinizes it and appends it to this->clat_.
     Unless this was the

     Note: final-probs in `raw_fst` are treated specially: they are used to
     guide the pruned determinization, but when you call GetLattice() it will be
     -- except for pruning effects-- as if all nonzero final-probs in `raw_fst`
     were: One() if final_costs == NULL; else the value present in `final_costs`.

       @param [in] raw_fst  (Consumed destructively).  The input
                  raw (state-level) lattice.  Would correspond to the
                  FST A in the paper if first_frame == 0, and B
                  otherwise.

     @return returns false if determinization finished earlier than the beam
         or the determinized lattice was empty; true otherwise.

     NOTE: if this is not the final chunk, you will probably want to call
     SetFinalCosts() directly after calling this.
  */
  bool AcceptRawLatticeChunk(Lattice *raw_fst);

  /*
    Sets final-probs in `clat_`.  Must only be called if the final chunk
    has not been processed.  (The final chunk is whenever GetLattice() is
    called with finalize == true).

    The reason this is a separate function from AcceptRawLatticeChunk() is that
    there may be situations where a user wants to get the latice with
    final-probs in it, after previously getting it without final-probs; or
    vice versa.  By final-probs, we mean the Final() probabilities in the
    HCLG (decoding graph; this->fst_).

       @param [in] token_label2final_cost   A map from the token-label
              corresponding to Tokens active on the final frame of the
              lattice in the object, to the final-cost we want to use for
              those tokens.  If NULL, it means all Tokens should be treated
              as final with probability One().  If non-NULL, and a particular
              token-label is not a key of this map, it means that Token
              corresponded to a state that was not final in HCLG; and
              such tokens will be treated as non-final.  However,
              if this would result in no states in the lattice being final,
              we will treat all Tokens as final with probability One(),
              a warning will be printed (this should not happen.)
  */
  void SetFinalCosts(const unordered_map<Label, BaseFloat> *token_label2final_cost = NULL);

  const CompactLattice &GetLattice() { return clat_; }

  // kStateLabelOffset is what we add to state-ids in clat_ to produce labels
  // to identify them in the raw lattice chunk
  // kTokenLabelOffset is where we start allocating labels corresponding to Tokens
  // (these correspond with raw lattice states);
  enum  { kStateLabelOffset = (int)1e8,  kTokenLabelOffset = (int)2e8, kMaxTokenLabel = (int)3e8 };

 private:

  // [called from AcceptRawLatticeChunk()]
  // Gets the final costs from token-final states in the raw lattice (see
  // glossary for definition).  These final costs will be subtracted after
  // determinization; in the normal case they are `temporaries` used to guide
  // pruning.  NOTE: the index of the array is not the FST state that is final,
  // but the label on arcs entering it (these will be `token-labels`).  Each
  // token-final state will have the same label on all arcs entering it.
  //
  // `old_final_costs` is assumed to be empty at entry.
  void GetRawLatticeFinalCosts(const Lattice &raw_fst,
                               std::unordered_map<Label, BaseFloat> *old_final_costs);

  // Sets up non_final_redet_states_.  See documentation for that variable.
  void GetNonFinalRedetStates();

  /** [called from AcceptRawLatticeChunk()] Processes arcs that leave the
      start-state of `chunk_clat` (if this is not the first chunk); does nothing
      if this is the first chunk.  This includes using the `state-labels` to
      work out which states in clat_ these states correspond to, and writing
      that mapping to `state_map`.

      Also modifies forward_costs_, because it has to do a kind of reweighting
      of the clat states that are the values it puts in `state_map`, to take
      account of the probabilities on the arcs from the start state of
      chunk_clat to the states corresponding to those redeterminized-states
      (i.e. the states in clat corresponding to the values it puts in
      `*state_map`).  It also modifies arcs_in_, mostly because there
      are rare cases when we end up `merging` sets of those redeterminized-states,
      because the determinization process mapped them to a single state,
      and that means we need to reroute the arcs into members of that
      set into one single member (which will appear as a value in
      `*state_map`).

        @param [in] chunk_clat   The determinized chunk of lattice we are
                          processing
        @param [out] state_map    Mapping from states in chunk_clat to
                          the state in clat_ they correspond to.
        @return     Returns true if this is the first chunk.
  */
  bool ProcessArcsFromChunkStartState(
      const CompactLattice &chunk_clat,
      std::unordered_map<CompactLattice::StateId, CompactLattice::StateId> *state_map);

  /**
     This function, called from AcceptRawLatticeChunk(), transfers arcs from
     `chunk_clat` to clat_.  For those arcs that have `token-labels` on them,
     they don't get written to clat_ but instead are stored in the arcs_ array.

        @param [in] chunk_clat    The determinized lattice for the chunk
                         we are processing; this is the source of the arcs
                         we are moving.
        @param [in] is_first_chunk  True if this is the first chunk in the
                         utterance; it's needed because if it is, we
                         will also transfer arcs from the start state of
                         chunk_clat.
        @param [in] state_map  Map from state-ids in chunk_clat to state-ids
                         in clat_.
        @param [in] chunk_state_to_token  Map from `token-final states`
                         (see glossary) in chunk_clat, to the token-label
                         on arcs entering those states.
        @param [in] old_final_costs  Map from token-label to the
                         final-costs that were on the corresponding
                         token-final states in the undeterminized lattice;
                         these final-costs need to be removed when
                         we record the weights in final_arcs_, because
                         they were just temporary.
   */
  void TransferArcsToClat(
      const CompactLattice &chunk_clat,
      bool is_first_chunk,
      const std::unordered_map<CompactLattice::StateId, CompactLattice::StateId> &state_map,
      const std::unordered_map<CompactLattice::StateId, Label> &chunk_state_to_token,
      const std::unordered_map<Label, BaseFloat> &old_final_costs);



  /**
     Adds one arc to `clat_`.  It's like clat_.AddArc(state, arc), except
     it also modifies arcs_in_ and forward_costs_.
   */
  void AddArcToClat(CompactLattice::StateId state,
                    const CompactLatticeArc &arc);
  CompactLattice::StateId AddStateToClat();


  // Identifies token-final states in `chunk_clat`; see glossary above for
  // definition of `token-final`.  This function outputs a map from such states
  // in chunk_clat, to the `token-label` on arcs entering them.  (It is not
  // possible that the same state would have multiple arcs entering it with
  // different token-labels, or some arcs entering with one token-label and some
  // another, or be both initial and have such arcs; this is true due to how we
  // construct the raw lattice.)
  void IdentifyTokenFinalStates(
      const CompactLattice &chunk_clat,
      std::unordered_map<CompactLattice::StateId, CompactLatticeArc::Label> *token_map) const;

  // trans_model_ is needed by DeterminizeLatticePhonePrunedWrapper() which this
  // class calls.
  const TransitionInformation &trans_model_;
  // config_ is needed by DeterminizeLatticePhonePrunedWrapper() which this
  // class calls.
  const LatticeIncrementalDecoderConfig &config_;


  // Contains the set of redeterminized-states which are not final in the
  // canonical appended lattice.  Since the final ones don't physically appear
  // in clat_, this means the set of redeterminized-states which are physically
  // in clat_.  In code terms, this means set of .first elements in final_arcs,
  // plus whatever other states in clat_ are reachable from such states.
  std::unordered_set<CompactLattice::StateId> non_final_redet_states_;


  // clat_ is the appended lattice (containing all chunks processed so
  // far), except its `final-arcs` (i.e. arcs which in the canonical
  // lattice would go to final-states) are not present (they are stored
  // separately in final_arcs_) and states which in the canonical lattice
  // should have final-arcs leaving them will instead have a final-prob.
  CompactLattice clat_;


  // arcs_in_ is indexed by (state-id in clat_), and is a list of
  // arcs that come into this state, in the form (prev-state,
  // arc-index).  CAUTION: not all these input-arc records will always
  // be valid (some may be out-of-date, and may refer to an out-of-range
  // arc or an arc that does not point to this state).  But all
  // input arcs will always be listed.
  std::vector<std::vector<std::pair<CompactLattice::StateId, int32> > > arcs_in_;

  // final_arcs_ contains arcs which would appear in the canonical appended
  // lattice but for implementation reasons are not physically present in clat_.
  // These are arcs to final states in the canonical appended lattice.  The
  // .first elements are the source states in clat_ (these will all be elements
  // of non_final_redet_states_); the .nextstate elements of the arcs does not
  // contain a physical state, but contain state-labels allocated by
  // AllocateNewStateLabel().
  std::vector<CompactLatticeArc> final_arcs_;

  // forward_costs_, indexed by the state-id in clat_, stores the alpha
  // (forward) costs, i.e. the minimum cost from the start state to each state
  // in clat_.  This is relevant for pruned determinization.  The BaseFloat can
  // be thought of as the sum of a Value1() + Value2() in a LatticeWeight.
  std::vector<BaseFloat> forward_costs_;

  // temporary used in a function, kept here to avoid excessive reallocation.
  std::unordered_set<int32> temp_;

  KALDI_DISALLOW_COPY_AND_ASSIGN(LatticeIncrementalDeterminizer);
};


/** This is an extention to the "normal" lattice-generating decoder.
   See \ref lattices_generation \ref decoders_faster and \ref decoders_simple
    for more information.

   The main difference is the incremental determinization which will be
   discussed in the function GetLattice().  This means that the work of determinizatin
   isn't done all at once at the end of the file, but incrementally while decoding.
   See the comment at the top of this file for more explanation.

   The decoder is templated on the FST type and the token type.  The token type
   will normally be StdToken, but also may be BackpointerToken which is to support
   quick lookup of the current best path (see lattice-faster-online-decoder.h)

   The FST you invoke this decoder with is expected to be of type
   Fst::Fst<fst::StdArc>, a.k.a. StdFst, or GrammarFst.  If you invoke it with
   FST == StdFst and it notices that the actual FST type is
   fst::VectorFst<fst::StdArc> or fst::ConstFst<fst::StdArc>, the decoder object
   will internally cast itself to one that is templated on those more specific
   types; this is an optimization for speed.
 */
template <typename FST, typename Token = decoder::StdToken>
class LatticeIncrementalDecoderTpl {
 public:
  using Arc = typename FST::Arc;
  using Label = typename Arc::Label;
  using StateId = typename Arc::StateId;
  using Weight = typename Arc::Weight;
  using ForwardLinkT = decoder::ForwardLink<Token>;

  // Instantiate this class once for each thing you have to decode.
  // This version of the constructor does not take ownership of
  // 'fst'.
  LatticeIncrementalDecoderTpl(const FST &fst, const TransitionInformation &trans_model,
                               const LatticeIncrementalDecoderConfig &config);

  // This version of the constructor takes ownership of the fst, and will delete
  // it when this object is destroyed.
  LatticeIncrementalDecoderTpl(const LatticeIncrementalDecoderConfig &config,
                               FST *fst, const TransitionInformation &trans_model);

  void SetOptions(const LatticeIncrementalDecoderConfig &config) { config_ = config; }

  const LatticeIncrementalDecoderConfig &GetOptions() const { return config_; }

  ~LatticeIncrementalDecoderTpl();

  /**
     CAUTION: it's unlikely that you will ever want to call this function.  In a
     scenario where you have the entire file and just want to decode it, there
     is no point using this decoder.

     An example of how to do decoding together with incremental
     determinization. It decodes until there are no more frames left in the
     "decodable" object.

     In this example, config_.determinize_max_delay, config_.determinize_min_chunk_size
     and config_.determinize_max_active are used to determine the time to
     call GetLattice().

     Users will probably want to use appropriate combinations of
     AdvanceDecoding() and GetLattice() to build their application; this just
     gives you some idea how.

     The function returns true if any kind of traceback is available (not
     necessarily from a final state).
  */
  bool Decode(DecodableInterface *decodable);

  /// says whether a final-state was active on the last frame.  If it was not,
  /// the lattice (or traceback) will end with states that are not final-states.
  bool ReachedFinal() const {
    return FinalRelativeCost() != std::numeric_limits<BaseFloat>::infinity();
  }

  /**
     This decoder has no GetBestPath() function.
     If you need that functionality you should probably use lattice-incremental-online-decoder.h,
     which makes it very efficient to obtain the best path. */

  /**
     This GetLattice() function returns the lattice containing
     `num_frames_to_decode` frames; this will be all frames decoded so
     far, if you let num_frames_to_decode == NumFramesDecoded(),
     but it will generally be better to make it a few frames less than
     that to avoid the lattice having too many active states at
     the end.

     @param [in] num_frames_to_include  The number of frames that you want
                     to be included in the lattice.  Must be >=
                     NumFramesInLattice() and <= NumFramesDecoded().

     @param [in] use_final_probs  True if you want the final-probs
                    of HCLG to be included in the output lattice.  Must not
                    be set to true if num_frames_to_include !=
                    NumFramesDecoded().  Must be set to true if you have
                    previously called FinalizeDecoding().

                    (If no state was final on frame `num_frames_to_include`, the
                    final-probs won't be included regardless of
                    `use_final_probs`; you can test whether this
                    was the case by calling ReachedFinal().

      @return clat   The CompactLattice representing what has been decoded
                     up until `num_frames_to_include` (e.g., LatticeStateTimes()
                     on this lattice would return `num_frames_to_include`).

     See also UpdateLatticeDeterminizaton().  Caution: this const ref
     is only valid until the next time you call AdvanceDecoding() or
     GetLattice().

     CAUTION: the lattice may contain disconnnected states; you should
     call Connect() on the output before writing it out.
  */
  const CompactLattice &GetLattice(int32 num_frames_to_include,
                                   bool use_final_probs = false);

  /*
    Returns the number of frames in the currently-determinized part of the
    lattice which will be a number in [0, NumFramesDecoded()].  It will
    be the largest number that GetLattice() was called with, but note
    that GetLattice() may be called from UpdateLatticeDeterminization().

    Made available in case the user wants to give that same number to
    GetLattice().
   */
  int NumFramesInLattice() const { return num_frames_in_lattice_; }

  /**
     InitDecoding initializes the decoding, and should only be used if you
     intend to call AdvanceDecoding().  If you call Decode(), you don't need to
     call this.  You can also call InitDecoding if you have already decoded an
     utterance and want to start with a new utterance.
  */
  void InitDecoding();

  /**
     This will decode until there are no more frames ready in the decodable
     object.  You can keep calling it each time more frames become available
     (this is the normal pattern in a real-time/online decoding scenario).
     If max_num_frames is specified, it specifies the maximum number of frames
     the function will decode before returning.
  */
  void AdvanceDecoding(DecodableInterface *decodable, int32 max_num_frames = -1);


  /** FinalRelativeCost() serves the same purpose as ReachedFinal(), but gives
      more information.  It returns the difference between the best (final-cost
      plus cost) of any token on the final frame, and the best cost of any token
      on the final frame.  If it is infinity it means no final-states were
      present on the final frame.  It will usually be nonnegative.  If it not
      too positive (e.g. < 5 is my first guess, but this is not tested) you can
      take it as a good indication that we reached the final-state with
      reasonable likelihood. */
  BaseFloat FinalRelativeCost() const;

  /** Returns the number of frames decoded so far. */
  inline int32 NumFramesDecoded() const { return active_toks_.size() - 1; }

  /**
     Finalizes the decoding, doing an extra pruning step on the last frame
     that uses the final-probs.  May be called only once.
  */
  void FinalizeDecoding();

 protected:
  /* Some protected things are needed in LatticeIncrementalOnlineDecoderTpl. */

  /** NOTE: for parts the internal implementation that are shared with LatticeFasterDecoer,
      we have removed the comments.*/
  inline static void DeleteForwardLinks(Token *tok);
  struct TokenList {
    Token *toks;
    bool must_prune_forward_links;
    bool must_prune_tokens;
    int32 num_toks;  /* Note: you can only trust `num_toks` if must_prune_tokens
                      * == false, because it is only set in
                      * PruneTokensForFrame(). */
    TokenList()
        : toks(NULL), must_prune_forward_links(true), must_prune_tokens(true),
          num_toks(-1) {}
  };
  using Elem = typename HashList<StateId, Token *>::Elem;
  void PossiblyResizeHash(size_t num_toks);
  inline Token *FindOrAddToken(StateId state, int32 frame_plus_one,
                               BaseFloat tot_cost, Token *backpointer, bool *changed);
  void PruneForwardLinks(int32 frame_plus_one, bool *extra_costs_changed,
                         bool *links_pruned, BaseFloat delta);
  void ComputeFinalCosts(unordered_map<Token *, BaseFloat> *final_costs,
                         BaseFloat *final_relative_cost,
                         BaseFloat *final_best_cost) const;
  void PruneForwardLinksFinal();
  void PruneTokensForFrame(int32 frame_plus_one);
  void PruneActiveTokens(BaseFloat delta);
  BaseFloat GetCutoff(Elem *list_head, size_t *tok_count, BaseFloat *adaptive_beam,
                      Elem **best_elem);
  BaseFloat ProcessEmitting(DecodableInterface *decodable);
  void ProcessNonemitting(BaseFloat cost_cutoff);

  HashList<StateId, Token *> toks_;
  std::vector<TokenList> active_toks_;  // indexed by frame.
  std::vector<StateId> queue_;       // temp variable used in ProcessNonemitting,
  std::vector<BaseFloat> tmp_array_; // used in GetCutoff.
  const FST *fst_;
  bool delete_fst_;
  std::vector<BaseFloat> cost_offsets_;
  int32 num_toks_;
  bool warned_;
  bool decoding_finalized_;

  unordered_map<Token *, BaseFloat> final_costs_;
  BaseFloat final_relative_cost_;
  BaseFloat final_best_cost_;

  /***********************
      Variables below this point relate to the incremental
      determinization.
  *********************/
  LatticeIncrementalDecoderConfig config_;
  /** Much of the the incremental determinization algorithm is encapsulated in
      the determinize_ object.  */
  LatticeIncrementalDeterminizer determinizer_;


  /* Just a temporary used in a function; stored here to avoid reallocation. */
  unordered_map<Token*, StateId> temp_token_map_;

  /** num_frames_in_lattice_ is the highest `num_frames_to_include_` argument
      for any prior call to GetLattice(). */
  int32 num_frames_in_lattice_;

  // A map from Token to its token_label.  Will contain an entry for
  // each Token in active_toks_[num_frames_in_lattice_].
  unordered_map<Token*, Label> token2label_map_;

  // A temporary used in a function, kept here to avoid reallocation.
  unordered_map<Token*, Label> token2label_map_temp_;

  // we allocate a unique id for each Token
  Label next_token_label_;

  inline Label AllocateNewTokenLabel() { return next_token_label_++; }


  // There are various cleanup tasks... the the toks_ structure contains
  // singly linked lists of Token pointers, where Elem is the list type.
  // It also indexes them in a hash, indexed by state (this hash is only
  // maintained for the most recent frame).  toks_.Clear()
  // deletes them from the hash and returns the list of Elems.  The
  // function DeleteElems calls toks_.Delete(elem) for each elem in
  // the list, which returns ownership of the Elem to the toks_ structure
  // for reuse, but does not delete the Token pointer.  The Token pointers
  // are reference-counted and are ultimately deleted in PruneTokensForFrame,
  // but are also linked together on each frame by their own linked-list,
  // using the "next" pointer.  We delete them manually.
  void DeleteElems(Elem *list);

  void ClearActiveTokens();


  // Returns the number of active tokens on frame `frame`.  Can be used as part
  // of a heuristic to decide which frame to determinize until, if you are not
  // at the end of an utterance.
  int32 GetNumToksForFrame(int32 frame);

  /**
     UpdateLatticeDeterminization() ensures the work of determinization is kept
     up to date so that when you do need the lattice you can get it fast.  It
     uses the configuration values `determinize_max_delay`, `determinize_min_chunk_size`
     and `determinize_max_active`, to decide whether and when to call
     GetLattice().  You can safely call this as often as you want (e.g.  after
     each time you call AdvanceDecoding(); it won't do subtantially more work if
     it is called frequently.
  */
  void UpdateLatticeDeterminization();


  KALDI_DISALLOW_COPY_AND_ASSIGN(LatticeIncrementalDecoderTpl);
};

typedef LatticeIncrementalDecoderTpl<fst::StdFst, decoder::StdToken>
    LatticeIncrementalDecoder;


} // end namespace kaldi.

#endif