class_docstr: CTC Prefix Beam Search is based on the paper
  `First-Pass Large Vocabulary Continuous Speech Recognition using Bi-Directional Recurrent DNNs`
  by Awni Y. Hannun and al (https://arxiv.org/abs/1408.2873).
  
  The implementation keep tracks of the blank and non-blank probabilities.
  It also suppors n-gram scoring on words and SentencePiece tokens. The input
  is expected to be a log-probabilities tensor of shape [batch, time, vocab_size].
  
  Several heuristics are implemented to speed up the decoding process:
  - pruning of the beam : the beams are pruned if their score is lower than
      the best beam score minus the beam_prune_logp
  - pruning of the tokens : the tokens are pruned if their score is lower than
      the token_prune_min_logp
  - pruning of the history : the beams are pruned if they are the same over
      max_ngram history
  - skipping of the blank : the frame is skipped if the blank probability is
      higher than the blank_skip_threshold
  
  Note: The CTCPrefixBeamSearcher can be more unstable than the CTCBeamSearcher
  or the TorchAudioCTCPrefixBeamSearch searcher. Please, use it with caution
  and check the results carefully.
  
  Note: if the Acoustic Model is not trained, the Beam Search will
  take a lot of time. We do recommand to use Greedy Search during validation
  until the model is fully trained and ready to be evaluated on test sets.
  
  Note: This implementation does not provide the time alignment of the
  hypothesis. If you need it, please use the CTCBeamSearcher.
  
  Arguments
  ---------
  **kwargs
      see CTCBaseSearcher, arguments are directly passed.
  
  Example
  -------
  >>> import torch
  >>> from speechbrain.decoders import CTCPrefixBeamSearcher
  >>> probs = torch.tensor([[[0.2, 0.0, 0.8],
  ...                   [0.4, 0.0, 0.6]]])
  >>> log_probs = torch.log(probs)
  >>> lens = torch.tensor([1.0])
  >>> blank_index = 2
  >>> vocab_list = ['a', 'b', '-']
  >>> searcher = CTCPrefixBeamSearcher(blank_index=blank_index, vocab_list=vocab_list)
  >>> hyps = searcher(probs, lens)
class_docstr_tok: ["CTC","Prefix","Beam","Search","is","based","on","the","paper","`","First-Pass","Large","Vocabulary","Continuous","Speech","Recognition","using","Bi-Directional","Recurrent","DNNs","`","by","Awni","Y.","Hannun","and","al","(","https",":","\/\/arxiv.org\/abs\/1408.2873",")",".","The","implementation","keep","tracks","of","the","blank","and","non-blank","probabilities",".","It","also","suppors","n-gram","scoring","on","words","and","SentencePiece","tokens",".","The","input","is","expected","to","be","a","log-probabilities","tensor","of","shape","[","batch",",","time",",","vocab_size","]",".","Several","heuristics","are","implemented","to","speed","up","the","decoding","process",":","-","pruning","of","the","beam",":","the","beams","are","pruned","if","their","score","is","lower","than","the","best","beam","score","minus","the","beam_prune_logp","-","pruning","of","the","tokens",":","the","tokens","are","pruned","if","their","score","is","lower","than","the","token_prune_min_logp","-","pruning","of","the","history",":","the","beams","are","pruned","if","they","are","the","same","over","max_ngram","history","-","skipping","of","the","blank",":","the","frame","is","skipped","if","the","blank","probability","is","higher","than","the","blank_skip_threshold","Note",":","The","CTCPrefixBeamSearcher","can","be","more","unstable","than","the","CTCBeamSearcher","or","the","TorchAudioCTCPrefixBeamSearch","searcher",".","Please",",","use","it","with","caution","and","check","the","results","carefully",".","Note",":","if","the","Acoustic","Model","is","not","trained",",","the","Beam","Search","will","take","a","lot","of","time",".","We","do","recommand","to","use","Greedy","Search","during","validation","until","the","model","is","fully","trained","and","ready","to","be","evaluated","on","test","sets",".","Note",":","This","implementation","does","not","provide","the","time","alignment","of","the","hypothesis",".","If","you","need","it",",","please","use","the","CTCBeamSearcher",".","Arguments","--","--","--","--","-","*","*","kwargs","see","CTCBaseSearcher",",","arguments","are","directly","passed",".","Example","--","--","--","-",">",">",">","import","torch",">",">",">","from","speechbrain.decoders","import","CTCPrefixBeamSearcher",">",">",">","probs","=","torch.tensor","(","[","[","[","0.2",",","0.0",",","0.8","]",",","...","[","0.4",",","0.0",",","0.6","]","]","]",")",">",">",">","log_probs","=","torch.log","(","probs",")",">",">",">","lens","=","torch.tensor","(","[","1.0","]",")",">",">",">","blank_index","=","2",">",">",">","vocab_list","=","[","'","a","'",",","'","b","'",",","'-","'","]",">",">",">","searcher","=","CTCPrefixBeamSearcher","(","blank_index=blank_index",",","vocab_list=vocab_list",")",">",">",">","hyps","=","searcher","(","probs",",","lens",")"]
docstr: Perform CTC Prefix Beam Search decoding.
  
  If self.lm is not None, the language model scores are computed and added to the CTC scores.
  
  Arguments
  ---------
  log_probs : torch.Tensor
      The log probabilities of the CTC input.
      Shape: (seq_length, vocab_size)
  wav_len : int
      The length of the input sequence.
  beams : list
      The list of CTCBeam objects.
  cached_lm_scores : dict
      The cached language model scores.
  cached_p_lm_scores : dict
      The cached prefix language model scores.
  processed_frames : int
      The start frame of the current decoding step. (default: 0)
  
  Returns
  -------
  beams : list
      The list of CTCBeam objects.
docstr_tok: ["Perform","CTC","Prefix","Beam","Search","decoding",".","If","self.lm","is","not","None",",","the","language","model","scores","are","computed","and","added","to","the","CTC","scores",".","Arguments","--","--","--","--","-","log_probs",":","torch.Tensor","The","log","probabilities","of","the","CTC","input",".","Shape",":","(","seq_length",",","vocab_size",")","wav_len",":","int","The","length","of","the","input","sequence",".","beams",":","list","The","list","of","CTCBeam","objects",".","cached_lm_scores",":","dict","The","cached","language","model","scores",".","cached_p_lm_scores",":","dict","The","cached","prefix","language","model","scores",".","processed_frames",":","int","The","start","frame","of","the","current","decoding","step",".","(","default",":","0",")","Returns","--","--","--","-","beams",":","list","The","list","of","CTCBeam","objects","."]
code: def partial_decoding(
      self,
      log_probs: torch.Tensor,
      wav_len: int,
      beams: List[CTCBeam],
      cached_lm_scores: dict,
      cached_p_lm_scores: dict,
      processed_frames: int = 0,
  ) -> List[CTCBeam]:
      """Perform CTC Prefix Beam Search decoding.
  
      If self.lm is not None, the language model scores are computed and added to the CTC scores.
  
      Arguments
      ---------
      log_probs : torch.Tensor
          The log probabilities of the CTC input.
          Shape: (seq_length, vocab_size)
      wav_len : int
          The length of the input sequence.
      beams : list
          The list of CTCBeam objects.
      cached_lm_scores : dict
          The cached language model scores.
      cached_p_lm_scores : dict
          The cached prefix language model scores.
      processed_frames : int
          The start frame of the current decoding step. (default: 0)
  
      Returns
      -------
      beams : list
          The list of CTCBeam objects.
      """
      # select only the valid frames, i.e., the frames that are not padded
      log_probs = log_probs[:wav_len]
  
      for frame_index, logit_col in enumerate(
          log_probs, start=processed_frames
      ):
          # skip the frame if the blank probability is higher than the threshold
          if logit_col[self.blank_index] > self.blank_skip_threshold:
              continue
  
          # get the tokens with the highest probability
          max_index = logit_col.argmax()
          tokens_index_list = set(
              np.where(logit_col > self.token_prune_min_logp)[0]
          ) | {max_index}
  
          curr_beams = beams.copy()
  
          # select tokens that are in the vocab
          # this is useful if the logit vocab_size is larger than the vocab_list
          tokens_index_list = tokens_index_list & set(
              range(len(self.vocab_list))
          )
  
          for token_index in tokens_index_list:
              p_token = logit_col[token_index]
              token = self.vocab_list[token_index]
  
              for beam in curr_beams:
                  p_b, p_nb = beam.p_b, beam.p_nb
  
                  # blank case
                  if token_index == self.blank_index:
                      beam.n_p_b = np.logaddexp(
                          beam.n_p_b, beam.score_ctc + p_token
                      )
                      continue
  
                  if token == beam.last_token:
                      beam.n_p_nb = np.logaddexp(
                          beam.n_p_nb, p_nb + p_token
                      )
  
                  new_text = beam.text + token
  
                  new_beam = self._get_new_beam(
                      frame_index,
                      new_text,
                      token,
                      token_index,
                      beams,
                      p=p_token,
                      previous_beam=beam,
                  )
  
                  n_p_nb = new_beam.n_p_nb
  
                  if (
                      token_index == beam.last_token_index
                      and p_b > -math.inf
                  ):
                      n_p_nb = np.logaddexp(n_p_nb, p_b + p_token)
                  elif token_index != beam.last_token_index:
                      n_p_nb = np.logaddexp(
                          n_p_nb, beam.score_ctc + p_token
                      )
                  new_beam.n_p_nb = n_p_nb
  
          # update the CTC probabilities
          for beam in beams:
              beam.step()
  
          # kenLM scores
          scored_beams = self.get_lm_beams(
              beams,
              cached_lm_scores,
              cached_p_lm_scores,
          )
  
          # remove beams outliers
          max_score = max([b.lm_score for b in scored_beams])
          scored_beams = [
              b
              for b in scored_beams
              if b.lm_score >= max_score + self.beam_prune_logp
          ]
          trimmed_beams = self.sort_beams(scored_beams)
  
          if self.prune_history:
              lm_order = 1 if self.lm is None else self.lm.order
              beams = self._prune_history(
                  trimmed_beams, lm_order=lm_order
              )
          else:
              beams = [CTCBeam.from_lm_beam(b) for b in trimmed_beams]
  
      return beams
  
imports: from itertools import groupby
  from speechbrain.dataio.dataio import length_to_mask
  import math
  import dataclasses
  import numpy
  import heapq
  import logging
  import torch
  import warnings
  from typing import Dict, List, Optional, Union, Any, Tuple
label_desc: Use image node_id 4 for calling the CTCPrefixBeamSearcher obj's underlying member method code with example usage: obj.partial_decoding(log_probs, wav_len, beams, cached_lm_scores, cached_p_lm_scores, processed_frames) and returns: beams