В информатике проблема исправления строк в строки относится к определению минимальной последовательности операций редактирования, необходимых для изменения одной строки в другую (т. е. вычислению кратчайшего расстояния редактирования ). Каждый тип операции редактирования имеет свое собственное значение стоимости. [1] Одна операция редактирования может изменять один символ строки на другой (стоимость W C ), удалять символ (стоимость W D ) или вставлять новый символ (стоимость W I ). [2]
Если все операции редактирования имеют одинаковую удельную стоимость (W C = W D = W I = 1), то задача та же, что и вычисление расстояния Левенштейна двух строк.
Существует несколько алгоритмов, обеспечивающих эффективный способ определения расстояния между строками и указания минимального количества требуемых операций преобразования. [3] [4] Такие алгоритмы особенно полезны для операций создания дельты , где что-то хранится как набор различий относительно базовой версии. Это позволяет хранить несколько версий одного объекта гораздо эффективнее, чем хранить их по отдельности. Это справедливо даже для отдельных версий нескольких объектов, если они не сильно отличаются или находятся между ними. В частности, такие алгоритмы различий используются в молекулярной биологии для обеспечения некоторой меры родства между различными видами организмов на основе сходства их макромолекул (таких как белки или ДНК ).
Расширенный вариант задачи включает новый тип операции редактирования: перестановку любых двух соседних символов со стоимостью W S .
Эту версию можно решить за полиномиальное время при определенных ограничениях на затраты на операцию редактирования. [2] [5]
Роберт А. Вагнер (1975) показал, что общая задача является NP-полной . В частности, он доказал, что когда W I < W C = W D = ∞ и 0 < W S < ∞ (или, что эквивалентно, изменение и удаление не допускаются), задача является NP-полной. [5]