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

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

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

  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 только когда обе строки равны

Реализации

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Дистанция Левенштейна" в других словарях:

  • Дистанция — Расстояние, в широком смысле, степень удалённости объектов друг от друга. Расстояние является фундаментальным понятием геометрии. Термин часто используется в других науках и дисциплинах: астрономия, география, геодезия, навигация и др. Расстояние …   Википедия

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

  • Владимир Иосифович Левенштейн — (родился в 1935 г.) российский учёный, доктор физико математических наук, работает ведущим научным сотрудником в Институте прикладной математики им. М. В. Келдыша. Благодаря введённому им в 1965 году понятию дистанции редактирования, названной… …   Википедия

  • Владимир Левенштейн — Владимир Иосифович Левенштейн (родился в 1935 г.) российский учёный, доктор физико математических наук, работает ведущим научным сотрудником в Институте прикладной математики им. М. В. Келдыша. Благодаря введённому им в 1965 году понятию… …   Википедия

  • Левенштейн, Владимир — Владимир Иосифович Левенштейн (родился в 1935 г.) российский учёный, доктор физико математических наук, работает ведущим научным сотрудником в Институте прикладной математики им. М. В. Келдыша. Благодаря введённому им в 1965 году понятию… …   Википедия

  • Левенштейн В. — Владимир Иосифович Левенштейн (родился в 1935 г.) российский учёный, доктор физико математических наук, работает ведущим научным сотрудником в Институте прикладной математики им. М. В. Келдыша. Благодаря введённому им в 1965 году понятию… …   Википедия

  • Левенштейн В. И. — Владимир Иосифович Левенштейн (родился в 1935 г.) российский учёный, доктор физико математических наук, работает ведущим научным сотрудником в Институте прикладной математики им. М. В. Келдыша. Благодаря введённому им в 1965 году понятию… …   Википедия

  • Левенштейн Владимир Иосифович — Владимир Иосифович Левенштейн (родился в 1935 г.) российский учёный, доктор физико математических наук, работает ведущим научным сотрудником в Институте прикладной математики им. М. В. Келдыша. Благодаря введённому им в 1965 году понятию… …   Википедия

  • Левенштейн, Владимир Иосифович — В Википедии есть статьи о других людях с такой фамилией, см. Левенштейн. Владимир Иосифович Левенштейн (род. 20 мая 1935)  российский учёный, доктор физико математических наук. Ведущий научный сотрудник Института прикладной математики им.… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»