Расстояние Левенштейна

Расстояние Левенштейна — наименьшее число правок, за которое одна строка превращается в другую. Правки бывают трёх видов: вставить знак, удалить и заменить. Между «конь» и «корень» расстояние 2: нужно вставить «р» и «е».

Как считается процент сходства

Расстояние делится на наибольшее возможное для строк такой длины, и результат вычитается из единицы. Для «kitten» и «sitting» выходит 1 − 3/7, около 57 %. Формула с числами показана под результатом.

Матрица

Включите «матрицу с пояснениями», чтобы увидеть таблицу расчёта. В каждой клетке — расстояние между началами двух строк, путь к ответу выделен. Нажмите на клетку, и под таблицей появится, из каких соседних клеток получено число и какая правка выбрана.