Под упаковкой (сжатием, уплотнением) понимают такое перекодирование данных, которое позволяет уменьшить по сравнению с исходным объем памяти, необходимый для их хранения.
Программы – архиваторы служат для сжатия файлов, что позволяет хранить их в сжатом виде в одном архивном файле (архиве), что позволяет уменьшить объём занимаемой файлами памяти.
Сжатие информации – это процесс преобразования информации, хранящейся в файле, к виду при котором уменьшается избыточность в её представлении и соответственно требуется меньший объём памяти для хранения.
Упаковка данных используется для экономии дискет при переносе программ и данных с одного компьютера на другой. В упакованном виде удобно хранить временно не используемые программы и данные, а также копии файлов, создаваемые на случай утраты оригиналов.
Созданные архивы можно обновлять, добавлять в них файлы, удалять файлы из архива, проверять архив на целостность. При необходимости файлы можно вывести их архива - разархивировать.
Архивный файл – это специальным образом организованный файл, содержащий в себе один или несколько файлов в сжатом или не сжатом виде и служебную информацию об именах файлов, дате и времени их создания или модификации, размерах и т.п.
Архивация (упаковка) – помещение (загрузка) исходных файлов в архивный файл в сжатом или не сжатом виде.
Разархивация (распаковка) – процесс восстановления файлов из архива точно в таком виде, какой они имели до загрузки в архив. При распаковке файлы извлекаются из архива и помещаются на диск или в оперативную память.
Программы, осуществляющие упаковку и распаковку файлов, называют программами-архиваторами.
Для сжатия файлов пользователями ПК широко используется множество программ архиваторов.
Преимущества архиваторов:
1. позволяют сжимать от 22 % до 90% информации;
2. позволяют обновлять программное обеспечение, причем архиватор сам следит за процессом обновления;
3. позволяют создавать самораспаковывающиеся архивы;
4. позволяют содержать в одном файле группу однородных файлов.
5. поддержка непрерывных архивов, в которых степень сжатия может быть на 10 - 50% больше, чем при обычных методах сжатия, особенно при упаковке большого количества маленьких похожих файлов;
6. поддержка многотомных архивов;
7. создание самораспаковывающихся (SFX) обычных и многотомных архивов с помощью стандартного или дополнительных модулей SFX;
8. восстановление физически поврежденных архивов;
9. другие дополнительные функции, например, шифрование, добавление архивных комментариев (с поддержкой ESC-последовательностей ANSI), протоколирование ошибок и пр.
А рхив содержит оглавление, в котором находится следующая информация:
- имя файла,
- дата и время создания или модификации,
- объем файла до и после архивации,
- процент сжатия,
- код циклического контроля для каждого файла (контрольная сумма)
Архиваторов очень много: ARJ, RAR, ZIP, CAB, LZH, GIF, TIF, PCX …
Архивные файлы могут быть непрерывными, многотомными, самораспаковывающимися.
Непрерывный архив – это архив, запакованный специальным способом, при котором все сжимаемые файлы рассматриваются как один последовательный поток данных.
Тома – это фрагменты архива, состоящего из нескольких частей. Тома поддерживаются только в формате RAR, вы не можете создавать тома ZIP. Обычно тома используются для сохранения большого архива на нескольких дискетах или других сменных носителях.
Самораспаковывающийся (SFX, от англ. SelF-eXtracting) архив – это архив, к которому присоединен исполнимый модуль. Этот модуль позволяет извлечь файлы, просто запустив архив как обычную программу. Таким образом, для извлечения содержимого SFX-архива не требуется дополнительных внешних программ. SFX-архивы, как и любые другие исполнимые файлы, обычно имеют расширение.EXE.
Самораспаковывающийся архивный файл – это загрузочный, исполняемый модуль, который способен к самостоятельной разархивации находящихся в нём файлов без использования программы архиватора
SFX-архивы удобны в тех случаях, когда нужно передать кому-то архив, но вы не уверены, что у адресата есть соответствующий архиватор для извлечения файлов. Вы также можете использовать SFX-архивы для распространения своих собственных программ.
Степень сжатия информации зависит от типа файла, а также от выбранного метода упаковки. Степень (качество) сжатия файлов характеризуется коэффициентом сжатия Кс, определяемым как отношение объёма сжатого файла Vc к объёму исходного файла Vo, выраженное в процентах: Кс = 
.
Чем меньше величина КС, тем выше степень сжатия информации.
Несмотря на изобилие алгоритмов сжатия данных, теоретически есть только три способа сжатия. Это либо изменение содержания данных, либо изменение их структуры, либо одновременно и то и другое.
Если при сжатии данных происходит изменение их содержания, потеря информации, то метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления исходной последовательности. Такие методы называют также методами сжатия с регулируемой потерей информации. Они применимы только для тех типов данных, для которых формальная утрата части содержания не приводит к значительному снижению потребительских свойств. В первую очередь это относится к мультимедийным данным: видеорядам, музыкальным записям, звукозаписям и рисункам. Методы сжатия с потерей информации обычно обеспечивают гораздо более высокую степень сжатия, чем обратимые методы, но их нельзя применять к текстовым документам, базам данных и, тем более, к программному коду.
Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим. Из результирующего кода можно восстановить исходный массив путем применения обратного метода. Обратимые методы применяются для сжатия любых типов данных.
Существует достаточно много обратимых методов сжатия данных, однако в их основе лежит сравнительно небольшое количество теоретических алгоритмов.
Алгоритм RLE
В основу алгоритмов RLE (от англ. слов Run Length Encoding –кодирование путём учёта повторений) положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора.
Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байтов) образуется следующий вектор:
| Значение | Коэффициент повтора |
При записи в строку он имеет вид:
0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов)
В данном примере коэффициент сжатия равен 8/10=0,8=80%
Понять идею этого метода упаковки позволяет следующий анекдот. Один полководец решил написать достаточно объёмные мемуары. Составленные воспоминания звучали примерно так: ”Утром я вскочил на своего коня и помчался в штаб армии. Подковы коня издавали звук “Цок-цок- цок- цок- цок- цок- цок…”. Через двое суток я соскочил с коня и вошёл в штаб.”. Для увеличения объёма литературного произведения словосочетание “цок” было написано на двухстах страницах. Очевидно, что информативность произведения не изменилась бы, если вместо 200 страниц перечисления цокающих звуков было бы указано: ”Затем следует 64000”раз звуки “цок-цок” “.
Программные реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но в среднем обеспечивают недостаточное сжатие. Наилучшими объектами для данного алгоритма являются графические файлы, в которых большие одноцветные участки изображения кодируются длинными последовательностями одинаковых байтов. Этот метод может давать заметный выигрыш на некоторых типах файлов баз данных, имеющих таблицы с фиксированной длиной полей. Для текстовых данных методы RLE, как правило, неэффективны.
Алгоритм KWE
В основу алгоритмов кодирования по ключевым словам Keyword Encoding положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Примером лексической единицы может служить слово (последовательность символов, ограниченная справа и слева пробелами или символами конца абзаца). Результат кодирования сводится в таблицу, которая прикладывается к результирующему коду и представляет собой словарь. Обычно для англоязычных текстов принято использовать двухбайтную кодировку символов. Обращающиеся при этом пары байтов называют токенами.
Эффективность данного метода существенно зависит от длины документа, поскольку из-за необходимости прикладывать к архиву словарь длина кратких документов не только не уменьшается, но даже возрастает.
Данный алгоритм наиболее эффективен для англоязычных текстовых документов и файлов баз данных. Для русскоязычных документов, отличающихся увеличенной длиной слов и большим количеством приставок, суффиксов и окончаний, не всегда удается ограничиться двухбайтными токенами, и эффективность метода значительно снижается.
Алгоритм Хафмана
В основе этого алгоритма лежит кодирование не байтами, а битовыми группами.
· Перед началом кодирования производится частотный анализ кода документа и выявляется частота повторения каждого из встречающихся символов.
· Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность).
· Образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.
В связи с тем, что к каждому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хафмана мало эффективен. Практика также показывает, что его эффективность зависит от заданной предельной длины кода (размера словаря). В среднем наиболее эффективными являются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит).
Синтетические алгоритмы
Рассмотренные выше алгоритмы в «чистом виде» на практике не применяются из-за того, что эффективность каждого из них сильно зависит от начальных условий. В связи с этим, современные средства архивации данных используют наиболее сложные алгоритмы, основанные на комбинации нескольких теоретических методов. Общим принципом в работе таких синтетических алгоритмов является предварительный просмотр и анализ исходных данных для индивидуальной настройки на особенности обрабатываемого материала.
2. Число 11110 перевести в другие системы счисления.
| 11110=11011112 | |||||||||||||
11110=1578
11110=6F16
3. Выполнить действия:
101011102+111100012
+11110001
1010112-100012=
10001 прямой код числа
01110 обратный код числа
+ 1
01111 дополнительный код
+ 101111
1010112-100012=110102
