какие изменения следует внести в области редактирования расстояния algo, если имеются разные веса для добавления/удаления или замены

Question

P.S. если существует различный вес для добавления, замены и удаления. Тогда есть какой-нибудь алгоритм, который мог бы мне помочь.

Или какие модификации требуются в алгоритме Вагнера-Фишера, чтобы минимизировать расстояние редактирования, если веса для добавления/удаления и замены различны?

Answer 1

Наиболее оптимален я знаю на сегодняшний день является Levenshtein, вы также можете взглянуть на this publication. Надеется, что это помогает :)

Answer 2

Не знает, если вы знаете, но так как в каждой строке редактирования расстояния PD зависит только предыдущий, вы можете сохранить только две последние строки. Таким образом, вы можете достичь сложности O (n), а не O (n^2) в наивной реализации.

Пример в Python (предполагая, что стоимость 2 для замены, 3 для добавления и 5 для удаления):

def levenshtein(s1, s2): 
    A = [0]*(len(s2)+1) 
    B = range(len(s2)+1) 
    for i, c1 in enumerate(s1, 1): 
     A[0] = i 
     for j, c2 in enumerate(s2, 1): 
      if c1 == c2: 
       A[j] = B[j-1] 
      else: 
       A[j] = min(B[j-1]+2, A[j-1]+3, B[j]+5) 
     A,B = B,A 

    return B[len(s2)] 

print levenshtein('kitten', 'sitting')