В информатике , то алгоритм Вагнера-Фишера является динамическое программирование алгоритм , который вычисляет расстояние редактирования между двумя строками символов.
История
Алгоритм Вагнера – Фишера имеет историю многочисленных изобретений . Наварро перечисляет следующих изобретателей с указанием даты публикации и признает, что список неполный: [1] : 43
- Винцюк , 1968 г.
- Нидлман и Вунш , 1970 г.
- Санкофф , 1972 г.
- Продавцы, 1974 г.
- Вагнер и Фишер , 1974 г.
- Лоуренс и Вагнер, 1975
Расчет расстояния
Алгоритм Вагнера-Фишер вычисляет расстояние редактирования , основываясь на наблюдении , что если мы оставляем за собой матрицу для удержания редактирования расстояния между всеми префиксами первой строки и все префиксами второго, то мы можем вычислить значения в матрице заливки матрица, и таким образом найти расстояние между двумя полными строками как последнее вычисленное значение.
Простая реализация в виде псевдокода для функции Distance, которая принимает две строки s длиной m и t длиной n и возвращает расстояние Левенштейна между ними, выглядит следующим образом. Обратите внимание, что входные строки имеют единичный индекс, тогда как матрица d имеет нулевой индекс и [i..k]
представляет собой замкнутый диапазон.
function Distance ( char s [ 1 .. m ], char t [ 1 .. n ]) : // для всех i и j, d [i, j] будет удерживать расстояние между // первыми i символами s и первые j символов t // обратите внимание, что d имеет (m + 1) * (n + 1) значений declare int d [ 0 .. м , 0 .. n ] установить каждый элемент в D к нулю // исходные префиксы могут быть преобразованы в пустую строку, // отбрасывая все символы для i с 1 до m : d [ i , 0 ] : = i // целевые префиксы могут быть достигнуты из пустого исходного префикса // путем вставки каждого символа для j от 1 до n : d [ 0 , j ] : = j для j от 1 до n : для i от 1 до m : если s [ i ] = t [ j ] : substitutionCost : = 0 else : substitutionCost : = 1 d [ i , j ] : = minimum ( d [ i -1 , j ] + 1 , // удаление d [ i , j -1 ] + 1 , // вставка d [ i -1 , j -1 ] + substitutionCost ) // подстановка вернуть d [ m , n ]
Два примера полученной матрицы (наведение курсора на подчеркнутое число показывает операцию, выполняемую для получения этого числа):
|
|
Инвариант сохраняется в течение всего алгоритма является то , что мы можем преобразовать начальный сегмент s[1..i]
в t[1..j]
использовании минимума d[i,j]
операций. В конце концов, нижний правый элемент массива содержит ответ.
Доказательство правильности
Как уже упоминалось ранее, инвариант является то , что мы можем преобразовать начальный сегмент s[1..i]
в t[1..j]
использовании минимум d[i,j]
операций. Этот инвариант имеет место, поскольку:
- Изначально это верно для строки и столбца 0, потому что
s[1..i]
может быть преобразовано в пустую строкуt[1..0]
, просто отбросив всеi
символы. Точно так же мы можем преобразоватьs[1..0]
вt[1..j]
, просто добавив всеj
символы. - Если
s[i] = t[j]
, и мы можем преобразоватьs[1..i-1]
кt[1..j-1]
вk
операции, то мы можем сделать то же самоеs[1..i]
и просто оставить последний символ в одиночку, даваяk
операции. - В противном случае расстояние - это минимум из трех возможных способов выполнить преобразование:
- Если мы можем преобразовать
s[1..i]
кt[1..j-1]
вk
операции, то мы можем просто добавитьt[j]
потом получитьt[1..j]
вk+1
операции (вставки). - Если мы можем преобразовать
s[1..i-1]
кt[1..j]
вk
операции, то можно удалить ,s[i]
а затем сделать то же самое преобразование, в общей сложностиk+1
операций (удаление). - Если мы можем преобразовать
s[1..i-1]
вt[1..j-1]
вk
операциях, то мы можем сделать то же самоеs[1..i]
и затем заменить оригиналs[i]
наt[j]
всеk+1
операции (подстановка).
- Если мы можем преобразовать
- Операции, необходимые для преобразования
s[1..n]
в,t[1..m]
- это, конечно, число, необходимое для преобразования всего изs
во все изt
, и, таким образом,d[n,m]
содержит наш результат.
Это доказательство не подтверждает, что указанное число на d[i,j]
самом деле минимально; это труднее показать и включает аргумент от противного, в котором мы предполагаем, что d[i,j]
оно меньше минимума из трех, и используем это, чтобы показать, что одно из трех не является минимальным.
Возможные модификации
Возможные модификации этого алгоритма включают:
- Мы можем адаптировать алгоритм, чтобы использовать меньше места, O ( m ) вместо O ( mn ), поскольку он требует, чтобы предыдущая строка и текущая строка сохранялись в любой момент.
- Мы можем хранить количество вставок, удалений и замен по отдельности или даже позиции, в которых они происходят, что всегда
j
. - Мы можем нормализовать расстояние до интервала
[0,1]
. - Если нас интересует только расстояние, если оно меньше порогового значения k , тогда достаточно вычислить диагональную полосу шириной 2k + 1 в матрице. Таким образом, алгоритм может быть запущен за время O ( kl ), где l - длина самой короткой строки. [2]
- Мы можем назначить различные штрафы за вставку, удаление и замену. Мы также можем указать штрафные затраты, которые зависят от того, какие символы вставлены, удалены или заменены.
- Этот алгоритм плохо распараллеливается из-за большого количества зависимостей данных . Однако все
cost
значения могут вычисляться параллельно, и алгоритм может быть адаптирован для выполненияminimum
функции поэтапно для устранения зависимостей. - Изучая диагонали вместо строк и используя ленивое вычисление , мы можем найти расстояние Левенштейна за время O ( m (1 + d )) (где d - расстояние Левенштейна), что намного быстрее, чем обычный алгоритм динамического программирования, если расстояние небольшое. [3]
Вариант продавца для строкового поиска
Инициализируя первую строку матрицы нулями, мы получаем вариант алгоритма Вагнера – Фишера, который можно использовать для нечеткого строкового поиска строки в тексте. [1] Эта модификация дает конечную позицию совпадающих подстрок текста. Чтобы определить начальную позицию совпадающих подстрок, количество вставок и удалений может быть сохранено отдельно и использовано для вычисления начальной позиции от конечной позиции. [4]
Полученный алгоритм отнюдь не эффективен, но на момент публикации (1980 г.) был одним из первых алгоритмов, выполняющих приближенный поиск. [1]
Рекомендации
- ^ Гасфилд, Дэн (1997). Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 978-0-521-58519-4.
- ^ Эллисон Л. (сентябрь 1992 г.). «Ленивое динамическое программирование может быть нетерпеливым» . Инф. Proc. Письма . 43 (4): 207–12. DOI : 10.1016 / 0020-0190 (92) 90202-7 .
- ^ Бруно Вольценлогель Палео. Примерный географический справочник для GATE, основанный на расстоянии Левенштейна . Студенческая секция Европейской летней школы по логике, языку и информации ( ESSLLI ), 2007.