imported>Gromolyak: /* Примеры реализации */

2026-02-04T23:10:26Z

Примеры реализации

Новая страница

{{другие значения термина|Кодирование|Кодирование}}
'''Дельта-кодирование''' ({{lang-en|Delta encoding}}) — способ представления [[данные|данных]] в виде разницы ([[Дельта (буква)|дельты]]) между последовательными данными вместо самих данных.

Пожалуй, наиболее простой пример заключается в сохранении значений байтов как различия (дельты) между последовательными значениями, в отличие от самих значений. Поэтому вместо 2, 4, 6, 9, 7, мы будем сохранять 2, 2, 2, 3, −2. Это не очень полезно в случае, когда используется само по себе, но может помочь в случае дальнейшей компрессии этих данных, в которых часто встречаются повторяющиеся значения. Например, звуковой формат [[Interchange File Format|IFF]] [[8SVX]] применяет это кодирование к чистым звуковым данным перед тем, как применять к ним компрессию. Только 8-битные звуковые [[семпл]]ы хорошо сжимаются в случае дельта-кодирования, а в случае 16-битных и выше семплов этот метод работает хуже. Поэтому алгоритмы компрессии часто выбирают дельта-кодирование только тогда, когда сжатие с ним лучше, чем без него. Однако, в сжатии видео дельта-фреймы могут значительно уменьшать размер фрейма и используются практически в каждом видеокодеке.

Вариация дельта-кодирования, которая кодирует различия между [[Префикс (информатика)|префиксами]] или [[суффикс]]ами [[Строковый тип|строк]], называется [[инкрементное кодирование|инкрементным кодированием]]. Оно в частности эффективно для отсортированных списков с малыми различиями между строками, такими, например, как список [[слово|слов]] из [[словарь|словаря]].

В дельта-кодированной передаче по сети, где только единичная копия файла доступна на каждом конце коммуникационного канала, используются специальные [[Обнаружение и исправление ошибок|коды коррекции ошибок]] для обнаружения того, какие части файла изменились со времени предыдущей версии.

Дельта-кодирование применяется как предварительный этап для многих алгоритмов сжатия, к примеру [[RLE]], и в [[инвертированный индекс|инвертированных индексах]] поисковых программ. Природа данных, которые будут закодированы, значительно влияет на эффективность сжатия. Дельта-кодирование повышает [[коэффициент сжатия]] в том случае, когда данные имеют маленькую или постоянную вариацию (как, к примеру, градиент на изображении); для данных, сгенерированных генератором случайных чисел с равномерным распределением, коэффициент сжатия изменится не сильно.

Дельта-кодирование делает невозможным произвольный доступ к данным, так как для обращения к элементу массива необходимо просуммировать значения всех предыдущих. Если это все же необходимо, применяется блочный вариант дельта-кодирования, в котором кодируются блоки некоторой заданной длины. Тогда необходимо лишь просуммировать значения с начала блока, которому принадлежит искомый элемент, но не всего файла. Размер блока выбирается в зависимости от приложения, обычно по результатам хронометража.

== Diff-кодирование ==
Следует различать дельта-кодирование и '''diff-кодирование'''. Дельта-кодирование находит разницу между элементами одной последовательности, а diff-кодирование сравнивает два разных источника данных, указывая различия между ними. Diff-кодирование реализовано в стандартной [[Unix]]-утилите [[diff]], а также для сокращения объёма интернет-трафика в протоколе HTTP согласно RFC 3229.

== Примеры реализации ==
Следующий код на [[Си (язык программирования)|Си]] осуществляет простую форму in-place дельта-кодирования и декодирования:

<source lang="c">void delta_encode(unsigned char *buffer, int length)
{
unsigned char last = 0;
for (int i = 0; i < length; ++i)
{
unsigned char current = buffer[i];
buffer[i] -= last;
last = current;
}
}

void delta_decode(unsigned char *buffer, int length)
{
unsigned char last = 0;
for (int i = 0; i < length; ++i)
{
buffer[i] += last;
last = buffer[i];
}
}</source>

== См. также ==
* [[Дельта-модуляция]]

{{rq|
{{нет источников|дата=2012-03-13}}
{{нет сносок|дата=2012-03-13}}
}}
{{методы сжатия}}
{{Системы управления версиями}}

[[Категория:Алгоритмы сжатия без потерь]]
[[Категория:Теория кодирования]]

Дельта-кодирование - История изменений

imported>Gromolyak: /* Примеры реализации */