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

Если элемент b выбран таким образом, что <math>(1 - p)^b = 0,5 \;</math>, это распределение вероятностей предполагает, что кодовое слово для x + b должно быть на один бит длиннее кодового слова для x. Решение уравнения <math>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>C_{\gamma} \;</math> член семейства Elias – <math>C_{\delta} \;</math>. Единственное отличие между ними заключается в том, что префиксная часть кодовых слов в дельта-коде представлена в виде гамма-кода, а не унарного выражения. Следующие элементы семейства кодов Элиаса легко получить, рекурсивно применяя тот же процесс, однако с практической точки зрения Cg оказывается последним полезным членом семейства даже для относительно больших значений x. Чтобы убедиться в этом, заметим, что |Cy(x)| C |Q(x)| в случае <math>x \le 31 \;</math>, что означает, что <math>C_{\delta} \;</math> длиннее следующего кода Элиаса только для значений <math>x \ge 2^{32} \;</math>.

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

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

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

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

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

В литературе описан широкий спектр других вариантов кодирования. Некоторые из них настраивают кодировку за счет изменения границ блоков, определяющих код, и кодирования значения x в виде идентификатора унарного блока, за которым следует минимальное бинарное смещение в пределах обозначенного блока [15].

К примеру, гамма-код Элиаса можно рассматривать как унарно-бинарную комбинацию относительно вектора размеров блоков <math>\langle 2^0, 2^1, 2^2, 2^3, 2^4, ... \rangle</math>. Тейхола [15] предложил гибридный подход, в рамках которого выбирается параметр k, а вектор размеров блоков задается формулой <math>\langle 2^k, 2^{k+1}, 2^{k+2}, 2^{k + 3}, ... \rangle</math>. Одним из вариантов для параметра k является длина в битах медианы последовательности значений, так что первый бит каждого кодового слова делит диапазон наблюдаемых значений символов приблизительно пополам. Другой вариант описали Болди и Винья [2], которые использовали вектор <math>\langle 2k - 1,(2^k - 1)2^k, (2k - 1)2^{2k}, (2k - 1)2^{3k} ,... \rangle</math> для получения семейства кодов, аналитически и эмпирически подходящих для случаев экспоненциального распределения вероятностей, в том числе связанных со сжатием веб-графов. При использовании этого метода значение k обычно принадлежит к диапазону от 2 до 4, а в суффиксной части используется минимальный двоичный код.

Теперь более детально рассмотрим диапазон значений, который может занимать вреднее значение. Поскольку в списке всего n = 10 значений, у нас есть четыре разных значения, предшествующих <math>s_5 \;</math>, и пять значений, следующих после него. Из этого соображения можно вывести более ограниченный диапазон для <math>s_5 \;</math>: lo' = lo + 4 и hi' = hi - 5, что означает, что пятое значение <math>M_2 \;</math> (число 7) можно закодировать при помощи алгоритма минимального двоичного кода в диапазоне [5, 24], используя только 4 бита. Первая строка таблицы 1 иллюстрирует этот процесс.

Важный аспект интерполяционного кода заключается в том, что могут возникнуть ситуации, в которых длина кодового слова равна 0, что становится понятным из равенства lo' = hi'. В этом случае нет необходимости в выдаче битов, поскольку в обозначенный диапазон попадает только одно значение, и декодер может вычислить его. Четыре символа из последовательности <math>M_2 \;</math> могут успешно воспользоваться этой возможностью. Благодаря этому свойству интерполяционное кодирование особенно эффективно в случаях, когда подмножества содержат кластеры последовательных элементов, либо локализованные области подмножеств имеют высокую плотность. В предельном случае, если подмножество содержит все элементы интервала, для его кодировки вообще не требуется ни одного бита при известном значении U. В более общем случае плотные множества могут быть представлены с использованием менее чем одного бита на символ.

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

В 1996 году Питер Фенвик в работе [13] описал аналогичный механизм, использующий арифметическое кодирование, добавив к нему еще одну модификацию. Его алгоритм ''структурного арифметического кодирования'' использует адаптивную оценку вероятностей и двухкомпонентные коды, представленные в виде показателя степени и суффиксной части, при этом обе части вычисляются адаптивным образом. У показателя степени небольшой диапазон, к тому же эта часть кода имеет возможность быстро менять вычисленную вероятность распределения, реагируя на локальные изменения вероятности. Этот двухэтапный процесс кодирования обладает уникальным преимуществом «размазывания» изменений вероятности по диапазону значений, не ограничивая их недавно обработанными фактическими значениями.