Алгоритм Хоффмана

Сжатие (архивация информации)

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

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

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

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

Существует два основных метода архивации без потерь:

- алгоритм Хоффмана;

- алгоритм Лемпеля – Зива.

Практически все популярные программы архивации без потерь используют объединение этих двух методов – алгоритм LZH.

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

Например, английский алфавит имеет частоты, показанные в табл. 7.1 Со

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

Таблица 7.1

Частота встречаемости букв анлгийского алфавита и соответсвующий код Хоффмана

Буква	Частота, %	Код Хоффмана	Буква	Частота, %	Код Хоффмана
E			M	2,5
T	10,5		U	2,4
A	8,1		G
O	7,9		Y	1,9
N	7,1		P	1,9
R	6,8		W	1,5
I	6,3		B	1,4
S	6,1		V	0,9
H	5,2		K	0,4
D	3,8		X	0,15
L	3,4		J	0,13
F	2,9		Q	0,11
C	2,7		Z	0,07

Строка двоичных кодов Хоффмана единственным образом разлагается на составные части, так как она действительно является просто строкой, представленной двоичным деревом знаков, обозначающих соответствующие буквы (рис. *.*)

Рис. 7.1

На рис. 9.3 правые ветки дерева соответствуют коду 1, а левые – коду 0.

Тогда строка из 29 знаков исходного текста

WENEEDMORESNOWFORBETTERSKIING

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

01110110 01100100 10011011 00011111 01011100 01101100 11100111

01010011 11010110 11100100 00100110 01011011 01101000 11101010 10110000 001,

которая единственным образом расчленяется на буквы алфавита при простом сканировании текста слева направо для восстановления исходного сообщения. Заметим, что в случае сжатия методом Хоффмана исходная строка из 29 байтов (один символ кодируется одним байтом) заменилась строкой из 16 байтов.

Алгоритм Лемпеля–Зива

Классический алгоритм Лемпеля–Зива - LZ77, названный так по году опубликования, предельно прост. Он формулируется следующим образом: “если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче, чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность”.

Пример

Фраза КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ

закодируется как

КОЛО(-4, 3)_(-5, 4)0_(-14, 7)ЬНИ

Строка из одинаковых символов

ААААААА

закодируется как

А(-1, 6)

Дата добавления: 2014-01-05