Архиватор

ОГЛАВЛЕНИЕ 

ВВЕДЕНИЕ          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. Допустим, у нас есть следующая таблица частот:

15	7	6	6	5
А	Б	В	Г	Д

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

А	Б	В	Г	Д
0	100	101	110	111

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

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

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

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

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

	sir_sid_eastman_easily_t	eases_sea_sick_seals

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

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

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

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

… sir

_sid_eastman_easily_tease

s_sea_sick_seals …

…

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