Дельта-кодирование

Дельта-кодирование — это метод сжатия данных, в котором вместо самих значений хранятся разности (дельты) между последовательными элементами данных. Основная идея заключается в том, что если данные меняются плавно (например, монотонный сигнал, видеоряд с малым изменением соседних кадров или отсчёты аудиосигнала), значения дельт будут малыми, что позволяет эффективно использовать коды переменной длины или уменьшить разрядность.

История

Метод дельта-кодирования впервые систематически описан в 1948 году Клодом Шенноном в работе «Математическая теория связи» как один из методов снижения избыточности. Однако практическое применение началось в 1950-х годах в системах телеметрии и цифровой связи. В СССР дельта-кодирование активно применялось с 1960-х годов для передачи телеметрических данных с космических аппаратов (например, система «Зенит»).

В 1970-х годах метод стал основой для алгоритмов сжатия изображений и видео, в частности для стандартов MPEG и JPEG. В современных системах дельта-кодирование используется в форматах FLAC, WavPack, некоторых версий PNG, а также в базах данных для эффективного хранения временных рядов.

Принцип работы

Основной алгоритм дельта-кодирования заключается в следующем:

1. Исходная последовательность данных: \( x_1, x_2, x_3, \dots, x_n \)
2. Вычисление дельт: \( \Delta_1 = x_1 \), \( \Delta_i = x_i - x_{i-1} \) для \( i \ge 2 \)
3. Сохранение или передача последовательности дельт \( \Delta_1, \Delta_2, \dots, \Delta_n \)

Обратное преобразование восстанавливает исходные данные:

• \( x_1 = \Delta_1 \)
• \( x_i = x_{i-1} + \Delta_i \)

Пример на числах

Исходные данные: [100, 102, 105, 103, 108] Дельта-кодирование: [100, 2, 3, -2, 5]

В данном случае дельты имеют малый разброс относительно больших исходных чисел. Если бы исходные данные были [1000000, 1000002, 1000005], дельта-кодирование дало бы [1000000, 2, 3] — то есть дельты требуют на порядок меньше бит для хранения.

Классификация методов

По типу вычисляемой разности

1. Простое (линейное) дельта-кодирование — разность между соседними элементами. Самый распространённый вариант.
2. Предсказательное дельта-кодирование с адаптацией — предсказание следующего значения по нескольким предыдущим (например, линейная экстраполяция). Используется в аудиокодеках и сжатии изображений.
3. Дифференциальное импульсно-кодовая модуляция (ДИКМ, DPCM) — вариант для аналого-цифрового преобразования сигналов.
4. Блочное дельта-кодирование — вычисление дельт не последовательно, а внутри блоков фиксированного размера.

По контексту применения

1. Сжатие временных рядов — базы данных мониторинга, IoT-устройства, метеоданные.
2. Сжатие изображений — предиктор для соседних пикселей (например, в PNG используется фильтр Sub, который вычисляет разность с пикселем слева).
3. Сжатие видео — межкадровая разность (между соседними кадрами) и внутрикадровая разность (между макроблоками).
4. Сжатие аудио — DPCM в кодеках типа ADPCM.
5. Сжатие текстовых данных — для строк, где меняются лишь отдельные символы.

Характеристики и ограничения

Преимущества

• Простота реализации — алгоритм требует минимальных вычислительных ресурсов и памяти.
• Эффективность для гладких данных — при малых изменениях между последовательными значениями дельты могут быть закодированы меньшим числом бит.
• Без потерь — дельта-кодирование полностью обратимо.
• Поддержка параллельной обработки — возможно вычисление дельт независимо для отдельных блоков.

Недостатки

• Чувствительность к ошибкам — единственная ошибка в переданной дельте распространяется на все последующие значения (эффект снежного кома). Для борьбы с этим используют периодические референсные точки.
• Неэффективность при резких скачках — если данные содержат большие перепады, дельты могут быть не менее велики, чем исходные значения.
• Зависимость от порядка данных — для несортированных последовательностей метод не даёт выигрыша.
• Неприменимость к категориальным данным — разность между категориями не определена.

Применение в современных системах

Сжатие изображений

В формате PNG используется фильтр Sub (разность с пикселем слева), Up (разность с пикселем сверху), Average (усреднение) и Paeth (предиктор на основе трёх соседей). Для каждого байта строки изображения выбирается наилучший предиктор, после чего выполняется сжатие через Deflate.

Сжатие видео

В стандартах MPEG-1/2/4, H.264, H.265 видео кодируется с использованием межкадрового дельта-кодирования: по кадрам вычисляется разность между текущим кадром и предсказанным на основе предыдущего. Эти разности (остатки) сжимаются с помощью преобразования Фурье (DCT) и квантования.

Сжатие аудио

Алгоритм ADPCM (Adaptive Differential Pulse Code Modulation) используется в стандартах телефонной связи G.711 и G.726. Разность между отсчётами кодируется адаптивным числом бит (от 2 до 5 бит на отсчёт). Это позволяет достичь сжатия в 4–8 раз без заметных потерь качества.

Базы данных временных рядов

СУБД InfluxDB, TimescaleDB, Prometheus и ClickHouse используют дельта-кодирование для хранения метрик мониторинга (температура, загрузка CPU). Например, для последовательности [150, 151, 152, 153] дельтами будут [150, 1, 1, 1], что занимает в памяти на 75% меньше.

Системы резервного копирования

Многие системы бэкапа (rsync, duplicity, rdiff-backup) используют дельта-кодирование для создания инкрементных копий — хранятся только различия между версиями файлов.

Интересные факты

1. Первый практический КПК «Newton» компании Apple (1993) использовал дельта-кодирование для распознавания рукописного текста.
2. В криптографии дельта-кодирование иногда применяется для маскировки статистических закономерностей, хотя это не считается надёжным методом.
3. Алгоритм Huffman часто комбинируют с дельта-кодированием: сначала вычисляют дельты, затем сжимают их кодом переменной длины.
4. В советских системах передачи данных «Коршун» (1960-е) использовалось дельта-кодирование для сжатия телеметрии с ракет.

Критика и альтернативы

Основная критика дельта-кодирования связана с распространением ошибок (error propagation). В современных системах для видео и аудио это решается периодической вставкой I-кадров (интракодеров), которые кодируются без дельт. Для баз данных применяют чексуммы и транзакционные журналы, чтобы локализовать повреждения.

Как альтернативы для сжатия плавно меняющихся данных рассматриваются:

• Преобразование Фурье (DCT) — основной метод в JPEG и MPEG, разделяющий сигнал на частотные компоненты.
• Вейвлет-преобразование — используется в JPEG 2000, даёт лучшее сжатие, но сложнее в реализации.
• LZ-алгоритмы (LZ77, LZ78) — словарные методы, эффективные для текстов и данных с повторяющимися шаблонами.

Источники

1. Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal.
2. Salomon, D. (2007). Data Compression: The Complete Reference. Springer.
3. Sayood, K. (2017). Introduction to Data Compression. Morgan Kaufmann.
4. Wallace, G. K. (1992). The JPEG Still Picture Compression Standard. IEEE Transactions on Consumer Electronics.
5. Документация к СУБД ClickHouse: раздел «Сжатие данных».
6. ISO/IEC 10918-1 (JPEG), ITU-T Recommendation H.264 (AVC).