Информатика / Алгоритмы и анализ данных

Расстояние Левенштейна: вставки, удаления и замены

Расстояние Левенштейна — минимальное число вставок, удалений и замен стоимостью 1, превращающих одну строку в другую. Перестановка соседних символов отдельной операцией не считается.

Опубликовано: 15 октября 2026 г.Обновлено: 15 октября 2026 г.

Формула

D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}

Схема Таблица для cat → cut

Строки соответствуют префиксам cat, столбцы — префиксам cut. Нижняя правая клетка 1: достаточно заменить a на u.

Обозначения

$D(i,j)$: расстояние между префиксами длин i и j, число операций
$a_i,b_j$: символы на текущих позициях, символы
$i,j$: длины рассмотренных префиксов, целые индексы
$[aᵢ≠bⱼ]$: цена диагонального перехода: 0 при равенстве символов, иначе 1, операция

Условия применения

Строки должны быть заданы в одном алфавите и сравнены после согласования регистра, Unicode и пробелов. Для обычной метрики вставка, удаление и замена имеют цену 1, совпадение — 0. Начальные границы задаются D(0,j)=j и D(i,0)=i.

Ограничения

Метрика не учитывает перестановку как одну операцию, фонетическое сходство и значение слов. Одинаковая цена замены всех символов может быть неуместна для раскладок клавиатуры. Полная таблица требует O(mn) времени и памяти без оптимизаций.

Подробное объяснение

Алгоритм сравнивает не строки целиком, а их префиксы. В клетке D(i,j) выбирают лучший из трех последних действий: удалить символ первой строки, вставить символ в преобразуемую строку или сопоставить последние символы заменой. Если они равны, добавляется ноль, иначе единица.

Граничные значения обязательны: из пустой строки префикс длины j можно получить ровно j вставками, поэтому D(0,j)=j; аналогично D(i,0)=i. Без этих границ рекурсия не имеет основания. Каждая клетка использует уже рассчитанные соседние клетки, что и делает метод динамическим программированием.

Формула считает порядок символов. Поэтому cat→tac требует двух замен, тогда как перестановочное расстояние было бы другой метрикой. В kitten→sitting нужны две замены и одна вставка, что даёт расстояние 3. Для русских строк важно считать символы после нормализации Unicode, иначе визуально одинаковые буквы могут иметь разные представления.

Полученное число — расстояние, а не процент сходства. Для порогового поиска его сравнивают с длиной строки и назначением поля; короткое расстояние в артикуле и в свободном тексте имеет разный практический смысл. При большом словаре применяют индексы и отсечения, чтобы не строить полную таблицу для каждой пары.

Как пользоваться формулой

Задайте две строки и правила сравнения символов: регистр и нормализация текста должны быть согласованы.
Создайте таблицу для всех пар префиксов, добавив отдельные строку и столбец для пустого префикса.
Заполните границы D(0,j)=j и D(i,0)=i: преобразование пустой строки требует вставок или удалений.
В каждой клетке сравните удаление, вставку и диагональный переход с ценой ноль при совпадении или один при замене.
Возьмите нижнюю правую клетку как расстояние и восстановите последовательность операций для проверки ответа.

Историческая справка

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

Историческая линия формулы

Расстояние названо в честь Владимира Иосифовича Левенштейна. Его русская статья 1965 года посвящена кодам, исправляющим выпадения, вставки и замещения символов. Современная табличная рекурсия — способ вычисления этого расстояния; её не следует смешивать с метрикой, допускающей перестановку соседних символов.

Пример

Для cat и cut: D(0,j)=j и D(i,0)=i. Заполнение таблицы показывает, что первые и последние символы совпадают, а a заменяется на u, поэтому D(cat,cut)=1. Для кот и коты вторая строка содержит добавленный символ ы; все три исходных символа совпадают, затем выполняется одна вставка, D(кот,коты)=1. Для kitten и sitting стандартная таблица дает D=3: замены k→s, e→i и вставка g после n. Ни одна последовательность из двух операций не может одновременно исправить эти независимые различия, поэтому найденное значение минимально.

Частая ошибка

Нельзя считать перестановку одной заменой: стандартное расстояние разрешает только вставку, удаление и замену. Не меняйте границы D(0,j)=j и D(i,0)=i. Не сравнивайте строки в разных регистрах или Unicode-формах без оговоренного правила. Не называйте расстояние процентом сходства и не округляйте целое число.

Практика

Задачи с решением

Короткая замена

Условие. Найдите расстояние между cat и cut.

Решение. Совпадают c и t, символ a заменяется на u одной операцией.

Ответ. D=1

Вставка

Условие. Найдите расстояние между кот и коты.

Решение. После совпадения трех первых символов добавляется ы.

Ответ. D=1

Дополнительные источники

https://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html
https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=31411&option_lang=rus

Связанные формулы

Информатика

Индекс Жаккара: сходство через пересечение множеств

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$

Индекс Жаккара показывает долю общих элементов в объединении двух множеств. Он принимает значения от 0 до 1: ноль означает отсутствие пересечения, а единица — совпадение множеств.

Информатика

Косинусное сходство векторов: формула и расчёт угла

$\cos\theta=\frac{a\cdot b}{\lVert a\rVert\,\lVert b\rVert}$

Косинусное сходство сравнивает направление двух ненулевых векторов и принимает значения от −1 до 1. Для неотрицательных векторов оно показывает, насколько совпадает профиль признаков.

Информатика

Расстояние Хэмминга между двоичными словами

$d(x,y)=\sum [x_i\ne y_i]$

Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.