Методы сжатия данных имеют достаточно длинную историю развития, которая началась задолго до появления первого компьютера. В этой статье будет произведена попытка дать краткий обзор основных теорий, концепций идей и их реализаций, не претендующий, однако, на абсолютную полноту. Более подробные сведения можно найти, например, в Кричевский Р.Е. , Рябко Б.Я. , 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 и даже переменной. Если распределение вероятностей частот появления символов из алфавита входного потока известно, то можно построить модель оптимального кодирования. Однако, ввиду существования огромного числа различных форматов файлов задача значительно усложняется т.к. распределение частот символов данных заранее неизвестно. В таком случае, в общем виде, используются два подхода.

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

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

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

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

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

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

Сжатие происходит с помощью программ архиваторов. На сегодняшний день наиболее распространенными являются четыре архиватора -- 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. Очень часто бывает необходимо производить регулярное архивирование одних и тех же папок на жестком диске. Добавив в закладки информацию о месторасположении этих папок, можно быстро переходить в них в окне программы и производить архивацию необходимых файлов и вложенных директорий.

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

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

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

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

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

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

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

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

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

В сети сегодня популярны десятки архиваторов, причем, в описание у каждой программы можно встретить что ее алгоритм самый-самый… Решил взять несколько популярных в сети архиваторов, а именно: WinRar, WinUha, WinZip, KGB archiver, 7Z и проверить их в «боевых» условиях.

Небольшое предисловие… Сравнение, возможно будет не слишком объективное. Сравнение ахиваторов проводилось на самом обычном домашнем компьютере, среднем по показателям на сегодняшний день. К тому же не брались различные типы данных: сравнение сжатия проводилось на обычном «вордовском» документе, коих у многих кто учиться или работает с ними - сможет скопиться огромное количество. Ну и логично, что информацию, которую редко используешь - целесообразно запаковать в архив и иногда извлекать. Да и передавать такой файл намного легче: и на флешку быстрее скопируется, нежели куча мелких файлов, да и по интернету быстрее скачается…

Таблица сравнения сжатия

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

Как видно из небольшой таблички, что самая высокая степень сжатия достигается у программы KGB Archiver 2 - в 23 раза уменьшился исходный размер файла! Т.е. если у вас на жестком диске несколько гигабайт различной документации, которой вы не пользуетесь и хотите удалить (но не покидает чувство, а вдруг пригодится) - не проще ли сжать такой программой и записать на диск…

Но обо всех «подводных камнях» по порядку…

KGB Archiver 2

В общем то не плохой архиватор, по заявлениям разработчиков их алгоритм сжатия один из самых «сильных». Сложно не согласиться…

Только вот скорость сжатия оставляет желать лучшего. Например, файл в примере (около 3 мб) программа сжимала около 3 мин! Нетрудно прикинуть, что один CD диск она будет сжимать пол дня, если не больше.

Но особое удивление вызывает не это. Распаковка файла длиться по времени столько же, сколько компрессия! Т.е. если вы потратили пол дня на то, чтобы сжать часть своих документов, то столько же времени вы потратите, чтобы достать их из архива.

Итог: программу можно использовать для небольших объемов информации, особенно, когда важен минимальный размер исходного файла (например, файл нужно разместить на дискете, или на небольшой по вместимости флешке). Но опять таки, угадать заранее размер сжатого файла нельзя, и возможно, время на сжатие вы потратите впустую…

WinRar

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

На удивление WinRar сжал файл за несколько секунд, причем размер файла уменьшился в 17 раз. очень достойный результат, если еще учесть что время затраченное на обработку ничтожно мало. А время на распаковку файла - еще меньше!

Итог: отличная программа, показывающая одни из самых лучших результатов. В процессе настроек сжатия можно так же указать максимальный размер архива и программа его разобьет на несколько частей. Это очень удобно, чтобы перенести файл с одного компьютера на другой на флешке или CD/DVD диске, когда целиком файл на не запишешь…

