Парное выравнивание длинных последовательностей строк

Question

Я хочу найти глобально оптимальное (или близкое к оптимальному) попарное выравнивание между двумя длинными (десятками тысяч) последовательностями строк, но алгоритм должен работать на любых последовательностях объектов.Я также хочу использовать свою собственную реализацию функции расстояния для вычисления сходства двух объектов.Для более коротких последовательностей я мог бы использовать алгоритм динамического деформирования во времени (DTW), но алгоритм DTW должен вычислять и хранить матрицу расстояний * m (n, m - длины последовательностей), что невозможно для более длинных последовательностей.Можете ли вы порекомендовать такой алгоритм?Работающая реализация была бы плюсом.

Следующий пример поясняет, что должен делать алгоритм:

Input:
Sequence A: i saw the top of the mountain
Sequence B: then i see top of the mountains

Result:    
Sequence A:      i saw the top of the mountain
Sequence B: then i see     top of the mountains

Answer 1

Не знаю, правильно ли я понял ваши требования, но мне кажется, что вы пытаетесь решить Устойчивую проблему брака .Оригинальное решение Гейла и Шепли в ссылке находится в O (n * m) времени и O (n + m) пространстве, если моя память мне не изменяет.Реализация была довольно простой.Существуют также более поздние решения с различными вариантами задачи.

Вы также можете попытаться решить эту проблему, используя максимальное согласование двудольных графов, например здесь , для получения другого критерия оптимальности.Это также можно сделать в O (n * m).