Проблема коррекции строка-строка
В информатике проблема исправления строк в строки относится к определению минимальной последовательности операций редактирования, необходимых для изменения одной строки в другую (т. е. вычислению кратчайшего расстояния редактирования ). Каждый тип операции редактирования имеет свое собственное значение стоимости. [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]
Ссылки
- ^ Вагнер, Роберт А.; Фишер, Майкл Дж. (1974). «Проблема коррекции строк в строки». Журнал ACM . 21 (1): 168–173. doi : 10.1145/321796.321811 . S2CID 13381535.
- ^ ab Lowrance, Roy; Wagner, Robert A. (апрель 1975 г.). «Расширение проблемы коррекции строк в строки». Journal of the ACM . 22 (2): 177–183. doi : 10.1145/321879.321880 . S2CID 18892193.
- ^ Редактировать расстояние#Вычисление
- ^ Тичи, Уолтер Ф. (1984). «Проблема коррекции строка-в-строку с перемещениями блоков». ACM Transactions on Computer Systems . 2 (4): 309–321. doi : 10.1145/357401.357404 . S2CID 14034845.
- ^ ab Wagner, Robert A. (май 1975). "О сложности расширенной проблемы коррекции строк в строки". Труды седьмого ежегодного симпозиума ACM по теории вычислений - STOC '75 . стр. 218–223. doi :10.1145/800116.803771. ISBN 9781450374194. S2CID 18705107.
