- Дистанция Левенштейна
-
Операцией редактирования называется одно из следующих действий со строкой:
- Добавление символа в произвольную позицию
- Удаление символа
- Замена одного символа другим
Расстояние Левенштейна (также дистанция Левенштейна, функция Левенштейна, алгоритм Левенштейна или дистанция редактирования) в теории информации и компьютерной лингвистике — это мера разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной строки в другую.
Пусть u и v – две строки над некоторым алфавитом.
Расстоянием Левенштейна d(u, v) между строками u и v называется наименьшее количество операций редактирования, необходимое, чтобы перевести u в v. Из соображений обратимости операций редактирования, имеем d(u, v) = d(v, u).
Метод разработан в 1965 году советским математиком Владимиром Иосифовичем Левенштейном и назван его именем.
Содержание
Пример 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, или в других подобных программных продуктах, при поиске и обработке текстов
- в поисковых системах для нахождения объектов или записей по имени
- в базах данных при поиске с неполно-заданным или неточно-заданным именем
- для исправления ошибок при вводе текста
- для исправления ошибок в результате автоматического распознавания отсканированного текста или речи
- в других приложениях, связанных с автоматической обработкой текстов
Функция Левенштейна же играет роль фильтра, заведомо отбрасывающего неприемлемые варианты (у которых значение функции больше некоторой заданной константы).
С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:
- При перестановке местами слов или частей слов получаются сравнительно большие расстояния
- Расстояния между абсолютно разными короткими словами оказываются небольшими, в то время как расстояние между сильно похожими длинными словами оказываются значительными
Алгоритм
Чаще всего используемый, простой алгоритм для расчета расстояния редактирования нуждается в матрице формы (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 только когда обе строки равны
Реализации
- См. Расстояние Левенштейна в Викиучебнике.
Родственные методы
- Расстояние Дамерау — Левенштейна
- Алгоритм Хирчберга
- Расстояние Хэмминга
- Расстояние Йенцена — Шаннона
- Фонетический поиск
Wikimedia Foundation. 2010.