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

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