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

Постановка задачи

Предположим, что необходимо представить сообщение [math]\displaystyle{ M = \langle s_1, s_2, ..., s_n \rangle }[/math], состоящее из n = |M| символов, в котором каждый символ [math]\displaystyle{ s_i \; }[/math] представляет собой целое число в диапазоне [math]\displaystyle{ 1 \le s_i \le U \; }[/math], верхняя граница U которого может быть или не быть известна и может быть или не быть конечной. Сообщения в такой форме часто встречаются на выходе некоторых этапов моделирования в системах сжатия данных. Задача заключается в представлении сообщения на базе бинарного выходного алфавита {0, 1} при помощи минимально возможного количества выходных бит. Специальный случай задачи имеет место, когда элементы сообщения являются строго возрастающими, т. е. [math]\displaystyle{ s_i \lt s_{i+1} \; }[/math]. В этом случае можно считать, что сообщение M определяет подмножество {1, 2, ..., U}. Примерами такого использования могут быть хранение множеств IP-адресов или кодов товаров, а также регистрация гиперссылок-адресов в графовом представлении сети Интернет.

Основным ограничением в этой задаче может оказаться невозможность предположить, что [math]\displaystyle{ n \gg U \; }[/math]. Иначе говоря, необходимо предполагать, что сообщение M оказывается слишком коротким (относительно совокупности U), чтобы гарантировать вычисление относящегося к M кода. Тем не менее, в случае строгого возрастания элементов гарантированно выполняется соотношение [math]\displaystyle{ n \le U \; }[/math]. Далее в качестве примера будет использоваться сообщение [math]\displaystyle{ M_1 = \langle 1, 3, 1, 1, 1, 10, 8, 2, 1, 1 \rangle \; }[/math]. Заметим, что любое сообщение M может быть преобразовано в другое сообщение M' на базе алфавита U' = Un при помощи префиксных сумм. Это преобразование является обратимым, обратная операция носит название «нахождения пробелов».

Основные результаты

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

Унарный и бинарный код

В качестве первого примера рассмотрим метод унарного кодирования, в котором символ x представлен в виде x-1 бит в значении «1», после которых идет один бит в значении «0». К примеру, три первых символа сообщения [math]\displaystyle{ M_1 \; }[/math] будут кодироваться последовательностью «0-110-0»; дефисы здесь имеют исключительно иллюстративную цель и не являются частью кодированного представления. Поскольку унарный код символа x имеет длину ровно x бит, для этого способа кодирования крайне предпочтительны небольшие целые числа; он имеет соответствующее идеальное распределение вероятностей появления символов (распределение, для которого данный конкретный шаблон длин кодовых слов позволяет получить минимальную длину сообщения), задаваемое формулой [math]\displaystyle{ Prob(x) = 2^{-x} \; }[/math].

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

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

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

Коды Голомба

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

Если элемент b выбран таким образом, что [math]\displaystyle{ (1 - p)^b = 0,5 \; }[/math], это распределение вероятностей предполагает, что кодовое слово для x + b должно быть на один бит длиннее кодового слова для x. Решение уравнения [math]\displaystyle{ 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».

Как и унарный, код Голомба является бесконечным; однако по построению он допускает настройку согласно другим распределениям вероятностей. В случае [math]\displaystyle{ b = 2^k \; }[/math] для целого k используется специальный случай кода Голомба, обычно называемый кодом Райса.

Коды Элиаса

Питер Элиас [15] в 1975 году также предложил гибридный вариант использования унарного и бинарного кодирования. Его семейство кодов определяется рекурсивно, самым простым кодом семейства является унарный.

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