Відстань редагування, або відстань Левенштейна, — це мінімальна кількість одиничних правок (вставлень, видалень або замін символів), потрібних, щоб перетворити один рядок на інший.

Сітка розміром (m+1)×(n+1) зберігає відстань редагування між кожним префіксом двох рядків. Кожна клітинка дорівнює мінімуму зі своїх лівого, верхнього та діагонального сусідів плюс вартість правки, тож правий нижній кут містить повну відстань.

Діагональний хід вирівнює по одному символу з кожного рядка. Якщо символи збігаються, вартість дорівнює нулю (копіювання); якщо різняться — це заміна вартістю один.

Після заповнення таблиці ви починаєте з правого нижнього кута й рухаєтесь назад до лівого верхнього, на кожному кроці обираючи сусіда, що дав поточне значення. Так відновлюється фактична послідовність правок.

Заповнення таблиці потребує O(m·n) часу та O(m·n) пам'яті, де m і n — довжини рядків. Пам'ять можна скоротити до O(min(m,n)), якщо потрібна лише відстань.

Перевірка орфографії, нечіткий пошук, вирівнювання ДНК і білків, виявлення плагіату, виправлення OCR та інструменти diff спираються на обчислення відстані редагування.

Значення відстані єдине, але може існувати кілька оптимальних шляхів правок однакової загальної вартості. Цей зворотний хід обирає один узгоджений шлях.

Відстань Геммінга рахує лише заміни й вимагає рядків однакової довжини. Відстань Левенштейна також дозволяє вставлення та видалення, тож опрацьовує рядки різної довжини.

Так. Зважена відстань редагування призначає різні вартості вставленню, видаленню та заміні, що поширено в перевірці орфографії, де одні помилки ймовірніші за інші. Ця симуляція використовує одиничні вартості.

Коли два рядки схожі, більшість символів вирівнюються напряму, тож оптимальний шлях проходить близько до головної діагоналі лише з кількома позадіагональними кроками вставлення чи видалення.