Учитывая 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
и т.д.
Я могу использовать алгоритм грубой силы для решения этой задачи, конечно. Но есть ли более быстрый алгоритм?
Спасибо за помощь.
Алгоритм Вагнера-Фишера дает вам ответ на все префиксы "бесплатно".
http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
Последняя строка матрицы Вагнера-Фишера содержит расстояние редактирования от каждого префикса от s до t.
Итак, как первая трещина в вашей проблеме, для каждого i запустите Wagner-Fischer и выберите самый маленький элемент в последней строке.
Мне будет интересно узнать, знает ли кто-нибудь еще (или может найти) лучший подход.
Найти подстроки в заданной строке очень легко. Вы берете обычный алгоритм Левенштейна и слегка его модифицируете.
ПЕРВЫЙ: Вместо заполнения первой строки матрицы 0,1,2,3,4,5,... Вы полностью заполняете его нулями. (зеленый прямоangularьник)
ВТОРОЙ: Затем вы запускаете алгоритм.
ТРЕТИЙ: Вместо того, чтобы возвращать последнюю ячейку последней строки, вы ищете наименьшее значение в последней строке и возвращаете его. (красный прямоangularьник)
Пример: игла: "аба", стог сена: "с аба с" → результат = 1 (преобразование аба → аба)
Я проверил это, и это работает.
Это намного быстрее, чем вы предлагаете пошагово проходить через строку, как вы это делаете в своем вопросе. Вы создаете матрицу только один раз.