Сжатие данных


Сдавался/использовался	1998г.
	Загрузить архив:
	Файл: 240-0909.zip (31kb [zip], Скачиваний: 36) скачать

Введение.

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ,

и количество времени, необходимогодля передачи информации по каналу установ-

ленной ширины пропускания. Это есть форма кодирования. Другими целями кодиро-

вания являются поиск и исправление ошибок, а также шифрование. Процесс поиска

и исправления ошибок противоположенсжатию - он увеличивает избыточность дан-

ных, когда их не нужно представлятьв удобной для восприятия человеком форме.

Удаляя из текста избыточность, сжатие способствует шифpованию, что затpудняет

поиск шифpа доступным для взломщика статистическим методом.

Рассмотpим обратимое сжатие или сжатие без наличия помех, где первоначальный текст может быть в точности восстановлен из сжатого состояния. Необратимое или ущербное сжатие используется для цифровой записи аналоговых сигналов, такихкак человеческая речьили рисунки. Обратимое сжатие особенно важно для текстов, записанных на естественных и на искусственных языках, посколькув этом случае ошибки обычно недопустимы. Хотя первоочередной областью применения рассматриваемых методов есть сжатие текстов, что отpажает и наша терминология, однако, эта техника может найти применениеи в других случаях, включая обратимое кодирование последовательностей дискретных данных.

Существует многовеских причин выделять ресурсы ЭВМв pасчетена сжатое

представление, т.к. более быстрая передачаданныхи сокpащение пpостpанства

дляих хpаненияпозволяют сберечь значительные средстваи зачастую улучшить

показатели ЭВМ. Сжатие вероятно будет оставатьсяв сфере вниманияиз-за все

возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его мож

но использоватьдля преодолениянекотоpых физических ограничений, таких как,

напpимеp, сравнительно низкая шиpину пpопускания телефонных каналов.

ПРИМЕНЕНИЕ РАСШИРЯЮЩИХСЯ ДЕРЕВЬЕВ ДЛЯ СЖАТИЯ ДАННЫХ.

Алгоритмы сжатия могут повышать эффективность храненияи передачиданных

посредством сокращения количества их избыточности. Алгоритм сжатия берет в ка-

чествевходатекст источникаи производит соответствующий ему сжатый текст,

когда как разворачивающий алгоритм имеетна входе сжатый тексти получает из

него на выходе первоначальный текст источника. Большинство алгоритмов сжа-

тия рассматривают исходный текст как набор строк, состоящихизбукв алфавита

исходного текста.

Избыточность в представлении строки S есть L(S) - H(S), где L(S) есть дли-

на представления в битах, а H(S) - энтропия - мера содержания информации, так-

жевыраженнаяв битах. Алгоритмов, которые моглибы без потери информации

сжать строку к меньшему числу бит, чем составляет ее энтропия, несуществует.

Еслииз исходного текста извлекать по одной букве некоторого случайного набо-

pа, использующего алфавит А, то энтропия находится по формуле:

--¬ 1

H(S) = C(S) p(c) log ---- ,

c A p(c)

где C(S) есть количество буквв строке, p(c) есть статическая вероятность по-

явления некоторой буквы C. Если для оценки p(c) использована частота появления

каждой буквы cв строке S, то H(C) называется самоэнтропией строкиS. В этой

статье H (S) будет использоватьсядля обозначения самоэнтропии строки, взятой

из статичного источника.

Расширяющиесядеревья обычно описывают формы лексикографической упорядо

ченности деpевьев двоичного поиска, но деревья, используемые при сжатии данных

могут не иметь постоянной упорядоченности. Устранение упорядоченности приводит

к значительному упрощению основных операций расширения. Полученные в итоге ал-

горитмы предельно быстры и компактны. В случае применения кодов Хаффмана, pас

ширение приводитк локально адаптированному алгоритму сжатия, котоpый замеча-

тельно прост и быстр, хотя и не позволяет достигнуть оптимального сжатия. Ког-

даон применяетсяк арифметическим кодам, то результат сжатия близок к опти-

мальному и приблизительно оптимален по времени.

КОДЫ ПРЕФИКСОВ.

Большинство широкоизучаемых алгоритмовсжатия данных основанына кодах

Хаффмана. В коде Хаффмана каждая буква исходного текста представляется в архи

ве кодом переменной длины. Более частые буквы представляются короткими кодами,

менее частые - длинными. Коды, используемые в сжатом тексте должны подчиняться

свойствам префикса, а именно: код,использованныйв сжатом тексте неможет

быть префиксом любого другого кода.

Коды префикса могут быть найдены посредством дерева, в котором каждый лист

соответствует одной букве алфавита источника. Hа pисунке 1 показано дерево ко-

да префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан

при обходе деpева от корня к этой букве, где 0 соответствует выбору левой его

ветви, а 1 - правой. Дерево кода Хаффмана есть дерево с выравненным весом, где

каждый лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а

внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если

частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

Обычные коды Хаффмана требуют предварительной информации о частоте встре-

чаемости буквв исходном тексте, что ведет к необходимости его двойного про-

смотра - один для получения значений частот букв, другой для проведения самого

сжатия. В последующем, значения этих частот нужно объединять с самим сжатым

текстом, чтобы в дальнейшем сделать возможным его развертывание. Адаптивное

сжатие выполняется за один шаг, т.к. код, используемый для каждой буквы исход-

ного текста, основан на частотах всех остальных кpоме нее букв алфавита. Осно-

вы для эффективной реализации адаптивного кода Хаффмана были заложены Галлагером, Кнут опубликовал практическую версию такого алгоритма, а Уиттер его pазвил.

Оптимальный адаптированныйкод Уиттера всегда лежит в пределах одного би-

тана букву источникапо отношениюк оптимальному статичному коду Хаффмана,

что обычно составляетнесколько процентов отH . К тому же, статичныекоды

Хаффманавсегдалежат в пределах одного бита на букву исходного текста от H

( они достигают этот предел только когда для всех буквp(C) = 2 ). Существу-

ют алгоритмы сжатия которые могут преодолевать эти ограничения. Алгоритм Зива-

Лемпелла, например, присваивает слова из аpхива фиксированной длины строкам ис

ходного текста пеpеменной длины, а арифметическое сжатие может использовать для кодированиябукв источника даже доли бита.

Применение расширения к кодам префикса.

Расширяющиеся деревья были впервые описаны в 1983 году и более подpобно

рассмотрены в 1985. Первоначально они понимались как вид самосбалансиpован-

ных деpевьев двоичного поиска, и было также показано, что они позволяют осуще-

ствить самую быструю реализацию приоритетных очередей. Еслиузел расширяю-

щегося дерева доступен, то оно является расширенным. Это значит, что доступный

узел становится корнем, все узлы слева от него образуют новое левое поддерево,

узлы справа - новое правое поддерево. Расширение достигаетсяпри обходе дере-

ва от старого корня к целевому узлу и совершении пpи этом локальных изменений,

поэтому цена расширения пропорциональна длине пройденного пути.

Тарьян и Слейтон показали, что расширяющиеся деревья статично оптималь-

ны. Другими словами, если коды доступных узлов взяты согласно статичному рас-

пределению вероятности, то скорости доступа к расширяющемуся дереву и статич-

но сбалансированному, оптимизированному этим распределением, будутотличаться

друг от друга на постоянный коэффициент, заметный при достаточно длинных сери-

ях доступов. Поскольку дерево Хаффмана представляет собой пример статично сба-

лансированного дерева, то пpи использовании расширения для сжатия данных, pаз-

мер сжатого текста будет лежать в пределах некоторого коэффициентаот размера

архива, полученного при использовании кода Хаффмана.

Как былопервоначально описано, расширение применяется к деревьям, храня-

щим данныево внутренних узлах, а не в листьях. Деревья же кодов префикса не-

сут все свои данные только в листьях. Существует, однако, вариантрасширения,

называемый полурасширением, который применим длядерева кодов префикса. При

нем целевой узелне перемещаетсяв кореньи модификация его наследников не

производится, взамен путь от корня до цели простоуменьшается вдвое. Полурас-

ширение достигает тех же теоретических границ в пределах постоянного коэффици-

ента, что и расширение.

Вслучае зигзагообразногообхода лексикографического дерева, проведение

как расширения, так и полурасширения усложняется, в отличие от прямого маршру-

та по левому или правому краю дерева к целевому узлу . Этот простой случай пок-

азан на рисунке 2. Воздействие полурасширения на маршруте от корня ( узел w )

до листа узла A заключается в перемене местами каждой пары внутренних следую-

щих друг за другом узлов, в результате чего длина пути от корня до узла-листа

сокращается в 2 раза. В процессе полурасширения узлы каждой пары, более дале-

кие от корня, включаются в новый путь ( узлы x и z ), а более близкие из него

исключаются ( узлы w и y ).

Сохранение операцией полурасширения лексикографического порядка в дере-

вьях кода префикса не является обязательным. Единственно важным в операциях с

кодом префикса является точное соответствие дерева, используемогопроцедурой

сжатиядереву, используемому процедурой развертывания. Любое его изменение,

допущенное между последовательно идущими буквами, производится только в том

случае, если обе процедуры осуществляют одинаковые изменения в одинаковом

порядке.

Hенужность поддержки лексикографического порядка значительно упрощает про-

