Сжатие целочисленных последовательностей и множеств
Постановка задачи
Предположим, что требуется представить сообщение [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-битный аналог байт-синхронизированного подхода, при котором один бит резервируется для флага «ограничитель-продолжатель», а три остальных используются для хранения данных.
Другие статические коды
В литературе описан широкий спектр других вариантов кодирования. Некоторые из них настраивают кодировку за счет изменения границ блоков, определяющих код, и кодирования значения x в виде идентификатора унарного блока, за которым следует минимальное бинарное смещение в пределах обозначенного блока [15].
К примеру, гамма-код Элиаса можно рассматривать как унарно-бинарную комбинацию относительно вектора размеров блоков [math]\displaystyle{ \langle 2^0, 2^1, 2^2, 2^3, 2^4, ... \rangle }[/math]. Тейхола [15] предложил гибридный подход, в рамках которого выбирается параметр k, а вектор размеров блоков задается формулой [math]\displaystyle{ \langle 2^k, 2^{k+1}, 2^{k+2}, 2^{k + 3}, ... \rangle }[/math]. Одним из вариантов для параметра k является длина в битах медианы последовательности значений, так что первый бит каждого кодового слова делит диапазон наблюдаемых значений символов приблизительно пополам. Другой вариант описали Болди и Винья [2], которые использовали вектор [math]\displaystyle{ \langle 2k - 1,(2^k - 1)2^k, (2k - 1)2^{2k}, (2k - 1)2^{3k} ,... \rangle }[/math] для получения семейства кодов, аналитически и эмпирически подходящих для случаев экспоненциального распределения вероятностей, в том числе связанных со сжатием веб-графов. При использовании этого метода значение k обычно принадлежит к диапазону от 2 до 4, а в суффиксной части используется минимальный двоичный код.
Фенвик [8] представил детальный обзор широкого спектра методов статического кодирования. Чен и др. [4] также недавно рассматривали задачу кодирования сообщений над разреженными алфавитами.
Контекстно-зависимый код
Ранее описанные статические коды используют один и тот же набор присваиваний кодовых слов на протяжении всего процесса кодирования сообщения. Большей эффективности сжатия можно достичь в ситуациях, когда распределение вероятности появления символов является гомогенным локально, но не глобально.
Моффат и Стювер [12] предложили оффлайновый алгоритм, который обрабатывает сообщение как единое целое – в данном случае не потому, что параметр требует вычисления (как это происходит при использовании двоичного кода), но потому, что символы сообщения кодируются непоследовательно. Предложенный ими интерполяционный код представляет собой рекурсивный метод кодирования, способный обеспечить исключительно компактное представление – особенно в случае, если пробелы не являются независимыми друг от друга.
Рассмотрим сообщение, представленное в виде подмножеств, аналогично последовательности [math]\displaystyle{ M_2 \; }[/math] в таблице 1. Предположим, что программа-декодер знает о том, что наибольшее значение в подмножестве не превышает 29. В таком случае про любой элемент в последовательности M можно сказать, что он больше или равен lo = 1 и меньше или равен hi = 29, и 29 различных вариантов могут быть закодированы при помощи двоичного кода, занимая менее [math]\displaystyle{ \lceil log_2(29 - 1 + 1) \rceil = 5 }[/math] бит каждый. В частности, среднее значение в [math]\displaystyle{ M_2 \; }[/math], в данном примере это [math]\displaystyle{ s_5 = 7 \; }[/math] (неважно, какое именно среднее значение будет выбрано), определенно может быть передано декодеру при помощи пяти бит. После того, как среднее значение будет определено, остальные значения могут быть закодированы в рамках более точных диапазонов, в силу чего для каждого из них может потребоваться менее пяти бит.
Теперь более детально рассмотрим диапазон значений, который может занимать вреднее значение. Поскольку в списке всего n = 10 значений, у нас есть четыре разных значения, предшествующих [math]\displaystyle{ s_5 \; }[/math], и пять значений, следующих после него. Из этого соображения можно вывести более ограниченный диапазон для [math]\displaystyle{ s_5 \; }[/math]: lo' = lo + 4 и hi' = hi - 5, что означает, что пятое значение [math]\displaystyle{ M_2 \; }[/math] (число 7) можно закодировать при помощи алгоритма минимального двоичного кода в диапазоне [5, 24], используя только 4 бита. Первая строка таблицы 1 иллюстрирует этот процесс.
Теперь мы имеем дело с двумя рекурсивными подзадачами – передачей левой части [math]\displaystyle{ \langle 1, 4, 5, 6 \rangle }[/math], зная, что любое значение должно быть больше lo = 1 и меньше hi = 7 - 1 = 6, и правой части [math]\displaystyle{ \langle 17, 25, 27, 28, 29 \rangle }[/math], зная, что любое значение должно быть больше lo = 7 + 1 = 8 и меньше или равно hi = 29. Эти два подмножества рекурсивно обрабатываются в порядке, изображенном далее в таблице 1, с расчетом более узких диапазонов [lo', hi'] и получением минимального двоичного кода.
Важный аспект интерполяционного кода заключается в том, что могут возникнуть ситуации, в которых длина кодового слова равна 0, что становится понятным из равенства lo' = hi'. В этом случае нет необходимости в выдаче битов, поскольку в обозначенный диапазон попадает только одно значение, и декодер может вычислить его. Четыре символа из последовательности [math]\displaystyle{ M_2 \; }[/math] могут успешно воспользоваться этой возможностью. Благодаря этому свойству интерполяционное кодирование особенно эффективно в случаях, когда подмножества содержат кластеры последовательных элементов, либо локализованные области подмножеств имеют высокую плотность. В предельном случае, если подмножество содержит все элементы интервала, для его кодировки вообще не требуется ни одного бита при известном значении U. В более общем случае плотные множества могут быть представлены с использованием менее чем одного бита на символ.
В таблице 1 приведен пример интерполяционного кода с использованием (в последнем столбце) минимального двоичного кода для каждого значения в его ограниченном диапазоне. В целях оптимизации можно использовать отцентрированный минимальный двоичный код, чтобы короткие кодовые слова приходились на середину диапазона, а не на его начало, используя тот факт, что среднее значение множества с большей вероятностью будет находиться ближе к середине диапазона элементов, чем к его границам. Для реализации этого расширения требуется тривиальная реструктуризация алгоритма минимального двоичного кодирования; на практике оно оказывается весьма результативным. Однако улучшение не гарантировано, а кроме того, при обработке последовательности M2 использование отцентрированного минимального двоичного кода добавляет один бит к сжатому представлению по сравнению с обычным минимальным двоичным кодом, что показано в таблице .
Чен и др. [5] детально описали техники декодирования интерполяционных кодов.
| Индекс i | Значение [math]\displaystyle{ s_i }[/math] | lo | hi | lo' | hi' | {[math]\displaystyle{ s_i }[/math] – lo’, hi – lo’} | Binary | MinBin |
|---|---|---|---|---|---|---|---|---|
| 5 | 7 | 1 | 29 | 5 | 24 | 2,19 | [math]\displaystyle{ \mbox{00010} }[/math] | [math]\displaystyle{ \mbox{0010} }[/math] |
| 2 | 4 | 1 | 6 | 2 | 4 | 2,2 | [math]\displaystyle{ \mbox{10} }[/math] | [math]\displaystyle{ \mbox{11} }[/math] |
| 1 | 1 | 1 | 3 | 1 | 3 | 0,2 | [math]\displaystyle{ \mbox{00} }[/math] | [math]\displaystyle{ \mbox{0} }[/math] |
| 3 | 5 | 5 | 6 | 5 | 5 | 0,0 | [math]\displaystyle{ \mbox{-} }[/math] | [math]\displaystyle{ \mbox{-} }[/math] |
| 4 | 6 | 6 | 6 | 6 | 6 | 0,0 | [math]\displaystyle{ \mbox{-} }[/math] | [math]\displaystyle{ \mbox{-} }[/math] |
| 8 | 27 | 8 | 29 | 10 | 27 | 17,17 | [math]\displaystyle{ \mbox{01111} }[/math] | [math]\displaystyle{ \mbox{11111} }[/math] |
| 6 | 17 | 8 | 26 | 8 | 25 | 9,17 | [math]\displaystyle{ \mbox{01001} }[/math] | [math]\displaystyle{ \mbox{1001} }[/math] |
| 7 | 25 | 18 | 26 | 18 | 26 | 7,8 | [math]\displaystyle{ \mbox{0111} }[/math] | [math]\displaystyle{ \mbox{1110} }[/math] |
| 9 | 28 | 28 | 29 | 28 | 28 | 0,0 | [math]\displaystyle{ \mbox{-} }[/math] | [math]\displaystyle{ \mbox{-} }[/math] |
| 10 | 29 | 29 | 29 | 29 | 29 | 0,0 | [math]\displaystyle{ \mbox{-} }[/math] | [math]\displaystyle{ \mbox{-} }[/math] |
Таблица 1. Пример кодирования сообщения [math]\displaystyle{ M_2 = \langle 1, 4, 5, 6, 7, 17, 25, 27, 28, 29 \rangle }[/math] при помощи алгоритма интерполяционного кодирования. При использовании минимального двоичного кода требуется в сумме 20 бит. Если lo' = hi', ни одного бита не выводится
Гибридные методы
Ранее было отмечено, что сообщение должно предполагаться относительно коротким по сравнению с полной возможной совокупностью символов и что [math]\displaystyle{ n \ll U \; }[/math]. Фрэнкл и Кляйн [9] заметили, что последовательность показателей степеней символов (т. е. последовательность значений [math]\displaystyle{ \lceil log_2 \; s_i \rceil }[/math]) в сообщении должна образовывать намного более плотный и компактный диапазон, чем само сообщение, так что можно эффективно использовать упрощенный код в префиксных частях, обозначающих показатель степени, и прямолинейное двоичное кодирование для суффиксных частей. Иными словами, вместо использования для префиксной части унарного кода можно использовать код Хаффмана с минимальной избыточностью.
В 1996 году Питер Фенвик в работе [13] описал аналогичный механизм, использующий арифметическое кодирование, добавив к нему еще одну модификацию. Его алгоритм структурного арифметического кодирования использует адаптивную оценку вероятностей и двухкомпонентные коды, представленные в виде показателя степени и суффиксной части, при этом обе части вычисляются адаптивным образом. У показателя степени небольшой диапазон, к тому же эта часть кода имеет возможность быстро менять вычисленную вероятность распределения, реагируя на локальные изменения вероятности. Этот двухэтапный процесс кодирования обладает уникальным преимуществом «размазывания» изменений вероятности по диапазону значений, не ограничивая их недавно обработанными фактическими значениями.
Другие методы кодирования
Среди других недавних примеров контекстно-зависимых кодов стоит упомянуть адаптивный последовательный двоичный код (Моффат и Ан [11]) и упакованные двоичные коды (Ан и Моффат [1]). Уиттен и др. [15], а также Моффат и Турпин [13] предложили модификации техник кодирования Хаффмана и арифметического кодирования, способные обеспечить более эффективное сжатие в случаях, когда длина сообщения M велика по отношению к размеру исходного алфавита U.
Применение
Основной областью применения техник сжатого представления множеств является хранение инвертированных индексов в больших системах поиска по всему тексту – например, у компаний, обеспечивающих поиск по Интернет-ресурсам [15].
Открытые вопросы
В последнее время велась работа над сжатыми представлениями множеств, которые поддерживали бы такие операции, как ранжирование и выбор, не требуя декомпрессии множества (см, например, Гупта и др. [10], Раман и др. [14]). Исследователи активно работают над улучшением этих методов и нахождением баланса между требованиями эффективности сжатия и эффективности доступа к данным.
Экспериментальные результаты
В этой области хорошим тоном являются сравнения на типичных наборах данных реалистичного размера, требующие эффективного сжатия и эффективного же декодирования. Уиттен и др. [15], а также многие другие авторы приводят подробные сведения о фактической эффективности сжатия.
Ссылка на код
На странице http://www.csse.unimelb.edu.au/~alistair/codes/ можно ознакомиться с простой текстовой системой «сжатия», позволяющей исследовать различные типы алгоритмов кодирования, перечисленных в данном материале.
См. также
Литература
1. Anh, V.N., Moffat, A.: Improved word-aligned binary compression for text indexing. IEEE Trans. Knowl. Data Eng. 18(6), 857-861 (2006)
2. Boldi, P., Vigna, S.: Codes for the world-wide web. Internet Math. 2(4), 405-427 (2005)
3. Brisaboa, N.R., Farina, A., Navarro, G., Esteller, M.F.: (S; C)-dense coding: An optimized compression code for natural language text databases. In: Nascimento, M.A. (ed.) Proc. Symp. String Processing and Information Retrieval. LNCS, vol. 2857, pp. 122-136, Manaus, Brazil, October 2003
4. Chen, D., Chiang, Y.J., Memon, N., Wu, X.: Optimal alphabet partitioning for semi-adaptive coding of sources of unknown sparse distributions. In: Storer, J.A., Cohn, M. (eds.) Proc. 2003 IEEE Data Compression Conference, pp. 372-381, IEEE Computer Society Press, Los Alamitos, California, March 2003
5. Cheng, C.S., Shann, J.J.J., Chung, C.P.: Unique-order interpolative coding for fast querying and space-efficient indexing in information retrieval systems. Inf. Process. Manag. 42(2), 407-428 (2006)
6. Culpepper, J.S., Moffat, A.: Enhanced byte codes with restricted prefix properties. In: Consens, M.P., Navarro, G. (eds.) Proc. Symp. String Processing and Information Retrieval. LNCS Volume 3772, pp. 1 -12, Buenos Aires, November 2005
7. de Moura, E.S., Navarro, G., Ziviani, N., Baeza-Yates, R.: Fast and flexible word searching on compressed text. ACM Trans. Inf. Syst. 18(2), 113-139(2000)
8. Fenwick, P.: Universal codes. In: Sayood, K. (ed.) Lossless Compression Handbook, pp. 55-78, Academic Press, Boston (2003)
9. Fraenkel, A.S., Klein, S.T.: Novel compression of sparse bitstrings -Preliminary report. In: Apostolico, A., Galil, Z. (eds) Combinatorial Algorithms on Words, NATO ASI Series F, vol. 12, pp. 169-183. Springer, Berlin (1985)
10. Gupta, A., Hon, W.K., Shah, R., Vitter, J.S.: Compressed data structures: Dictionaries and data-aware measures. In: Storer, J.A., Cohn, M. (eds) Proc. 16th IEEE Data Compression Conference, pp. 213-222, IEEE, Snowbird, Utah, March 2006 Computer Society, Los Alamitos, CA
11. Moffat, A., Anh, V.N.: Binary codes for locally homogeneous sequences. Inf. Process. Lett. 99(5), 75-80 (2006) Source code available from www.cs.mu.oz.au/~alistair/rbuc/
12. Moffat, A., Stuiver, L.: Binary interpolative coding for effective index compression. Inf. Retr. 3(1), 25-47 (2000)
13. Moffat, A., Turpin, A.: Compression and Coding Algorithms. Kluwer Academic Publishers, Boston (2002)
14. Raman, R., Raman, V., Srinivasa Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 233-242, San Francisco, CA, January 2002, SIAM, Philadelphia, PA
15. Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann,San Francisco, (1999)
