Дистанция Левенштейна

Операцией редактирования называется одно из следующих действий со строкой:

1. Добавление символа в произвольную позицию
2. Удаление символа
3. Замена одного символа другим

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

Пусть u и v – две строки над некоторым алфавитом.

Расстоянием Левенштейна d(u, v) между строками u и v называется наименьшее количество операций редактирования, необходимое, чтобы перевести u в v. Из соображений обратимости операций редактирования, имеем d(u, v) = d(v, u).

Метод разработан в 1965 году советским математиком Владимиром Иосифовичем Левенштейном и назван его именем.

Пример 1

Чтобы перевести слово «конь» в слово «кот» нужно совершить одно удаление и одну замену, соответственно расстояние Левенштейна составляет 2:

1. Конь → Коть (Заменяем н на т)
2. Коть → Кот (Удаляем ь)

Практическим применением расстояния Левенштейна является определение похожести последовательностей символов, к примеру в исправлении орфографии или при поиске повторов.

Пример 2

Иногда, для большей наглядности, в редакционном предписании используют обозначения следующего вида:

I – insert D – delete R – replace M – match

Тогда для 2-х строк “CONNECT” и “CONEHEAD” можно построить следующую таблицу преобразований:

M	M	M	R	R	R	R	I
C	O	N	N	E	C	T
C	O	N	E	H	E	A	D

В итоге, можно не только подсчитать функцию Левенштейна, но также показать одно из преобразований.

Задача о редакционном расстоянии

Редакционное предписание между двумя строками определяется как минимальное число редакционных операций, то есть вставок, удалений, замен, необходимых для преобразования одной строки S1 в другую S2.

Теперь рассмотрим задачу вычисления функции Левенштейна и её редакционного предписания с помощью динамического программирования.

Для двух строк S1 и S2 значение D(i, j) определим, как редакционное расстояние между S1[1..i] и S2[1..j].

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

Применение

Расстояние Левенштейна активно применяется в различных грамматических приложениях, таких как правописание в MS Office, или в других подобных программных продуктах, при поиске и обработке текстов

1. в поисковых системах для нахождения объектов или записей по имени
2. в базах данных при поиске с неполно-заданным или неточно-заданным именем
3. для исправления ошибок при вводе текста
4. для исправления ошибок в результате автоматического распознавания отсканированного текста или речи
5. в других приложениях, связанных с автоматической обработкой текстов

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

С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:

1. При перестановке местами слов или частей слов получаются сравнительно большие расстояния
2. Расстояния между абсолютно разными короткими словами оказываются небольшими, в то время как расстояние между сильно похожими длинными словами оказываются значительными

Алгоритм

Чаще всего используемый, простой алгоритм для расчета расстояния редактирования нуждается в матрице формы (n + 1) × (m+1), где n и m суть длины сравниваемых строк. В псевдокоде алгоритм выглядит так:

int LevenshteinDistance(char s[1..n], char t[1..m])
   declare int d[0..n,0..m]
   declare int i, j, cost
   for i := 0 to n
       d[i,0] := i
   for j := 0 to m
       d[0,j] := j
   for i := 1 to n
       for j := 1 to m
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i,j] := minimum(d[i-1,j  ] + 1,    // insertion
                             d[i,  j-1] + 1,    // deletion
                             d[i-1,j-1] + cost) // substitution
   return d[n,m]

Этот алгоритм легко реализуем и вручную в виде таблицы.

В языке программирования levenshtein.

Границы

Для Дистанции Левенштейна существуют следующие верхние и нижние границы:

• Дистанция Левенштейна, как минимум, равна разнице длины сравниваемых строк
• Она не может быть больше длины самой длинной строки
• Она равна 0 только когда обе строки равны

Реализации

• См. Расстояние Левенштейна в Викиучебнике.

Родственные методы

• Расстояние Дамерау — Левенштейна
• Алгоритм Хирчберга
• Расстояние Хэмминга
• Расстояние Йенцена — Шаннона
• Фонетический поиск