Визначення
Відстань Левенштейна, також відома як функція, алгоритм або відстань редагування Левенштейна, є мірою відмінності між двома послідовностями символів (рядків) у теорії інформації та комп'ютерній лінгвістиці. Вона обчислюється як мінімальна кількість операцій вставки, видалення та заміни, необхідних для перетворення однієї послідовності в іншу.
Математичне визначення
Відстань Левенштейна між двома рядками s та t довжини m та n відповідно визначається як:
D(s, t) = min{edit(i, j)}
де edit(i, j) — це мінімальна вартість редагування, необхідна для перетворення s[0:i] у t[0:j].
Вартість кожної операції редагування визначається матрицею вартостей:
| | Вставка | Видалення | Заміна |
|———|———|———-|———|
| Вставка | c_i | ∞ | c_r |
| Видалення | ∞ | c_d | c_r |
| Заміна | c_r | c_r | 0 |
де c_i, c_d та c_r — вартість вставки, видалення та заміни відповідно.
Обчислення
Відстань Левенштейна зазвичай обчислюється за допомогою динамічного програмування, який передбачає побудову двовимірної матриці, в якій D(i, j) містить відстань між s[0:i] та t[0:j].
Матриця вибудовується рекурсивно:
D(i, 0) = i * c_i
D(0, j) = j * c_d
Для всіх i in [1, m], j in [1, n]:
D(i, j) = min{D(i-1, j) + c_i, D(i, j-1) + c_d, D(i-1, j-1) + (s[i] != t[j]) * c_r}
Застосування
Відстань Левенштейна має численні застосування у теорії інформації та комп'ютерній лінгвістиці, зокрема:
- Визначення правопису: Вимірювання схожості між рядками для перевірки правопису та автоматичного виправлення.
- Кластеризація даних: Групування подібних рядків разом, наприклад, у текстовій класифікації.
- Пошук співпадінь: Знаходження рядків, що містять подібні підрядки, наприклад, у біоінформатиці та обробці природної мови.
- Пошук найближчих сусідів: Пошук рядків, які є найбільш подібними до заданого рядка, наприклад, у навчання з учителем.
- Машинний переклад: Автоматичне перетворення тексту з однієї мови в іншу з використанням моделей, навчених на відстані Левенштейна.
Переваги відстані Левенштейна
- Ефективно відображає ступінь відмінності між рядками.
- Інтуїтивно зрозуміла та проста в обчисленні.
- Може бути адаптована до різноманітних сценаріїв за рахунок коригування матриці вартостей.
Недоліки відстані Левенштейна
- Не враховує семантичне значення символів.
- Може бути обчислювально дорогою для великих рядків.
- Не завжди виявляє відмінності, коли символи переставлені або пропущені.
Відстань Левенштейна є широко використовуваною і ефективною мірою відмінності між рядками, яка знайшла численні застосування у теорії інформації та комп'ютерній лінгвістиці. Інтуїтивне визначення та відносно просте обчислення роблять її зручним інструментом для вимірювання схожості та визначення різниці між рядками тексту.
Часто задавані питання
1. Що таке операція редагування?
Операція редагування — це вставка, видалення або заміна символу у рядку.
2. Як мінімізувати відстань Левенштейна?
Мінімізація відстані Левенштейна передбачає знаходження послідовності операцій редагування з найменшою загальною вартістю, яка трансформує один рядок в інший.
3. Чи враховує відстань Левенштейна порядок символів?
Так, відстань Левенштейна враховує порядок символів у рядках.
4. У чому різниця між відстанню Левенштейна та відстанню Хеммінга?
Відстань Хеммінга враховує лише кількість замін, тоді як відстань Левенштейна також враховує вставки та видалення.
5. Які альтернативи відстані Левенштейна?
Існують і інші міри схожості рядків, такі як відстань Джаро-Вінклера, відстань Косинса та відстань Зондергайма.