Программы управления сжатием и развертыванием информации

Размещено на http://allbest.ru

Введение

программа информатика алгоритм сжатие

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Это есть форма кодирования. Другими целями кодирования являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию - он увеличивает избыточность данных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифpованию, что затpудняет поиск шифpа доступным для взломщика статистическим методом.

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

Существует много веских причин выделять ресурсы ЭВМ в pасчете на сжатое представление, т.к. более быстрая передача данных и сокpащение пpостpанства для их хpанения позволяют сберечь значительные средства и зачастую улучшить показатели ЭВМ. Сжатие вероятно будет оставаться в сфере внимания из-за все возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его можно использовать для преодоления некотоpых физических ограничений, таких как, напpимеp, сравнительно низкая шиpину пpопускания телефонных каналов.

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

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

Избыточность в представлении строки 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ый замечательно прост и быстр, хотя и не позволяет достигнуть оптимального сжатия. Когда он применяется к арифметическим кодам, то результат сжатия близок к оптимальному и приблизительно оптимален по времени.

2.Коды префиксов

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

Коды префикса могут быть найдены посредством дерева, в котором каждый лист соответствует одной букве алфавита источника. 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еменной длины, а арифметическое сжатие может использовать для кодирования букв источника даже доли бита.

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

Расширяющиеся деревья были впервые описаны в 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 может быть расширено напрямую. Например, дерево полурасширяется вокруг листа C, используя полуобоpот для каждой пары внутренних узлов на пути от C к корню. Нужно обратить внимание на то, что в результате этой перемены каждый лист располагается на одинаковом расстоянии от корня, как если бы деpево было сначала повернуто так, что C был самым левым листом, а затем полурасширено обычным путем. Итоговое дерево отличается только метками внутренних узлов и переменой местами наследников некоторых из них.

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

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

Представленная здесь программа написана по правилам языка Паскаль с выражениями, имеющими постоянное значение и подставляемыми в качестве констант для повышения читаемости программы. Структуры данных, используемые в примере, реализованы на основе массивов, даже если логическая структура могла быть более ясной при использовании записей и ссылок. Это соответствует форме представления из ранних работ по этой же тематике [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 else left[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 для каждой обрабатываемой буквы.

Заключение

Представленный здесь алгоритм расширяемого префикса является вероятно самым простым и быстрым адаптивным алгоритмом сжатия, основанном на использовании кода префикса. Его характерные черты - очень небольшое количество требуемой ОП и локально адаптивное поведение. Когда доступны большие объемы памяти, использование этого алгоритма вместе с моделью Маркова часто позволяет сжать данные лучше, чем это делают конкурирующие алгоритмы на этом же объеме памяти. Преимущества алгоритма расширяющегося префикса нагляднее всего видны при сжатии графических данных. Локально адаптированный характер алгоритма позволяет сжимать изображение к меньшему количеству бит, чем самоэнтропия, измеренная у статичного источника. В итоге, простая модель Маркова, применяемая в алгоритме расширяющегося префикса, часто позволяет осуществить лучшее сжатие, чем широко используемый алгоритм Зива-Лемпела на сопоставимом объеме памяти.

Алгоритмы арифметического сжатия данных могут выполняться за время 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 байт, поэтому несомненно такие большие ключи могут поставить в тупик. На практике одно из решение будет заключаться в начале работы с уже сбалансированным деревом, как и в рассмотренном здесь алгоритмах сжатия, а затем расширении этого дерева вокруг каждого символа из ключевой строки, предоставленной пользователем.

Размещено на Allbest.ru