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

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

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

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

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

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

Под степенью сжатия понимают отношение размеров сжатого файла и исходного, выраженное в процентах.

Степень сжатия зависит от используемой программы сжатия, метода сжатия и типа исходного файла. Лучше всего сжимаются файлы графических образов, текстовые файлы, файлы данных, степень сжатия которых может достигать 5 — 40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей — 60 — 90%. Почти не сжимаются архивные файлы. Программы для архивации отличаются используемыми методами сжатия, что соответственно влияет на степень сжатия.

Архивация (упаковка) — помещение (загрузка) исходных файлов в архивный файл в сжатом или несжатом виде.

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

Программы, осуществляющие упаковку и распаковку файлов, называются программами-архиваторами.

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

Основные виды программ-архиваторов

В настоящее время применяется несколько десятков программ-архиваторов, которые отличаются перечнем функций и параметрами работы, однако лучшие из них имеют примерно одинаковые характеристики. Из числа наиболее популярных программ можно выделить: Zip (и его модификация WinZip), WinRAR, Arj (и его разновидности), G-Zip, 7-Zip.

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

Самораспаковывающийся архив получил название SFX-архив (SelF-eXtracting). Архивы такого типа обычно создаются в формате ЕХЕ-файла.

Многие программы-архиваторы производят распаковку файлов, выгружая их на диск, но имеются и такие, которые предназначены для создания упакованного исполняемого модуля (программы). В результате такой упаковки создается программный файл с теми же именем и расширением, который при загрузке в оперативную память самораспаковывается и сразу запускается. Вместе с тем возможно и обратное преобразование программного файла в распакованный формат. К числу таких архиваторов относятся программы Upx, PKLITE, LZEXE.

Ппрограмма EXPAND, входящая в состав утилит операционной системы Windows, применяется для распаковки файлов программных продуктов, поставляемых фирмой Microsoft.

Способы управления программой-архиватором

Управление программой-архиватором осуществляется одним из следующих способов:

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

Степень сжатия информации зависит от нескольких причин:

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

Во-вторых, большое значение имеет метод сжатия.

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

Программы сжатия информации

Сжатие происходит с помощью программ архиваторов. На сегодняшний день наиболее распространенными являются четыре архиватора -- WinRar, WinAce, 7Zip и WinZip. Что касается последней программы, она не выдерживает никакой критики.

Более подробно остановимся на архиваторе - WinRar Данный архиватор может ассоциироваться со следующими типами файлов: RAR, ZIP, CAB, ARJ, LZH, ACE, 7-Zip, TAR, GZip, UUE, BZ2, JAR, ISO.

Программа поддерживает файлы практически неограниченного размера (до 8,589,934,591 Гб). Правда, для работы с файлами размером более 4 Гб вам необходимо работать в файловой системе NTFS.

При выборе оптимальных настроек для сжатия необходимо учитывать несколько моментов:

Несмотря на то, что WinRAR поддерживает формат ZIP, в большинстве случаев рекомендуется выбирать RAR. Это обеспечит более высокий уровень сжатия. Вы можете сжать файлы в ZIP, если вы не уверены, что на компьютере, на котором будут распакованы файлы, будет установлена программа, с помощью которой можно будет распаковать файлы в формате RAR.

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

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

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

Среди других настроек WinRar"a можно отметить возможность создания самораспаковывающихся архивов с указанием пути распаковки. Такие файлы не требуют наличия на компьютере, на котором их планируется разархивировать, программы-архиватора. Подобные архивы получили название SFX-archives. Их недостатком по сравнению с обычными архивными файлами является больший размер, так как они, кроме собственно запакованных файлов, содержат также исполнительный EXE-модуль.

Cодержимое RAR-архива можно сделать невидимым. Для этого в настройках программы, в окне Archiving with Password нужно установить флажок напротив строки Encrypt File Names.

Можно также установить пароль на открытие архива. В результате ошибки передачи архива по локальной сети или скачивания его из Интернета, а также по причине аппаратного сбоя или вирусной атаки архив может быть поврежден. WinRar позволяет определить целостность данных, протестировав архив с помощью опции Test Archived Files.

Для того чтобы свести к минимуму вероятность потери данных, при создании архивов WinRar рекомендуется использовать опцию Put Recovery Record (этот флажок можно найти на вкладке General окна создания архива).

Если это было сделано, то в случае повреждения архива его можно будет восстановить.

Кроме этого в WinRar, можно уменьшить вероятность повреждения RAR-архива, указав при его создании размер информации для восстановления. Для этого нужно выполнить команду Commands > Protect Archive From Damage в окне Winrar. При этом объем Recovery Record не может превышать десяти процентов от общего размера архива.

Для восстановления поврежденных RAR-архивов необходимо выбрать нужный файл в окне WinRar и выполнить команду Tools > Repair.

WinRAR умеет встраиваться в контекстное меню, причем поддерживает не только меню проводника, но и других программ, например популярного файлового менеджера Total Commander. Это дает возможность быстро архивировать файлы, используя настройки по умолчанию и не открывая для этого окно программы. Кстати, настройки по умолчанию можно изменить, в соответствии с тем, какие требования вы предъявляете к своим архивам. Сделать это можно, открыв окно WinRar и выполнив команду Options > Settings. В этом окне нужно перейти на вкладку Compression и нажать кнопку Create Default. Настройки, заданные в этом окне и будут использоваться для быстрой архивации. Если же требуется изменить настройки архивации, это тоже можно сделать при помощи контекстного меню. Для этого нужно выбрать команду Add to Archive… Тут можно установить формат и степень сжатия, указать имя архива и выбрать другие параметры архивации.

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

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

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