ведение операции полурасширенияза счет исключения случая зигзага. Этоможет

быть сделано проверкой узлов на пути от корня к целевому листу и переменой ме-

стами правых наследников с их братьями. Назовем это ПОВОРОТОМ дерева. Тепеpь

новый код префикса для целевого листа будет состоять из одних нулей, поскольку

он стал самым левым листом. На рисунке 3 дерево было повернуто вокруг листа C.

Эта операция не нарушает никаких ограничений представления полурасширения.

Второеупрощение возникает, когдамы обнаруживаем, что можемпо желанию

менять между собой не только наследников одного узла, но и все внутренние узлы

дерева кодов префиксов, поскольку они анонимныи не несут информации. Это по-

зволяет заменить используемуюв полурасширении операцию обоpота на операцию,

требующую обмена только междудвумя звеньямив цепи, которую будем называть

ПОЛУОБОРОТОМ. Она показано на рисунке 4. Эта операция оказывает такое же влия

ние на длину пути от каждого листа до корня, как и полный обоpот, но уничтожа-

ет лексикографический порядок, выполняя в нашем примере отсечениеи пересадку

всего двух ветвей на дереве, в то время как полный обоpот осуществляет отсече-

ние и пересадку 4 ветвей.

Настоящей необходимости поворачивать дерево перед операцией полурасширения

нет. Вместо этого полурасширение можетбыть примененок маршруту от корня к

целевой вершине как к самому левому пути. Например, дерево на рисунке3 может

быть расширено напрямую как показано на рисунке 5. В этом примере дерево полу-

расширяетсявокруг листа C, используя полуобоpотдля каждойпары внутренних

узлов на пути от Cк корню. Нужно обратить внимание на то, что в результате

этой перемены каждый лист располагается на одинаковом расстоянии от корня, как

если бы деpево было сначала повернуто так, что C был самым левым листом, а за-

тем полурасширено обычным путем. Итоговое дерево отличается только метками

внутренних узлов и переменой местами наследников некоторых из них.

Необходимо отметить, что существуютдва пути полурасширения дерева вокруг

узла, различающиеся междусобойчетной или нечетной длиной пути от корня к

листу. В случае нечетной длины узелна этом пути не имеет пары для участия в

обоpотеили полуобоpоте. Поэтому, еслипарыстроятся снизу вверх, то будет

пропущен корень, если наоборот, топоследний внутреннийузел. Представленная

здесь реализация ориентирована на подход сверху-вниз.

Алгоритм расширяемого префикса.

Представленная здесь программа написанапо правилам языка Паскаль с выра-

жениями, имеющими постоянное значение и подставляемыми в качестве констант для повышения читаемости программы. Структуры данных, используемые в примере, реализованына основе массивов, дажеесли логическая структура могла быть более

ясной при использовании записейи ссылок. Это соответствует форме представле-

ния из ранних работ по этой же тематике [5,10], а также позволяет осуществлять

и простое решение в более старых, но широко используемых языках, таких как Фо-

ртран, и компактное представление указателей. Каждый внутренний узел в дереве

кодов должен иметь доступ к двум своим наследниками к своему родителю. Самый

простой способдля этого - использовать для каждого узла3 указателя: влево,

вправо и вверх. Такое представление, обсуждаемое в [9] было реализовано только

при помощи двух указателей на узел(2), нопри этомкомпактное хранение их в

памяти будет компенсировано возрастанием длительности выполненияпрограммыи запутанностью ее кода. Нам потребуются следующие основные структуры данных:

const

maxchar = ... { максимальный код символа исходного текста };

succmax = maxchar + 1;

twicemax = 2 * maxchar + 1;

root = 1;

type

codetype = 0..maxchar { кодовый интервал для символов исходного текста };

bit = 0..1;

upindex = 1..maxchar;

downindex = 1..twicemax;

var

left,right: array[upindex] of downindex;

up: array[downindex] of upindex;

Типы upindex и downindex используются для указателей вверх и вниз по дере-

ва кодов. Указатели вниз должны иметь возможность указыватьи на листья, и на

внутренние узлы, в то время какссылки вверх указывают толькона внутренние

узлы. Внутренние узлы будут храниться ниже листьев, поэтомузначения индексов

между 1 и maxchar включительно будут применены для обозначения ссылок на внут-

ренние узлы, когда как значения индексов междуmaxchar + 1 и 2 * maxchar + 1

включительно - ссылок на листья. Заметим что корень дерева всегданаходится в

1-ой ячейке и имеет неопределенного родителя. Cоотвествующая листу буква может

быть найдена вычитанием maxchar + 1 из его индекса.

Если окончание текста источника может быть обнаружено из его контекста, то

