Алгоритм редактирования расстояния (где можно вносить изменения во все подстроки)

Question

Существуют ли примеры алгоритмов для определения расстояния редактирования между 2 строками, когда есть дополнительные примитивные операции (стандарт - вставка, удаление, транспонирование и замена одного символа), которые работают со всей подстрокой.Примеры возможных дополнительных примитивных операций:

1) Функция дублирования - которая копирует любую подстроку и вставляет ее в случае необходимости

2) Функция перемещения - которая перемещает любую подстроку в новое место

Используя их, если d & D - это расстояние Левенштейна, но D также включает 1) и 2), d ("Sheep", "SheepBeep") = 4 (так как необходимо сделать 4 вставки), но D ("Sheep", "SheepBeep") = 2 (вставьте "B", затем продублируйте "eep").Аналогично, d ("CarDog", "DogCar") = 6, но D ("CarDog", "DogCar") = 1 на 2).

Существуют ли (простые) модификации, которые можно внести в Levenstein Distance алгоритм для достижения этой цели?

Answer 1

Наличие только вставки, удаления и перемещения приводит к NP-сложной проблеме .Кажется очень маловероятным, что добавление дубликатов, транспонирование и замена делает это снова проще.Таким образом, подходы с полиномиальным временем, такие как динамическое программирование Левенштейна, вряд ли будут работать.

Подобные проблемы также рассматривались в биоинформатике под такими терминами, как «перестройка генома» и «расстояние перемещения».