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

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

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

История

Алгоритм Вагнера-Фишера имеет историю множественных изобретений . Наварро перечисляет следующих его изобретателей с указанием даты публикации и признает, что список неполный: ^{[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 ]                     

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

Инвариант , поддерживаемый на протяжении всего алгоритма, заключается в том, что мы можем преобразовать начальный сегмент 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 , то достаточно вычислить диагональную полосу шириной ⁠ ⁠ ${\displaystyle 2k+1}$ в матрице. Таким образом, алгоритм может быть запущен за время O ( kl ) , где l — длина самой короткой строки. ^[2]
• Мы можем задать различные штрафные стоимости для вставки, удаления и замены. Мы также можем задать штрафные стоимости, которые зависят от того, какие символы вставляются, удаляются или заменяются.
• Этот алгоритм плохо распараллеливается из-за большого количества зависимостей данных . Однако все costзначения можно вычислять параллельно, и алгоритм можно адаптировать для выполнения minimumфункции поэтапно, чтобы устранить зависимости.
• Исследуя диагонали вместо строк и используя ленивые вычисления , мы можем найти расстояние Левенштейна за время O ( m (1 + d )) (где d — расстояние Левенштейна), что намного быстрее обычного алгоритма динамического программирования, если расстояние небольшое. ^[3]

Вариант продавца для поиска по строке

Инициализируя первую строку матрицы нулями, мы получаем вариант алгоритма Вагнера–Фишера, который можно использовать для нечеткого поиска строки в тексте. ^[1] Эта модификация дает конечную позицию совпадающих подстрок текста. Чтобы определить начальную позицию совпадающих подстрок, количество вставок и удалений можно хранить отдельно и использовать для вычисления начальной позиции из конечной позиции. ^[4]

Полученный алгоритм ни в коем случае не является эффективным, но на момент своей публикации (1980) он был одним из первых алгоритмов, выполнявших приближенный поиск. ^[1]

Ссылки

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.