Левенштейн - сбивающий с толку алгоритм - мне потребовалось немало недоумений, когда я захотел добавить некоторую чувствительность к контексту (угадать, что может быть связано, вместо того, чтобы пытаться исправить ошибку.)
Что происходитОн заключается в том, что при построении таблицы каждая ячейка содержит количество изменений между двумя частями двух строк, представленных положением в таблице.Чтобы заполнить следующую ячейку в таблице, вы посмотрите на три возможных ячейки, из которых вы могли бы прийти, чтобы попасть туда.Вертикальный и горизонтальный подходы по своей сути являются правками, поэтому он добавляет 1 к счету.Диагональ редактируется, только если символы не совпадают.Затем вы выбираете наиболее эффективный из трех подходов, чтобы вычислить значение для текущей ячейки.
Сила этого подхода в том, что нет возврата назад, и, следовательно, он выполняется за время O (n ^ 2).Вам не нужно знать, как редактировать строку, чтобы преобразовать одну в другую, вам нужно только знать стоимость ее выполнения.(Хотя, если вы хотите знать, какие изменения необходимы, вы можете сохранить информацию о том, какой путь был выбран в функции max (), и пройти назад по цепочке, чтобы создать список изменений.)
Что касаетсяпочему ходы означают то, что они делают: каждая ячейка массива - это сравнение первых x символов первой строки с первыми y символами второй строки.Движение вправо означает получение символа из первой строки.Перемещение вниз означает взятие символа из второй строки.Выполнение любого из них является несоответствием и увеличивает ваш счетчик редактирования.Выполнение обоих одновременно означает, что вы взяли символ из обеих строк, вы увеличиваете количество правок, только если они не совпадают.
Базовый алгоритм не говорит вам как Вы попали туда, только сколько шагов потребовалось.Если вам нужно это выяснить, вы сохраняете решение, принятое на каждом этапе.