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

Теперь мы имеем дело с двумя рекурсивными подзадачами – передачей левой части h1, 4, 5, 6i, зная, что любое значение должно быть больше lo = 1 и меньше = 7 - 1 = 6, и правой части h17, 25, 27, 28, 29i, зная, что любое значение должно быть больше lo = 7 + 1 = 8 и меньше или равно = 29. Эти два подмножества рекурсивно обрабатываются в порядке, изображенном далее в таблице 1, с расчетом более узких диапазонов [lo, hi] и получением минимального двоичного кода.

Важный аспект интерполяционного кода заключается в том, что могут возникнуть ситуации, в которых длина кодового слова равна 0, что становится понятным из равенства lo0 = hi0. В этом случае нет необходимости в выдаче битов, поскольку в обозначенный диапазон попадает только одно значение, и декодер может вычислить его. Четыре символа из последовательности M2 могут успешно воспользоваться этой возможностью. Благодаря этому свойству интерполяционное кодирование особенно эффективно в случаях, когда подмножества содержат кластеры последовательных элементов, либо локализованные области подмножеств имеют высокую плотность. В предельном случае, если подмножество содержит все элементы интервала, для его кодировки вообще не требуется ни одного бита при известном значении U. В более общем случае плотные множества могут быть представлены с использованием мене чем одного бита на символ.

Ранее было отмечено, что сообщение должно предполагаться относительно коротким по сравнению с полной возможной совокупностью символов и что n <$; U. Фрэнкл и Кляйн [ ] заметили, что последовательность показателей степеней символов (т.е. последовательность значений dlog2sie) в сообщении должна образовывать намного более плотный и компактный диапазон, чем само сообщение, так что можно эффективно использовать упрощенный код в префиксных частях, обозначающих показатель степени, и прямолинейное двоичное кодирование для суффиксных частей. Иными словами, вместо использования для префиксной части унарного кода можно использовать код Хаффмана с минимальной избыточностью.

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

Среди других недавних примеров контекстно-зависимых кодов стоит упомянуть адаптивный последовательный двоичный код (Моффат и Ан [11]) и упакованные двоичные коды (Ан и Моффат [ ]). Уиттен и др. [ ], а также Моффат и Турпин [13] предложили модификации техник кодирования Хаффмана и арифметического кодирования, способные обеспечить более эффективное сжатие в случаях, когда длина сообщения M велика по отношению к размеру исходного алфавита U.