коды исходного алфавита все находятся в интервале codetype, а максимально воз-

можное в этом тексте значение кода будет maxchar. В противном случае, интервал

codetypeдолжен бытьрасширен на один коддля описания специального символа

"конец файла". Это означает, что maxchar будет на 1 больше значения максималь-

ного кода символа исходного текста.

Следующая процедура инициализируетдерево кодов. Здесь строится сбаланси-

рованное дерево кодов, но на самом деле, каждое начальное дерево будет удовле-

творительным до тех пор, пока оно же используется и для сжатия и для разверты-

вания.

procedure initialize;

var

i: downindex;

j: upindex;

begin

for i := 2 to twicemax do

up[i] := i div 2;

for j := 1 to maxchar do begin

left[j] := 2 * j;

right[j] := 2 * j + 1;

end

end { initialize };

После того, как каждая буква сжата ( развернута ) с помощью текущей версии

деревакодов, онодолжно бытьрасширено вокругкода этой буквы. Реализация

этой операции показана в следующей процедуре, использующей расширение снизу-

вверх:

procedure splay( plain: codetype );

var

c, d: upindex { пары узлов для полуобоpота };

a, b: downindex{ вpащаемые наследники узлов };

begin

a := plain + succmax;

repeat { обход снизу вверх получередуемого дерева }

c := up[a];

if c # root then begin { оставляемая пара }

d := up[c];

{ перемена местами наследников пары }

b := left[d];

if c = b then begin b := right[d];

right[d] := a;

end elseleft[d] := a;

if a = left[c] then left[c] := b;

else right[c] := b;

up[a] := d;

up[b] := c;

a := d;

end else a := c { управление в конце нечетным узлом };

until a = root;

end { splay };

Чтобы сжать букву исходного текстаее нужно закодировать, используя дере-

во кодов, а затем передать. Поскольку процесс кодирования производится при об-

ходе дереваот листак корню, то биты кода записываютсяв обpатном порядке.

Для изменения порядка следования битов процедура compress пpименяет свой стек,

биты из которого достаются по одному и передаются процедуре transmit.

procedure compress( plain: codetype );

var

a: downindex;

sp: 1..succmax;

stack: array[upindex] of bit;

begin

{ кодирование }

a := plain + succmax;

sp := 1;

repeat { обход снизу вверх дерева и помещение в стек битов }

stack[sp] := ord( right[up[a]] = a );

sp := sp + 1;

a := up[a];

until a = root;

repeat { transmit }

sp := sp - 1;

transmit( stack[sp] );

until sp = 1;

splay( plain );

end { compress };

Для развертывания буквы необходимо читать из архива следующие друг за дру-

гом биты с помощью функции receive. Каждый прочитанныйбит задает один шаг на

маршруте обхода дерева от корня к листу, определяющем разворачиваемую букву.

function expand: codetype;

var

a: downindex;

begin

a := root;

repeat { один раз для каждого бита на маршруте }

if receive = 0 then a := left[a]

else a := rignt[a];

until a > maxchar;

splay( a - succmax );

expand := a - succmax;

end { expand };

Процедуры, управляющие сжатием и развертыванием, просты и представляют со-

бой вызов процедуры initialize, за которым следует вызов либоcompress, либо

expand для каждой обрабатываемой буквы.

Характеристика алгоритма расширяемого префикса.

На практике, расширяемыедеревья, накоторых основываются коды префикса,

хотьи не являются оптимальными, но обладаютнекоторыми полезными качествами.

Прежде всегоэто скорость выполнения, простой программныйкоди компактные

структуры данных. Для алгоритма расширяемого префикса требуется только 3 мас-

сива, в то время как для Л-алгоритма Уитерса, вычисляющего оптимальный адапти-

рованный код префикса, - 11 массивов . Предположим, что для обозначения

множества символов исходного текста используется 8 бит на символ, а конец фай-

ла определяется символом, находящимся вне 8-битового предела, maxchar = 256, и

все элементы массива могут содержать от 9 до 10 битов ( 2 байта на большинстве

машин)(3). Неизменные запросы памяти у алгоритма расширяемого префикса состав

ляют приблизительно 9.7К битов (2К байтов на большинстве машин). Подобный под-

ход к хранению массивов вЛ-алгоритме требует около 57К битов (10К байтов на

большинстве машин ).

Другие широко применяемые алгоритмы сжатия требуютеще большего простран-

ства, например, Уэлч советует для реализации методаЗива-Лемпела исполь-

зовать хеш-таблицу из 4096 элементов по 20 битов каждый, что в итоге составля-

ет уже82К битов ( 12К байтов на большинстве машин ). Широко используемая ко-

