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

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

История

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

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

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

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

Простая реализация в виде псевдокода функции Distance , которая принимает две строки: s длины m и t длины n и возвращает расстояние Левенштейна между ними, выглядит следующим образом. Входные строки имеют один индекс, а матрица d имеет нулевой индекс, и [i..k] представляет собой закрытый диапазон.

function Distance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the distance between
  // the first i characters of s and the first j characters of t
  // note that d has (m+1)*(n+1) values
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m:
      d[i, 0] := i
 
  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n:
      d[0, j] := j
 
  for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution
 
  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] в 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 — длина самой короткой строки.
• Мы можем назначить разные штрафные издержки за вставку, удаление и замену. Мы также можем указать стоимость штрафов, которая зависит от того, какие символы вставлены, удалены или заменены.
• Этот алгоритм плохо распараллеливается из-за большого количества зависимостей данных . Однако все cost значения могут вычисляться параллельно, а алгоритм может быть адаптирован для выполнения minimum функционировать поэтапно, чтобы устранить зависимости.
• Исследуя диагонали вместо строк и используя ленивую оценку , мы можем найти расстояние Левенштейна за время O ( m (1 + d )) (где d — расстояние Левенштейна), что намного быстрее, чем обычный алгоритм динамического программирования, если расстояние небольшое.

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

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

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