Почему расстояние Левенштейна рассчитывается без последней вставки

Question

Сегодня я изучал расстояние Левенштейна и наткнулся на то, что кажется странным способом вычисления в хорошо известном алгоритме Вагнера-Фишера.Пожалуйста, помогите мне понять, где я ошибся.

Первая строка - Max.

Вторая - Annas.

Матрица преобразования будетследующее:

Алгоритм сообщает, что расстояние Левенштейна от Макса до Анны равно 4.

Так вот как я понимаю, это должно работать: (учитывая, чтостоимость любого действия составляет 1)

M против A -> Заменить m на a ( 1 действие на данный момент)

A против N -> Заменить a на n ( 2 действий до сих пор)

X против N -> Заменить x на n ( 3 действий на данный момент)

После этого нам просто нужно добавить буквы, оставленные a и s, которые на 2 требуют от нас больше действийВ результате получается 5 , а не 4.

Я вижу, что он идет по более простому пути, вероятно, но что это?Пожалуйста, объясните это алгоритмы логики работы.

Спасибо.

Answer 1

Вы восстановили неправильный путь.Фактически он заменяет 'm' на 'a', вставляет 'n', вставляет 'n', соответствует 'a' на 'a', а вставляет 's' ^ H ^ H ^ H^ H заменяет 'x' на 's'.Стоимость 4.

редактировать: я слишком умен, чтобы это так выразить.Существует несколько путей стоимостью 4, но все они связаны с переходом от («m», «ann») к («ma», «anna»).

еще раз отредактируйте: я думаю, что ключевой момент в том, что не все действия стоят одинаково;спички бесплатны.Вот почему сетка затрат выглядит так: ("ma", "anna") стоит 3, потому что вы можете добраться из ("m", "ann"), которая стоит 3, потратив 0 ,(«max», «annas») стоит 4, так как вы можете добраться туда («ma», «anna»), что стоит 3, потратив 1.