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

Лучшим известным кодом для вычислений считается ''бинарный'' (или ''двоичный''). Если <math>2^{k - l} < U \le 2^k \;</math> для некоторого целого k, то символы <math>1 \le s_i \le U \;</math> могут быть представлены <math>k \ge log_2 \; U</math> битами каждый. В этом случае код является ''конечным'', а идеальное распределение вероятности задается формулой <math>Prob(x) = 2^{-k} \;</math>. В случае <math>U = 2^k \;</math> имеет место соотношение <math>Prob(x) = 2^{-log_2 \; n} = 1/n</math>.