Введение

Метод сжатия данных без потерь. Кодирование Голомба — это метод сжатия данных без потерь, использующий семейство кодов сжатия данных, разработанных Соломоном В. Голомбом в 1960-х годах. Алфавиты, подчиняющиеся геометрическому распределению, имеют код Голомба в качестве оптимального префиксного кода, что делает кодирование Голомба особенно эффективным в ситуациях, когда малые значения во входном потоке встречаются значительно чаще, чем большие.

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

Кодирование Райса (изобретённое Робертом Ф. Райсом) подразумевает использование подмножества семейства кодов Голомба для создания более простого (но, возможно, не оптимального) префиксного кода. Райс использовал этот набор кодов в адаптивной схеме кодирования; под "кодированием Райса" могут подразумеваться как эта адаптивная схема, так и использование данного подмножества кодов Голомба. В отличие от кода Голомба, имеющего настраиваемый параметр, который может принимать любое положительное целое значение, коды Райса используют параметр, являющийся степенью двойки. Это делает коды Райса удобными для реализации на компьютере, поскольку умножение и деление на 2 можно эффективно выполнять в двоичной арифметике. Райс предложил это более простое подмножество, поскольку геометрические распределения часто изменяются во времени, недостаточно точно известны или и то, и другое, поэтому выбор, казалось бы, оптимального кода может оказаться не столь выгодным. Кодирование Райса применяется в качестве этапа энтропийного кодирования во многих методах сжатия изображений и аудиоданных без потерь.

Использование с подписанными целыми числами

Схема Голомба была разработана для кодирования последовательностей неотрицательных чисел. Однако её легко расширить для работы с последовательностями, содержащими отрицательные числа, используя схему перекрытия и чередования, в которой все значения однозначно и обратимо отображаются на некоторое положительное число. Последовательность начинается так: 0, −1, 1, −2, 2, −3, 3, −4, 4… n-е отрицательное значение (то есть −n) отображается на n-е нечётное число (2n − 1), а m-е положительное значение отображается на m-е чётное число (2m). Это можно математически выразить следующим образом: положительное значение x отображается на 2x, а отрицательное значение y отображается на 2|y| − 1. Такой код может быть использован для упрощения, даже если он не является оптимальным. Действительно оптимальные коды для двустороннего геометрического распределения включают в себя несколько вариантов кода Голомба, зависящих от параметров распределения, в том числе и этот.