Алгоритм Вагнера – Фишера - Wagner–Fischer algorithm

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

История

Алгоритм Вагнера – Фишера имеет историю множественное изобретение. Наварро перечисляет следующих изобретателей с указанием даты публикации и признает, что этот список неполный:^[1]:43

• Винцюк, 1968
• Нидлман и Вунш, 1970
• Санкофф, 1972
• Продавцы, 1974 г.
• Вагнер и Фишер, 1974
• Лоуренс и Вагнер, 1975

Расчет расстояния

Алгоритм Вагнера – Фишера вычисляет расстояние редактирования на основе наблюдения, что если мы зарезервируем матрица удерживать расстояние редактирования между всеми префиксы первой строки и всех префиксов второй, то мы можем вычислить значения в матрице с помощью заливка матрицу, и таким образом найти расстояние между двумя полными строками как последнее вычисленное значение.

Простая реализация, поскольку псевдокод для функции Левенштейн это требует двух струн, s длины м, и т длины п, и возвращает Расстояние Левенштейна между ними выглядит следующим образом. Обратите внимание, что входные строки одноиндексированы, а матрица d имеет нулевой индекс, и [i..k] замкнутый круг.

функция Левенштейн(char s[1..м], char т[1..п]):  // для всех i и j d [i, j] будет содержать расстояние Левенштейна между  // первые i символов s и первые j символов t  // обратите внимание, что d имеет (m + 1) * (n + 1) значений  объявить int d[0..м, 0..п]   набор каждый элемент в d к нуль   // исходные префиксы можно преобразовать в пустую строку  // отбрасываем все символы  за я из 1 к м:      d[я, 0] := я   // целевые префиксы могут быть достигнуты из пустого исходного префикса  // вставляя каждый символ  за j из 1 к п:      d[0, j] := j   за j из 1 к п:      за я из 1 к м:          если s[я] = т[j]:            замена := 0          еще:            замена := 1          d[я, j] := минимум(d[я-1, j] + 1,                   // удаление                             d[я, j-1] + 1,                   // вставка                             d[я-1, j-1] + замена)  // подстановка   возвращаться d[м, п]

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

k я т т е п 0 1 2 3 4 5 6 s 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

S а т ты р d а у 0 1 2 3 4 5 6 7 8 S 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 d 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] в т [1..j] используя минимум d [i, j] операции. В конце концов, нижний правый элемент массива содержит ответ.

Доказательство правильности

Как упоминалось ранее, инвариантный в том, что мы можем преобразовать начальный сегмент s [1..i] в т [1..j] используя минимум d [i, j] операции. Этот инвариант имеет место, поскольку:

• Изначально это верно для строки и столбца 0, потому что s [1..i] можно преобразовать в пустую строку т [1..0] просто отбросив все я символы. Аналогично мы можем преобразовать s [1..0] к т [1..j] просто добавив все j символы.
• Если s [i] = t [j], и мы можем преобразовать s [1..i-1] к т [1..j-1] в k операций, то мы можем сделать то же самое с s [1..i] и просто оставьте последний символ в покое, дав k операции.
• В противном случае расстояние будет минимальным из трех возможных способов преобразования:
  • Если мы можем преобразовать s [1..i] к т [1..j-1] в k операций, то мы можем просто добавить т [j] потом получить т [1..j] в к + 1 операции (вставка).
  • Если мы можем преобразовать s [1..i-1] к т [1..j] в k операции, то мы можем удалить s [i] а затем проделайте то же преобразование, всего к + 1 операции (удаление).
  • Если мы можем преобразовать s [1..i-1] к т [1..j-1] в k операций, то мы можем сделать то же самое с s [1..i]и обменять оригинал s [i] за т [j] впоследствии, в общей сложности к + 1 операции (подстановка).
• Операции, необходимые для преобразования s [1..n] в т [1..м] это, конечно, число, необходимое для преобразования всех s во все т, и так d [n, m] держит наш результат.

Это доказательство не подтверждает, что число, помещенное в d [i, j] фактически минимален; это труднее показать и требует аргумент от противного в котором мы предполагаем d [i, j] меньше минимального из трех, и используйте это, чтобы показать, что одно из трех не является минимальным.

Возможные модификации

Возможные модификации этого алгоритма включают:

• Мы можем адаптировать алгоритм, чтобы использовать меньше места, О (м) вместо О(млн), поскольку для этого требуется, чтобы предыдущая и текущая строки сохранялись одновременно.
• Мы можем хранить отдельно количество вставок, удалений и замен или даже позиции, в которых они происходят, что всегда j.
• Мы можем нормировать расстояние на интервал [0,1].
• Если нас интересует только расстояние, если оно меньше порога k, то достаточно вычислить диагональную полосу шириной 2к + 1 в матрице. Таким образом, алгоритм может быть запущен в О (kl) время, где л - длина самой короткой строки.^[2]
• Мы можем назначить различные штрафы за вставку, удаление и замену. Мы также можем указать штрафные затраты, которые зависят от того, какие символы вставлены, удалены или заменены.
• Этот алгоритм распараллеливает плохо, из-за большого количества зависимости данных. Однако все Стоимость значения могут вычисляться параллельно, и алгоритм может быть адаптирован для выполнения минимум функционировать поэтапно, чтобы устранить зависимости.
• Изучая диагонали вместо строк и используя ленивая оценка, мы можем найти расстояние Левенштейна в О(м (1 + d)) время (где d - расстояние Левенштейна), что намного быстрее обычного алгоритма динамического программирования, если расстояние невелико.^[3]

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

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

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

Рекомендации

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