Сжатие целочисленных последовательностей и множеств: различия между версиями

В 1966 году Соломон Голомб предложил изящный гибрид унарного и бинарного кодирования [15]. Он заметил, что при выборе случайного подмножества с n элементами из множества <math>1 \ldots U</math> пробелы между последовательными элементами этого подмножества определяются посредством геометрического распределения вероятностей <math>Prob(x) = p(1 - p)^{x - 1} \;</math>, где p = n/U – вероятность того, что любой выбранный объект является элементом подмножества.

Если элемент b выбран таким образом, что <math>(1 - p)^b = 0,5 \;</math>, это распределение вероятностей предполагает, что кодовое слово для x + b должно быть на один бит длиннее кодового слова для x. Решение уравнения <math>b = log \; 0,5 / log(1 - p) \approx 0,69/p \approx 0,69 \; U/n</math> позволяет получить параметр b, определяющий ''код Голомба''. Для представления целого числа x вычислим значение 1 + ((x — 1) div b) в качестве результата деления и закодируем эту составляющую в виде унарного кода, а затем вычислим остаток в виде 1 + ((x — 1) mod b) и закодируем его в виде минимального двоичного кода, учитывая максимальную границу b. После сокращения эти два компонента образуют кодовое слово для целого числа x. В качестве примера рассмотрим число b = 5. Пять минимальных двоичных кодовых слов для пяти возможных бинарных суффиксов кодовых слов выглядят следующим образом: «00», «01», «10», «110», «111». В этом случае представление числа 8 будет иметь унарный префикс «10», обозначающий частное 2, и остаток от деления в виде минимального двоичного кода «10», представляющего 3, в результате кодовое слово будет иметь вид «10-10».

Как и унарный, код Голомба является бесконечным; однако по построению он допускает настройку согласно другим распределениям вероятностей. В случае <math>b = 2^k \;</math> для целого k используется специальный случай кода Голомба, обычно называемый ''кодом Райса''.

Питер Элиас [15] в 1975 году также предложил гибридный вариант использования унарного и бинарного кодирования. Его семейство кодов определяется рекурсивно, самым простым кодом семейства является унарный.