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

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

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

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

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

Программа Формат Степень сжатия Размер, к.байт Во сколько раз уменьшился размер файла ?
KGB Archiver 2 .kgb максимум 141411 22,99
WinRar .rar максимум 190546 17,07
WinUha .uha максимум 214294 15,17
7Z .7z максимум 218511 14,88
WinZip .zip максимум 299108 10,87
Исходный файл .rtf Без сжатия 3252107 1

Как видно из небольшой таблички, что самая высокая степень сжатия достигается у программы 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 поддерживают все современные архиваторы!

3. Показатель степени сжатия файлов

Сжатие информации в архивных файлах производится за счет устранения избыточности различными способами, например за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов или повторяющейся последовательности символов в виде коэффициента повторения и соответствующих символов. Алгоритмы подобного сжатия информации реализованы в специальных программах-архиваторах (наиболее известные из которых arj/arjfolder, pkzip/pkunzip/winzip, rar/winrar) применяются определенные Сжиматься могут как один, так и несколько файлов, которые в сжатом виде помещаются в так называемый архивный файл или архив.

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

Степень сжатия файлов характеризуется коэффициентом Кс, определяемым как отношение объема сжатого файла Vc к объему исходного файла Vо, выраженное в процентах (в некоторых источниках используется обратное соотношение):

Кс=(Vc/Vo)*100%

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

Наиболее хорошо сжимаются файлы графических образов, текстовые файлы и файлы данных, для которых коэффициент сжатия может достигать 5 - 40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей Кс = 60 - 90%. Почти не сжимаются архивные файлы. Это нетрудно объяснить, если знать, что большинство программ-архиваторов используют для сжатия варианты алгоритма LZ77 (Лемпеля-Зива), суть которого заключается в особом кодировании повторяющихся последовательностей байт (читай - символов). Частота встречаемости таких повторов наиболее высока в текстах и точечной графике и практически сведена к нулю в архивах.

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

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

Характеристики архиваторов -- обратно зависимые величины. То есть, чем больше скорость сжатия, тем меньше степень сжатия, и наоборот.

На компьютерном рынке предлагается множество архиваторов -- у каждого свой набор поддерживаемых форматов, свои плюсы и минусы, свой круг почитателей, свято верящих в то, что используемый ими архиватор самый лучший. Не будем никого и ни в чем разубеждать -- просто попытаемся беспристрастно оценить самые популярные архиваторы в плане функциональности и эффективности. К таковым отнесем WinZip, WinRAR, WinAce, 7-Zip -- они лидируют по количеству скачиваний на софтовых серверах. Рассматривать остальные архиваторы вряд ли целесообразно, поскольку процент применяющих их пользователей (судя по числу скачиваний) невелик.

Поскольку в задании каждая пара значений (,) встречается один раз, то корреляционная таблица примет вид единичной матрицы. Значит условные средние совпадают со значениями. Отсюда следует, что корреляционное отношение равно 1 и, следовательно...

Аппроксимация функций методом наименьших квадратов

