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

основы связанной с найденной

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

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

В качестве примера арифметического кодирования рассмотрим алфавит из 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 и findrange

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

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

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

интервал [ min, max ), где f [ min, max ). Обратная функция findrange( 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 байт,

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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: