lattice-incremental-decoder.h

Go to the documentation of this file.

// 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 "lattice-faster-decoder.h"

namespace kaldi {
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;


  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) {
    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");

  }
  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))
        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.";
  }
};



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 TransitionModel &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_; }

  void InitializeRawLatticeChunk(
      Lattice *olat,
      unordered_map<Label, LatticeArc::StateId> *token_label2state);

  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();

  bool ProcessArcsFromChunkStartState(
      const CompactLattice &chunk_clat,
      std::unordered_map<CompactLattice::StateId, CompactLattice::StateId> *state_map);

  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);



  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 TransitionModel &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);
};


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 TransitionModel &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 TransitionModel &trans_model);

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

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

  ~LatticeIncrementalDecoderTpl();

  bool Decode(DecodableInterface *decodable);

  bool ReachedFinal() const {
    return FinalRelativeCost() != std::numeric_limits<BaseFloat>::infinity();
  }

  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_; }

  void InitDecoding();

  void AdvanceDecoding(DecodableInterface *decodable, int32 max_num_frames = -1);


  BaseFloat FinalRelativeCost() const;

  inline int32 NumFramesDecoded() const { return active_toks_.size() - 1; }

  void FinalizeDecoding();

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

  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_;
  LatticeIncrementalDeterminizer determinizer_;


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

  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);

  void UpdateLatticeDeterminization();


  KALDI_DISALLOW_COPY_AND_ASSIGN(LatticeIncrementalDecoderTpl);
};

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


} // end namespace kaldi.

#endif