Кодирование чисел

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

Байт-кодирование

Каждое число кодируется переменным числом байт. Первые семь бит каждого байта занимают значимые данные числа, восьмой обозначает заканчиваются ли на этом байте данные о текущем числе или продолжаются в следующем байте.

Гамма-кодирование Элиса

При данном кодировании число X представляется как 1+ [logX] (округление до целых снизу) нулевых битов, за которым следует ненулевой бит и само число без старшего бита. Такое кодирование более компактно чем побайтовое кодирование сохраняет числа от 0 до 16.

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

При кодировании данным методом число 1+ [logX] кодируется гамма-кодированием, вслед за чем записывается само число без старшего бита. Данное кодирование эффективнее гамма-кодирования для чисел более 64 и компактнее гамма-кодирования для чисел менее 15.

Параметрические коды Голомба

Преимущество этих кодов в возможности настройки кодирования под конкретные данные. При этом кодировании с параметром k число X представляется из двух частей: частное q=[(X-1)/k]+1 в виде последовательности нулевых бит, заканчивающейся единичным битом и бинарного представления остатка r=X-(q*k)-1. Показано, что минимальное число бит при кодировании случайной последовательности чисел при равномерном их распределении достигается при k=0.69*mean(Х), где mean(Х) – медиана кодируемой последовательности.