Cтрока x длины |x| = m записывается как x₁x₂ … x_m, где x_i представляет i-й символ x.

Подстрока x_ix_i+1 … x_j строки x, где i<=j<=m, будет обозначаться x(i,j). В случае, когда i>j, обращенная подстрока обозначается так x_R(i,j).

Обычно x будет обозначать искомый образец, а y – текстовую строку; |x| = m, |y| = n и, конечно, m<=n.

Пример:

x = trismegistus
|x| = 12
x(7,10) = gist
x_R(7,4) = gems

Обобщенная задача сопоставления строк, включающая в себя нахождение подстрок строки текста, близких к заданному образцу строки, называется также задачей нечеткого сопоставления строк. Задачу нечеткого сопоставления строк можно сформулировать следующим образом:

Здесь и далее, d — метрика.

Расстояние Хемминга [Hamming, 1982] между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Это эквивалентно минимальной цене преобразования первой строки во вторую в случае, когда разрешена только операция замены с единичным весом. Если допускается сравнение строк разной длины, то, как правило, требуются также вставка и удаление. Если придать им тот же вес, что и замене, минимальная общая цена преобразования будет равна одной из метрик, предложенных Левенштейном [Levenstein, 1965]. Другая метрика равна минимальной цене преобразования в случае, когда разрешены только вставка и удаление. Это эквивалентно назначению цены 1 удалению и вставке, и 2 замене, так как последнюю можно заменить парой вставка-удаление. Первую из этих метрик мы ниже называем расстоянием Левенштейна, а вторую – расстоянием редактирования.

Задача, таким образом, состоит в том, чтобы при заданной функции расстояния найти все подстроки текста, отстоящие от образца не более, чем на k.

Rencontres Du Film Court Antananarivo

Если d является расстоянием Хемминга, задача называется сопоставлением строк с k несовпадениями, если же d – расстояние Левенштейна, задача называется сопоставлением строк с k различиями (или, иногда, ошибками).

Наивный подход к задаче сопоставления строк, требующий времени O(mn), легко адаптировать к задаче k несовпадений, разрешив k несовпадений при сравнениях символов подстроки в тексте.

Однако, как и для задачи сопоставления строк, для задач k несовпадений и k различий были изобретены более эффективные подходы.

k несовпадений – Ландау-Вишкин
k-различий – Ландау-Вишкин

Их алгоритм гораздо лучше, если k пропорционально O(m/log n). Для неограниченных алфавитов он алгоритм быстрее, если k пропорционально O(log^1/2m). Он, безусловно, превосходен, когда границей k является O(log^1/2m). Заметим, однако, что при больших k, то есть когда k равняется O(m), его эффективность не лучше, чем у адаптации прямого, с квадратичным временем, подхода динамического программирования.

Для практических целей особо рекомендую
AGREP^zip

Если цель нечеткого поиска — исключить ошибки наборщика, то метод, оптимизированный для поиска очень похожих на образец вхождений описан в статье
Tries for approximate string matching^zip

Также советую посетить сайт ITMAN, он посвящен исключительно нечеткому поиску и, на мой взгляд, весьма интересен.

Реферат на тему:

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

План:

Введение
• 1Свойства
• 2Применение
• 3Редакционное предписание
• 4Обобщения
  • 4.1Разные цены операций
  • 4.2Транспозиция
• 5Формула
• 6Алгоритм Вагнера — Фишера

Примечания

Введение

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

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

1. Свойства

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

где d(S₁,S₂) — расстояние Левенштейна между строками S₁ и S₂, а |S| — длина строки S.

2. Применение

Расстояние Левенштейна и его обобщения активно применяется:

• для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированого текста или речи).
• для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.
• в биоинформатике для сравнения генов, хромосом и белков.

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

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

3.

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

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (replace) — заменить, M (match) — совпадение.

Например, для 2-х строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:

Найти только расстояние Левенштейна — более простая задача, чем найти ещё и редакционное предписание (подробнее см. ниже).

