Алгоритм Вагнера-Фишера

Алгоритм программирования

В информатике алгоритм Вагнера–Фишера — это динамический алгоритм программирования , который вычисляет расстояние редактирования между двумя строками символов.

История

Алгоритм Вагнера-Фишера имеет историю множественных изобретений . Наварро перечисляет следующих его изобретателей с указанием даты публикации и признает, что список неполный: ^[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 .. m , 0 .. n ] устанавливает каждый элемент в d в ноль // исходные префиксы можно преобразовать в пустую строку, // отбросив все символы for i от 1 до m : d [ i , 0 ] := i // целевые префиксы можно получить из пустого исходного префикса , // вставив каждый символ for j от 1 до n : d [ 0 , j ] := j for j от 1 до n : for i от 1 до m : if s [ i ] = t [ j ] : substitutionCost := 0 else : стоимость замены := 1                                                                      d [ i , j ] := minimum ( d [ i - 1 , j ] + 1 , // удаление d [ i , j - 1 ] + 1 , // вставка d [ i - 1 , j - 1 ] + substitutionCost ) // подстановка return d [ m , n ]

Два примера результирующей матрицы (при наведении курсора на подчеркнутое число отображается операция, выполненная для получения этого числа):

		к	я	т	т	е	н
	0	1	2	3	4	5	6
с	1	1	2	3	4	5	6
я	2	2	1	2	3	4	5
т	3	3	2	1	2	3	4
т	4	4	3	2	1	2	3
я	5	5	4	3	2	2	3
н	6	6	5	4	3	3	2
г	7	7	6	5	4	4	3

		С	а	т	ты	г	г	а	у
	0	1	2	3	4	5	6	7	8
С	1	0	1	2	3	4	5	6	7
ты	2	1	1	2	2	3	4	5	6
н	3	2	2	2	3	3	4	5	6
г	4	3	3	3	3	4	3	4	5
а	5	4	3	4	4	4	4	3	4
у	6	5	4	4	5	5	5	4	3

Инвариант , поддерживаемый на протяжении всего алгоритма, заключается в том, что мы можем преобразовать начальный сегмент 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]операции ( вставку).kt[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]

Ссылки

^ abc Наварро, Гонсало (2001). "Путеводитель по приближенному сопоставлению строк" (PDF) . ACM Computing Surveys . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID 207551224.
^ Гасфилд, Дэн (1997). Алгоритмы на строках, деревьях и последовательностях: компьютерная наука и вычислительная биология . Кембридж, Великобритания: Cambridge University Press. ISBN 978-0-521-58519-4.
^ Allison L (сентябрь 1992 г.). «Ленивое динамическое программирование может быть жадным». Inf. Proc. Letters . 43 (4): 207–12. doi :10.1016/0020-0190(92)90202-7.
^ Бруно Вольценлогель Палео. Приблизительный географический справочник для GATE на основе расстояния Левенштейна. Студенческая секция Европейской летней школы по логике, языку и информации ( ESSLLI ), 2007.

[navarro-1] Наварро, Гонсало (2001). "Путеводитель по приближенному сопоставлению строк" (PDF) . ACM Computing Surveys . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID 207551224.

[2] Гасфилд, Дэн (1997). Алгоритмы на строках, деревьях и последовательностях: компьютерная наука и вычислительная биология . Кембридж, Великобритания: Cambridge University Press. ISBN 978-0-521-58519-4.

[3] Allison L (сентябрь 1992 г.). «Ленивое динамическое программирование может быть жадным». Inf. Proc. Letters . 43 (4): 207–12. doi :10.1016/0020-0190(92)90202-7.

[4] Бруно Вольценлогель Палео. Приблизительный географический справочник для GATE на основе расстояния Левенштейна. Студенческая секция Европейской летней школы по логике, языку и информации ( ESSLLI ), 2007.