Расстояние Левенштейна

Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — это метрика, измеряющая различие между двумя последовательностями символов (строками). Она определяется как минимальное количество односимвольных операций вставки, удаления и замены, необходимых для преобразования одной строки в другую. Понятие введено советским математиком Владимиром Иосифовичем Левенштейном в 1965 году в контексте теории кодирования и теории информации.

Определение и формальное описание

Расстояние Левенштейна между двумя строками \( a \) и \( b \) (длиной \( |a| \) и \( |b| \) соответственно) задаётся рекуррентной формулой:

\[ \operatorname{lev}(a, b) = \begin{cases} |a| & \text{если } |b| = 0, \\ |b| & \text{если } |a| = 0, \\ \operatorname{lev}(\operatorname{tail}(a), \operatorname{tail}(b)) & \text{если } a[0] = b[0], \\ 1 + \min \begin{cases} \operatorname{lev}(\operatorname{tail}(a), b) \\ \operatorname{lev}(a, \operatorname{tail}(b)) \\ \operatorname{lev}(\operatorname{tail}(a), \operatorname{tail}(b)) \end{cases} & \text{иначе}, \end{cases} \]

где \(\operatorname{tail}(x)\) — строка \( x \) без первого символа. Первый элемент минимума соответствует удалению символа из \( a \), второй — вставке символа в \( a \), третий — замене символа.

Допустимые операции

В классическом варианте Левенштейна разрешены три операции, каждая со стоимостью 1:

• Вставка символа (например, «кот» → «коот»).
• Удаление символа (например, «кот» → «кт»).
• Замена символа (например, «кот» → «кит»).

Существуют модификации, где операциям присваиваются разные веса (например, замена может стоить 2, если рассматривается как удаление + вставка), что приводит к расстоянию Дамерау — Левенштейна, которое дополнительно учитывает перестановку соседних символов.

История

В 1965 году Владимир Левенштейн, работавший в Институте прикладной математики АН СССР, опубликовал статью «Двоичные коды с исправлением выпадений, вставок и замещений символов». В ней он исследовал проблему исправления ошибок в двоичных последовательностях и впервые предложил метрику, позже названную его именем. Первоначально расстояние использовалось в теории кодирования для оценки минимального количества ошибок, которое может исправить код.

В 1970-х годах алгоритм вычисления расстояния был независимо переоткрыт и популяризирован в западной литературе, в частности, Робертом Вагнером и Майклом Фишером, которые в 1974 году опубликовали динамический алгоритм (алгоритм Вагнера — Фишера) с временной сложностью \( O(|a| \cdot |b|) \).

Алгоритмы вычисления

Классический алгоритм Вагнера — Фишера

Наиболее распространённый метод основан на динамическом программировании. Строится матрица размером \((|a|+1) \times (|b|+1)\), где элемент \( D[i][j] \) хранит расстояние Левенштейна между первыми \( i \) символами строки \( a \) и первыми \( j \) символами строки \( b \). Заполнение происходит по правилу:

\[ D[i][j] = \min \begin{cases} D[i-1][j] + 1 & \text{(удаление)} \\ D[i][j-1] + 1 & \text{(вставка)} \\ D[i-1][j-1] + \text{cost} & \text{(замена, cost = 0 если } a[i-1] = b[j-1] \text{, иначе 1)} \end{cases} \]

Итоговое расстояние находится в ячейке \( D[|a|][|b|] \). Временная сложность — \( O(mn) \), пространственная — \( O(mn) \), хотя может быть оптимизирована до \( O(\min(m, n)) \) за счёт хранения только двух строк матрицы.

Оптимизации

• Алгоритм с ограничением по порогу: если известно, что расстояние не превышает некоторого \( k \), можно вычислять только диагональную полосу матрицы шириной \( 2k+1 \), сокращая сложность до \( O(k \cdot \min(m, n)) \).
• Алгоритм Укконена: использует свойства расстояния для раннего завершения при превышении порога.
• Битовые параллельные алгоритмы (например, алгоритм Мейерса): используют битовые операции для ускорения вычислений на современных процессорах, особенно для коротких строк.

Применение

Проверка орфографии и автозамена

