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

При переходе от одного члена семейства к другому предыдущий член определяет количество бит в стандартном бинарном представлении кодируемого значения x (иначе говоря, значение <math>1 + \lfloor log_2 \; x \rfloor</math>; после определения длины концевые биты x, при пропуске верхнего бита, кодируются бинарным образом.

К примеру, второй член семейства Элиаса, <math>C_{\gamma} \;</math> («гамма-код»), можно рассматривать как унарно-бинарный код: унарный код определяет префиксную часть, представляющую собой степень x, а последующий бинарный отражает величину x в рамках диапазона, обозначенного префиксной частью. Таким образом, первые несколько кодовых слов гамма-кода выглядят как «0», «10-0», «10-1», «110-00» и так далее; дефисы здесь также приведены исключительно в иллюстративных целях. В общем случае кодовое слово в гамма-коде для значения x требует <math>1 + \lfloor log_2 \; x \rfloor</math> бит для унарной префиксной части и <math>\lfloor log_2 \; x \rfloor</math> – для бинарной суффиксной, а идеальное распределение вероятностей задается формулой <math>Prob(x) \ge 1 /(2x^2) \;</math>.

Следующий после <math>C_{\gamma} \;</math> член семейства Elias – <math>C_{\delta} \;</math>. Единственное отличие между ними заключается в том, что префиксная часть кодовых слов в дельта-коде представлена в виде гамма-кода, а не унарного выражения. Следующие элементы семейства кодов Элиаса легко получить, рекурсивно применяя тот же процесс, однако с практической точки зрения Cg оказывается последним полезным членом семейства даже для относительно больших значений x. Чтобы убедиться в этом, заметим, что |Cy(x)| C |Q(x)| в случае x < 31, что означает, что <math>C_{\delta} \;</math> длиннее следующего кода Элиаса только для значений x > 232.