Программы-архиваторы

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

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

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

Это может показаться Вам несущественным, но все же, давайте точно определим, сколько на жестком диске файлов. Так как в каждом байте восемь бит, то у Вас должно быть 2 в степени 80 000 файлов, причем размер каждого из них точно 10 000 байт. В результате мысленного эксперимента у нас по-прежнему останется 2 в степени 80 000 файлов, каждый из которых будет короче, чем 10 000 байт. Однако не совсем понятно, каким образом могут получиться два совершенно одинаковых "сжатых" файла! А ведь именно это мы и получаем, поскольку не так уж и много существует файлов короче 10000 байтов. Предположив, что полученные файлы отличаются друг от друга по размеру всего на один байт, то есть 9 999 байтов, затем 9 998 байтов и так далее, вы получите меньше чем 2 в степени 80 000 возможных вариантов.

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

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

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

Программы архиваторы

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

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

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

AAAAAABBBBBCCCCC

В шестнадцатеричной системе

42 42 42 42 42 4C 4C 4C 4C 4C 41 41 41 41 41

Архиватор может представить этот файл в следующем виде (шестнадцатеричном):

01 05 42 06 05 4C 0A 05 41

Это значит: с первой позиции пять раз повторяется символ "B", с позиции 6 пять раз повторяется символ "L" и с позиции 11 пять раз повторяется символ "A". Для хранения файла в такой форме потребуется всего 9 байт, что на 6 байт меньше исходного.

Описанный метод является простым и очень эффективным способом сжатия файлов. Однако он не обеспечивает большой экономии объема, если обрабатываемый текст содержит небольшое количество последовательностей повторяющихся символов. Более изощренный метод сжатия данных, используемый в том или ином виде практически любым архиватором, - это так называемый оптимальный префиксный код и, в частности, кодирование символами переменной длины (алгоритм Хаффмана). Код переменной длины позволяет записывать наиболее часто встречающиеся символы и группы символов всего лишь несколькими битами, в то время как редкие символы и фразы будут записаны более длинными битовыми строками. Например, в любом английском тексте буква E встречается чаще, чем Z, а X и Q относятся к наименее встречающимся. Таким образом, используя специальную таблицу соответствия, можно закодировать каждую букву Е меньшим числом бит и использовать более длинный код для более редких букв.

Популярные архиваторы ARJ, PAK, PKZIP работают на основе алгоритма Лемпела-Зива. Эти архиваторы классифицируются как адаптивные словарные кодировщики, в которых текстовые строки заменяются указателями на идентичные им строки, встречающиеся ранее в тексте. Например, все слова какой-нибудь книги могут быть представлены в виде номеров страниц и номеров строк некоторого словаря. Важнейшей отличительной чертой этого алгоритма является использование грамматического разбора предшествующего текста с расположением его на фразы, которые записываются в словарь. Указатели позволяют сделать ссылки на любую фразу в окне установленного размера, предшествующего текущей фразе. Если соответствие найдено, текущая фраза заменяется указателем на своего предыдущего двойника.

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

Все программы для архивации условно можно разделить на две категории:

- Для командной строки MS-DOS (ARJ, PKZIP, RAR и тд.)

- Для ос WINDOWS (WINZIP, WINRAR и т. д.)

 

Понятие архивации

 

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

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

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

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

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

Коэффициент сжатия характеризует процентное отношение сжатого (архивного) файла по отношению к исходному, т.е. Kсжатия = (Laрхив/Lисхоный) 100%

Однако удобнее использовать обратное отношение, которое показывает во сколько раз архивный файл меньше исходного. Kуменьшения = (Lисхоный/ Laрхив)

Существует два основных метода архивации

Алгоритм Хаффмана. Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 1 байта, а для записи редких символов – более длинные, то суммарный объем файла уменьшится. Например буквы а,о,е,и – встречаются очень часто в русском тексте, объем каждой буквы равен 1 байт (8 бит), их можно заменить на цифры 0,1,2,3, которые можно разместить в 2-х битах. Т.е. сжатие будет равен 25%, т.е. сжатие в 4 раза.

Алгоритм Лемпеля-Зива. Классический алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования. Он формулируется следующим образом : «если в более раннем тексте уже встречалась подобная последовательность байт, то в архивный файл записывается только ссылка на эту последовательность (смещение, длина), а не сам текст». Так фраза «КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ» [24] закодируется в последовательность «КОЛО(-4,3)_О(-6,4)_(-7,7)ЬНИ» [13]. Коэффициент сжатие - 54%. Аналогично сжимается изображение. Большие области одного цвета заменяются на ссылку: (цвет, длина) Графические файлы сжимаются очень хорошо– в 100–200 раз

Типы архивных файлов

В файловой системе компьютера архивные файлы имеют строго заданный тип (расширение). Так, наиболее часто встречающиеся архивы имеют тип: ZIP, RAR, ARJ.

Кроме них на компьютерах используются архивы: CAB, LZH, TAR, GZ, UUE, BZ2, ISO…

Архивный файл

 

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

- имя файла;

- сведения о каталоге, в котором содержится файл;

- дата и время последней модификации файла;

- размер файла на диске и в архиве;

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

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

- game.rar – заархивирован при помощи архиватора WinRAR;

- game.arj – заархивирован при помощи архиватора ARJ;

- game.zip - заархивирован при помощи архиватора ZIP.

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

 

 

 

• Архиваторы MS DOS

 

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

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

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

Наиболее известные программы-архиваторы для MS-DOS: ARJ (разработчик - Robert K. Jung), PKZIP(компания PKWARE Inc.), IHA (Haruyasu Yoshizaki), ZOO (Rahul Dhesi). Безусловным лидером во всем мире за последние 5 лет стал архиватор RAR. В настоящее время RAR активно вытесняет ZIP как основную утилиту сжатия FTP архивов в сети INTERNET. RAR является единственной всемирно используемой программой, созданной русским программистом (за исключением TETRIS). Все архиваторы отличаются используемыми алгоритмами сжатия, форматами архивных файлов, скоростью работы и т.д.

 

• ARJ

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

Программа ARJ позволяет:

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