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

Основное ограничение на статические коды выражается неравенством Крафта-Макмиллана [13]: если кодовое слово для символа x имеет длину <math>\ell_x \;</math>, то необходимо выполнение неравенства <math>\sum_{x = 1}^U 2^{- \ell_x} \le 1</math> для того, чтобы код был декодируемым слева направо и ни одно кодовое слово не было префиксом любого другого кодового слова. Еще одним важным ограничением является комбинаторная стоимость описания множества. Если подмножество из n элементов множества 1, ..., U выбирается случайным образом, то для описания этого подмножества требуется <math>log_2 \; \binom{U}{n} \approx n \; log_2 \; \frac{U}{n}</math> бит.

У унарного кода есть полезное свойство – бесконечная длина. Однако, за исключением случаев, когда сообщение M состоит главным образом из небольших целых чисел, унарный код является достаточно дорогостоящим. В частности, представление сообщения <math>M = \langle s_1, ..., s_n \rangle</math> в виде унарного кода требует <math>\sum_i s_i \;</math> бит, а если M представляет собой представление подмножества 1...U с пробелами, его длина может составить U бит.

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

В 1966 году Соломон Голомб предложил изящный гибрид унарного и бинарного кодирования [ ]. Он заметил, что при выборе случайного подмножества с n элементами из множества 1 • • • U пробелы между последовательными элементами этого подмножества определяются посредством геометрического распределения вероятностей Prob(x) = p(1 - p)x~l, где p = n/U – вероятность того, что любой выбранный объект является элементом подмножества.

Если элемент b таким образом, что (1 - p)b = 0:5, это распределение вероятностей предполагает, что кодовое слово для x + b должно быть на один бит длиннее кодового слова для x. Решение уравнения b = log0:5/log(1 - p) ?rf 0:69/p ?rf 0:69U/n позволяет получить параметр 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».