Я вычисляю взвешенное расстояние редактирования между двумя строками, используя небольшую модификацию расстояния Левенштейна, где я использую контекстно-определенные c вероятности операции редактирования. В отличие от стандартного Левенштейна, который рассматривает только лучшую последовательность операций редактирования, здесь меня интересует сумма затрат на возможные последовательности операций редактирования, преобразующие одну строку в другую.
Для двух строк s1 и s2, У меня есть тензор стоимости формы len(s1) × len(s2) × 3 с затратами, которые соответствуют выполнению удаления, вставки соответственно. Для простоты обе строки начинаются с технического начального символа, который обозначает пустую строку.
deletion_id = 0
insertion_id = 1
substitute_id = 2
alpha = np.zeros((len(s1), len(s2))
alpha[0, 0] = 1.0
for t, _ in enumerate(s1):
for v, _ in enumerate(s2):
if v >= 1:
alpha[t, v] += costs[t, v, insertion_id] * alpha[t, v - 1]
if t >= 1:
alpha[t, v] += costs[t, v, deletion_id] * alpha[t - 1, v]
if v >= 1 and t >= 1:
alpha[t, v] += costs[t, v, subsitute_id] * alpha[t - 1, v - 1]
Сумма вероятностей всех возможных заканчивается в alpha[len(s1) - 1, len(s2) - 1].
Вложенный для Циклы очень напоминают определение умножения матриц. Векторизация вычислений может ускорить процесс, но я не понял, как переформулировать это с помощью умножения матриц. Есть идеи?