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

Question

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

Answer 1

Вы можете попробовать Метод выделения различий между файлами (через здесь ):

Алгоритм, который использует «ход» оператор описан в П. Геккеля 1978 бумага

(Извините за интерфейс scribd, но я предполагаю, что документ не был OCR'd.)

Answer 2

Резюме для Модели редактирования блока для приблизительного соответствия строк выглядит многообещающе.

Answer 3

Да;Есть много алгоритмов и теорий, связанных с биологией;выравнивание генома и перестройка хромосомы.Не зная ваших данных, действительно сложно упомянуть что-то более конкретное.Я упоминаю сортировку блинов как меру перестановки в другом сообщении stackoverflow , есть также несколько других замечательных вариантов (сжатие, в частности).Конечно, этот метод не сможет разбить ваши данные на блоки.При работе с небольшими данными последовательности у вас не должно возникнуть проблем при создании всех группировок.