Архиватор

ОГЛАВЛЕНИЕ 

ВВЕДЕНИЕ          3

ГЛАВА I Алгоритмы Сжатия       4

1. Типы сжатия        4
2. Кодирование  Хафмана       5
3. Словарные методы

1.3.1 LZ77(скользящее окно)      7

1.3.2 Недостатки  LZ77       10

1.3.3 LZ78         11

1.3.4 LZW         13

1.3.5Декодирование LZW      14

1.3.6 Структура LZW       15 

ГЛАВА II Разработка архиватора ArchivatorLZW    16

     2.1 Блок-схема алгоритма сжатия файла    17 

     2.2 Алгоритм         18

                 2.2.1 Алгоритм сжатия файла    19

                 2.2.2 Алгоритм распаковки  файла    20   

     2.3 Создание интерфейса       21

     2.4  Программная реализация алгоритмов    22

      2.5 Примеры         23

      2.6 Листинг программы       25  

ВЫВОД           34

ЛИТЕРАТУРА          35 
 
 
 
 
 
 

Введение.

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

Первые алгоритмы  сжатия были примитивными в связи  с тем, что была примитивной вычислительная техника. С развитием мощностей  компьютеров стали возможными все  более мощные алгоритмы. Настоящим  прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось  к примитивному кодированию символов. Словарные алгоритмы позволяли кодировать повторяющиеся строки символов, что позволило резко повысить степень сжатия.

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

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

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

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

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

1.1 Типы сжатия.

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

Второй тип  алгоритмов сжатия используется в случаях, когда пользователю не требуется  полного совпадения входной и  обработанной информации. Как правило, такие алгоритмы используются для  уменьшения избыточности файлов, содержащих изображения и звуки, и основываются на нечувствительности человеческих органов  восприятия к небольшим искажениям в представляемой информации. Сжатие данных с потерей части информации обеспечивает наивысшую степень  и скорость сжатия данных. Примерами  таких алгоритмов являются форматы JPEG и MPEG, обеспечивающие 20-кратную степень  сжатия.

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

Алгоритмы сжатия.

1.2 Кодирование Хаффмана

Один из первых алгоритмов эффективного кодирования  информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический  алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании  этой таблицы строится дерево кодирования  Хаффмана (Н-дерево).

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а двое его детей(потомков) удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
7. Допустим, у нас есть следующая таблица частот:

8. Этот процесс можно представить как построение дерева, корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n₀ потомков — символы из предыдущего шага и т. д.
9. Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
10. Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

11. Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д — наибольшим.
12. При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ).

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

Словарные методы.

LZ77 (скользящее  окно)

Основная идея этого метода состоит в использовании  ранее прочитанной части входного файла в качестве словаря. Кодер  создает окно для входного файла  и двигает его справа налево в  виде строки символов, требующих сжатие. Таким образом, метод основан  на скользящем окне. Окно разбивается  на две части. Часть слева называется буфером поиска. Она будет служить  текущим словарем, и в ней всегда содержатся символы, которые недавно  поступили и были закодированы. Правая часть окна называется упреждающим  буфером, содержащим текст, который  будет сейчас закодирован. На практике буфер поиска состоит из нескольких тысяч байт, а длина упреждающего буфера равна нескольким десяткам символов. Вертикальная черта | между символами  t и е означает текущее разделение между двумя буферами. Итак, предположим, что текст «sir_sid_eastman_easily_t» уже сжат, а текст «eases_sea_sick_seals» нуждается в сжатии.

