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

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

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