Редагування відстані: таблиця динамічного програмування Левенштейна

Опислення "наскільки відмінними" є два рядки

Відстань Левенштейна між двома рядками – це мінімальна кількість односимвольних вставлень, видалень та замін, необхідних для перетворення одного на інший. Це дає відстань між "кошеням" і "сидзом" рівною 3: заміна k→s, заміна e→i, вставка g. Не існує більш розумної послідовності редагувань, яка робить це менше ніж за 3 кроки, і таблиця DP є доказом цього.

Повторення

Нехай dp[i][j] буде відстанню редагування між першими i символами рядка A та першими j символами рядка B. Кожна комірка повинна враховувати лише три можливі останні рухи — вставку, видалення або відповідність/заміну останніх символів:

dp[0][j] = j // j вставки для побудови B з порожнього A dp[i][0] = i // i видалень для зменшення A до порожнього dp[i][j] = dp[i-1][j-1] якщо A[i] == B[j] (вільна відповідність) dp[i][j] = 1 + min( dp[i-1][j], // видалення A[i] dp[i][j-1], // вставка B[j] dp[i-1][j-1] // заміна A[i] -> B[j] ) якщо A[i] != B[j]

dp[0][j] = j                         // j inserts to build B from empty A
dp[i][0] = i                         // i deletes to reduce A to empty

dp[i][j] = dp[i-1][j-1]                          if A[i] == B[j]   (free match)
dp[i][j] = 1 + min(
             dp[i-1][j],      // delete A[i]
             dp[i][j-1],      // insert B[j]
             dp[i-1][j-1]     // substitute A[i] -> B[j]
           )                                     if A[i] != B[j]

Відстеження фактичного вирівнювання

Число dp[n][m] само по собі лише повідомляє, скільки редагувань потрібно, але не вказує, які саме. Щоб відновити послідовність, потрібно рухатися назад, починаючи з комірки право нижче: на кожній комірці перевіряйте, з якої з до трьох сусідніх комірок вона могла походити відповідно до рекуренції, і робіть крок до тієї, яка відповідає – діагональний крок означає відповідність або заміну, вертикальний крок – видалення, горизонтальний крок – вставку. Цей простежений шлях є точно тим, що показують інструменти відмінностей як послідовність незмінних, доданих та видалених символів.

Зменшення використання пам'яті: алгоритм Гіршберга

Оскільки кожна рядок таблиці DP залежить лише від рядка над нею, обчислення значення dp[n][m] потребує лише O(min(n, m)) місця — зберігаються лише два рядки та відкинуто решту. Відновлення звичайної відповідності зазвичай виглядає як необхідність утримувати всю таблицю для зворотного просування, але алгоритм Гіршберга (1975) обходить це: він запускає одночасний перебіг лише рядків вперед від початку A та перебіг лише рядків назад від кінця A, знаходить стовпець, де оптимально зустрічаються дві половини рішень, розділяє проблему там і рекурсивно обробляє кожну половину. Результатом є повна відповідність за той самий час O(nm), але лише з використанням O(n+m) місця — стандартної техніки для вирівнювання геномних послідовностей, що містять мільйони символів, де таблиця O(nm) не поміститься в пам'яті.

Де це зустрічається

Редактори слів використовують відстань Левенштейна для ранжування кандидатів на виправлення за кількістю змін, необхідних для їх відповідності невірному слову. Інструменти командного рядка та системи контролю версій використовують пов'язану з ними найдовшу спільну підпослідовність (Longest Common Subsequence) динамічне програмування (DP), щоб обчислювати відмінності. Біоінформатика використовує зважені варіанти – алгоритми Найштейна (глобальні) та Сміта-Вотермена (локальні), де вартість заміни походить із матриці оцінювання, яка відображає ступінь біологічної подібності між двома амінокислотами або нуклеотидами, а вартість пробілу (вставки/видалення) зазвичай вища для відкриття, ніж для продовження.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Edit Distance і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.