Что подразумевается под степенью сжатия файла?

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

Степень сжатия файла зависит только от типа файла: так ли это на самом деле?

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

При попытке упаковки таких данных в архив существенного уменьшения размера добиться практически невозможно. То же самое касается формата WAV. Однако, если произвести не сжатие, а перекодирование из WAV в MP3, размер можно уменьшить раз в десять и более. Многие пользователи тут же и отталкиваются от того, что степень сжатия файла зависит именно от начального и конечного формата. Это не совсем так, поскольку важную роль играет и применяемый алгоритм перекодирования, о чем будет сказано отдельно. А пока остановимся на использовании архиваторов.

От чего зависит степень сжатия файла при упаковке в архив?

Чтобы изначально понять суть сжатия такого типа, для простоты объяснения в пример приведем самый обычный архиватор WinRAR. Типы упаковываемых данных не трогаем, а основное внимание сосредоточим на инструментах самого приложения.

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

Если же применительно к архиваторам рассматривать файловые форматы, из самых сжимаемых можно выделить текстовые документы любых форматов.

Относительно неплохо сжимаются некоторые исполняемые файлы EXE-формата (при стандартном методе сжатия можно добиться уменьшения размера больше, чем вполовину). Самыми, как уже говорилось, несжимаемыми являются объекты мультимедиа. И, если картинки уменьшить по размеру хоть как-то можно, с аудио и видео без изменения начального формата такие действия не проходят, и архиваторы тут совершенно ни причем.

Типы сжатия графики, видео и аудио

Применительно к мультимедиа различают два основных типа сжатия: с потерей качества (lossy) и без потерь (lossless). И в данном случае степень сжатия файла зависит как раз от используемой технологии компрессии.

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

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

Самые распространенные программы на все случаи жизни

От чего зависит степень сжатия файла, немного разобрались. Теперь следует сказать несколько слов о применяемых программных продуктах. Среди архиваторов самыми распространенными можно назвать WinRAR, WinZIP и 7-Zip.

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

Краткие итоги

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

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

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

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

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

Процесс записи файлов в архивный файл называется архивацией (архивированием, упаковкой), а извлечение файлов из архива - разархивацией (разархивированием, распаковкой).

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

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

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

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

§ существующие непрерывные архивы обновляются медленнее, чем обычные;

§ зашифрованные непрерывные архивы невозможно изменять;

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

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

Непрерывные архивы лучше использовать в тех случаях, когда:

§ архив редко обновляется;

§ нет необходимости часто извлекать из архива один или несколько файлов;

§ архивируется один большой файл;

§ степень сжатия важнее скорости сжатия.

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

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

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

Файлы в существующих томах невозможно добавлять, обновлять или удалять.

Самораспаковывающийся (SFX, от английских слов SelF-eXtracting) архив - это архив, к которому присоединен исполнимый модуль. Этот модуль позволяет извлечь файлы, просто запустив архив как обычную программу. Таким образом, для извлечения содержимого SFX-архива не требуется дополнительных внешних программ. SFX-архивы, как и любые другие исполнимые файлы, обычно имеют расширение.EXE, но с ними можно работать так же, как и с любым другим архивом.

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

Многотомные и самораспаковывающиеся архивы также могут быть непрерывными.

Программы, осуществляющие архивацию/разархивацию файлов, называют программы-архиваторы .

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

При создании архива программа-архиватор автоматически присваивает архивному файлу «свое» расширение, например, zip, rar и др.

Управление программой-архиватором осуществляется одним из следующих способов:

1. с помощью командной строки;

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

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

4. с помощью элементов графического интерфейса.

Несмотря на множество программ-архиваторов, современный пользователь, как правило, реально работает с двумя форматами архивов: ZIP и RAR.

Методы сжатия данных имеют достаточно длинную историю развития, которая началась задолго до появления первого компьютера. В этой статье будет произведена попытка дать краткий обзор основных теорий, концепций идей и их реализаций, не претендующий, однако, на абсолютную полноту. Более подробные сведения можно найти, например, в Кричевский Р.Е. , Рябко Б.Я. , Witten I.H. , Rissanen J. , Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. и др.

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

Степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;

Скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;

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

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

Под необратимым сжатием подразумевают такое преобразование входного потока данных, при котором выходной поток, основанный на определенном формате информации, представляет, с некоторой точки зрения, достаточно похожий по внешним характеристикам на входной поток объект, однако отличается от него объемом. Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (т.е. сжатой и несжатой информации, в соответствии с некоторым определенным форматом данных), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия, например, данных растровых графических файлов с низкой степенью повторяемости байтов в потоке. При таком подходе используется свойство структуры формата графического файла и возможность представить графическую картинку приблизительно схожую по качеству отображения (для восприятия человеческим глазом) несколькими (а точнее n) способами. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходное изображение в процессе сжатия изменяется, то под качеством можно понимать степень соответствия исходного и результирующего изображения, оцениваемая субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.

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

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

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

Сжатие способом кодирования серий

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.

Сжатие без применения метода RLE

Процесс сжатия данных без применения метода RLE можно разбить на два этапа: моделирование (modelling) и, собственно, кодирование (encoding). Эти процессы и их реализующие алгоритмы достаточно независимы и разноплановы.

Процесс кодирования и его методы

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

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