admin / 14.09.2018
Cтрока x длины |x| = m записывается как x1x2 … xm, где xi представляет i-й символ x.
Подстрока xixi+1 … xj строки x, где i<=j<=m, будет обозначаться x(i,j). В случае, когда i>j, обращенная подстрока обозначается так xR(i,j).
Обычно x будет обозначать искомый образец, а y – текстовую строку; |x| = m, |y| = n и, конечно, m<=n.
Пример:
x = trismegistus
|x| = 12
x(7,10) = gist
xR(7,4) = gems
Обобщенная задача сопоставления строк, включающая в себя нахождение подстрок строки текста, близких к заданному образцу строки, называется также задачей нечеткого сопоставления строк. Задачу нечеткого сопоставления строк можно сформулировать следующим образом:
Здесь и далее, d — метрика.
Расстояние Хемминга [Hamming, 1982] между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Это эквивалентно минимальной цене преобразования первой строки во вторую в случае, когда разрешена только операция замены с единичным весом. Если допускается сравнение строк разной длины, то, как правило, требуются также вставка и удаление. Если придать им тот же вес, что и замене, минимальная общая цена преобразования будет равна одной из метрик, предложенных Левенштейном [Levenstein, 1965]. Другая метрика равна минимальной цене преобразования в случае, когда разрешены только вставка и удаление. Это эквивалентно назначению цены 1 удалению и вставке, и 2 замене, так как последнюю можно заменить парой вставка-удаление. Первую из этих метрик мы ниже называем расстоянием Левенштейна, а вторую – расстоянием редактирования.
Задача, таким образом, состоит в том, чтобы при заданной функции расстояния найти все подстроки текста, отстоящие от образца не более, чем на k.
Содержание
Если d является расстоянием Хемминга, задача называется сопоставлением строк с k несовпадениями, если же d – расстояние Левенштейна, задача называется сопоставлением строк с k различиями (или, иногда, ошибками).
Наивный подход к задаче сопоставления строк, требующий времени O(mn), легко адаптировать к задаче k несовпадений, разрешив k несовпадений при сравнениях символов подстроки в тексте.
Однако, как и для задачи сопоставления строк, для задач k несовпадений и k различий были изобретены более эффективные подходы.
k несовпадений – Ландау-Вишкин
k-различий – Ландау-Вишкин
Их алгоритм гораздо лучше, если k пропорционально O(m/log n). Для неограниченных алфавитов он алгоритм быстрее, если k пропорционально O(log1/2m). Он, безусловно, превосходен, когда границей k является O(log1/2m). Заметим, однако, что при больших k, то есть когда k равняется O(m), его эффективность не лучше, чем у адаптации прямого, с квадратичным временем, подхода динамического программирования.
Для практических целей особо рекомендую
AGREPzip
Если цель нечеткого поиска — исключить ошибки наборщика, то метод, оптимизированный для поиска очень похожих на образец вхождений описан в статье
Tries for approximate string matchingzip
Также советую посетить сайт ITMAN, он посвящен исключительно нечеткому поиску и, на мой взгляд, весьма интересен.
Реферат на тему:
Примечания
Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Впервые задачу упомянул в 1965 году советский математик Владимир Иосифович Левенштейн при изучении последовательностей 0 − 1.[1] Впоследствии более общую задачу для произвольного алфавита связали с его именем. Большой вклад в изучение вопроса внёс Гасфилд.[2]
Очевидно, справедливы следующие утверждения:
где d(S1,S2) — расстояние Левенштейна между строками S1 и S2, а |S| — длина строки S.
Расстояние Левенштейна и его обобщения активно применяется:
С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:
Редакционное предписание
Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: 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 |
Найти только расстояние Левенштейна — более простая задача, чем найти ещё и редакционное предписание (подробнее см. ниже).
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии[3], разную вероятность разных ошибок при вводе текста и т. д. В общем случае:
Необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).
Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау — Левенштейна. Для неё также существует алгоритм, требующий O(MN) операций. Дамерау показал, что 80 % ошибок при наборе текста человеком являются транспозициями. Кроме того, расстояние Дамерау — Левенштейна используется и в биоинформатике.
Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике, а не с нулевого, как принято в языках C, C++, Java.
Пусть S1 и S2 — две строки (длиной M и N соответственно) над некоторым алфавитом, тогда редакционное расстояние d(S1,S2) можно подсчитать по следующей рекуррентной формуле
, где
,
где m(a,b) равна нулю, если a = b и единице в противном случае; min(a,b,c) возвращает наименьший из аргументов.
Рассмотрим формулу более подробно. Здесь D(i,j) — расстояние между префиксами строк: первыми i символами строки S1 и первыми j символами строки S2. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной i, нужно совершить i операций удаления, а чтобы получить строку длиной j из пустой, нужно произвести j операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
Пускай S1 кончается на символ «a», S2 кончается на символ «b». Есть три варианта:
Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить операций, значит, всего потребуется
операций.
Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма:
Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений:
(Напоминаем, что элементы строк нумеруются с первого, а не с нулевого.)
Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M,N) в левый верхний, на каждом шаге ища минимальное из трёх значений:
Здесь (i, j) — клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.
Этот алгоритм называется алгоритмом Вагнера — Фишера. Он предложен Р. Вагнером (R. A. Wagner) и М. Фишером (M. J. Fischer) в 1974 году.[4]
Алгоритм в виде, описанном выше, требует операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 105 строк потребуется около 40 гигабайт памяти.
Если требуется только расстояние, легко уменьшить требуемую память до Θ(min(M,N)). Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна.
Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
или даже
Если требуется редакционное предписание, экономия памяти усложняется.
Для того, чтобы обеспечить время при памяти Θ(min(M,N)), определим матрицу E минимальных расстояний между суффиксами строк, то есть E(i, j) — расстояние между последними i символами S1 и последними j символами S2.
Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро.
Теперь опишем алгоритм, считая, что S2 — кратчайшая из двух строк.
Время выполнения удовлетворяет (с точностью до умножения на константу) условию
откуда следует (доказывается индукцией по M)
следовательно
Требуемая память пропорциональна N + N / 2 + N / 4 + …
= 2N
Кроме того, есть алгоритмы, экономящие память за счёт существенного замедления, например, время становится кубическим, а не квадратичным, по длине строк.
Fischer. The string-to-string correction problem. J. ACM 21 1 (1974). P. 168—173
Расстояние Левенштейна (также дистанция Левенштейна, функция Левенштейна, алгоритм Левенштейна или дистанция редактирования) в теории информации и компьютерной лингвистике — это мера разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной строки в другую.
Метод разработан в 1965 году советским математиком Владимиром Иосифовичем Левенштейном и назван его именем.
Чтобы перевести слово «конь» в слово «кот» нужно совершить одно удаление и одну замену, соответственно расстояние Левенштейна составляет 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.
Для Дистанции Левенштейна существуют следующие верхние и нижние границы:
Алгоритм Левенштейна в среде 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]; }
FILED UNDER : IT