4. Обобщения

4.1. Разные цены операций

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии^[3], разную вероятность разных ошибок при вводе текста и т. д. В общем случае:

• w(a, b) — цена замены символа a на символ b
• w(ε, b) — цена вставки символа b
• w(a, ε) — цена удаления символа a

Необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при

• w(a, а) = 0
• w(a, b) = 1 при a≠b
• w(ε, b) = 1
• w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).

4.2. Транспозиция

Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау — Левенштейна. Для неё также существует алгоритм, требующий O(MN) операций. Дамерау показал, что 80 % ошибок при наборе текста человеком являются транспозициями. Кроме того, расстояние Дамерау — Левенштейна используется и в биоинформатике.

5. Формула

Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике, а не с нулевого, как принято в языках C, C++, Java.

Пусть S₁ и S₂ — две строки (длиной M и N соответственно) над некоторым алфавитом, тогда редакционное расстояние d(S₁,S₂) можно подсчитать по следующей рекуррентной формуле

, где

,

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

5.1. Доказательство

Рассмотрим формулу более подробно. Здесь D(i,j) — расстояние между префиксами строк: первыми i символами строки S₁ и первыми j символами строки S₂. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной i, нужно совершить i операций удаления, а чтобы получить строку длиной j из пустой, нужно произвести j операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:

• Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
• Две замены разных символов можно менять местами
• Два стирания или две вставки можно менять местами
• Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
• Стирание и вставку разных символов можно менять местами
• Вставка символа с его последующей заменой — неоптимально (излишняя замена)
• Вставка символа и замена другого символа меняются местами
• Замена символа с его последующим стиранием — неоптимально (излишняя замена)
• Стирание символа и замена другого символа меняются местами

Пускай S₁ кончается на символ «a», S₂ кончается на символ «b». Есть три варианта:

1. Символ «а», на который кончается S₁, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые i − 1 символов S₁ в S₂ (на что потребовалось операций), значит, всего потребовалось операций
2. Символ «b», на который кончается S₂, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили S₁ в первые j − 1 символов S₂, после чего добавили «b». Аналогично предыдущему случаю, потребовалось операций.
3. Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
   1. Если a = b, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили операций.
   2. Если , мы последний символ меняли один раз.

      Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить операций, значит, всего потребуется операций.

6. Алгоритм Вагнера — Фишера

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма:

Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений:

(Напоминаем, что элементы строк нумеруются с первого, а не с нулевого.)

Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M,N) в левый верхний, на каждом шаге ища минимальное из трёх значений:

• если минимально (D(i-1, j) + цена удаления символа S1[i]), добавляем удаление символа S1[i] и идём в (i-1, j)
• если минимально (D(i, j-1) + цена вставки символа S2[j]), добавляем вставку символа S1[i] и идём в (i, j-1)
• если минимально (D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]), добавляем замену S1[i] на S2[j] (если они не равны; иначе ничего не добавляем), после чего идём в (i-1, j-1)

Здесь (i, j) — клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.

Этот алгоритм называется алгоритмом Вагнера — Фишера. Он предложен Р. Вагнером (R. A. Wagner) и М. Фишером (M. J. Fischer) в 1974 году.^[4]

6.1. Память

Алгоритм в виде, описанном выше, требует операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 10⁵ строк потребуется около 40 гигабайт памяти.

Если требуется только расстояние, легко уменьшить требуемую память до Θ(min(M,N)). Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна.

Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как

или даже

Если требуется редакционное предписание, экономия памяти усложняется.

Для того, чтобы обеспечить время при памяти Θ(min(M,N)), определим матрицу E минимальных расстояний между суффиксами строк, то есть E(i, j) — расстояние между последними i символами S₁ и последними j символами S₂.

Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро.

Теперь опишем алгоритм, считая, что S₂ — кратчайшая из двух строк.

