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

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

Предположим, что необходимо представить сообщение M = hs1;s2... sni, состоящее из и = jMj символов, в котором каждый символ si представляет собой целое число в диапазоне 1 < si < U, верхняя граница U которого может быть или не быть известна и может быть или не быть конечной. Сообщения в такой форме часто встречаются на выходе некоторых этапов моделирования в системах сжатия данных. Задача заключается в представлении сообщения на базе бинарного выходного алфавита {0, 1} при помощи минимально возможного количества выходных бит. Специальный случай задачи имеет место, когда элементы сообщения являются строго возрастающими, т.е. si < si+1. В этом случае можно считать, что сообщение M определяет подмножество {1, 2, ..., U}. Примерами такого использования могут быть хранение множеств IP-адресов или кодов товаров, а также регистрация гиперссылок-адресов в графовом представлении сети Интернет.

Основным ограничением в этой задаче может оказаться невозможность предположить, что n > U. Иначе говоря, необходимо предполагать, что сообщение M оказывается слишком коротким (относительно совокупности U), чтобы гарантировать вычисление относящегося к M кода. Тем не менее, в случае строгого возрастания элементов гарантированно выполняется соотношение n < U. Далее в качестве примера будет использоваться сообщение M1 = h1, 3, 1, 1, 1, 10, 8, 2, 1, 1i. Заметим, что любое сообщение M может быть преобразовано в другое сообщение M0 на базе алфавита U0 = Un при помощи префиксных сумм. Это преобразование является обратимым, обратная операция носит название «нахождения разностей».

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

Основное ограничение на статические коды выражается неравенством Крафта-Макмиллана ([ ]): если кодовое слово для символа x имеет длину lx, то необходимо выполнение неравенства Y^=\ 2~^* 5 1 для того, чтобы код был декодируемым слева направо и ни одно кодовое слово не было префиксом любого другого кодового слова. Еще одним важным ограничением является комбинаторная стоимость описания множества. Если подмножество из n элементов множества 1, ..., U выбирается случайным образом, то для описания этого подмножества требуется log2 (n) Јrf nlog2(U/n) бит.

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

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

У унарного кода есть полезное свойство – бесконечная длина. Однако, за исключением случаев, когда сообщение M состоит главным образом из небольших целых чисел, унарный код является достаточно дорогостоящим. В частности, представление сообщения M = hs1, …, sni в виде унарного кода требует Pi si бит, а если M представляет собой представление подмножества 1, ..., U с пробелами, его длина может составить U бит.

Лучшим известным кодом для вычислений считается бинарный (или двоичный). Если 2k~l < U < 2k для некоторого целочисленного k, то символы 1 < si < U могут быть представлены k > log2 U битами каждый. В этом случае код является конечным, а идеальное распределение вероятности задается формулой Prob(x) = 2 k. В случае U = 2k имеет место соотношение Prob(x) = 2~ъ^п = 1/ n.

Если U точно известно и не является степенью двойки, 2k — U кодовых слов можно сократить до длины 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».

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

Коды Элиаса

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