WinUha

Сравнительно молодой архиватор. Назвать его сверх-популярным нельзя, но интерес у многих пользователей к нему кто часто работает с архивами - есть. И не случайно, ведь по заявлениям разработчиков архиватора, его алгоритм сжатия сильнее чем у RAR и 7Z.

В нашем небольшом эксперименте я бы не сказал что это так. Возможно, что на некоторых других данных он и покажет куда лучшие результаты…

Кстати, при установке выбирайте английский язык, на русском - программа выдает «крякозабры».

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

7Z

Очень популярный бесплатный архиватор. Многие утверждают что степень сжатия в 7z реализована даже лучше чем в WinRar. Вполне возможно, но при сжатии с уровнем «Ультра» на большинстве файлов он проигрывает WinRar’у.

Итог: неплохая альтернатива WinRar’у. Вполне сопоставимая степень сжатия, хорошая поддержка русского языка, удобное встраивание в контекстное меню проводника.

WinZip

Легендарный, один из самых популярных некогда архиваторов. В сети, наверное, самые часто-встречающиеся архивы - это «ZIP». И не случайно - ведь несмотря на не самую высокую степень сжатия, скорость работы - просто поражает. Например, Windows открывает такие архивы как обычные папки!

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

АРХИВАТОРЫ

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

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

Степень сжатия : K c =V c /V o *100%

K c – коэффициент сжатия, V c – объем сжатого файла, V o – исходный объем файла.

Степень сжатия зависит от:

1) используемой пограммы – архиватора,

2) метода сжатия,

3) типа исходного файла: текстового, графического, видео, звукового и т.д.

Программы, осуществляющие упаковку и распаковку файлов называются архиваторами. Наиболее распространенными являются: ARJ, ZIP, RAR. Расширение архивных файлов совпадает с названием использованного для их создания архиватора.

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

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

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

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

3. В следующим принципе используется закономерность что в тексте буквы встречаются с разной частотой. Например в этом тексте пробел самый распространенный символ, очень часто встречаются символы «а», «и». Эти часто встречающиеся символы можно представлять короткой комбинацией битов, остальные символы возможно кодировать более длинной последовательностью. Например:

4. Физически ПК выделяет место для размещения файлов на диске по кластерам - блоками по 4 кБ. Меньше выделить невозможно. Например если файл имеет размер 8193 байта (8 кБ и 1 байт), физически он будет занимать 16 кБ или 16384 байта. Объединение группы файлов в один позволяет сэкономить на этих остатков. При упаковки маленьких файлов это дает большую экономию.

Итого, при отдельном размещении файлов не используются 6 кБ, что составляет 100% от содержания файлов. Во втором случае неиспользуемыми остается 2 кБ, 33%.

Архиватор zip

Запаковка файлов pkzip [ключи] <имя архива> [пути файлов]

Ключи: -rp архивация с подкаталогами с сохранением структуры

SPWD защита архива паролем (PWD)

A добавить файлы в архив

M переместить файлы в архив

V просмотр содержимого архива

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

Распаковка файлов pkunzip [ключи] <имя архива> [имена файлов]

Ключи: -d распаковка с подкаталогами с сохранением структуры

SPWD пароль архива (PWD)

Архиватор arj

arj <команда> [ключи] <имя архива> [имена файлов]

Для архиватора arj один файл выполняет операции и распаковки и запаковки.

Команды: a архивация

e распаковка без сохранения структуры каталогов

x распаковка с сохранением структуры

l просмотр содержимого архива

m переместить файлы в архив

d удалить файлы из архива

Ключи: -r упаковка с подкаталогами с сохранением структуры

V разбивка архива на тома с объемом vol(если указан)

размер для стандартных дискет (360, 720, 1200, 1440) указывается в килобайтах, размер нестандартных дискет указывается в байтах

V указывается при распаковке многотомного архива

GPWD пароль архива (PWD )

Запаковка файлов

Распаковка файлов