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

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

9 голосов
/ 15 ноября 2011

Дано 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

и т. Д.

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

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

Ответы [ 2 ]

4 голосов
/ 14 июня 2016

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

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

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

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

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

enter image description here

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

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

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

4 голосов
/ 15 ноября 2011

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

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

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

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

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

...