Алгоритм более быстрого редактирования расстояния

Проблема: я знаю тривиальную формулировку DP расстояния редактирования и вычисление за O(mn) для двух строк размера n и m соответственно. Но недавно я узнал, что если нам нужно вычислить только минимальное значение расстояния редактирования f и оно ограничено |f|‹=s, то мы можем вычислить его за O(min(m,n) + s^2) или O(s*min(m,n)) [википедия] время.

Пожалуйста, объясните формулировку dp, если она основана на DP, или объясните алгоритм.

Просмотрите раздел improved algorithm ссылки http://en.wikipedia.org/wiki/Edit_distance .

еще одна ссылка на улучшенный алгоритм УККОНЕН http://www.berghel.net/publications/asm/asm.php

Заранее спасибо.


c++ optimization algorithm dynamic-programming edit-distance
person v78    schedule 04.10.2014    source источник

Ответы (1)


arrow_upward
13
arrow_downward

Вы можете рассчитать расстояние редактирования за время O(min(n, m) * s), используя следующую простую идею:

Рассмотрим i-ю строку в DP-таблице.

Итак, если мы знаем, что ответ ‹= s, то нас интересуют клетки с координатами (i, i - s), (i, i - s + 1), ... ,(i, i + s). Потому что в других ячейках ответ строго больше s.

Например, предположим, что мы знаем, что расстояние редактирования между «абакаба» и «баадба» меньше 3.

DP-таблица для этих строк

Итак, мы можем пропустить красные ячейки, потому что они имеют значение больше, чем s.

Асимптотика алгоритма O(min(n, m) * s), поскольку мы вычисляем s клеток слева и справа от главной диагонали.

person Nikita Sivukhin    schedule 04.10.2014
comment
но каждая запись (i, j) таблицы зависит от (i-1, j-1), (i-1, j), (i, j-1) записей. Как найти (5,2),(4,1) и т. д. записи таблицы в общем случае, когда a[i]!=b[j] (0 индексировано)? - person v78; 04.10.2014
comment
Если какая-то ячейка зависит от красной ячейки, мы можем считать, что красная ячейка имеет значение s. Конечно, с помощью этого алгоритма мы не можем правильно вычислить все значения. Важен тот факт, что этот алгоритм корректно вычисляет все ячейки со значением не более s. Благодаря этому мы можем найти расстояние редактирования (потому что мы знаем, что оно не больше s). - person Nikita Sivukhin; 04.10.2014
comment
Можете ли вы предоставить некоторые ссылки для этой идеи .. - person v78; 04.10.2014
comment
ntz-develop.blogspot.ru/2011/03/fuzzy- string-search.html На этой странице вы можете прочитать о расстоянии между строками. Также несколько слов об изложенном выше алгоритме. - person Nikita Sivukhin; 04.10.2014
comment
как определить значение s? - person otaku; 07.10.2014
comment
Мы можем рассчитать S исходя из специфики задачи. Возможно, мы будем игнорировать строки с большим расстоянием редактирования (думаю, это может быть полезно при анализе текста). Но я не знаю быстрого алгоритма, который может вычислить S. (нашел статью в инете: mit.edu/~andoni/papers/compEdit.pdf Может будет интересно) - person Nikita Sivukhin; 08.10.2014
comment
спасибо, посмотрю - person otaku; 10.10.2014