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

Question

Учитывая 2 строки s а также t, Мне нужно найти для каждой подстроки в s изменить расстояние (расстояние Левенштейна) до t, На самом деле мне нужно знать для каждого i положение в s каково минимальное расстояние редактирования для всех подстрок, начинающихся в позиции i,

Например:

t = "ab"    
s = "sdabcb"

И мне нужно получить что-то вроде:

{2,1,0,2,2}

Объяснение:

1st position:
distance("ab", "sd") = 4 ( 2*subst )
distance("ab", "sda") = 3( 2*delete + insert )
distance("ab", "sdab") = 2 ( 2 * delete)
distance("ab", "sdabc") = 3 ( 3 * delete)
distance("ab", "sdabcb") = 4 ( 4 * delete)
So, minimum is 2

2nd position:
distance("ab", "da") = 2 (delete + insert)
distance("ab", "dab") = 1 (delete)
distance("ab", "dabc") = 2 (2*delete)
....
So, minimum is 1

3th position:
distance("ab", "ab") = 0
...
minimum is 0

и так далее.

Конечно, я могу использовать алгоритм перебора для решения этой задачи. Но есть ли более быстрый алгоритм?

Спасибо за помощь.

Answer 1

Алгоритм Вагнера-Фишера дает вам ответ на все префиксы "бесплатно".

http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

Последняя строка матрицы Вагнера-Фишера содержит расстояние редактирования от каждого префикса s в t,

Таким образом, как первый треск на вашу проблему, для каждого i, запустите Wagner-Fischer и выберите самый маленький элемент в последнем ряду.

Мне будет любопытно узнать, знает ли кто-либо еще (или может найти) лучший подход.

Answer 2

Найти подстроки в заданной строке очень легко. Вы берете обычный алгоритм Левенштейна и слегка его модифицируете.

ПЕРВЫЙ: вместо того, чтобы заполнять первую строку матрицы 0,1,2,3,4,5,... вы заполняете ее полностью нулями. (зеленый прямоугольник)

ВТОРОЙ: Затем вы запускаете алгоритм.

ТРЕТЬЕ: Вместо того, чтобы возвращать последнюю ячейку последней строки, вы ищете наименьшее значение в последней строке и возвращаете его. (красный прямоугольник)

Пример: needle: "aba", стог сена: "c abba c" -> result = 1 (преобразование abba -> aba)

Я нашел это здесь: http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/

Я проверил это, и это работает.

Это гораздо быстрее, чем вы предлагаете пошагово проходить через строку, как вы это делаете в своем вопросе. Вы создаете матрицу только один раз.