Одно из первых и наиболее известных применений — поиск слов, близких к введённому пользователем, в словаре. Системы проверки орфографии (например, в текстовых процессорах) вычисляют расстояние Левенштейна между введённым словом и каждым словом словаря, предлагая варианты с наименьшим расстоянием. Для ускорения используются префиксные деревья (trie) и фильтрация по длине.

Биоинформатика

В биоинформатике расстояние Левенштейна (часто в форме глобального выравнивания Нидлмана — Вунша) применяется для сравнения последовательностей ДНК, РНК и белков. Операции вставки, удаления и замены соответствуют мутациям — инделям и точечным заменам нуклеотидов или аминокислот.

Обработка естественного языка

• Поиск дубликатов: сравнение текстовых строк для выявления почти совпадающих записей в базах данных (например, «Иванов И.И.» и «Иванов Иван Иванович»).
• Стемминг и лемматизация: вспомогательная метрика для оценки морфологического сходства словоформ.
• Машинный перевод: оценка качества перевода через сравнение с эталоном (метрика TER — Translation Edit Rate).

Информационная безопасность

• Обнаружение плагиата: выявление заимствований с незначительными изменениями (перестановка слов, замена синонимов).
• Анализ вредоносного кода: сравнение сигнатур вредоносных программ для выявления вариантов (полиморфных модификаций).

Теория кодирования

В теории кодирования расстояние Левенштейна используется для оценки корректирующей способности кодов, исправляющих ошибки вставки/удаления (например, коды Левенштейна, коды Хэмминга с модификациями).

Варианты и обобщения

Расстояние Дамерау — Левенштейна

В 1964 году Фредерик Дамерау предложил дополнить классический набор операций перестановкой двух соседних символов (транспозицией), что часто встречается при опечатках (например, «кот» → «кто»). Расстояние Дамерау — Левенштейна учитывает четыре операции: вставка, удаление, замена и транспозиция. Алгоритм вычисления требует модификации матрицы динамического программирования.

Расстояние Хэмминга

Частный случай расстояния Левенштейна для строк одинаковой длины, когда разрешена только операция замены. Расстояние Хэмминга равно числу позиций, в которых символы различаются.

Взвешенное расстояние Левенштейна

В некоторых приложениях операциям присваиваются разные стоимости. Например, замена буквы на фонетически близкую может стоить меньше, чем на далёкую. В биоинформатике матрицы замен (например, BLOSUM или PAM) задают стоимость замены аминокислот.

Обобщение на другие структуры данных

Расстояние Левенштейна может быть обобщено на деревья (расстояние редактирования дерева), графы и последовательности других типов (например, числовые ряды).

Ограничения и критика

• Вычислительная сложность: квадратичная сложность \( O(mn) \) делает алгоритм неприменимым для сравнения очень длинных строк (например, целых книг) без оптимизаций.
• Нечувствительность к контексту: метрика не учитывает семантику или синтаксис. Например, строки «кот» и «собака» могут иметь то же расстояние, что и «кот» и «код», хотя семантически первая пара различна сильнее.
• Линейный порядок операций: расстояние не отражает, насколько «естественной» является последовательность правок. Например, замена всех символов может быть дешевле, чем одна вставка, хотя с точки зрения восприятия первое — более грубое изменение.

Интересные факты

• В 1974 году Роберт Вагнер и Майкл Фишер опубликовали алгоритм динамического программирования, который стал стандартом. Однако сам Левенштейн в оригинальной работе 1965 года не приводил алгоритма — он лишь доказал существование метрики.
• Расстояние Левенштейна используется в системах автоматического распознавания речи для поиска наиболее вероятной последовательности слов (через алгоритм Витерби, который также основан на динамическом программировании).
• В проекте «Википедия» (организация Meta признана экстремистской и запрещена в РФ) расстояние Левенштейна применяется для выявления вандализма — быстрых замен текста на бессмысленный или оскорбительный.

Источники

• Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады АН СССР. — 1965. — Т. 163, № 4. — С. 845–848.
• Wagner R. A., Fischer M. J. The string-to-string correction problem // Journal of the ACM. — 1974. — Vol. 21, № 1. — P. 168–173.
• Gusfield D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. — Cambridge University Press, 1997. — 556 p.
• Navarro G. A guided tour to approximate string matching // ACM Computing Surveys. — 2001. — Vol. 33, № 1. — P. 31–88.