Применение расширяющихся деревьев для сжатия данных

Заметьте, что каждая буква, сжатая арифметическим методом требует обраще- ния к процедуре 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ащается вокруг А, имея результатом то, что вес Х сокращается весом А и наращивается весом С. В то же время, поскольку это есть часть повторного пути от А к корню, вес А уве- личивается. Итоговый код будет:

procedure update(c: codetype);
var
 c, d: upindex { пара полувpащаемых узлов };
 a, b: downindex { наследники полувpащемых узлов };
begin
 a := c + succmax;
 repeat { вверх по дереву, чередуя и наращивая }
  c := up[a];
  if c #0root then
  begin { оставшаяся пара }
  d := up[c];
  { обмен между наследниками пары }
  b := left[d];
  if c = b then
  begin
  b := right[d];
  right[d] := a;
  end
  else
  left[d] := a;
  if a = left[c] then
  left[c] := b
  else
  right[c] := b;
  up[a] := d;
  up[b] := c;
  freq[c] := (freq[c] - freq[a]) + freq[b];
  freq[a] := freq[a] + 1;
  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итма Виттена, Нейла и Клири[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асширение может быть лучшим подходом.
Заключение.
Представленный здесь алгоритм расширяемого префикса является вероятно са- мым простым и быстрым адаптивным алгоритмом сжатия, основанном на использова- нии кода префикса. Его характерные черты - очень небольшое количество требуе- мой ОП и локально адаптивное поведение. Когда доступны большие объемы памяти, использование этого алгоритма вместе с моделью Маркова часто позволяет сжать данные лучше, чем это делают конкурирующие алгоритмы на этом же объеме памяти.
Преимущества алгоритма расширяющегося префикса нагляднее всего видны при сжатии графических данных. Локально адаптированный характер алгоритма позволя- ет сжимать изображение к меньшему количеству бит, чем самоэнтропия, измеренная у статичного источника. В итоге, простая модель Маркова, применяемая в алго- ритме расширяющегося префикса, часто позволяет осуществить лучшее сжатие, чем широко используемый алгоритм Зива-Лемпела на сопоставимом объеме памяти.
Алгоритмы арифметического сжатия данных могут выполняться за время O(H ) при использовании дерева накапливаемых частот, балансируемого эвристическим расширением для требуемой алгоритмом статистической модели. Это создает но- вое ограничение, поэтому простой эвристический метод помещения в начало ( move -to-front ) является более эффективным для маленьких типовых алфавитов(4).
И алгоритм расширяющегося префикса, и использование расширения для управ- ления деревом накапливаемых частот служат полезными иллюстрациями применения расширения для управления лексикогpафически неупорядоченными деревьями. Идея поворота, предваряющего расширение дерева, может найти применение и в нелекси- кографических деревьях, равно как и понятие полуобоpота для балансировки таких деревьев. Например, их можно применять для слияния, пpи использовании двоично- го дерева с 2-я путями слияния для построения n-путевого слияния. У Сарасвата уже появлялись подобные идеи при разработке средств слияния деревьев на Проло- ге[7].
Интересно отметить, что по сравнению с другими адаптивными схемами сжатия, потеря здесь 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 байт, хо- тя, чтобы позволить расширению установить дерево во все возможные состояния, нужны ключи еще длиннее чем этот, но даже короткий ключ может позволить осу- ществить шифрование на приемлемом уровне.
------------------------------------------------------------------------------
(1) Такие алгоритмы являются без помех. В этой статье алгоpитмы с помехами или приближенные не рассматриваются.
(2) В [9] в случае тройственной реализации необходим лишний бит на узел, чтобы отличать только левого наследника от только правого, но поскольку дерево кодов префикса целиком двоичное, этот бит здесь не нужен.
(3) Перемены в кодовых стандартах позволяют массиву иметь индексы от 0 до 255 вместо от 1 до 256, что ведет к экономию памяти в обоих алгоритмах.
(4) Алистер Моффэт из мельнбургского университета независимо достиг тех же ре- зультатов используя СД выведенную из имплицитной груды подобного материа- ла.
Литература.
1. Bently,J.l., Sleator,D.D., Tarjan,R.E., and Wei,V.K.
A locally adaptive data compression scheme.
Communications of the ACM. 29, 4 ( Apr. 1986 ), 320-330.
2. Gallagen,R.G.
Information Theory and Reliable Communication.
John Wiley & Sons, New York, 1968.
3. Gallager,R.G.
Variations on a theme by Huffman.
IEEE Trans.Inform.Theory IT-24, 6 ( Nov.1978 ), 666-674.
4. Jones,D.W.
An empirical comparison of priority queue and set inplementations.
Communication of the ACM. 29, 4 ( Apr. 1986 ), 300-311.
5. Knuth,D.E.
Dynamic Huffman coding.
J.Algorithms 6, 2 ( Feb. 1985 ), 163-180.
6. Rubin,F.
Arithmetic stream coding using fixed precision registers.
IEEE Trans.Inform.Theory IT-25, 6 ( Nov. 1979 ), 672-675.
7. Saraswat,V.
Merge trees using splaying - or how to splay in parralel and bottom-up.
PROLOG Digest 5, 22 ( Mar. 27, 1987 ).
8. Sleator,D.D., and Tarjan,R.E.
Self-adjusting binary trees.
In Proceedings of the ACM SIGACT Symposium on Theory of Computing
( Boston, Mass., Apr.25-27 ).ACM, New York, 1983, pp.235-245.
9. Tarjan,R.E., and Sleator,D.D.
Self-adjusting binary search trees.
J.ACM 32, 3 ( July 1985 ), 652-686.
10. Vitter,J.S.
Two papers on dynamic Huffman codes.
Tech.Rep.CS-85-13.Brown University Computer Science,
R.I. Revised Dec.1986.
11. Welch,T.A.
A technique for high-performance data compression.
IEEE Comput. 17, 6 ( June 1984 ), 8-19.
12. Witten,I.H.,Neal,R.M., and Cleary,J.G.
Arithmetic coding for data compression.
Communication of the ACM. 30, 6 ( June 1987 ), 520-540.

DelphiWorld 6.0

Отправить комментарий

Проверка
Антиспам проверка
Image CAPTCHA
...