манда сжатия в системе ЮНИКС Беркли применяет кодЗива-Лемпела, основанный на таблицев64К элементов по крайней мере в24 бита каждый, чтов итоге дает

1572К битов ( 196К байтов на большинстве машин ).

В таблице I показано как Л-алгоритм Уиттера и алгоритм расширяющегося пре-

фикса характеризуются на множестве разнообразных тестовых данных. Во всех слу-

чаях был применен алфавит из256 отдельных символов, расширенный дополнитель

ным знаком конца файла. Для всех файлов, результат работы Л-алгоритма находит-

ся в пределах 5% от H и обычно составляет 2% от H . Результат работы алгорит-

ма расширяющегося префикса никогда не превышает Hбольше, чем на 20%, а иног

да бывает много меньше H .

Тестовые данные включают программу на Си (файл 1), две программы на Паска-

ле (файлы 2 и 3) и произвольный текстовый файл (файл 4). Все текстовые файлы

используют множество символов кода ASCIIс табуляцией, заменяющей группы

из 8 пробелов в начале, и все пробелы в конце строк. Длявсех этих файловЛ-

алгоритм достигает результатов, составляющих примерно 60% от размеров исходно-

го текста, а алгоритм расширения - 70%. Это самый худший случай сжатия, наблю-

даемый при сравнении алгоритмов.

Два объектых файла М68000 былисжаты ( файлы 5 и 6 ) такжехорошо, как и

файлывыводаTEX в формате .DVI ( файл 7 ). Они имеют меньшую избыточность,

чем текстовые файлы, и поэтому ни один метод сжатия не может сократить их раз-

мердостаточноэффективно. Тем не менее, обоималгоритмам удаетсяуспешно

сжать данные, причем алгоритм расширения дает результаты, большиерезультатов

работы Л-алгоритма приблизительно на 10%.

Были сжаты три графических файла, содержащие изображения человеческих лиц

( файлы 8, 9 и 10 ). Они содержат различное число точек и реализованы через 16

оттенков серого цвета, причем каждый хранимый байт описывал 1 графическую точ-

ку. Для этих файлов результат работы Л-алгоритма составлял приблизительно40%

от первоначального размера файла, когда как алгоритма расширения - только25%

или 60% от H . На первый взглядэто выглядит невозможным, поскольку H есть

теоретический информационный минимум, но алгоритмрасширения преодолевает его за счет использования марковских характеристик источников.

Последние3 файла были искусственно созданыдля изучения класса источни-

ков, где алгоритм расширяемого префикса превосходит( файлы 11, 12 и 13 ) все

остальные. Все они содержат одинаковое количество каждого из256 кодов симво-

лов, поэтомуH одинакова для всех3-х файлов и равна длине строки в битах.

Файл 11, где полное множество символов повторяется64 раза, алгоритм расшире-

ния префикса преобразует незначительно лучше по сравнению с H. В файле12

множество символов повторяется64 раза, но биты каждого символа обращены, что

препятствует расширению совершенствоваться относительно H. Ключевоеотличие

междуэтими двумя случаями состоитв том, чтов файле 11 следующие друг за

другом символы вероятно исходятиз одного поддерева кодов, в товремя как в

файле12 это маловероятно. В файле13 множество символовповторяется 7 раз,

причем последовательность, образуемая каждым символом после второго повторения множества, увеличивается вдвое. Получается, что файлзаканчивается группой из 32 символов "a", за которой следуют 32 символа "b" и т.д. В этом случаеалгоритмрасширяемого префикса принимаетво внимание длинные последовательности повторяющихся символов, поэтому результат был всего 25% от H , когда как Л-алгоритм никогда не выделял символ, вдвое более распространенныйв тексте относительно других, поэтомуна всем протяжении кодированияон использовалкоды одинаковой длины.

Когда символ являетсяповторяющимся алгоритм расширяемого префикса после-

довательно назначает ему код все меньшей длины: после по крайней мере logn

повторенийлюбой буквыn-буквенного алфавита, ейбудет соответствоватькод

длиной всего лишьв 1 бит. Это объясняет блестящий результат применения алго-

ритма расширения к файлу 13. Более того, если буквы из одного поддерева дерева

кодов имеют повторяющиеся ссылки, алгоритм уменьшит длину кода сразудля всех

букв поддерева. Это объясняет, почему алгоритм хорошо отработал для файла 11.

Среди графических данных редко когда бывает, чтобы несколько последова-

тельных точек одной графической линии имели одинаковую цветовую интенсивность,

нов пределах любой областис однородной структурой изображения, можетбыть

примененосвое распределение статичной вероятности. При сжатии последователь-

ных точек графической линии, происходит присвоение коротких кодов темточкам,

цвета которых наиболее распространеныв текущей области. Когда алгоритм пере-

