Первоначально единственной информацией, известной о букве узла дерева i, есть частота этой буквы freq[i]. Это означает, что интервал [0, freq[i]) будет соответствовать какойлибо букве, если весь алфавит состоит из нее одной. Дано: интервал [a, b) связан с некоторым листом поддерева с корнем в узле i, тогда может быть вычислен интервал, связанный с этим листом в поддереве up[i]. Если i - левый наследник, то это просто интервал [ a, b ), если правый, то - [ a + d, b + d ), где d = freq[up[i]] - freq[i], или, что одно и то же: d = freq[left[up[i]]].

Если проблема сохранения сбалансированности в дереве накапливаемых частот не стоит, то функция update будет тривиальной, состоящей из обхода дерева от изменяемого листа до корня, сопровождающегося увеличением значения каждого встреченного узла на единицу. В противном случае время, затраченное на операции findletter, findrange и update при первоначально сбалансированном дереве будет в сpеднем O(log n) на одну букву для n-буквенного алфавита. Это лучше, чем худший вариант O(n), достигаемый посредством применения линейной СД (с организацией move-to-front или без нее ), но может быть улучшено еще.
Заметьте, что каждая буква, сжатая арифметическим методом требует обращения к процедуре findrange, за которым следует вызов update. Т.о. путь от корня к букве в дереве накапливаемых частот будет проделан дважды во время сжатия и дважды во время развертывания. Минимизация общего времени сжатия или развертывания сообщения требует минимизации общей длины всех путей, пройденных в дереве. Если частоты букв известны заранее, то статичное дерево Хаффмана будет минимизировать длину этого маршрута! Длина пути для сообщения S будет ограничена значением 2(Hs(S) + C(S)), где C(S) - количество букв в строке, а множитель 2 отражает тот факт, что каждый маршрут проходится дважды.
Нет смысла в использовании дерева накапливаемых частот, если все вероятности известны заранее, что позволяет применять простую поисковую таблицу для нахождения вероятностей. Если они неизвестны, то оптимальный Л-алгоритм Уиттера может быть легко модифицирован для управления деревом накапливаемых частот, причем длина пути обхода дерева, имеющая место во время сжатия или развертывания не будет превышать значение 2( H (S) + C(S) ). Аналогично можно использовать алгоритм расширяющегося префикса, дающего ограничение O(H (S)) для длины пути, но при большем постоянном множителе. Ранее пpиведенные опытные результаты показывают, что эти постоянные множители более чем компенсируются простотой алгоритма расширяющегося префикса.
x w x - A + C w
A -----------o------------o C -----------o------------o
| | | |
| =====> | |
| | | |
B C B A + 1
Рисунок 8: Полуобоpот в дереве накапливаемых частот
В соответствии с этим алгоритмом операции расширения не нужно затрагивать информации внутренних узлов дерева. Когда расширение выполняется как часть операции update, каждая операция полувpащения должна предохранять инвариацию регулирования весов узлов дерева. На рисунке 8 дерево полувpащается вокруг А, имея результатом то, что вес Х сокращается весом А и наращивается весом С. В то же время, поскольку это есть часть повторного пути от А к корню, вес А увеличивается. Итоговый код будет:

Программа игнорирует проблему переполнения счетчиков частот. Арифметическое сжатие данных постоянно производит вычисление по формуле a * b / c, и предел точности результата вычисления определяется размером памяти, выделяемой промежуточным произведениям и делимым, а не самим целочисленным переменным. Многие 32-битные машины накладывают 32-битовое ограничение на произведения и делимые, и т.о. на самом деле устанавливают 16-битовый предел на представление целых чисел a, b и c в вышеуказанном выражении. Когда это ограничение передается коду самой программе архиватора, то чистый результат имеет ограничение в 16383 для максимального значения, возвращаемого функцией maxrange или значения freq[root]. Поэтому, если сжатый файл имеет длину более 16383 байтов, необходимо периодически пересчитывать все частоты в СД, чтобы втиснуть их в этот интервал. Простой путь для этого - разделить значения всех частот на маленькую константу, например 2, и округлением вверх предохранить частоты от обнуления.
Значения листьев в дереве накапливаемых частот легко могут быть пересчитаны делением на 2, но значения внутренних узлов пересчитать на так легко изза трудности распространения округляемых результатов вверх по дереву. Простейший способ перестройки дерева показан в следующей процедуре:

Характеристика арифметических кодов
Hа основе алгоpитма Виттена, Нейла и Клири[12] вышепредставленные процедуры были обьединены в среде языка Паскаль. Как и ожидалось, значительной разницы между сжатыми текстами, полученными в результате работ первоначального и модифицированного алгоритмов арифметического сжатия не оказалось. Обычно эти тексты имеют одинаковую длину.
:
3 | Объектный
| Текстовой
| Графический
|
2 |
s 10 |
----- |
C(S) |
1 |
|
| o - Пеpвоначальный (move-to-front)
| o - Модифициpованный (pасшиpяющиеся деpевья)
0 |-------|-------|-------|-------|-------|-------|-------|-------|
0 1 2 3 4 5 6 7 8
H (S) / C(S)
Рисунок 9: Характеристика алгоритмов арифметического сжатия
Рисунок 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асширение может быть лучшим подходом.
Заключение
Представленный здесь алгоритм расширяемого префикса является вероятно самым простым и быстрым адаптивным алгоритмом сжатия, основанном на использовании кода префикса. Его характерные черты - очень небольшое количество требуемой ОП и локально адаптивное поведение. Когда доступны большие объемы памяти, использование этого алгоритма вместе с моделью Маркова часто позволяет сжать данные лучше, чем это делают конкурирующие алгоритмы на этом же объеме памяти.