Проблема построчной коррекции
В информатике проблема построчной коррекции относится к определению минимальной стоимости последовательности операций редактирования, необходимой для изменения одной строки в другую (т. е. вычислению кратчайшего расстояния редактирования ). Каждый тип операции редактирования имеет свою собственную стоимость. [1] Одной операцией редактирования может быть замена одного символа строки на другой (стоимость W C ), удаление символа (стоимость WD ) или вставка нового символа (стоимость W I ). [2]
Если все операции редактирования имеют одинаковую стоимость единицы (W C = WD = W I = 1), проблема аналогична вычислению расстояния Левенштейна для двух строк.
Существует несколько алгоритмов , обеспечивающих эффективный способ определения расстояния между строками и указания минимального количества необходимых операций преобразования. [3] [4] Такие алгоритмы особенно полезны для операций создания дельты , когда что-то хранится как набор различий относительно базовой версии. Это позволяет хранить несколько версий одного объекта гораздо эффективнее, чем хранить их по отдельности. Это справедливо даже для отдельных версий нескольких объектов, если они не сильно различаются, или чего-то среднего. Примечательно, что такие алгоритмы различия используются в молекулярной биологии для обеспечения некоторой меры родства между различными видами организмов на основе сходства их макромолекул (таких как белки или ДНК ).
Расширение
[ редактировать ]Расширенный вариант задачи включает новый тип операции редактирования: замену любых двух соседних символов стоимостью WS .
Эту версию можно решить за полиномиальное время при определенных ограничениях на затраты на операцию редактирования. [2] [5]
Роберт А. Вагнер (1975) показал, что общая проблема является NP-полной . В частности, он доказал, что когда W I < W C = WD = ∞ и 0 < WS < ∞ (или, что то же самое, изменение и удаление не разрешены), проблема является NP-полной. [5]
Ссылки
[ редактировать ]- ^ Вагнер, Роберт А.; Фишер, Майкл Дж. (1974). «Проблема построчной коррекции» . Журнал АКМ . 21 (1): 168–173. дои : 10.1145/321796.321811 . S2CID 13381535 .
- ^ Jump up to: а б Лоуренс, Рой; Вагнер, Роберт А. (апрель 1975 г.). «Расширение проблемы построчной коррекции» . Журнал АКМ . 22 (2): 177–183. дои : 10.1145/321879.321880 . S2CID 18892193 .
- ^ Редактировать расстояние#Вычисление
- ^ Тичи, Уолтер Ф. (1984). «Проблема построчной коррекции при перемещении блоков» . Транзакции ACM в компьютерных системах . 2 (4): 309–321. дои : 10.1145/357401.357404 . S2CID 14034845 .
- ^ Jump up to: а б Вагнер, Роберт А. (май 1975 г.). «О сложности расширенной задачи построчной коррекции» . Материалы седьмого ежегодного симпозиума ACM по теории вычислений - STOC '75 . стр. 218–223. дои : 10.1145/800116.803771 . ISBN 9781450374194 . S2CID 18705107 .