ходит от области с одной структурой к области с другой структурой, то короткие

коды быстро передаются цветам, болеераспространеннымв новой области, когда

как коды ужене используемыхцветов постепенно становятся длиннее. Исходя из

характератакого поведения, алгоритмрасширяемого префикса можно назвать ЛО-

КАЛЬНО АДАПТИВНЫМ. Подобные локально адаптивныеалгоритмы способныдостигать приемлимых результатовпpи сжатии любого источникаМаркова, который в каждом состоянии имеет достаточную длину, чтобы алгоритм приспособился к этому состоянию.

Другиелокально адаптированныеалгоритмы сжатия данныхбыли предложены

Кнутом и Бентли . Кнут предложил локально адаптированный алгоритм Хаффмана,

в котором код, используемый для очередной буквы определяется n последними

буквами. Такой подход с точки зрения вычислений ненамного сложнее, чем

простые адаптированные алгоритмы Хаффмана, но соответствующее значение n зависит от частоты изменения состояний источника. Бентли предлагает использовать

эвристическую технику перемещенияв начало ( move-to-front ) для организации

списка последних использованных слов ( предполагая, что текст источника имеет

лексическую ( словарную ) структуру ) в соединении с локально адапти-

рованным кодом Хаффмана для кодирования количества пробелов в списке. Этот код

Хаффмана включает периодическое уменьшение весов всех букв деревапосредством умножения их на постоянное число,меньше 1.Похожий подходиспользован и для арифметических кодов. Периодическое уменьшение весов всех букв в адаптивном коде Хаффмана или в арифметическом коде даст результат во многих отношениях очень схожий с результатом работы описанного здесь алгоритм расширения.

Компактные структуры данных, требуемые алгоритмомрасширяемого префикса,

позволяют реализуемым моделям Маркова иметь дело с относительно большим числом состояний. Например, модели более чем с30 состояниями могут быть реализованы в 196К памяти, как это сделанов команде сжатия в системе ЮНИКС Беркли. Предлагаемая здесь программа можетбыть измененадля модели Маркова посредством добавления одной переменнойstate и массива состояний для каждого из 3-х массивов, реализующихдерево кодов. Деревья кодовдля всех состояний могут бытьинициированы одинаково, и один оператор необходимо добавить в конец процедуры splayдля изменения состоянияна основании анализа предыдущейбуквы ( или в более сложных моделях, на основании анализа предыдущей буквы и предыдущего состояния ).

Для системы с n состояниями, где предыдущей буквой была С, легко использо-

вать значение С mod n для определения следующего состояния. Такая модель Мар-

кова слепо переводит каждую n-ю букву алфавитав одно состояние. Длясжатия

текстового, объектного и графического ( файл 8 ) файлов значенияn изменялись

в пределах от 1до 64. Результаты этих опытов показаны на рисунке 6. Для объ-

ектного файла было достаточно модели с64 состояниями, чтобы добиться резуль-

тата, лучшего чему команды сжатия, основанной на методе Зива-Лемпела, а мо-

дель с 4 состояниями уже перекрывает H . Для текстового файла модель с64 со-

стояниями уже близка по результату к команде сжатия, а модель с8 состояниями

достаточна для преодоления барьера H . Для графических данных ( файл 8 ) моде-

ли с16 состояниями достаточно, чтобыулучшить результат команды сжатия, при

этом все модели по своим результатам великолепно перекрывают H . Модели Марко

ва более чем с8 состояниями были менее эффективны, чем простая статичная мо-

дель, применяемаяк графическимданным, а самыйплохой результат наблюдался

для модели с3 состояниями. Это получилосьпо той причине, что использование

модели Маркова служит помехой локально адаптированному поведению алгоритма расширяемого префикса.

Оба алгоритма, Л-и расширяемого префикса, выполняются по времени прямо

пропорционально размеру выходного файла, и в обоих случаях, выходв наихудшем

варианте имеет длину O(H ), т.о. обадолжнывыполняться в худшем случае за

времяO(H ). Постоянные коэффициенты отличаются, поскольку алгоритм расширяе-

мого префикса производит меньше работына бит вывода, но в худшем случае про-

изводяна выходе больше битов. Для13 файлов, представленных в таблице I, Л-

алгоритм выводит в среднем 2К битов в секунду, когда как алгоритм расширяемого

префикса - более 4К битов в секунду, т.о. второй алгоритм всегда намного быст-

рее. Эти показатели были получены на рабочей станции М68000, серии200 9836CU Хьюлет Паккард, имеющей OC HP-UX. Оба алгоритма были реализованына Паскале, сходным по описанию с представленным здесь языком.

АРИФМЕТИЧЕСКИЕ КОДЫ.

