a := d;
end else begin { помещение непарного ( нечетного ) узла в конец пути }
freq[a] := freq[a] + 1;
a := up[a];
end;
until a = root;
freq[root] := freq[root] + 1;
end { update };
Программа игнорирует проблему переполнения счетчиков частот. Арифметическое
сжатие данных постоянно производит вычисление по формуле a * b / c, и предел
точности результата вычисления определяется размером памяти, выделяемой
промежуточным произведениям и делимым, а не самим целочисленным перемен ным.
Многие 32-битные машины накладывают 32-битовое ограничение на произведения и
делимые, и т.о. на самом деле устанавливают 16-битовый предел на представление
целых чисел a, b и c в вышеуказанном выражении. Когда это ограничение передается
коду самой программе архиватора, то чистый результат имеет ограничение в 16383
для максимального значения, возвращаемого функцией maxrange или значения
freq[root]. Поэтому, если сжатый файл имеет длину более 16383 байтов, необходимо
периодически пересчитывать все частоты в СД, чтобы втиснуть их в этот интервал.
Простой путь для этого - разделить значения всех частот на маленькую константу,
например 2, и округлением вверх предохранить частоты от обнуления.
Значения листьев в дереве накапливаемых частот легко могут быть пересчитаны
делением на 2, но значения внутренних узлов пересчитать на так легко изза
трудности распространения округляемых результатов вверх по дереву. Простейший
способ перестройки дерева показан в следующей процедуре:
procedure rescale;
var
u: upindex;
d: downindex;
begin
for d := succmax to twicemax do
freq[d] := ( freq[d] + 1 ) div 2;
for u := maxchar downto 1 do begin
left[u] := 2 * u;
right[u] := ( 2 * u ) + 1;
freq[u] := freq[left[u]] + freq[right[u]];
up[left[u]] := u;
up[right[u]] := u;
end;
end { rescale };
Характеристика арифметических кодов.
Hа основе алгоpитма Виттена, Нейла и Клири вышепредставленные процедуры были
обьединены в среде языка Паскаль. Как и ожидалось, значительной разницы между
сжатыми текстами, полученными в результате работ первоначального и
модифицированного алгоритмов арифметического сжатия не оказалось. Обычно эти
тексты имеют одинаковую длину.
Рисунок 9 показывает скорость двух этих алгоритмов как функцию от H . Время
представлено в милисекундах на байт исходного текста, а энтропия - в битах на
байт источника. Файлы с 2 битами/байт и 8 битами/байт созданы искусственно, а
остальные представляют собой:
цифровой графический файл, использующий 16 оттенков серого цвета ( 3.49
бит/байт );
текстовой файл ( 4.91 бит/байт исходного текста );
M68000 объектный файл ( 6.02 бит/байт ).
Время измерялось на рабочей станции HP9836 в среде HP-UX.
Как показано на рисунке 9, применение расширения к дереву накапливаемых частот
улучшает алгоритм move-to-front, используемый Виттеном, Нейлом и Клири [12],
только когда сжимаемые данные имеют энтропию больше, чем 6.5 бит/байт. Ниже
этого значения метод move-to-front всегда работает немного лучше расширения.
Т.о. расширение или другие подходы к балансированию дерева накапливаемых частот
вероятно не оправдываются пpи сжатии данных, использующих 256-буквенный алфавит.
Однако, опыты показывают, что для большего алфавита pасширение может быть лучшим
подходом.
Заключение.
Представленный здесь алгоритм расширяемого префикса является вероятно самым
простым и быстрым адаптивным алгоритмом сжатия, основанном на использовании кода
префикса. Его характерные черты - очень небольшое количество требуемой ОП и
локально адаптивное поведение. Когда доступны большие объемы памяти,
использование этого алгоритма вместе с моделью Маркова часто позволяет сжать
данные лучше, чем это делают конкурирующие алгоритмы на этом же объеме памяти.
Преимущества алгоритма расширяющегося префикса нагляднее всего видны при сжатии
графических данных. Локально адаптированный характер алгоритма позволяет сжимать
изображение к меньшему количеству бит, чем самоэнтропия, измеренная у статичного
источника. В итоге, простая модель Маркова, применяемая в алгоритме
расширяющегося префикса, часто позволяет осуществить лучшее сжатие, чем широко
используемый алгоритм Зива-Лемпела на сопоставимом объеме памяти.
Алгоритмы арифметического сжатия данных могут выполняться за время O(H) при
использовании дерева накапливаемых частот, балансируемого эвристическим
расширением для требуемой алгоритмом статистической модели. Это создает новое
ограничение, поэтому простой эвристический метод помещения в начало ( move
-to-front ) является более эффективным для маленьких типовых алфавитов.
И алгоритм расширяющегося префикса, и использование расширения для управления
деревом накапливаемых частот служат полезными иллюстрациями применения
расширения для управления лексикогpафически неупорядоченными деревьями. Идея
поворота, предваряющего расширение дерева, может найти применение и в
нелексикографических деревьях, равно как и понятие полуобоpота для балансировки
таких деревьев. Например, их можно применять для слияния, пpи использовании
двоичного дерева с 2-я путями слияния для построения n-путевого слияния.
Интересно отметить, что по сравнению с другими адаптивными схемами сжатия,
потеря здесь 1 бита из потока сжатых данных является катастрофой! Поэтому
pешение проблемы восстановления этой потери представляет несомненный интерес,
что кроме того предполагает возможность использования таких схем сжатия в
криптографии. Хорошо известно, что сжатие сообщения перед его шифровкой
увеличивает трудность взламывания кода просто потому, что поиск кода основан на
избыточности информации в зашифрованном тексте, а сжатие сокращает это
излишество. Новая возможность, представленная в описанных здесь алгоритмах
сжатия, состоит в использовании начального состояния дерева префикса кодов или
начального состояния дерева накапливаемых частот в качестве ключа для прямого
шифрования в процессе сжатия. Алгоритм арифметического сжатия может кроме того
усложнить работу взломщика кодов тем, что границы букв не обязательно находятся
также и между битами.
Ключевое пространство для такого алгоритма шифрования огромно. Для n букв
алфавита существует n! перестановок на листьях каждого из C деревьев, содержащих
n - 1 внутренних узлов, где C = ( 2i )! / i! ( i+1 )! есть i-ое число Каталана.
Это произведение упрощается к ( 2( n-1 ) )! / ( n-1 )!. Для n = 257 ( 256 букв с
символом end-of-file конца файла ) это будет 512!/256! или что-то меньшее 2 .
Компактное целое представление ключа из этого пространства будет занимать 675
байт, поэтому несомненно такие большие ключи могут поставить в тупик. На
практике одно из решение будет заключаться в начале работы с уже
сбалансированным деревом, как и в рассмотренном здесь алгоритмах сжатия, а затем
расширении этого дерева вокруг каждого символа из ключевой строки,
предоставленной пользователем. Вpяд ли они будет вводить ключи длиной 675 байт,
хотя, чтобы позволить расширению установить дерево во все возможные состояния,
нужны ключи еще длиннее чем этот, но даже короткий ключ может позволить
осуществить шифрование на приемлемом уровне.