Расстояние Левенштейна

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

Впервые задачу упомянул[1] в 1965 году советский математик Владимир Иосифович Левенштейн при изучении <math>0-1</math> последовательностей. Впоследствии более общую задачу для произвольного алфавита связали с его именем. Большой вклад в изучение вопроса внёс[2] Гасфилд.

Содержание

Формальное определение

Пусть <math>S_1</math> и <math>S_2</math> — две строки (длиной <math>n</math> и <math>m</math> соответственно) над некоторым алфавитом, тогда редакционное расстояние <math>\rm{d}(S_1, S_2)</math> можно подсчитать по следующей рекуррентной формуле

<math>\rm{d}(S_1, S_2) = \rm{D}(n, m) = \left\{\begin{array}{llcl} 0&&;&i = 0,\ j = 0\\ i&&;&j = 0,\ i > 0\\ j&&;&i = 0,\ j > 0\\ \rm{min}(\\ &\rm{D}(i, j - 1) + 1\\ &\rm{D}(i - 1, j) + 1&;&j > 0,\ i > 0\\ &\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\ ) \end{array}\right. </math>,

где <math>\rm{m}(a,b)</math> равна нулю, если <math>a = b</math> и единице в противном случае; <math>\min(a, b, c)</math> возвращает наименьший из аргументов.

Рассмотрим формулу более подробно. Здесь шаг по <math>i</math> символизирует удаление (D) из первой строки, по <math>j</math> — вставку (I) в первую строку, а шаг по обоим индексам символизирует замену символа (R) или отсутствие изменений (M). Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <math>i</math>, нужно совершить <math>i</math> операций удаления, а чтобы получить строку длиной <math>j</math> из пустой, нужно произвести <math>j</math> операций вставки. В нетривиальном случае нужно выбрать минимальную «стоимость» из трёх вариантов. Вставка/удаление будет в любом случае стоить одну операцию, а вот замена может не понадобиться, если символы равны — тогда шаг по обоим индексам бесплатный. Формализация этих рассуждений приводит к формуле, указанной выше. Более строгое доказательство приведено в книге Гасфилда.

Очевидно, справедливы следующие утверждения:

  • <math>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</math>
  • <math>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</math>
  • <math>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</math>

Редакционное предписание

Введём теперь понятие редакционного предписания — последовательности действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, 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

Алгоритм

С помощью стандартной динамики <math>\rm{D}(n,m)</math> можно вычислить за <math>\Theta(m \cdot n)</math>. При этом, поскольку в каждый момент времени используются только текущая и предыдущая строка, можно занимать всего <math>\Theta(\min(m,n))</math> памяти. См. Реализации в Викиучебнике.

Однако всё несколько усложняется, если требуется также найти редакционное предписание. В таком случае снижение использования памяти возможно только за счёт понижения производительности. Наиболее широко распространены следующие варианты (<math>n = \max(|S_1|,|S_2|)</math>):

  • <math>\Theta(n^2)</math> времени и <math>\Theta(n^2)</math> памяти:

При вычислении редакционного расстояния хранятся все шаги, затем предписание восстанавливается явно, возвращаясь по сохранённым шагам. См. Реализацию в Викиучебнике.

  • <math>\Theta(n^3)</math> времени и <math>\Theta(n)</math> памяти;

Хранится только две строки — текущая и предыдущая. Для восстановления предписания <math>O(n)</math> раз идут до текущего элемента (после каждого раза его индекс уменьшается на <math>O(1)</math>). См. Реализацию в Викиучебнике

  • <math>\Theta(n^2 \cdot \sqrt{n})</math> времени и <math>\Theta(n \cdot \sqrt{n})</math> памяти.

Метод схож с предыдущим, только каждый раз хранятся полосы высотой <math>\lceil\sqrt{n}\rceil</math>, а индекс уменьшается на <math>O(\sqrt{n})</math>. См. Реализацию в Викиучебнике

Применение

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

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

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

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

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

См. также

Ссылки и сноски

  1. В. И. Левенштейн (1965) Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР 163.4:845-848.
  2. Гасфилд (2003) Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. Невский Диалект БВХ-Петербург

Внешние ссылки

Личные инструменты

Served in 0.107 secs.