• Если длина одной из строк (или обеих) не больше 1, задача тривиальна. Если нет, выполним следующие шаги.
• Разделим строку S₁ на две подстроки длиной M / 2. (Если M нечётно, то длины подстрок будут (M − 1) / 2 и (M + 1) / 2.) Обозначим подстроки и .
• Для вычислим последнюю строку матрицы D, а для  — последнюю строку матрицы E.
• Найдём i такое, что минимально. Здесь D и Е — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение S₂ на две подстроки, минимизирующее сумму расстояния левой половины S₁ до левой части S₂ и расстояния правой половины S₁ до правой части S₂. Следовательно, левая подстрока S₂ соответствует левой половине S₁, а правая — правой.
• Рекурсивно ищем редакционное предписание, превращающее в левую часть S₂ (то есть в подстроку S2[1…i])
• Рекурсивно ищем редакционное предписание, превращающее в правую часть S₂ (то есть в подстроку S2[i + 1…N]).
• Объединяем оба редакционных предписания.^[5]

Время выполнения удовлетворяет (с точностью до умножения на константу) условию

,

откуда следует (доказывается индукцией по M)

следовательно

Требуемая память пропорциональна N + N / 2 + N / 4 + …

= 2N

Кроме того, есть алгоритмы, экономящие память за счёт существенного замедления, например, время становится кубическим, а не квадратичным, по длине строк.

Примечания

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

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

Пример

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

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

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

Применение

Расстояние Левенштейна активно применяется при поиске и обработке текстов

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

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

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

Алгоритм

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

В псевдокоде алгоритм выглядит так:

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]

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

В языке программирования PHP этот алгоритм реализован функцией levenshtein.

Границы

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

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

Реализации

Алгоритм Левенштейна в среде PowerBuilder (где нумерация элементов массивов начинается с единицы):

function integer gf_lev_distance (string a_vsource, string a_vtarget); integer l_nlength_vsource integer l_nlength_vtarget integer v_cost integer column_to_left,current_column integer i,j v_cost = 0 l_nlength_vsource = len(a_vsource) l_nlength_vtarget = len(a_vtarget) if l_nlength_vsource = 0 then return l_nlength_vtarget elseif l_nlength_vtarget = 0 then return l_nlength_vsource ELSE FOR j = 1 to (l_nlength_vtarget + 1) column_to_left[j] = j next FOR i = 1 to l_nlength_vsource current_column[1] = i FOR j = 2 to (l_nlength_vtarget + 1) IF mid(a_vsource, i, 1) = mid(a_vtarget, j — 1, 1) THEN v_cost = 0 ELSE v_cost = 1 END IF current_column[j] = current_column[j — 1] + 1 if (column_to_left[j] + 1) < current_column[j] then current_column[j] = column_to_left[j] + 1 end if if (column_to_left[j — 1] + v_cost) < current_column[j] then current_column[j] = column_to_left[j — 1] + v_cost end if next FOR j = 1 to (l_nlength_vtarget + 1) column_to_left[j] = current_column[j] next next end if return current_column[l_nlength_vtarget + 1] — 1 end function

Алгоритм Левенштейна в среде JAVA (где нумерация элементов массивов начинается с нуля):

static int levDistance(String s1, String s2) { int lengthS1 = s1.length(); int lengthS2 = s2.length(); int tab = new int[lengthS1 + 1][lengthS2 + 1]; int i, j, diff; for( i = 0; i <= lengthS1; i++ ) tab[i][0] = i; for( j = 0; j <= lengthS2; j++ ) tab[0][j] = j; for( i = 1; i <= lengthS1; i++ ) { for( j = 1; j <= lengthS2; j++ ) { if ( s1.charAt( i — 1 ) == s2.charAt( j — 1 ) ) diff = 0; else diff = 1; tab[i][j] = min( min(tab[i-1][j] + 1, // insertion tab[i][j-1] + 1), // deletion tab[i-1][j-1] + diff); // substitution } } return tab[lengthS1][lengthS2]; }

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