WikiDer > Алгоритм Вагнера – Фишера

Wagner–Fischer algorithm

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

История

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

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

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

Простая реализация, поскольку псевдокод для функции Левенштейн это требует двух струн, 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яттеп
0123456
s1123456
я2212345
т3321234
т4432123
я5543223
п6654332
грамм7765443
Sаттырdау
012345678
S101234567
ты211223456
п322233456
d433334345
а543444434
у654455543

В инвариантный поддерживается на протяжении всего алгоритма, заключается в том, что мы можем преобразовать начальный сегмент 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. ^ а б c Наварро, Гонсало (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.