Расстояние Левенштейна — метрика на множестве конечных последовательностей, определяемая как минимальное число одноэлементных операций редактирования, необходимых для превращения одной последовательности в другую. В классическом случае разрешены три операции единичной стоимости: вставка одного символа, удаление одного символа и замена одного символа другим.Paul E. Black (ed.). Levenshtein distance // Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Обновлено 15 мая 2019. Дата обращения: 11 сентября 2026.
Расстояние названо в честь советского математика Владимира Иосифовича Левенштейна, исследовавшего в 1965 году двоичные коды с исправлением выпадений, вставок и замен символов.В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады АН СССР. — 1965. — Т. 163, № 4. — С. 845—848. Расстояние Левенштейна является одним из видов редакционного расстояния (), а не синонимом всего семейства редакционных расстояний: в других моделях могут использоваться иные операции или иные стоимости операций.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.
Расстояние применяется в приближённом сопоставлении строк, исправлении ошибок, поиске по словарям, компьютерной лингвистике, оценке систем распознавания текста и в других задачах сравнения последовательностей.
История В исходной работе 1965 года Левенштейн рассматривал передачу двоичной информации по каналу, в котором наряду с заменами и допускаются выпадения символов и вставки новых символов. Тем самым три операции, позднее ставшие основой классического расстояния Левенштейна, возникли в контексте теории кодирования и исправления ошибок синхронизации.
Алгоритмическая формулировка общей задачи преобразования одной строки в другую с помощью вставок, удалений и замен была систематизирована Робертом Вагнером и Майклом Фишером в 1974 году. Они показали, что оптимальную стоимость можно вычислить методом динамического программирования за время, пропорциональное произведению длин двух строк.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.
В дальнейшем появились алгоритмы, использующие малую фактическую дистанцию или заранее заданный порог, битовые представления динамической таблицы и конечные автоматы для поиска строк в ограниченной редакционной окрестности.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.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.
Определение Пусть и — две последовательности. Обозначим через расстояние Левенштейна между префиксом из первых элементов последовательности и префиксом из первых элементов последовательности . Граничные условия имеют вид
Для и
где
Первый вариант соответствует удалению элемента из первой последовательности, второй — вставке элемента, третий — совпадению или замене. Расстояние между полными последовательностями равно .
Определение не требует, чтобы элементами последовательностей были именно буквы. В зависимости от задачи сравниваемыми единицами могут быть символы, кодовые точки Unicode, графемные кластеры, слова или другие дискретные объекты. Поэтому численное значение расстояния имеет смысл только вместе с указанием того, что считается одним элементом последовательности.
Примеры Между строками кот и скот расстояние равно 1: достаточно вставить букву с в начало первой строки.
Между дом и дым расстояние также равно 1: требуется одна замена о на ы.
Для некоторых пар существует несколько различных оптимальных редакционных предписаний одинаковой стоимости. Поэтому само значение расстояния не определяет единственную последовательность преобразований.
Алгоритм Вагнера — Фишера Классический алгоритм строит таблицу размером . Первая строка и первый столбец соответствуют преобразованиям пустой последовательности в префиксы второй строки и наоборот. Остальные клетки вычисляются из трёх соседних состояний по рекуррентной формуле выше.
Упрощённый псевдокод:
function LevenshteinDistance(a, b): m := length(a) n := length(b) 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 a[i] = b[j]: cost := 0 else: cost := 1
D[i, j] := min( D[i-1, j] + 1, D[i, j-1] + 1, D[i-1, j-1] + cost )
return D[m, n]
В отличие от рекурсивного перебора всех возможных редакционных последовательностей, динамическое программирование сохраняет решения перекрывающихся подзадач и вычисляет каждую клетку таблицы один раз.
Временная и пространственная сложность Для строк длины и полная таблица вычисляется за времени. При хранении всей таблицы требуется памяти.
Если нужна только численная величина расстояния, достаточно хранить текущую и предыдущую строки таблицы. Поскольку в качестве внешнего измерения можно выбрать более короткую из двух строк, объём памяти уменьшается до .
Восстановление редакционного предписания Если полная таблица сохранена, из клетки можно двигаться к по предшественникам, давшим оптимальное значение. Горизонтальный и вертикальный шаги соответствуют вставке и удалению, диагональный — совпадению или замене.
При равенстве нескольких оптимальных предшественников может существовать несколько редакционных предписаний одинаковой минимальной стоимости. Таким образом, расстояние является однозначным числом, но оптимальный сценарий редактирования не обязан быть единственным.
Восстановление одного оптимального выравнивания возможно и с линейным объёмом памяти с помощью рекурсивного разделения задачи, родственного линейно-пространственной технике Хиршберга.D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences // Communications of the ACM. — 1975. — Vol. 18, no. 6. — P. 341—343. doi:10.1145/360825.360861.
Специализированные алгоритмы Алгоритмы с ограничением по расстоянию Во многих задачах интерес представляют только строки, находящиеся на расстоянии не более заданного . Если фактическое расстояние мало, значительная часть динамической таблицы заведомо не влияет на ответ. Укконен описал алгоритмы, вычислительные затраты которых зависят от расстояния или порога, а не только от произведения длин строк.
Такой подход используется в приближённом словарном поиске: если допустимо не более нескольких ошибок, вычисление можно ограничить полосой около главной диагонали таблицы.
Бит-векторный алгоритм Майерса В 1999 году Джин Майерс предложил бит-векторный алгоритм приближённого сопоставления, в котором несколько состояний динамического программирования кодируются битами машинного слова. Это позволяет обновлять множество состояний параллельно с помощью побитовых операций процессора. Метод особенно полезен в задачах поиска относительно короткого образца в большом тексте.
Автоматы Левенштейна Для фиксированного образца и порога можно построить конечный автомат, принимающий все строки, расстояние Левенштейна от которых до образца не превышает . Клаус Шульц и Стоян Михов исследовали такие автоматы для быстрого исправления строк по словарю.Klaus U. Schulz, Stoyan Mihov. Fast string correction with Levenshtein automata // International Journal on Document Analysis and Recognition. — 2002. — Vol. 5, no. 1. — P. 67—85. doi:10.1007/s10032-002-0082-8.
Условная нижняя граница Для точного вычисления редакционного расстояния на общих строках близкой длины классическая динамика имеет квадратичную зависимость от длины. Артурс Бакурс и Пётр Индик показали условную нижнюю границу: если точное edit distance для строк длины можно было бы вычислять за для некоторой постоянной , то была бы опровергнута сильная гипотеза об экспоненциальном времени (SETH).Arturs Backurs, Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH Is False) // SIAM Journal on Computing. — 2018. — Vol. 47, no. 3. — P. 1087—1097. doi:10.1137/15M1053128.
Это условный, а не безусловный запрет: результат не исключает существенно более быстрые алгоритмы для специальных классов входов, малого расстояния, приближённых вычислений или иных моделей задачи.
Свойства При единичной стоимости вставки, удаления и замены расстояние Левенштейна является метрикой. Для любых строк , и выполняются:
тогда и только тогда, когда ; ; .
Следовательно, множество конечных строк над фиксированным алфавитом с расстоянием Левенштейна образует метрическое пространство.
Если длины строк равны и , то
Нижняя граница следует из необходимости компенсировать различие длин по меньшей мере вставками или удалениями. Верхняя граница достигается заменами в общей по длине части и затем вставками либо удалениями оставшихся символов.
Связь с расстоянием Хэмминга Для строк одинаковой длины выполняется
где — расстояние Хэмминга. Каждое несовпадение позиций можно устранить одной заменой, поэтому последовательность из замен всегда допустима для расстояния Левенштейна. Равенство, однако, выполняется не всегда: вставки и удаления иногда дают более короткий редакционный путь.
Связь с наибольшей общей подпоследовательностью Если замены запрещены и разрешены только вставки и удаления, минимальная стоимость преобразования строк длины и равна
где — длина наибольшей общей подпоследовательности. Это относится к insertion–deletion-модели редакционного расстояния и не совпадает с классической моделью Левенштейна, в которой одна замена стоит 1.
Взвешенные редакционные расстояния В классической модели каждая вставка, удаление и замена имеют стоимость 1. В более общем случае вводятся стоимости
— замены на ; — удаления ; — вставки .
Такие модели полезны, когда различные ошибки или преобразования имеют неодинаковую вероятность. Например, в фонетическом или орфографическом сравнении замена двух близких символов может считаться менее дорогой, чем замена сильно различающихся.
Произвольно выбранные веса не обязаны сохранять все свойства метрики. При несимметричных стоимостях может нарушаться симметрия, а при несогласованных стоимостях — треугольное неравенство. Поэтому выражение «расстояние Левенштейна» в строгом смысле обычно относят к классической единичной модели, а обобщения описывают как взвешенные редакционные расстояния.
Расстояние Дамерау — Левенштейна Если к трём классическим операциям добавить транспозицию двух соседних символов как одну операцию, получается расстояние Дамерау — Левенштейна. Оно особенно связано с моделированием опечаток.
Распространённое утверждение о том, что Фредерик Дамерау якобы установил, что «80 % опечаток являются транспозициями», неверно. В работе 1964 года речь шла о том, что более 80 % изученных орфографических ошибок объяснялись одной ошибкой одного из четырёх типов: вставкой, удалением, заменой либо транспозицией соседних символов.Fred J. Damerau. A technique for computer detection and correction of spelling errors // Communications of the ACM. — 1964. — Vol. 7, no. 3. — P. 171—176. doi:10.1145/363958.363994.
Применения Исправление ошибок и приближённый поиск В системах проверки орфографии слово можно сравнивать со словарными формами и использовать малое расстояние как один из критериев формирования кандидатов. Однако одной только редакционной близости недостаточно для выбора лингвистически наиболее вероятного варианта: практические системы могут дополнительно учитывать частоты слов, морфологию, контекст, фонетическую близость и вероятностные модели языка.
Аналогично в приближённом поиске можно искать строки, находящиеся от запроса на расстоянии не более заданного порога. Такой поиск устойчив к небольшим опечаткам, пропускам и лишним символам.
Автоматическая коррекция искажённых текстов