Методы и приемы работы со сжатыми файлами Шарипов И.К., 2011г.

2 План лекции Теоретические основы сжатия данных Объекты сжатия Обратимость сжатия Алгоритмы Программные средства сжатия данных Программные средства уплотнения носителей

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

4 Теоретические основы сжатия данных Характерной особенностью большинства типов данных, с которыми традиционно работают люди, является определенная избыточность. Степень избыточности зависит от типа данных. Степень избыточности данных зависит от принятой системы кодирования. Например, можно сказать, что кодирование текстовой информации средствами русского языка (с использованием русской азбуки) дает в среднем избыточность на 20-30% больше, чем кодирование адекватной информации средствами английского языка.

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

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

7 Обратимость сжатия Несмотря на изобилие алгоритмов сжатия данных, теоретически есть только три способа уменьшения их избыточности. Это либо изменение содержания данных, либо изменение их структуры, либо и то и другое вместе.

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

9 Методы сжатия с потерей информации обычно обеспечивают гораздо более высокую степень сжатия, чем обратимые методы, но их нельзя применять к текстовым документам, базам данных и, тем более, к программному коду..JPG для графических данных;.MPG для видеоданных;.МРЗ для звуковых данных.

10 Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим.GIF,.TIF,.PCX и многие другие для графических данных;.AVI для видеоданных;.ZIP,.ARJ,.RAR,.LZH,.LH,.CAB и многие другие для любых типов данных.

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

12 Свойства алгоритмов сжатия

13 Алгоритм RLE В основу алгоритмов RLE положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора. Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (10 байтов) образуется следующий вектор: При записи в строку он имеет вид: 0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов).

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

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

16 Пример реализации Алгоритма Хаффмана

17 Программные средства сжатия данных

18.ZIP Наиболее распространен формат.ZIP, который является стандартом де-факто для архивов, распространяемых через Интернет. Этот формат является полностью открытым – его использование не требует никаких лицензионных отчислений. Операционная система Windows ХР позволяет рассматривать ZIP-архивы как сжатые папки. Все файловые операции можно выполнять в сжатой папке так же, как в обычной. Однако специализированные средства работы с архивами обеспечивают более широкий набор функций.

19 Базовые требования к диспетчерам архивов извлечение файлов из архивов; создание новых архивов; добавление файлов в имеющийся архив; создание самораспаковывающихся архивов; создание распределенных архивов на носителях малой емкости; тестирование целостности структуры архивов; полное или частичное восстановление поврежденных архивов; защита архивов от просмотра и несанкционированной модификации.

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

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

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

23 Дополнительные требования к диспетчерам архивов просмотр файлов различных форматов без извлечения их из архива; поиск файлов и данных внутри архивов; установку программ из архивов без предварительной распаковки; проверку отсутствия компьютерных вирусов в архиве до его распаковки;

24 Дополнительные требования к диспетчерам архивов криптографическую защиту архивной информации; декодирование сообщений электронной почты; «прозрачное» уплотнение исполнимых файлов.ЕХЕ и.DLL; создание самораспаковывающихся многотомных архивов; выбор или настройку коэффициента сжатия информации.

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

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

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

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

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

30 «Присоединение» уплотненного диска Термин присоединение диска (mounting – монтаж) возник еще в те годы, когда прикладные программисты работали за терминалами больших ЭВМ и были полностью оторваны от аппаратных средств компьютера.