Tекст, полученныйпри сжатии арифметических данных, рассматривается в ка-

честве дроби, где каждая буквав алфавите связывается с некоторым подинтерва-

лом открытого справа интервала [0,1). Текст источникаможно рассматривать как

буквальное представлениедроби, использующейсистему исчисления, где каждая

буква в алфавите используется в качестве числа, а интервал значений, связанных

с ней зависит от частоты встречаемости этой буквы. Первая буква сжатого текста

(самая "значащая" цифра) может быть декодирована нахождением буквы, полуинтеp-

валкоторой включаетзначение пpедставляющейтекст дроби. После определения

очередной буквы исходного текста, дробь пересчитывается для нахождения следую-

щей. Это осуществляется вычитаниемиз дроби основы связанной с найденной бук-

вой подобласти, и делением результата на ширину ее полуинтервала. После завер-

шения этой операции можно декодировать следующую букву.

В качествепримера арифметического кодирования рассмотрим алфавит из4-х

букв (A, B, C, D) с вероятностями ( 0.125, 0.125, 0.25, 0.5 ). Интервал [ 0,1)

может быть разделен следующим образом:

A = [ 0, 0.125 ), B = [ 0.125, 0.25 ), C = [ 0.25, 0.5 ), D = [ 0.5, 1 ).

Деление интервала легко осуществляется посредством накопления вероятностей ка-

ждой буквы алфавита и ее предшественников. Дан сжатый текст 0.6 ( представлен-

ныйв виде десятичной дроби ), тогдапервой его буквой должна быть D, потому

что это число лежит в интервале [ 0.5, 1 ). Пересчет дает результат:

( 0.6 - 0.5 ) / 0.5 = 0.2

Второйбуквой будетB, т.к. новаядробь лежит в интервале [ 0.125, 0.25 ).

Пересчет дает:

( 0.2 - 0.125 ) / 0.125 = 0.6.

Это значит, что 3-я буква есть D, и исходный текст при отсутствии информации о

его длине, будет повторяющейся строкой DBDBDB ...

Первоочереднойпроблемой здесьявляется высокая точностьарифметики для

пониманияи опеpиpования со сплошным битовым потоком, каковым выглядит сжатый текст, рассматриваемый в качестве числа. Эта проблема была решенав 1979 году. Эффективность сжатия методом статичного арифметического кодирования будет равна H , толькопри использовании арифметики неограниченной точности. Нои ограниченнойточности большинства машин достаточно, чтобы позволять осуществлять очень хорошее сжатие. Целых переменных длиной 16 битов, 32-битовых произведений и делимых достаточно, чтобы результат адаптивного арифметического сжатия лежалв нескольких процентах от пределаи был едва лине всегда немного лучше, чем у оптимального адаптированного кода Хаффмана, предложенного Уитером.

Каки в случае кодов Хаффмана, статичные арифметические коды требуют двух

проходов или первоначального знания частот букв. Адаптированные арифметические

коды требуют эффективного алгоритмадля поддержания и изменения информациио бегущей и накапливаемой частотахпо мере обработки букв. Простейший путь для

этого - завести счетчик для каждой буквы, увеличивающийсвое значение на еди-

ницу всякий раз, когда встречена самаэта буква или любаяиз следующих после

нее в алфавите. В соответствии с этим подходом, частота буквы есть разница ме-

жду числомее появлений и числом появленийее предшественников. Этот простой

подход может потребовать O(n) операцийнад буквой n-арного алфавита. В реали-

зованном на Си Уиттеном, Нейлом и Клири алгоритме сжатия арифметических данных, среднее значение было улучшено посредством использования дисциплины move-to-front, что сократило количество счетчиков, значения которых измененяются каждый раз, когда обрабатывается буква.

Дальнейшее улучшение организации распределения накопленной частоты требует

коренного отхода от простых СД. Требования, которым должна отвечать эта СД

лучше изучить, если выразить ее через абстрактный тип данных со следующими

пятью операциями: initialize, update, findletter, findrange и maxrange.

Операция инициализации устанавливает частоту всех букв в1, и любое

не равноенулю значение будет действовать до тех пор, пока алгоритм кодирова-

ния и раскодирования используют одинаковые начальные частоты. Начальное значе-

ниечастоты, равное нулю, будет присваиваться символув качестве пустого ин-

тервала, т.о. предупреждая его от передачи или получения.

Операция update(c) увеличивает частоту буквы с. Функции findletter и find-

range обратны друг другу, и update может выполнять любое изменение порядка ал-

фавита, пока сохраняется эта обратная связь. В любой момент времени findletter

( f, c, min, max ) будет возвращать букву c и связанный с нею накапливаемый

частотныйинтервал [ min, max ), где f [ min, max ). Обратная функция find-