Кодер просматривает  буфер поиска в обратном порядке (справа налево) и ищет в нем первое появление символа е из упреждающего буфера. Он обнаруживает такой символ в начале слова easily. Значит, е находится (по смещению) на расстоянии 8 от конца буфера поиска. Далее кодер определяет, сколько совпадающих символов следует за этими двумя символами е. В данном случае совпадение по символам eas имеет длину 3. Кодер продолжает поиск, пытаясь найти более длинные совпадающие последовательности. В нашем (лучае имеется еще одна совпадающая последовательность той же длины 3 в слове eastman со смещением 16. Декодер выбирает самую длинную из них, а при совпадении длин - самую удаленную, и готовит метку (16, 3, «е»).

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

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

В общем случае, метка из LZ77 имеет три поля: смещение, длина и следующий символ в  упреждающем буфере (в нашем случае, это будет второе е в слове  teases. Эта метка записывается в выходной файл, а окно сдвигается вправо (или входной файл сдвигается влево) на четыре позиции: три позиции для совпадающей последовательности и одна позиция для следующего символа.  

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

Ясно, что метки  вида (0,0,...), которые кодируют единичные  символы, не обеспечивают хорошее сжатие. Легко оценить их длину. Размер смещения равен  , где  - длина буфера поиска. На практике этот буфер имеет длину в несколько сотен байт, поэтому смещение имеет длину 10 - 12 бит. Поле «длина» имеет размер равный , где  - длина упреждающего буфера (в следующем абзаце будет объяснено почему надо вычитать 1). Обычно упреждающий буфер имеет длину нескольких десятков байтов. Поэтому длина этого поля равна нескольким битам. Размер поля «символ», обычно, равен 8 бит, но в общем случае - , где  - размер алфавита. Полный размер метки (0,0,...) одиночного символа равен  бит, что много больше длины 8 «сырого» символа без нулевых элементов кода.

Следующий пример показывает, почему поле «длина» может  быть длиннее размера упреждающего буфера:

Первый символ а в упреждающем буфере совпадает с 5-ым а буфера поиска. Может показаться, что оба крайних а подходят с длиной совпадения 3, поэтому кодер выберет самый левый символ и создаст метку (28,3,«а»). На самом деле кодер образует метку (3,4,«_»). Строка из четырех символов «alfa» из упреждающего буфера совпадает с тремя символами «alf» буфера поиска и первым символом «а» упреждающего буфера. Причина этого заключается в том, что декодер может обращаться с такой меткой очень естественно безо всяких модификаций. Он начинает с позиции 3 буфера поиска и копирует следующие 4 символа, один за другим, расширяя буфер вправо. Первые 3 символа копируются из старого содержимого буфера, а четвертый является копией первого из этих новых трех. Следующий пример еще более убедителен (хотя он немного надуман):

Кодер создает  метку (1,9,«А») для совпадения первых девяти копий символа «А» в  упреждающем буфере, включая десятый символ А. Вот почему длина совпадения, в принципе, может быть равна размеру упреждающего буфера минус 1.

Декодер метода LZ77 гораздо проще кодера (то есть, метод LZ77 является асимметричным методом  сжатия). Он должен соорудить такой  же буфер поиска, как и кодер. Декодер вводит метку, находит совпадение в своем буфере, записывает совпадающие символы и символ из третьего поля в буфер. Этот метод или его модификация хорошо работает, если файл сжимается один раз (или несколько раз), но часто разжимается. Часто используемый архив старых сжатых файлов может служить хорошим примером использования этого алгоритма.

На первый взгляд в описанном методе сжатия не делается никаких предположений относительно входных данных. В частности, не обращается внимание на частоты появления отдельных символов. Однако, немного подумав, видно, что из-за природы скользящего окна метод LZ77 всегда сравнивает упреждающий буфер с недавним содержимым буфера поиска, но не с данными, поступившими очень давно (и которые уже покинули буфер поиска). Следовательно, неявно предполагается, что похожие участки входного файла повторяются близко друг от друга. Данные, удовлетворяющие этому свойству будут хорошо сжиматься.

1.3.2 Недостатки

Перед тем, как  обсуждать алгоритм LZ78, остановимся  на недостатках метода LZ77 и его  вариантов. Было уже отмечено, что  этот алгоритм основывается на предположении, что похожие образцы сжимаемых  данных находятся близко друг от друга. Если содержимое файла не удовлетворяет  этому условию, то он будет сжиматься  плохо. Простой пример это текст, в котором слово «economy» встречается часто и равномерно распределено по всему тексту. Может случиться, что когда это слово попадает в упреждающий буфер, его предыдущая копия уже вышла из буфера просмотра. Более лучший алгоритм мог бы сохранять часто встречающиеся слова в словаре, а не сдвигал бы их все время.

Другой недостаток метода - это ограниченные размеры  упреждающего буфера. Размер совпадающей  строки лимитирован числом , но  приходится держать маленьким, так как процесс сравнения строк основан на сравнении индивидуальных символов. Если удвоить , то степень сжатия могла бы возрасти, но одновременно с этим произойдет замедление процесса поиска совпадений. Размер  буфера поиска тоже ограничен. Большой буфер поиска мог бы тоже улучшить компрессию, но опять возрастет сложность поиска по дереву, даже двоичному. Увеличение буферов также означает удлинение меток, что сокращает фактор сжатия. Двухбайтовые метки сжимают последовательности из 2-х символов в два байта плюс один флаговый бит. Запись двух байтов кода ASCII в виде этого же кода плюс два флаговых бита дает весьма малую разницу в размере по сравнению с записью метки. Это будет лучший выбор для кодера в смысле экономии времени, а плата всего один лишний бит. Мы будем говорить, что в этом случае кодер имеет 2-х байтовую точку безызбыточности. Для более длинных меток точка безызбыточности вырастает до 3 байтов.  

1.3.3 LZ78

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

Словарь начинает строиться из пустой строки в позиции  нуль. По мере поступления и кодирования  символов, новые строки добавляются  в позиции 1, 2 и т.д. Когда следующий  символ  читается из входного файла, в словаре ищется строка из одного символа . Если такой строки нет, то  добавляется в словарь, а на выход подается метка . Эта метка означает строку «нуль » (соединение нулевой строки и ). Если вхождение символа  обнаружено (скажем, в позиции 37), то читается следующий символ , и в словаре ищется вхождение двухсимвольной строки . Если такое не найдено, то в словарь записывается строка , а на выход подается метка . Такая метка означает строку , так как позицию 37 в словаре занимает символ . Процесс продолжается до конца входного файла.

В общем случае текущий символ читается и становится однобуквенной строкой. Затем кодер  пытается найти ее в словаре. Если строка найдена, читается следующий  символ и присоединяется к текущей  строке, образуя двухбуквенную строку, которую кодер опять пытается найти в словаре. До тех пор  пока такие строки находятся в  словаре, происходит чтение новых символов и их присоединение к текущей  строке. В некоторый момент такой  строки в словаре не оказывается. Тогда кодер добавляет ее в  словарь и строит метку, в первом поле которой стоит указатель  на последнюю найденную в словаре  строку, а во втором поле записан  последний символ строки (на котором  произошел обрыв успешных поисков). В табл. 1.1 показаны шаги при декодировании последовательности «sir_sid_eastman_easily_teases_sea_sick_seals».

Табл. 1.1. Шаги кодирования LZ78.

На каждом шаге строка, добавленная в словарь, совпадает  с кодируемой строкой минус последний  символ. В типичном процессе сжатия словарь начинается с коротких строк, но по мере продвижения по кодируемому  тексту, все более и более длинные  строки добавляются в словарь. Размер словаря может быть фиксированным  или определяться размером доступной  памяти каждый раз, когда запускается  программа сжатия LZ78. Большой словарь  позволяет делать глубокий поиск  длинных совпадений, но ценой этого  служит длина поля указателей (а, значит, и длина метки) и замедление процесса словарного поиска.

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

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

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

2. Удалить все  дерево при переполнении и  начать строить новое. Это решение  эффективно разбивает данные  на блоки, и в каждом блоке  используется свой собственный  словарь. Если содержимое сжимаемых  данных меняется от блока к  блоку, то этот метод дает  хорошие результаты, поскольку в  словаре не хранятся строки, которые  с малой вероятностью поступят  в дальнейшем. Здесь опять, как  и в LZ77 неявно предполагается, что похожие данные будут группироваться  близко друг к другу. 

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

Декодер LZ78 работает примерно так же, как и кодер, строя  словарь и оперируя с ним. Поэтому  он более сложен, чем декодер LZ77.

1.3.4 LZW

Это весьма популярный вариант алгоритма LZ78, который был  разработан Терри Уэлчем (Terry Welch) в 1984 ([Welch 84] и [Phillips 92]). Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Для лучшего понимания алгоритма LZW мы временно забудем, что словарь является деревом и будем предполагать, что словарь - это просто массив, состоящий из строк разной длины. Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с номерами от 0 до 255) заносятся в словарь до поступления сжимаемых данных. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, поэтому метка может состоять всего лишь из указателя, и нет надобности дополнительно хранить код символа, как в алгоритмах LZ77 и LZ78.

Метод LZW накапливает  поступающие на вход символы в  строке I. После каждого нового символа, добавленного в строку I, кодер ищет I в словаре. Если строка обнаружена, то процесс удлинения I продолжается. В некоторый момент добавление нового символа х приводит к необнаружению строки Iх (символ х был добавлен к I). Тогда кодер (1) записывает в выходной файл указатель в словаре на строку I, (2) сохраняет строку Iх (которая теперь будет называться фразой) в словаре на следующей допустимой позиции и (3) инициализирует (присваивает) строке I новое значение х. Чтобы проиллюстрировать процесс кодирования, мы еще раз воспользуемся последовательностью «alf_eats_alfalf а». Последовательность шагов отображена в табл. 1.2. Кодер выдает на выход файл:

97 (а), 108 (1), 102 (f), 32 (_), 101 (е), 97 (а), 116 (t), 115 (s), 32 (_), 256 (al), 102 (f), 265 (alf), 97 (a),

а в словаре  появляются следующие новые записи: (256: al), (257: lf), (258: f_), (259: _е), (260: ea), (261: at), (262: ts), (263: s_), (264: _a), (265: alf), (266: fa), (267: alfa).