UK 
EnglishТипова
Polski📝 Відстань редагування — таблиця ДП Левенштейна
Заповнюйте таблицю динамічного програмування Левенштейна клітинка за клітинкою, тоді простежте найдешевший шлях вставок, видалень і замін, що перетворює один рядок на інший.
Про відстань редагування (Левенштейна)
Відстань редагування, формалізована Володимиром Левенштейном 1965 року, вимірює мінімальну кількість односимвольних вставок, видалень і замін, потрібних, щоб перетворити один рядок на інший. Вона обчислюється за O(mn) часу та O(mn) пам'яті (або O(min(m,n)) пам'яті за допомогою пооднорядкового трюку) методом динамічного програмування: заповнюється таблиця (m+1)×(n+1), де кожна клітинка d[i][j] містить відстань редагування між першими i символами джерела та першими j символами цілі. Алгоритм є основою для перевірки орфографії, вирівнювання послідовностей ДНК (де заміни моделюють мутації) та нечіткого пошуку рядків у пошукових системах.
Симуляція заповнює таблицю ДП клітинка за клітинкою з регульованою швидкістю, кольорово позначаючи кожну операцію. Після завершення зворотний прохід підсвічує оптимальний шлях вирівнювання через матрицю, показуючи, які саме вставки, видалення та заміни було обрано.
Часті запитання
Яке рекурентне співвідношення використовується для заповнення матриці Левенштейна?
Кожна клітинка заповнюється так: d[i][j] = d[i−1][j−1], якщо s[i] = t[j] (символи збігаються, без витрат); інакше d[i][j] = 1 + min(d[i−1][j], d[i][j−1], d[i−1][j−1]) для видалення, вставки та заміни відповідно. Перший рядок і стовпець ініціалізуються значеннями 0…m та 0…n, оскільки перетворення порожнього рядка вимагає i вставок або j видалень.
Яка різниця між відстанню редагування та відстанню Гемінга?
Відстань Гемінга рахує лише заміни між двома рядками однакової довжини. Відстань редагування є суворо більш загальною: вона дозволяє вставки й видалення, тому застосовна до рядків різної довжини. Для рядків однакової довжини без вставок/видалень відстані Гемінга та Левенштейна збігаються. Відстань Гемінга обчислюється за O(n), тоді як Левенштейна — за O(mn), що відображає її більшу виразність.
Як відстань редагування пов'язана з найдовшою спільною підпослідовністю (LCS)?
Якщо дозволені лише вставки й видалення (без замін), то відстань редагування = m + n − 2·LCS(s, t): два зайві символи для кожної пари, узгодженої в LCS, скасовують одне видалення й одну вставку. Левенштейн додає заміни (вартістю 1) як скорочення, що замінює видалення + вставку (вартістю 2), коли це вигідно. Таблиці ДП мають однакову структуру, відрізняючись лише членом вартості заміни.
Як зворотний прохід відновлює оптимальне вирівнювання з таблиці ДП?
Починаючи з d[m][n], алгоритм переходить до тієї клітинки-попередника (по діагоналі для збігу/заміни, ліворуч для вставки, вгору для видалення), яка має найменше значення. Нічия може розв'язуватися довільно; кожен вибір дає інше, але однаково оптимальне вирівнювання. Послідовність кроків, прочитана у зворотному порядку, дає сценарій редагування (запис CIGAR у нотації біоінформатики).
Що таке відстань Дамерау–Левенштейна?
Відстань Дамерау–Левенштейна додає транспозицію двох сусідніх символів як четверту елементарну операцію вартістю 1. Це краще підходить для моделювання людських помилок набору тексту, де транспозиції становлять до 80% описок. Для її обчислення потрібне складніше ДП з O(|Σ|) додатковими масивами для відстеження останньої позиції появи кожного символу, що дає O(mn) часу, але з більшою константою.
Чи можна обчислити відстань редагування швидше, ніж за O(mn)?
Для довільних рядків найкращий відомий алгоритм працює за O(mn/log n) із застосуванням паралелізму на рівні слів (алгоритм Масека–Патерсона та бітово-векторні варіанти). Для рядків, які «майже рівні» (відстань k ≪ n), існує алгоритм Укконена за O(kn), що заповнює лише діагональну смугу шириною 2k+1 у матриці. На практиці бітово-паралельні варіанти використовуються в таких інструментах, як agrep та утиліта diff у Unix.
Як відстань редагування використовується в біоінформатиці?
У вирівнюванні послідовностей алфавітом є нуклеотиди A, C, G, T, а матриця замін (наприклад, BLOSUM62 для білків) замінює рівномірний штраф вартістю 1. Алгоритм Сміта–Вотермана — це варіант локальної відстані редагування, що знаходить підпослідовність із найвищою оцінкою вирівнювання, виявляючи консервативні функціональні домени. Глобальне вирівнювання використовує алгоритм Нідлмана–Вунша, який математично ідентичний Левенштейну з афінними штрафами за пропуски.
Яка відстань редагування між словами «kitten» і «sitting»?
Відстань редагування дорівнює 3: заміна 'k'→'s' (kitten→sitten), заміна 'e'→'i' (sitten→sittin) і вставка 'g' наприкінці (sittin→sitting). Це класичний підручниковий приклад для ілюстрації алгоритму, з таблицею ДП розміром 7×8, яку часто показують на курсах з алгоритмів.
Як засоби перевірки орфографії використовують відстань редагування?
Засіб перевірки орфографії обчислює відстань редагування між помилковим словом і кожним словом у словнику (або скороченому списку кандидатів із BK-дерева), а тоді пропонує слова на відстані 1 або 2 як виправлення. BK-дерева використовують нерівність трикутника відстані редагування для скорочення пошуку у словнику, зменшуючи середню кількість порівнянь з O(|словника|) до O(|словника|0.2) на практиці.
Чи задовольняє відстань редагування нерівність трикутника?
Так — відстань редагування є справжньою метрикою: вона невід'ємна, симетрична, дорівнює нулю тоді й лише тоді, коли рядки ідентичні, і задовольняє d(s, u) ≤ d(s, t) + d(t, u). Ця властивість метрики дає змогу BK-деревам і VP-деревам індексувати рядки для швидкого наближеного пошуку найближчих сусідів, що лежить в основі пошуку подібності при виправленні орфографії та в базах даних ДНК.