Сравнение последовательностей с обнаружением перемещенных блоков

Мне нужно сравнить 2 последовательности и найти расстояние между ними. Редактирование может включать операции удаления и вставки (с весом модификации 1 на символ), а также операции блочного перемещения (с весом 0.1 на символ)
. Например:
A B C D E F G H
F G H A B C Y D X E
Блок FGH был перемещен сюда.
Есть ли какой-нибудь существующий алгоритм для эффективного решения этой задачи?

1
задан jifuyo 9 September 2010 в 04:18
поделиться