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

В основе этого алгоритма лежит кодирование не байтами, а битовыми группами.

• Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов.

• Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность).

• Образующаяся в результате кодирования иерархическая структура приклады­вается к сжатому документу в качестве таблицы соответствия.

Глава 14. Приемы и методы работы со сжатыми данными

Пример кодирования символов русского алфавита представлен на рис. 14.1.

Как видно из схемы, представленной на рис. 14.1, используя 16 бит, можно закоди­ровать до 256 различных символов. Однако ничто не мешает использовать и пос­ледовательности длиной до 20 бит — тогда можно закодировать до 1024 лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова).

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

Синтетические алгоритмы

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

Программные средства сжатия данных

«Классическими» форматами сжатия данных, широко используемыми в повсе­дневной работе с компьютером, являются форматы.ZIP и.ARJ. В последнее время к ним добавился популярный формат.RAR. Программные средства, предназначен­ные для создания и обслуживания архивов, выполненных в данных форматах, при­ведены в табл. 14.2.

14.2. Программные средства сжатия данных

Таблица 14.2. Средства архивации файлов

Операционная система	Формат сжатия	Средство архивации	Средство разархивирования
MS-DOS	.ZIP	PKZIP.EXE	PKUNZIP.EXE
.RAR	RAR. EXE	UNRAR.EXE
.ARJ	ARJ.EXE
Windows 9x	.ZIP	WinZip
.RAR	WinRAR
.ARJ	WinArj

Я Несмотря на то что средства архивации, предназначенные для операционной системы MS-DOS, вполне могут работать под управлением Windows 9x (в окне Сеанс MS-DOS), пользоваться ими не рекомендуется. В первую очередь, это связано с тем, что при обработке файлов происходит утрата «длинных имен» файлов и подмена их именами MS-DOS по спецификации 8.3. Это может создать потребителю документа определен­ные неудобства, а в случаях, когда архивация производится с цепью резервного копи­рования, утрата «длинных имен» вообще недопустима.