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

В литературе описан широкий спектр других вариантов кодирования. Некоторые из них настраивают кодировку за счет изменения границ блоков, определяющих код, и кодирования значения 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. В более общем случае плотные множества могут быть представлены с использованием менее чем одного бита на символ.