class_docstr: Класс, реализующий взвешенный конечный преобразователь,
  осуществляющий замены из заданного списка операций
  
  Аргументы:
  ----------
  alphabet : list
      алфавит
  
  operation_costs : dict or None(optional, default=None)
      словарь вида {(up,low) : cost}
  
  allow_spaces : bool(optional, default=False)
      разрешены ли элементы трансдукции, содержащие пробел
      (используется только если явно не заданы operation costs
      и они равны значению по умолчанию)
class_docstr_tok: ["\u041a\u043b\u0430\u0441\u0441",",","\u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0439","\u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u044b\u0439","\u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439","\u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c",",","\u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u044e\u0449\u0438\u0439","\u0437\u0430\u043c\u0435\u043d\u044b","\u0438\u0437","\u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e","\u0441\u043f\u0438\u0441\u043a\u0430","\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439","\u0410\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u044b",":","--","--","--","--","--","alphabet",":","list","\u0430\u043b\u0444\u0430\u0432\u0438\u0442","operation_costs",":","dict","or","None","(","optional",",","default=None",")","\u0441\u043b\u043e\u0432\u0430\u0440\u044c","\u0432\u0438\u0434\u0430","{","(","up",",","low",")",":","cost","}","allow_spaces",":","bool","(","optional",",","default=False",")","\u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u044b","\u043b\u0438","\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b","\u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0446\u0438\u0438",",","\u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435","\u043f\u0440\u043e\u0431\u0435\u043b","(","\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f","\u0442\u043e\u043b\u044c\u043a\u043e","\u0435\u0441\u043b\u0438","\u044f\u0432\u043d\u043e","\u043d\u0435","\u0437\u0430\u0434\u0430\u043d\u044b","operation","costs","\u0438","\u043e\u043d\u0438","\u0440\u0430\u0432\u043d\u044b","\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e","\u043f\u043e","\u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e",")"]
docstr: Функция, динамически заполняющая таблицу costs стоимости трансдукций,
  costs[i][j] --- минимальная стоимость трансдукции,
  переводящей first[:i] в second[:j]
  
  Аргументы:
  ----------
  first, second : string
      Верхний и нижний элементы трансдукции
  update_func : callable, float*float -> bool
      update_func(x, y) возвращает новое значение в ячейке таблицы costs,
      если старое значение --- y, а потенциально новое значение --- x
      везде update_func = min
  add_pred : callable : float*float -> bool
      add_pred(x, y) возвращает, производится ли добавление
      нового элемента p стоимости x в ячейку backtraces[i][j]
      в зависимости от значения costs[i][j]=y и текущей стоимости x
  clear_pred : callable : float*float -> bool
      clear_pred(x, y) возвращает, производится ли очистка
      ячейки backtraces[i][j] в зависимости от значения costs[i][j]=y
      и текущей стоимости x элемента p, добавляемого в эту ячейку
  
  Возвращает:
  -----------
  costs : array, dtype=float, shape=(len(first)+1, len(second)+1)
      массив, в ячейке с индексами i, j которого хранится
      минимальная стоимость трансдукции, переводящей first[:i] в second[:j]
  backtraces : array, dtype=list, shape=(len(first)+1, len(second)+1)
      массив, в ячейке с индексами i, j которого хранятся
      обратные ссылки на предыдущую ячейку в оптимальной трансдукции,
      приводящей в ячейку backtraces[i][j]