Далее аппроксимируем функцию квадратичной функцией. Для определения коэффициентов, и воспользуемся системой (3.2.1) Используя итоговые суммы таблицы 3, расположенные в ячейках B29, C29, D29, E29, F29, G29 и H29, запишем систему (2.1.4) в виде (3.2...

Виды архиваторов

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

Как можно классифицировать информационные системы по степени автоматизации?

Классификация информационных технологий

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

Как один из необходимых этапов в создании эффективной системы безопасности территории, предприятия, ОИД, выполним анализ уязвимости предприятия «FitMax»...

Математическое обоснование степени уязвимости объекта информационной деятельности на примере предприятия ООО "FitMax"

Для каждого из каналов проводятся расчеты вероятности степени защищенности информации. Акустический канал: Виброакустический канал: Человеческий фактор: Исходя из полученных данных...

Микропроцессор: назначение, состав, основные характеристики

Способов работы с файлами в Windows существует несколько. Первый -- это «дисковые папки» в папке «Мой компьютер». С их помощью можно добраться до любого нужного файла в любой папке и на любом диске. Однако этот способ далеко не идеален...

Поисковая система

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

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

Расчет параметров асинхронного энергосберегающего электродвигателя

Характеристики степеней защиты электрических машин обозначают двумя латинскими буквами IP (International Protection) и двумя цифрами...

Система электронной коммерции и статистики для продажи автомобильных запчастей

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

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

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

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

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

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

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

Степень сжатия файлов характеризуется коэффициентом Кс, определяемым как отношение объема сжатого файла Vc к объему исходного файла Vо, выраженное в процентах:

Kc=(Vc/ V0)*100%

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

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

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

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

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

Наиболее популярные форматы архивов
ZIP - еще со времен DOS-a один из самых популярных и распространенных архивных форматов, основанный на алгоритмах сжатия предложенных в 80-х годах прошлого столетия израильскими математиками Лемпелем и Зивом. Он отличается приемлемой степенью сжатия информации и достаточно высоким быстродействием. Сегодня он является стандартом де-факто в интернете, и его в обязательном порядке поддерживают практически все программы-архиваторы.
RAR - разработан российским программистом Евгением Рошалем и позволяет получить размер сжатого файла гораздо меньший, чем ZIP, но ценой этому является более продолжительный процесс обработки архива. В целом формат RAR значительно лучше других оптимизирован для решения сложных задач с использованием большого количества файлов и гигабайтных дисковых пространств.
ARJ - несколько устаревший формат, до сих пор отличающийся, наверное, наиболее широкими возможностями по настройке.
CAB - применяется в продуктах Microsoft как стандартный для упаковки файлов, причем его алгоритм, нигде не опубликованный и хранимый фирмой за семью печатями, представляет собой достаточно совершенный продукт, имеющий высокий коэффициент сжатия.
GZIP, TAR - получили наибольшее распространение в системах на базе Unix и ее самой популярной разновидности Linux.
ACE - достаточно новый формат с высокой степенью сжатия, завоевывающий все большую популярность.
Многие программы, являющиеся достаточно популярными в мире архиваторов базируются на том или ином формате и носят аналогичные названия. Например, для ОС Windows наиболее популярными являются архиваторы WinRAR, WinZIP, WinACE. Кроме этого все они имеют инструменты для работы с другими форматами архивов. Несмотря на это, могут возникнуть проблемы с совместимостью форматов архивов в различных программах. Во многих случаях удачным решением проблемы совместимости архивов различных типов является создание архивов в виде самораспаковывающихся программ (EXE-файлов), в состав которых входят все необходимые механизмы для извлечения информации из архива, таким образом, отпадает необходимость иметь на компьютере соответствующую программу-распаковщик архива.

Gif" width="25" height="25" />.php?viewcat=4">Обсудить на форуме

Несмотря на то, что объемы внешней памяти ЭВМ постоянно растут, потребность в архивации не уменьшается. Это объясняется тем, что архивация необходима не только для экономии места в памяти, но и для надежного хранения копий ценной информации, а также для быстрой передачи информации по сети на другие ЭВМ.

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

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

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

Степень сжатия информации зависит от содержимого файла, а также от выбранного метода архивации. Степень (качество) сжатия файлов характеризуется коэффициентом сжатия K c , определяемым как отношение объема сжатого файла V c к объему исходного файла V o , выраженное в процентах:

Чем меньше величина K c , тем выше степень сжатия информации.

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

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

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

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

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

Наиболее популярны и широко используются следующие архиваторы: ARJ, PKZIP/PKUNZIP, RAR, ACE, LHA, ICE, PAK, PKARC/PKXARC, ZOO, HYPER, AIN.

Наиболее высокоэффективными являются архиваторы RAR, ACE, AIN, ARJ.

Они обеспечивают наибольшую степень сжатия информации и имеют наиболее высокую скорость работы. Архиватор RAR имеет удобный графический интерфейс и позволяет читать текстовые файлы, находящиеся как в rar-архиве, так и в arj и zip-архивах. Архиватор AIN имеет русскоязычный интерфейс. Архиваторы WinRAR-95 и WinZIP работают только в среде Windows. Они необходимы при работе с длинными и русскими именами файлов в Windows. В настоящее время именно эти архиваторы применяются чаще всего.


Раздел 3. Прикладное программное обеспечение ИТ

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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