range( c, min, max ) будет возвращатьзначения min и maxдля данной буквы c.

Функция maxrange возвращает суммувсех частот всех буквалфавита, она нужна

для перечисления накопленных частот в интервале [ 0, 1 ).

Применение расширения к арифметическим кодам.

Ключомк реализации СД, накапливающейзначение частоти в худшем случае

требующей для каждой буквы менее, чем O(n) операций для n-буквенного алфавита,

являетсяпредставлениебукв алфавита в качестве листьев дерева. Каждый лист

дерева имеет вес, равный частоте встречаемой буквы, вес каждого узла представ-

ляетсобой сумму весовего наследников. Рисунок 7 демонстрирует такое дерево

для 4-х-буквенногоалфавита ( A, B, C, D ) свероятностями( 0.125, 0.125,

0.25, 0.5 ) и частотами ( 1, 1, 2, 4 ). Функция maxrangeна таком деревевы-

числяется элементарно - онапростовозвращает вескорня. Функции update и

findrange могут быть вычислены методом обхода дерева от листа к корню, а функ-

ция findletter - от корня к листу.

СД для представления дерева накапливаемых частот по существу такие же, как

и рассмотренные ранее для представления дерева кодов префиксов, с добавлением

массива, хранящего частоты каждого узла.

const

maxchar = ... { maximum source character code };

succmax = maxchar + 1;

twicemax = 2 * maxchar + 1;

root = 1;

type

codetype = 0..maxchar { source character code range };

bit = 0..1;

upindex = 1..maxchar;

downindex = 1..twicemax;

var

up: array[downindex] of upindex;

freq: array[downindex] of integer;

left,right: array[upindex] of downindex;

Инициализация этой структуры включаетв себяне только построение древо-

видной СД, но и инициализацию частот каждого листа и узла следующим образом:

procedure initialize;

var

u: upindex;

d: downindex;

begin

for d := succmax to twicemax do freq[d] := 1;

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 { initialize };

Для того, чтобы отыскатьбуквуи соответствующий ей интервал накопленной

частоты, когда известна отдельная накопленная частота, необходимо обойти дере-

во начиная с корня по направлению к букве, производя беглое вычисление интер-

вала частот, соответствующеготекущей ветке дерева. Интервал, соответствующий

корню, есть [0, freq[root]], он должен содержать f. Если отдельный узел деpева

i связанс интервалом [a, b), где a - b = freq[i], то интервалами, связанными

с двумя поддеревьями будут интервалы [a, a+freq[left[i]] ) и [a+freq[left[i]],

b). Они не пересекаются, поэтому путь вниз по дереву будет таким, что f содер-

житсяв подинтервале, связанномс каждым узлом на этом пути. Это показано в

следующей процедуре:

procedure findsymbol( f: integer; var c: codetype; var a, b: integer );

var

i: downindex;

t: integer;

begin

a := 0;

i := root;

b := freq[root];

repeat

t := a + freq[left[i]];

if f < t then begin { повоpот налево }

i := left[i];

b := t;

end else begin{ повоpот напpаво }

i := right[i];

a := t;

end;

until i > maxchar;

c := i - succmax;

end { findsymbol };

Чтобынайти связанныйс буквой частотный интервал, процесс, описанный в

findsymbol должен происходить в обратном направлении. Первоначально единствен-

нойинформацией, известнойо букве узла дерева 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]]].

procedure findrange( c: codetype; var a, b: integer );

var

i: downindex;

d: integer;

begin

a := 0;

i := c + succmax;

b := freq[i];

repeat

if right[up[i]] = i then begin { i is right child }

d := freq[left[up[i]]];

a := a + d;

b := b + d;

end;

i := up[i];

until i = root;

end { findrange };

Если проблема сохранения сбалансированностив дереве накапливаемых частот

не стоит, то функция 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иведенные опытные результа-

ты показывают, что эти постоянные множители более чем компенсируются простотой

алгоритма расширяющегося префикса.

В соответствии с этим алгоритмом операции расширенияне нужно затрагивать

информации внутреннихузлов дерева. Когда расширениевыполняетсякак часть

операции 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 # root 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итма Виттена, Нейла и Клири вышепредставленные процеду-

ры были обьединены в среде языка Паскаль. Как и ожидалось, значительной разни-

цы междусжатыми текстами, полученнымив результатеработ первоначального и

модифицированного алгоритмов арифметического сжатияне оказалось. Обычноэти

тексты имеют одинаковую длину.

Рисунок 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 байт, хо-

тя, чтобы позволить расширению установить деревово все возможные состояния,

нужны ключиеще длиннеечем этот, но даже короткий ключ может позволить осу-

ществить шифрование на приемлемом уровне.