docstr_tok: ["\u0424\u0443\u043d\u043a\u0446\u0438\u044f",",","\u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438","\u0437\u0430\u043f\u043e\u043b\u043d\u044f\u044e\u0449\u0430\u044f","\u0442\u0430\u0431\u043b\u0438\u0446\u0443","costs","\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438","\u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0446\u0438\u0439",",","costs","[","i","]","[","j","]","--","-","\u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f","\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c","\u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0446\u0438\u0438",",","\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u044f\u0449\u0435\u0439","first","[",":","i","]","\u0432","second","[",":","j","]","\u0410\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u044b",":","--","--","--","--","--","first",",","second",":","string","\u0412\u0435\u0440\u0445\u043d\u0438\u0439","\u0438","\u043d\u0438\u0436\u043d\u0438\u0439","\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b","\u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0446\u0438\u0438","update_func",":","callable",",","float","*","float","-",">","bool","update_func","(","x",",","y",")","\u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442","\u043d\u043e\u0432\u043e\u0435","\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435","\u0432","\u044f\u0447\u0435\u0439\u043a\u0435","\u0442\u0430\u0431\u043b\u0438\u0446\u044b","costs",",","\u0435\u0441\u043b\u0438","\u0441\u0442\u0430\u0440\u043e\u0435","\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435","--","-","y",",","\u0430","\u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e","\u043d\u043e\u0432\u043e\u0435","\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435","--","-","x","\u0432\u0435\u0437\u0434\u0435","update_func","=","min","add_pred",":","callable",":","float","*","float","-",">","bool","add_pred","(","x",",","y",")","\u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442",",","\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f","\u043b\u0438","\u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435","\u043d\u043e\u0432\u043e\u0433\u043e","\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430","p","\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438","x","\u0432","\u044f\u0447\u0435\u0439\u043a\u0443","backtraces","[","i","]","[","j","]","\u0432","\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438","\u043e\u0442","\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f","costs","[","i","]","[","j","]","=y","\u0438","\u0442\u0435\u043a\u0443\u0449\u0435\u0439","\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438","x","clear_pred",":","callable",":","float","*","float","-",">","bool","clear_pred","(","x",",","y",")","\u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442",",","\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f","\u043b\u0438","\u043e\u0447\u0438\u0441\u0442\u043a\u0430","\u044f\u0447\u0435\u0439\u043a\u0438","backtraces","[","i","]","[","j","]","\u0432","\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438","\u043e\u0442","\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f","costs","[","i","]","[","j","]","=y","\u0438","\u0442\u0435\u043a\u0443\u0449\u0435\u0439","\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438","x","\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430","p",",","\u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0433\u043e","\u0432","\u044d\u0442\u0443","\u044f\u0447\u0435\u0439\u043a\u0443","\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442",":","--","--","--","--","--","-","costs",":","array",",","dtype=float",",","shape=","(","len","(","first",")","+1",",","len","(","second",")","+1",")","\u043c\u0430\u0441\u0441\u0438\u0432",",","\u0432","\u044f\u0447\u0435\u0439\u043a\u0435","\u0441","\u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438","i",",","j","\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e","\u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f","\u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f","\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c","\u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0446\u0438\u0438",",","\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u044f\u0449\u0435\u0439","first","[",":","i","]","\u0432","second","[",":","j","]","backtraces",":","array",",","dtype=list",",","shape=","(","len","(","first",")","+1",",","len","(","second",")","+1",")","\u043c\u0430\u0441\u0441\u0438\u0432",",","\u0432","\u044f\u0447\u0435\u0439\u043a\u0435","\u0441","\u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438","i",",","j","\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e","\u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f","\u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0435","\u0441\u0441\u044b\u043b\u043a\u0438","\u043d\u0430","\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e","\u044f\u0447\u0435\u0439\u043a\u0443","\u0432","\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439","\u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0446\u0438\u0438",",","\u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0449\u0435\u0439","\u0432","\u044f\u0447\u0435\u0439\u043a\u0443","backtraces","[","i","]","[","j","]"]
code: def _fill_levenshtein_table(
      self,
      first,
      second,
      update_func,
      add_pred,
      clear_pred,
      threshold=None,
  ):
      """
      Функция, динамически заполняющая таблицу costs стоимости трансдукций,
      costs[i][j] --- минимальная стоимость трансдукции,
      переводящей first[:i] в second[:j]
  
      Аргументы:
      ----------
      first, second : string
          Верхний и нижний элементы трансдукции
      update_func : callable, float*float -> bool
          update_func(x, y) возвращает новое значение в ячейке таблицы costs,
          если старое значение --- y, а потенциально новое значение --- x
          везде update_func = min
      add_pred : callable : float*float -> bool
          add_pred(x, y) возвращает, производится ли добавление
          нового элемента p стоимости x в ячейку backtraces[i][j]
          в зависимости от значения costs[i][j]=y и текущей стоимости x
      clear_pred : callable : float*float -> bool
          clear_pred(x, y) возвращает, производится ли очистка
          ячейки backtraces[i][j] в зависимости от значения costs[i][j]=y
          и текущей стоимости x элемента p, добавляемого в эту ячейку
  
      Возвращает:
      -----------
      costs : array, dtype=float, shape=(len(first)+1, len(second)+1)
          массив, в ячейке с индексами i, j которого хранится
          минимальная стоимость трансдукции, переводящей first[:i] в second[:j]
      backtraces : array, dtype=list, shape=(len(first)+1, len(second)+1)
          массив, в ячейке с индексами i, j которого хранятся
          обратные ссылки на предыдущую ячейку в оптимальной трансдукции,
          приводящей в ячейку backtraces[i][j]
      """
      m, n = len(first), len(second)
      # если threshold=None, то в качестве порога берётся удвоенная стоимость
      # трансдукции, отображающей символы на одинаковых позициях друг в друга
      if threshold is None:
          threshold = 0.0
          for a, b in zip(first, second):
              threshold += self.get_operation_cost(a, b)
          if m > n:
              for a in first[n:]:
                  threshold += self.get_operation_cost(a, "")
          elif m < n:
              for b in second[m:]:
                  threshold += self.get_operation_cost("", b)
          threshold *= 2
      # инициализация возвращаемых массивов
      costs = np.zeros(shape=(m + 1, n + 1), dtype=np.float64)
      costs[:] = np.inf
      backtraces = [None] * (m + 1)
      for i in range(m + 1):
          backtraces[i] = [[] for j in range(n + 1)]
      costs[0][0] = 0.0
      for i in range(m + 1):
          for i_right in range(i, min(i + self.max_up_length, m) + 1):
              up = first[i:i_right]
              max_low_length = self.max_low_lengths_by_up.get(up, -1)
              if max_low_length == -1:  # no up key in transduction
                  continue
              up_costs = self.operation_costs[up]
              for j in range(n + 1):
                  if costs[i][j] > threshold:
                      continue
                  if len(backtraces[i][j]) == 0 and i + j > 0:
                      continue  # не нашлось обратных ссылок
                  for j_right in range(
                      (j if i_right > i else j + 1),
                      min(j + max_low_length, n) + 1,
                  ):
                      low = second[j:j_right]
                      curr_cost = up_costs.get(low, np.inf)
                      old_cost = costs[i_right][j_right]
                      new_cost = costs[i][j] + curr_cost
                      if new_cost > threshold:
                          continue
                      if add_pred(new_cost, old_cost):
                          if clear_pred(new_cost, old_cost):
                              backtraces[i_right][j_right] = []
                          costs[i_right][j_right] = update_func(
                              new_cost, old_cost
                          )
                          backtraces[i_right][j_right].append((i, j))
      return costs, backtraces
  
imports: import copy
  import itertools
  import numpy
  from sortedcontainers import SortedListWithKey
  from .tabled_trie import Trie, make_trie
label_desc: Use image node_id 10 for calling the SegmentTransducer obj's underlying member method code with example usage: obj._fill_levenshtein_table(first, second, update_func, add_pred, clear_pred, threshold) and returns: costs,  backtraces