class_docstr: A convenience class for calculating the Levenshtein edit distance.
  
  Class will cache some intermediate values to hasten the calculation. The implementation follows the implementation
  from https://github.com/mjpost/sacrebleu/blob/master/sacrebleu/metrics/lib_ter.py,
  where the most of this implementation is adapted and copied from.
  
  Args:
      reference_tokens: list of reference tokens
      op_insert: cost of insertion operation
      op_delete: cost of deletion operation
      op_substitute: cost of substitution operation
class_docstr_tok: ["A","convenience","class","for","calculating","the","Levenshtein","edit","distance",".","Class","will","cache","some","intermediate","values","to","hasten","the","calculation",".","The","implementation","follows","the","implementation","from","https",":","\/\/github.com\/mjpost\/sacrebleu\/blob\/master\/sacrebleu\/metrics\/lib_ter.py",",","where","the","most","of","this","implementation","is","adapted","and","copied","from",".","Args",":","reference_tokens",":","list","of","reference","tokens","op_insert",":","cost","of","insertion","operation","op_delete",":","cost","of","deletion","operation","op_substitute",":","cost","of","substitution","operation"]
docstr: Dynamic programming algorithm to compute the Levenhstein edit distance.
  
  Args:
      prediction_tokens: A tokenized predicted sentence.
      prediction_start: An index where a predicted sentence to be considered from.
      cache: A cached Levenshtein edit distance.
  
  Returns:
      Edit distance between the predicted sentence and the reference sentence
docstr_tok: ["Dynamic","programming","algorithm","to","compute","the","Levenhstein","edit","distance",".","Args",":","prediction_tokens",":","A","tokenized","predicted","sentence",".","prediction_start",":","An","index","where","a","predicted","sentence","to","be","considered","from",".","cache",":","A","cached","Levenshtein","edit","distance",".","Returns",":","Edit","distance","between","the","predicted","sentence","and","the","reference","sentence"]
code: def _levenshtein_edit_distance(
      self,
      prediction_tokens: List[str],
      prediction_start: int,
      cache: List[List[Tuple[int, _EditOperations]]],
  ) -> Tuple[
      int,
      List[List[Tuple[int, _EditOperations]]],
      Tuple[_EditOperations, ...],
  ]:
      """Dynamic programming algorithm to compute the Levenhstein edit distance.
  
      Args:
          prediction_tokens: A tokenized predicted sentence.
          prediction_start: An index where a predicted sentence to be considered from.
          cache: A cached Levenshtein edit distance.
  
      Returns:
          Edit distance between the predicted sentence and the reference sentence
  
      """
      prediction_len = len(prediction_tokens)
  
      empty_rows: List[List[Tuple[int, _EditOperations]]] = [
          list(self._get_empty_row(self.reference_len))
          for _ in range(prediction_len - prediction_start)
      ]
      edit_distance: List[List[Tuple[int, _EditOperations]]] = (
          cache + empty_rows
      )
      length_ratio = (
          self.reference_len / prediction_len
          if prediction_tokens
          else 1.0
      )
  
      # Ensure to not end up with zero overlaip with previous role
      beam_width = (
          math.ceil(length_ratio / 2 + _BEAM_WIDTH)
          if length_ratio / 2 > _BEAM_WIDTH
          else _BEAM_WIDTH
      )
  
      # Calculate the Levenshtein distance
      for i in range(prediction_start + 1, prediction_len + 1):
          pseudo_diag = math.floor(i * length_ratio)
          min_j = max(0, pseudo_diag - beam_width)
          max_j = (
              self.reference_len + 1
              if i == prediction_len
              else min(self.reference_len + 1, pseudo_diag + beam_width)
          )
  
          for j in range(min_j, max_j):
              if j == 0:
                  edit_distance[i][j] = (
                      edit_distance[i - 1][j][0] + self.op_delete,
                      _EditOperations.OP_DELETE,
                  )
              else:
                  if (
                      prediction_tokens[i - 1]
                      == self.reference_tokens[j - 1]
                  ):
                      cost_substitute = self.op_nothing
                      operation_substitute = _EditOperations.OP_NOTHING
                  else:
                      cost_substitute = self.op_substitute
                      operation_substitute = (
                          _EditOperations.OP_SUBSTITUTE
                      )
  
                  # Tercom prefers no-op/sub, then insertion, then deletion. But since we flip the trace and compute
                  # the alignment from the inverse, we need to swap order of insertion and  deletion in the
                  # preference.
                  # Copied from: https://github.com/mjpost/sacrebleu/blob/master/sacrebleu/metrics/ter.py.
                  operations = (
                      (
                          edit_distance[i - 1][j - 1][0]
                          + cost_substitute,
                          operation_substitute,
                      ),
                      (
                          edit_distance[i - 1][j][0] + self.op_delete,
                          _EditOperations.OP_DELETE,
                      ),
                      (
                          edit_distance[i][j - 1][0] + self.op_insert,
                          _EditOperations.OP_INSERT,
                      ),
                  )
  
                  for operation_cost, operation_name in operations:
                      if edit_distance[i][j][0] > operation_cost:
                          edit_distance[i][j] = (
                              operation_cost,
                              operation_name,
                          )
  
      trace = self._get_trace(prediction_len, edit_distance)
  
      return (
          edit_distance[-1][-1][0],
          edit_distance[len(cache) :],
          trace,
      )
  
file_path: torchmetrics/src/torchmetrics/functional/text/helper.py
imports: import math
  from enum import Enum, unique
  from typing import Dict, List, Sequence, Tuple, Union
label_desc: Use image node_id 3 for calling the _LevenshteinEditDistance obj's underlying member method code with example usage: obj._levenshtein_edit_distance(prediction_tokens, prediction_start, cache) and returns: edit_distance,  edit_distance,  trace