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

Если U точно известно и не является степенью двойки, <math>2^k — U \;</math> кодовых слов можно сократить до длины k — 1 бит, получив ''минимальный двоичный код''. Символам <math>1 \ldots 2^k — U</math> удобно присвоить короткие кодовые слова. При этом кодовые слова для оставшихся символов, <math>(2^k - U + 1) \ldots U</math>, по-прежнему будут иметь длину k бит.

Если элемент 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».