Чередование дельт или переплетение SCCS — это метод, используемый системой контроля исходного кода для хранения всех версий файла. Все строки из всех редакций «сплетены» вместе в единый блок данных с вкраплениями управляющих инструкций, указывающих, какие строки в какие ревизии файла включены. Чередование дельт традиционно реализуется с учетом строковых текстовых файлов, хотя ничто не мешает применить этот метод и к двоичным файлам.
Чередование дельт было впервые реализовано Марком Рочкиндом в SCCS в 1975 году. Его конструкция делает все версии доступными одновременно, так что для получения любой версии требуется одинаковое время. Он также содержит достаточную информацию для идентификации автора каждой строки (обвинения) в одном блоке. [1] С другой стороны, поскольку анализируются все ревизии файла, каждая операция становится медленнее по мере добавления новых ревизий. Термин «чередующаяся дельта» был придуман позже, в 1982 году, Уолтером Ф. Тичи , автором системы контроля версий , которая сравнивает переплетение SCCS с его новым механизмом обратной дельты в RCS. [2]
В SCCS следующий блок переплетения
^ АИ 1 ^ AD 2 фу ^ АЭ 2 бар ^ АИ 2 Баз ^ АЭ 2 ^ АЭ 1
представляет файл, содержащий строки «foo» и «bar» в первой версии и строки «bar» и «baz» во второй версии. Строка «^A» обозначает символ управления-A.
Линии управления в чередующемся дельта-блоке имеют следующее значение: [3]
Время, необходимое для извлечения любой ревизии из такого чередующегося дельта-блока, пропорционально размеру архива. Размер архива — это сумма размеров всех разных строк во всех ревизиях.
Чтобы извлечь конкретную ревизию, необходимо создать массив структур, сообщающий, будет ли конкретный блок, помеченный серийным номером в чередующихся дельтах, скопирован на выход или нет. Исходная реализация SCCS требует ок. 100 байт памяти для каждого серийного номера в дельтах, чтобы знать, как извлечь конкретную версию. Таким образом, для распаковки файла истории SCCS с одним миллионом дельт потребуется 100 МБ виртуальной памяти. Размер можно уменьшить прибл. 32 байта на дельту, если извлечение файла с аннотациями не требуется.
Преимущества метода плетения заключаются в следующем:
Bazaar намеревался использовать чередующиеся дельты в 2006 году [5] , но от него отказались из-за низкой производительности после того, как оно было фактически реализовано в bzr 0.1. Он по-прежнему предоставляет алгоритм слияния в стиле переплетения. [6]