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

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

Дельта-кодирование (англ. Delta encoding) — способ представления данных в виде разницы (дельты) между последовательными данными вместо самих данных.

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

Вариация дельта-кодирования, которая кодирует различия между префиксами или суффиксами строк, называется инкрементным кодированием. Оно в частности эффективно для отсортированных списков с малыми различиями между строками, такими, например, как список слов из словаря.

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

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

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

Diff-кодирование

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

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

Следующий код на Си осуществляет простую форму in-place дельта-кодирования и декодирования:

#include <sys/types.h>
 
void
delta_encode(char *bp, size_t n)
{
        char last = 0, tmp;
        int i;
 
        for (i = 0; i < n; ++i) {
                tmp = bp[i];
                bp[i] -= last;
                last = tmp;
        }
}
 
void
delta_decode(char *bp, size_t n)
{
        char last = 0;
        int i;
 
        for (i = 0; i < n; ++i) {
                bp[i] += last;
                last = bp[i];
        }
}

См. также



Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Дельта-кодирование" в других словарях:

  • Дельта-компрессия — Дельта кодирование (Delta encoding) способ сохранения или передачи данных в форме разницы (дельты) между последовательными данными вместо самих данных. Это часто называется дельта компрессия, потому что некоторые образцы кодирования могут… …   Википедия

  • Кодирование длин серий — (англ. Run length encoding, RLE) или Кодирование повторов  простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании… …   Википедия

  • Кодирование — Кодирование: В Викисловаре есть статья «кодирование» Кодирование информации  процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической… …   Википедия

  • Дельта-код Элиаса —   это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Содержание 1 Кодирование 2 Декодирование 3 Эффективность …   Википедия

  • Дельта модуляция — Дельта модуляция. Метод дельта модуляции (ДМ) был изобретен более 60 лет назад (в 1946 г.). Эффективным способом преобразования сигналов в цифровую форму является дельта модуляция, которая иллюстрируется рисунке(см. ниже). В каждый момент отсчета …   Википедия

  • Кодирование энтропии — кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых… …   Википедия

  • Кодирование с минимальной избыточностью — Кодирование энтропии кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных… …   Википедия

  • Дельта-модуляция — Технологии модуляции  п·Аналоговая модуляция AM · SSB · ЧМ(FM) · ЛЧМ · ФМ(PM) · СКМ Цифровая модуляция АМн …   Википедия

  • Кодирование Шеннона-Фано — Алгоритм Шеннона Фано  один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм… …   Википедия

  • Кодирование Хаффмана — Алгоритм Хаффмана (англ. Huffman) адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»