code: def get_alignment_by_dp(
      ref_phrase: str,
      hyp_phrase: str,
      dp_data: Tuple[defaultdict, defaultdict, defaultdict, int],
  ) -> List[Tuple[str, str, float, float, int, int, int]]:
      """Get best alignment path between a reference and (possibly) misspelled phrase using n-gram mappings vocabulary.
      Args:
          ref_phrase: candidate reference phrase (letters separated by space, real space replaced by underscore)
          hyp_phrase: (possibly) misspelled phrase (letters separated by space, real space replaced by underscore)
          dp_data: n-gram mapping vocabularies used by dynamic programming
      Returns:
          list of tuples (hyp_ngram, ref_ngram, logprob, sum_logprob, joint_freq, orig_freq, misspelled_freq)
              This is best alignment path.
  
      Example:
          ref_phrase: "a n h y d r i d e"
          hyp_phrase: "a n d _ h y d r o d"
  
      Result:
              [("*", "*", 0.0, 0.0, 0, 0, 0)
               ("a n d _ h", "a n h", -2.34, -2.34, 226, 2338, 2203)
               ("y d r o", "y d r i", -2.95, -5.29, 11, 211, 1584)
               ("d", "d e", -1.99, -7.28, 60610, 444714, 2450334)
          ]
      Final path score is in path[-1][3]:  -7.28
      Note that the order of ref_phrase and hyp_phrase matters, because n-gram mappings vocabulary is not symmetrical.
      """
      joint_vocab, orig_vocab, misspelled_vocab, max_len = dp_data
      hyp_letters = ["*"] + hyp_phrase.split()
      ref_letters = ["*"] + ref_phrase.split()
      DpInfo = namedtuple(
          "DpInfo",
          [
              "hyp_pos",
              "ref_pos",
              "best_hyp_ngram_len",
              "best_ref_ngram_len",
              "score",
              "sum_score",
          ],
      )
      history = defaultdict(DpInfo)
      history[(0, 0)] = DpInfo(
          hyp_pos=0,
          ref_pos=0,
          best_hyp_ngram_len=1,
          best_ref_ngram_len=1,
          score=0.0,
          sum_score=0.0,
      )
      for hyp_pos in range(len(hyp_letters)):
          for ref_pos in range(len(ref_letters)):
              if (
                  hyp_pos == 0 and ref_pos == 0
              ):  # cell (0, 0) is already defined
                  continue
              # consider cell (hyp_pos, ref_pos) and find best path to get there
              best_hyp_ngram_len = 0
              best_ref_ngram_len = 0
              best_ngram_score = float("-inf")
              best_sum_score = float("-inf")
              # loop over paths ending on non-empty ngram mapping
              for hyp_ngram_len in range(
                  1, 1 + min(max_len, hyp_pos + 1)
              ):
                  hyp_ngram = " ".join(
                      hyp_letters[
                          (hyp_pos - hyp_ngram_len + 1) : (hyp_pos + 1)
                      ]
                  )
                  for ref_ngram_len in range(
                      1, 1 + min(max_len, ref_pos + 1)
                  ):
                      ref_ngram = " ".join(
                          ref_letters[
                              (ref_pos - ref_ngram_len + 1) : (
                                  ref_pos + 1
                              )
                          ]
                      )
                      if (ref_ngram, hyp_ngram) not in joint_vocab:
                          continue
                      joint_freq = joint_vocab[(ref_ngram, hyp_ngram)]
                      orig_freq = orig_vocab.get(ref_ngram, 1)
                      ngram_score = math.log(joint_freq / orig_freq)
                      previous_cell = (
                          hyp_pos - hyp_ngram_len,
                          ref_pos - ref_ngram_len,
                      )
                      if previous_cell not in history:
                          print(
                              "cell ", previous_cell, "does not exist"
                          )
                          continue
                      previous_score = history[previous_cell].sum_score
                      sum_score = ngram_score + previous_score
                      if sum_score > best_sum_score:
                          best_sum_score = sum_score
                          best_ngram_score = ngram_score
                          best_hyp_ngram_len = hyp_ngram_len
                          best_ref_ngram_len = ref_ngram_len
              # loop over two variants with deletion of one character
              deletion_score = -6.0
              insertion_score = -6.0
              if hyp_pos > 0:
                  previous_cell = (hyp_pos - 1, ref_pos)
                  previous_score = history[previous_cell].sum_score
                  sum_score = deletion_score + previous_score
                  if sum_score > best_sum_score:
                      best_sum_score = sum_score
                      best_ngram_score = deletion_score
                      best_hyp_ngram_len = 1
                      best_ref_ngram_len = 0
  
              if ref_pos > 0:
                  previous_cell = (hyp_pos, ref_pos - 1)
                  previous_score = history[previous_cell].sum_score
                  sum_score = insertion_score + previous_score
                  if sum_score > best_sum_score:
                      best_sum_score = sum_score
                      best_ngram_score = insertion_score
                      best_hyp_ngram_len = 0
                      best_ref_ngram_len = 1
  
              if best_hyp_ngram_len == 0 and best_ref_ngram_len == 0:
                  raise ValueError(
                      "best_hyp_ngram_len = 0 and best_ref_ngram_len = 0"
                  )
  
              # save cell to history
              history[(hyp_pos, ref_pos)] = DpInfo(
                  hyp_pos=hyp_pos,
                  ref_pos=ref_pos,
                  best_hyp_ngram_len=best_hyp_ngram_len,
                  best_ref_ngram_len=best_ref_ngram_len,
                  score=best_ngram_score,
                  sum_score=best_sum_score,
              )
      # now trace back on best path starting from last positions
      path = []
      hyp_pos = len(hyp_letters) - 1
      ref_pos = len(ref_letters) - 1
      cell_info = history[(hyp_pos, ref_pos)]
      path.append(cell_info)
      while hyp_pos > 0 or ref_pos > 0:
          hyp_pos -= cell_info.best_hyp_ngram_len
          ref_pos -= cell_info.best_ref_ngram_len
          cell_info = history[(hyp_pos, ref_pos)]
          path.append(cell_info)
  
      result = []
      for info in reversed(path):
          hyp_ngram = " ".join(
              hyp_letters[
                  (info.hyp_pos - info.best_hyp_ngram_len + 1) : (
                      info.hyp_pos + 1
                  )
              ]
          )
          ref_ngram = " ".join(
              ref_letters[
                  (info.ref_pos - info.best_ref_ngram_len + 1) : (
                      info.ref_pos + 1
                  )
              ]
          )
          joint_freq = joint_vocab.get((ref_ngram, hyp_ngram), 0)
          orig_freq = orig_vocab.get(ref_ngram, 0)
          misspelled_freq = misspelled_vocab.get(hyp_ngram, 0)
          result.append(
              (
                  hyp_ngram,
                  ref_ngram,
                  info.score,
                  info.sum_score,
                  joint_freq,
                  orig_freq,
                  misspelled_freq,
              )
          )
      return result
  
imports: import json
  import math
  import random
  import re
  from collections import defaultdict, namedtuple
  from typing import Dict, List, Set, Tuple, Union
  import numpy
  from numba import jit
label_desc: Use image node_id 4 for calling a global function with example usage: get_alignment_by_dp(ref_phrase, hyp_phrase, dp_data) and returns: result