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

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

Моффат и Стювер [ ] предложили оффлайновый алгоритм, который обрабатывает сообщение как единое целое – в данном случае не потому, что параметр требует вычисления (как это происходит при использовании двоичного кода), но потому, что символы сообщения кодируются непоследовательно. Предложенный ими интерполяционный код представляет собой рекурсивный метод кодирования, способный обеспечить исключительно компактное представление – особенно в случае, если пробелы не являются независимыми друг от друга.

Рассмотрим сообщение, представленное в виде подмножеств, аналогично последовательности M2 в таблице 1. Предположим, что программа-декодер знает о том, что наибольшее значение в подмножестве не превышает 29. В таком случае про любой элемент в последовательности M можно сказать, что он больше или равен lo = 1 и меньше или равен hi = 29, и 29 различных вариантов могут быть закодированы при помощи двоичного кода, занимая менее dlog2(29 — 1 + 1)e = 5 бит каждый. В частности, среднее значение в M2, в данном примере s5 = 7 (неважно, какое именно среднее значение будет выбрано), определенно может быть передано декодеру при помощи пяти бит. После того, как среднее значение будет определено, остальные значения могут быть закодированы в рамках более точных диапазонов, в силу чего для каждого из них может потребоваться менее пяти бит.

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