Ві́дстань Левенште́йна — міра відмінності між двома рядками або, ширше, між двома скінченними послідовностями символів. У класичному варіанті вона дорівнює найменшій кількості односимвольних операцій вставки, вилучення та заміни, потрібних для перетворення однієї послідовності на іншу; вартість кожної з цих операцій вважають рівною 1.В. І. Левенштейн. «Двоичные коды с исправлением выпадений, вставок и замещений символов» // Доклады Академии наук СССР. — 1965. — Т. 163, № 4. — С. 845–848. Англійський переклад: V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady, 10(8), 707–710, 1966. Math-Net.
Назва походить від імені радянського математика Володимира Левенштейна, який увів цю міру 1965 року в дослідженні кодів, здатних виправляти помилки вставки та вилучення. Відстань Левенштейна є одним із класичних різновидів відстані редагування. Термін «відстань редагування» вживають і в ширшому значенні — для сімейства моделей, у яких можна змінювати набір дозволених операцій або їхню вартість.Gonzalo Navarro. “A guided tour to approximate string matching” // ACM Computing Surveys. — 2001. — Vol. 33, No. 1. — P. 31–88. doi:10.1145/375360.375365.
Відстань Левенштейна застосовують у пошуку приблизних збігів, корекції орфографії, обробці природної мови, зіставленні записів, оцінюванні результатів розпізнавання тексту й мовлення та порівнянні біологічних послідовностей.
Визначення
Нехай
і
— дві послідовності. Позначимо через відстань Левенштейна між префіксом та префіксом .
Для порожньої послідовності маємо крайові умови
Для і :
де
Три складники відповідають відповідно вилученню символу з вихідної послідовності, вставці символу з цільової послідовності та збігу або заміні останнього символу двох префіксів.Robert A. Wagner, Michael J. Fischer. “The String-to-String Correction Problem” // Journal of the ACM. — 1974. — Vol. 21, No. 1. — P. 168–173. doi:10.1145/321796.321811.
Шукана відстань між повними послідовностями дорівнює .
Приклад
Щоб перетворити слово «небо» на «треба», достатньо трьох операцій:
небо → неба — замінити о на а; неба → реба — замінити н на р; реба → треба — вставити т на початку.
Менш ніж трьома операціями таке перетворення здійснити неможливо, отже
Властивості та межі
За одиничної вартості вставки, вилучення та заміни відстань Левенштейна є метрикою: вона невід'ємна, дорівнює нулю тоді й лише тоді, коли послідовності однакові, є симетричною та задовольняє нерівність трикутника.
Для послідовностей довжин і виконується
Нижня межа випливає з того, що одна вставка або одне вилучення змінює довжину лише на одиницю. Верхню межу можна отримати, замінивши символи в спільній за довжиною частині, а потім вставивши або вилучивши решту символів.
Якщо послідовності мають однакову довжину, відстань Гемінга є верхньою межею для відстані Левенштейна:
Рівність виконується не завжди, оскільки відстань Левенштейна, на відміну від відстані Гемінга, дозволяє також вставки й вилучення.
Якщо заміни заборонено й дозволено лише вставки та вилучення, мінімальна кількість операцій пов'язана з довжиною найдовшої спільної підпослідовності:
Цей зв'язок досліджувався, зокрема, в українській фаховій літературі разом із задачею оптимального зіставлення рядків.Медведєв М. Г. «Відстань Левенштейна та пов'язані з нею задачі» // Наукові записки НаУКМА. Комп'ютерні науки. — 2000. — Т. 18. — С. 33–37. eKMAIR, НаУКМА.
Обчислення
Динамічне програмування
Класичний спосіб обчислення використовує динамічне програмування. У таблиці розміру зберігають відстані між усіма парами префіксів.
function LevenshteinDistance(s[1..m], t[1..n]): create d[0..m, 0..n]
for i = 0..m: d[i,0] = i
for j = 0..n: d[0,j] = j
for i = 1..m: for j = 1..n: if s[i] = t[j]: cost = 0 else: cost = 1
d[i,j] = minimum( d[i-1,j] + 1, // вилучення s[i] d[i,j-1] + 1, // вставка t[j] d[i-1,j-1] + cost // збіг або заміна )
return d[m,n]
Інваріант алгоритму полягає в тому, що d[i,j] містить мінімальну кількість операцій, потрібних для перетворення перших i символів s на перші j символів t.
Заповнення всієї таблиці потребує часу та пам'яті.
Оптимізація пам'яті
Якщо потрібно визначити лише значення відстані, повну таблицю зберігати не обов'язково: для обчислення нового рядка достатньо попереднього рядка та вже обчисленої частини поточного. Якщо зберігати дані вздовж коротшої послідовності, робочу пам'ять можна зменшити до .Esko Ukkonen. “Algorithms for approximate string matching” // Information and Control. — 1985. — Vol. 64, No. 1–3. — P. 100–118. doi:10.1016/S0019-9958(85)80046-2.
Відновлення послідовності редагувань
Якщо повну таблицю збережено, одну оптимальну послідовність операцій можна відновити зворотним проходом від клітинки до клітинок-попередників, які дають поточне мінімальне значення. Для однієї пари рядків може існувати кілька різних оптимальних шляхів з однаковою сумарною вартістю.
Саме обчислення матриці не означає автоматичного знаходження «всіх шляхів»: щоб перерахувати всі оптимальні послідовності редагувань, потрібно окремо пройти всі рівноцінні переходи між клітинками, що в загальному випадку може утворити багато варіантів.
Алгоритми, залежні від відстані
Коли фактична відстань між рядками мала порівняно з їхньою довжиною або наперед задано допустимий поріг, немає потреби обчислювати всі клітинки матриці. Ukkonen запропонував точні алгоритми, які обмежують обчислення релевантною смугою таблиці та залежать від величини допустимої або фактичної відстані.
Термін approximate string matching у цьому контексті означає пошук рядків із дозволеною кількістю відмінностей, а не обов'язково наближене чисельне обчислення самої відстані.
Біт-паралельні методи
Gene Myers 1999 року описав біт-векторний алгоритм приблизного зіставлення, у якому кілька станів динамічного програмування кодують у бітах машинного слова й оновлюють за допомогою бітових операцій.Gene Myers. “A fast bit-vector algorithm for approximate string matching based on dynamic programming” // Journal of the ACM. — 1999. — Vol. 46, No. 3. — P. 395–415. doi:10.1145/316542.316550.
Варіанти та пов'язані відстані
Зважена відстань редагування
У зваженій відстані редагування операції вставки, вилучення та заміни можуть мати різну вартість, а ціна заміни може залежати від конкретної пари символів. Довільний вибір вартостей не гарантує збереження всіх властивостей метрики: наприклад, асиметричні вартості можуть порушити симетрію.
Відстань Дамерау — Левенштейна додає до базових операцій транспозицію двох сусідніх символів.
Нормалізація та подібність
Необроблена відстань потенційно зростає зі збільшенням довжини рядків, тому в прикладних задачах використовують нормалізовані варіанти. Єдиного універсального означення «нормалізованої відстані Левенштейна» немає.
Один із поширених варіантів:
а відповідну подібність можна задати як
Для інших схем нормалізації властивості можуть відрізнятися; тому конкретну формулу слід указувати разом із результатом.
Застосування
Обробка україномовного тексту
У задачах обробки українського тексту відстань Левенштейна може бути складовою алгоритмів пошуку, нормалізації та добору кандидатів. У дослідженні Львівської політехніки, присвяченому автоматичному пошуку ключових слів в україномовному контенті, стемінг слів української мови поєднували з відстанню Левенштейна; експеримент проводили на 100 наукових публікаціях технічного спрямування.Бісікало О. В., Висоцька В. А. «Експериментальне дослідження пошуку значущих ключових слів україномовного контенту» // Вісник Національного університету «Львівська політехніка». Інформаційні системи та мережі. — 2015. — № 829. — С. 255–272. Інституційний репозитарій Львівської політехніки.
Цей приклад також показує, що сама символьна відстань не замінює мовноспецифічного опрацювання: для української мови в прикладних системах можуть бути важливими морфологія, стемінг, словники та контекст.
Прізвища, топоніми та дедуплікація
У базах даних відстань Левенштейна застосовують як один зі способів порівняння рядкових полів, що містять орфографічні варіанти або помилки введення. Однак для українських прізвищ і топонімів фонетична подібність не завжди добре відображається простим числом символьних редагувань.
У роботі дослідників Київського університету імені Бориса Грінченка та співавторів порівнювали підходи до дедуплікації українських прізвищ, назв лікарських засобів і топонімів. Автори прямо порівнюють фонетичний алгоритм з відстанями Левенштейна, Дамерау — Левенштейна, Гемінга, Джаро — Вінклера та іншими методами й наголошують на специфіці української вимови та правопису.Zhengbing Hu, Volodymyr Buriachok, V. Y. Sokolov. “Deduplication Method for Ukrainian Last Names, Medicinal Names, and Toponyms Based on Metaphone Phonetic Algorithm” // Advances in Intelligent Systems and Computing. — 2021. — Vol. 1247. — P. 518–533. doi:10.1007/978-3-030-55506-1_47. Інституційний репозитарій Київського університету імені Бориса Грінченка.
Отже, мала орфографічна відстань є корисною ознакою для нечіткого зіставлення, але не є тотожною фонетичній або семантичній тотожності записів.
Транслітерація та зіставлення імен
Для українських власних назв додаткову складність створює транслітерація кирилиці латиницею. В Україні чинна офіційна таблиця транслітерації українського алфавіту латиницею, затверджена постановою Кабінету Міністрів України № 55 від 27 січня 2010 року.Кабінет Міністрів України. «Про впорядкування транслітерації українського алфавіту латиницею»: постанова від 27.01.2010 № 55. Законодавство України, Верховна Рада України.
У реальних корпусах і новинних даних одна й та сама особа може водночас бути представлена за різними історичними або міжнародними схемами транслітерації, мати варіант написання чи друкарську помилку. У дослідженнях розв'язання іменованих сутностей для даних, пов'язаних з Україною, відстань Дамерау — Левенштейна використовували для обробки невеликих відмінностей між такими записами.“Named Entity Resolution Methods” у дослідженні корпусу RUWA, CEUR Workshop Proceedings. CEUR-WS.
При цьому відстань редагування не є заміною офіційної транслітерації: вона лише вимірює відмінність між уже поданими рядками.
Назви лікарських засобів
Схожість написання назв лікарських засобів є одним із прикладних випадків, де мала відстань між рядками може мати практичне значення. В українському дослідженні назв препаратів із Державного реєстру лікарських засобів України було проаналізовано 5638 назв; для всіх пар обчислювали відстань Левенштейна, а пари з відстанню 1 або 2 розглядали як потенційно схожі для подальшого аналізу ризику плутанини та застосування Tall Man Lettering.Решетар Є. М. Дослідження подібності назв лікарських засобів та застосування Tall Man Lettering: кваліфікаційна робота. Ужгородський національний університет. Репозитарій УжНУ.
Такий підхід є прикладом застосування відстані як інструменту попереднього виявлення схожих назв, а не самостійного доказу того, що конкретна пара назв буде сплутана користувачами.
OCR і розпізнавання рядкових об'єктів
Під час оптичного розпізнавання символів результат можна порівнювати з еталонним текстом або з результатами інших кадрів за допомогою відстані редагування. В українському науково-технічному журналі 2024 року описано метод інтеграції результатів розпізнавання рядкових об'єктів у відеопотоках, який поєднує динамічне програмування з узагальненою відстанню Левенштейна; експерименти проводили на наборі MIDV-500.Xia Guanxiang, В'ячеслав Ковтун. «Методи розпізнавання рядкових об'єктів у відео потоках реального часу» // Вимірювальна та обчислювальна техніка в технологічних процесах. — 2024. — № 4. — С. 338–347. doi:10.31891/2219-9365-2024-80-41.
Для оцінювання OCR та автоматичного розпізнавання мовлення часто використовують похідні показники CER і WER. Їх обчислюють із кількості замін , вилучень та вставок у оптимальному редагувальному вирівнюванні: