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

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

Предположим, что необходимо представить сообщение [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], где [math]\displaystyle{ p = \frac{n}{U} }[/math] – вероятность того, что любой выбранный объект является элементом подмножества.

Если элемент 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, при пропуске верхнего бита, кодируются бинарным образом.

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

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

Коды Фибоначчи

Еще один любопытный код был выведен на основе последовательности Фибоначии, которая в данном контексте выглядит следующим образом: [math]\displaystyle{ F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, F_5 = 8 }[/math] и т. д. Представление натурального числа Цекендорфа представляет собой список чисел Фибоначчи, которые в сумме дают нужное число, при этом использование двух последовательных чисел Фибоначчи не допускается. К примеру, число 10 представляет собой сумму [math]\displaystyle{ 2 + 8 = F_2 + F_5 }[/math].

Самый простой код Фибоначчи выводится непосредственно из упорядоченного представления Цекендорфа для нужного числа и содержит бит в значении «0» в i-й позиции кодового слова (считая слева), если [math]\displaystyle{ F_i \; }[/math] не входит в сумму, и «1» – если входит; индексы рассматриваются в порядке возрастания. Поскольку [math]\displaystyle{ F_i \; }[/math] и [math]\displaystyle{ F_{i + 1} \; }[/math] не могут одновременно входить в состав представления, последними двумя битами строки должны быть «01». Добавления справа бита «1», таким образом, будет достаточно для обозначения конца любого кодового слова. Как всегда, из предположения о монотонном возрастании вероятностей появления символов следует, что небольшим значениям присваиваются короткие коды. Единица кодируется значением «1-1», следующими кодовыми словами являются «01-1», «001-1», «101-1», «0001-1» и «1001-1»; дефисы здесь также служат иллюстративным целям.

В силу соотношения [math]\displaystyle{ F_n \approx \phi^n \; }[/math], где [math]\displaystyle{ \phi \; }[/math] – золотое сечение [math]\displaystyle{ \phi = (1 + \sqrt{5})/2 \approx 1,61803 \; }[/math], кодовое слово для x имеет длину примерно [math]\displaystyle{ 1 + log_{\phi} \; x \approx 1 + 1,44 \; log_2 \; x }[/math] бит и оказывается более коротким по сравнению со словами гамма-кода Элиаса для всех значений, кроме x = 1. Оно также не уступает словам дельта-кода Элиаса для широкого диапазона практически важных значений между 2 и [math]\displaystyle{ F_19 = 6765 }[/math]. Возможно также использование кодов Фибоначчи более высокого порядка, с большей минимальной длиной кодового слова, а также с уменьшенными коэффициентами при логарифмическом терме. Фенвик в своей работе [8] выполнил качественный обзор кодов Фибоначчи.

Байт-синхронизованные коды

Выполнение необходимых операций упаковки и распаковки битов для выявления неограниченных последовательностей битов может быть достаточно дорогостоящим с точки зрения пропускной способности функций декодирования. Для решения этой проблемы был разработан целый класс кодов, работающих не с битами, а с байтами - и байт-синхронизированные коды.

Простейшим примером байт-синхронизированного кода может служить восьмибитный аналог механизма гамма-кода Элиаса с чередованием битов. Верхний бит каждого байта зарезервирован для флага, имеющего значение «0» в случае, если этот байт является последним в кодовом слове, и «1», если он не является последним и нужно учитывать также следующий байт. Другие семь битов каждого байта используются для представления данных. К примеру, число 1234 кодируется при помощи двух байтов, «2 09-0 08», и реконструируется при помощи вычисления ([math]\displaystyle{ 209 - 128 + 1) \times 128^0 + (008 + 1) \times 128^1 = 1234 }[/math].

В этом простейшем случае байт-синхронизированного кода используются [math]\displaystyle{ 8 \lceil (log_2 \; x)/7 \rceil }[/math] бит, что делает его асимптотически более эффективным, чем гамма-код Элиаса, требующий [math]\displaystyle{ 1 + 2 \lfloor log_2 \; x \rfloor }[/math] бит. Однако, поскольку минимальная длина кодового слова составляет восемь бит, байт-синхронизированные коды оказываются чрезмерно дорогостоящими для представления небольших чисел.

Декодирование байт-синхронизированных кодов не требует продолжительного времени. Другое полезное свойство такого подхода – возможность быстрого «просмотра» вперед сжатого потока на заданное число кодовых слов. И, наконец, третье преимущество байт-синхронизированных кодов – возможность поиска в сжатом сообщении посредством перевода шаблона поиска в последовательность байтов при помощи того же алгоритма кодирования и последующего применения утилиты побайтового сопоставления с образцом [7]. Если все последние байты имеют нулевые верхние биты, это означает, что единичный прогон дополнительной проверки обнаружил ложные «попадания».

Более эффективный механизм применения байт-синхронизированных кодов был получен в результате наблюдения, заключающегося в том, что в качестве разделителя между байтом-ограничителем и байтом-продолжателем не обязательно должно использоваться принятое ранее число 128, и выбор подходящего числа определяет соответствующие компромиссные соотношения длин кодовых слов [3]. При использовании так называемого (S, C)-байт-синхронизированного подхода выбираются значения S и C, составляющие в сумме S + C = 256, так что каждое кодовое слово состоит из последовательности (пустой или непустой) байтов-продолжателей со значениями, большими или равными S, и заканчивается финальным байтом-ограничителем со значением, меньшим S. Также известны методы, в которых байты применяются в качестве единиц кодирования при выполнении кодирования Хаффмана, использующего либо восьмибитные символы для кодирования, либо семибитные символы с флагами [7]; а также методы, выполняющие частичную перестановку алфавита и не требующие полного отображения [6]. Кулпеппер и Моффат [6] также описали метод кодирования с синхронизацией по байтам, создающий множество кодовых слов на основе байтов, в которых первый байт уникальным образом определяет длину кодового слова. Аналогичным образом можно использовать полубайтовое кодирование, 4-битный аналог байт-синхронизированного подхода, при котором один бит резервируется для флага «ограничитель-продолжатель», а три остальных используются для хранения данных.

Другие статические коды