МР_к_ЛПЗ_по_ОП.01_09.02.02. Методические указания по проведению лабораторно практических занятий по оп. 01. Основы теории информации для специальности 09. 02. 02 Компьютерные сети
 Скачать 1.36 Mb.
|
|
Тема: Практическое применение различных алгоритмов сжатия Цель: Целью лабораторной работы является получение навыков работы с архиваторами RAR, ARJ и ZIP, и ознакомление с основными алгоритмами сжатия информации. Время выполнения: 2 часа Оборудование: ПК. Программное обеспечение: операционная система, программы архиваторы: RAR, ARJ и ZIP Теоретические основы При эксплуатации персональных компьютеров по самым различным причинам возможны порча или потеря информации на магнитных дисках. Это может произойти из - за физической порчи магнитного диска, неправильной корректировки или случайного уничтожения файлов, разрушения информации компьютерным вирусом и т.д . Для того чтобы уменьшить потери в таких ситуациях, следует иметь архивные копии используемых файлов и систематически обновлять копии изменяемых файлов. Для хранения архивов данных можно использовать внешние запоминающие устройства большой емкости , которые дают возможность легко скопировать жесткий диск (например, магнитооптика, стримеры, " Арвид " и др.) Однако при этом резервные копии занимают столько же места, сколькозанимают исходные файлы , и для копирования нужных файлов может потребоваться много дискет. Более удобно для создания архивных копий использовать специально разработанные программы архивации файлов, которые сжимают информацию . При архивировании степень сжатия файлов сильно зависит от их формата. Некоторые форматы данных ( графические, PageMaker и др.) имеютупакованные разновидности, при этом сжатие производится создающей исходный файл программой, однако лучшие архиваторы способны поджать и их. Совсем другая картина наблюдается при архивации текстовых файлов. Текстовые файлы обычно сжимаются на 50-70%, а программы на 20-30%. Принцип работы архиваторов основан на поиске в файле " избыточной" информации и последующем ее кодировании с целью получения минимального объема. Самым известным методом архивации файлов является сжатие последовательностей одинаковых символов. Например, внутри вашего файла находятся последовательности байтов , которые часто повторяются. Вместо того чтобы хранить каждый байт , фиксируется количество повторяющихся символов и их позиция. Для наглядности приведем следующий пример: Упаковываемый файл занимает 15 байт и состоит из следующей последовательности символов: BBBBBLLLLLAAAAA В шестнадцатиричной системе : 42 42 42 42 42 4 С 4 С 4 С 4 С 4 С 41 41 41 41 41 Архиватор может представить этот файл в следующем шестнадцатиричном виде : 01 05 42 06 05 4 С OA 05 41 Эти последовательности можно интерпретировать следующим образом: с первой позиции 5 раз повторяется знак В, с шестой позиции 5 раз повторяется знак L и с позиции 11 5 раз повторяется знак А. Согласитесь, очень простая демонстрация алгоритма архивации .Очевидно, что для хранения файла в его последней форме требуется лишь 9 байт - меньше на 6 байт . Описанный метод является простым и очень эффективным способом сжатия файлов. Однако он не обеспечивает большой экономии объема, если обрабатываемый текст содержит небольшое количество последовательностей повторяющихся символов. Существуют два основных способа проведения сжатия: • статистический • словарный. Лучшие статистические методы применяют арифметическое кодирование, лучшие словарные - метод Зива -Лемпела . В статистическом сжатии каждому символу присваивается код , основанный на вероятности его появления в тексте . Высоко вероятные символы получают короткие коды, и наоборот . Такой способ сжатия называют оптимальным префиксным кодом . Для его построения используют алгоритмы Хаффмана или Шеннона- Фано. Например, анализируя любой английский текст, можно установить , что буква Е встречается гораздо чаще, чем Z, а Х и Q относятся к наименее встречающимся . Таким образом, используя специальную таблицу соответствия, можнозакодировать каждую букву Е меньшим числом бит, используя более длинный код для более редких букв , тогда как в обычных кодировках любому символу соответствует битовая последовательность фиксированной длины ( как правило, кратной байту). В словарном методе группы последовательных символов или " фраз " заменяются кодом. Замененная фраза может быть найдена в некотором " словаре". Популярные архиваторы ARJ, RAR работают на основе алгоритма Лемпела - Зива . Сущность алгоритмов Зива и Лемпела состоит в том , что фразы заменяются указателем на то место, где они в тексте уже ранее появлялись . Это семейство алгоритмов обозначается как LZ- сжатие . Такой метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, т.к. они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Декодирование сжатого текста осуществляется напрямую - происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа декодировщика . Одной из форм такого указателя является пара (m,l), которая заменяет фразу из l символов, начинающуюся со смещения m во входном потоке. Например, указатель (7,2) адресует 7-ой и 8-ой символы исходной строки . Используя это обозначение, строка " abbaabbbabab" будет закодирована как " abba(1,3)(3,2)(8,3) ". Заметим , что несмотря на рекурсию в последнем указателе, производимое кодирование не будет двусмысленным . Распространено не верное представление, что за понятием LZ- метода стоит единственный алгоритм . Из- за большого числа вариантов этого метода лучшее описание можно осуществить только через его растущую семью , где каждый член отражает свое решение разработчика . Эти версии отличаются друг от друга в двух главных факторах : есть ли предел обратного хода указателя, и на какие подстроки из этого множества он может ссылаться. Продвижение указателя в ранее просмотренную часть текста может быть неограниченным ( расширяющееся окно) или ограничено окном постоянного размера из N предшествующих символов, где N обычно составляет несколько тысяч. Выбранные подстроки также могут быть неограниченным или ограниченным множеством фраз, выбранных согласно некоторому замыслу . Каждая комбинация этих условий является компромиссом между скоростью выполнения, объемом требуемой ОП и качеством сжатия. Расширяющееся окно предлагает лучшее сжатие за счет организации доступа к большему количеству подстрок . Но по мере роста окна , кодировщик может замедлить свою работу из - за возрастания времени поиска соответствующих подстрок, а сжатие может ухудшиться из - за увеличения размеров указателей. Если памяти для окна будет не хватать, произойдет сброс процесса, что также ухудшит сжатие до поры нового увеличения окна . Окно постоянного размера лишено этих проблем , но содержит меньше подстрок, доступных указателю. Ограничение множества доступных подстрок размерами фиксированного окна уменьшает размер указателей и убыстряет кодирование. К основным функциям архиваторов относятся : • архивация указанных файлов или всего текущего каталога ; • извлечение отдельных или всех файлов из архива ; • просмотр содержимого архивного файла; • проверка целостности архивов; • восстановление поврежденных архивов; • ведение многотомных архивов; • вывод файлов из архива на экран или на печать ; • парольная защита архива . Архиватор ARJ не имеет графического интерфейса , и вся работа с ним осуществляется с командной строки . Формат команд имеет следующий вид : arj<команда > [- <спецификация 1>[ - <спецификация 2>]…] < имя архива> [< имя файла >…] Подробную информацию о списке команд архиватора можно получить, набрав в командной строке: arj /? Рассмотрим наиболее популярные команды архиватора: Для архивации файлов: arj a < имя архива><имя файла 1>< имя файла 2> Для извлечения файлов из архива: arj e < имя архива><имя файла 1>< имя файла 2> Для просмотра содержимого архивного файла: arj l < имя архива> Для проверки целостности архива: arj t < имя архива> Для восстановления испорченного архива :arj -jr< имя архива> Для создания многотомного архива: arj a –v< размер тома><имя архива> <имя файла 1>< имя файла 2> Для вывода файла из архива на экран: arj p < имя архива><имя файла > Для создания архива с паролем: arj a –g< пароль><имя архива><имя файла > или arj a –g? < имя архива><имя файла > в последнем случае пароль будет запрошен отдельной строкой. Для создания самораспаковывающихся архивов: arj a -je<имя архива><имя файла 1>< имя файла 2> Архиватор RAR имеет версии , как для Dos, Win 3.XX так и для Windows 95/98. Последние версии WinRar имеют графический интерфейс и работа с ними очень проста и понятна. Данный архиватор позволяет создавать как архивы *.rar так и архивы *.zip К достоинствам данного архиватора можно отнести: • графический интерфейс; • высокую степень сжатия, даже мультимедийных файлов; • возможность оценить размер архива, не производя архивирование. • большую вероятность восстановления поврежденных архивов. Практическое задание 1.Найдите на компьютере не менее 5-ти текстовых файлов ( расширение .txt) 2.Произведите их сжатие архиватором RAR в обычный и SFX- архив. 3.Зафиксируйте размер файла до сжатия и после него. 4.Вычислите коэффициент сжатия ( отношение размера исходного файла к размеру сжатого файла) 5.Повторите пункты 1-4 для графических файлов ( расширение .bmp) 6.Повторите пункты 1-4 для графических файлов ( расширение .jpg) 7.Повторите пункты 1-4 для звуковых файлов ( расширение .wav) 8.Сведите полученные результаты в таблицу. Сделайте выводы о том, какие файлы сжимаются лучше. 9.Напишите отчет о проделанной работе. Содержание отчета Отчет должен содержать следующие разделы: Ответы на контрольные вопросы. Результаты сжатия файлов в виде таблицы. Выводы о проделанной работе. Контрольные вопросы 1. Зачем нужно архивировать информацию ? 2. На чем основана работа архиваторов. По какому принципу они сжимают информацию. 3. Каковы функции архиваторов. 4. Чем отличаются SFX – архивы. Лабораторная работа №6 Тема: Сравнение и анализ архиваторов Цель: формирование практических навыков и умений архивирования и сжатия файлов. Время выполнения: 2 часа Оборудование: ПК. Программное обеспечение: операционная система, программы архиваторы. Теоретические основы Характерной особенностью большинства типов данных, с которыми традиционно работают пользователи, является определенная избыточность. Степень избыточности зависит от типа данных. При обработке информации избыточность также играет важную роль. Так, например, при преобразовании или селекции информации избыточность используют для повышения ее качества (репрезентативности, актуальности, адекватности и т.п.). Однако, когда речь заходит не об обработке, а о хранении готовых документов или их передаче, то избыточность можно уменьшить, что дает эффект сжатия данных. Если методы сжатия информации применяют к готовым документам, то нередко термин сжатие данных подменяют термином архивация данных, а программные средства, выполняющие эти операции, называют архиваторами. Степень сжатия файлов характеризуется коэффициентом Кс,определяемым как отношение объема сжатого файла Vcк объему исходного файла v, выраженное в процентах: Кo=(VcV*100). Степень сжатия зависит от используемой программы, метода сжатия и типа исходного файла. Наиболее хорошо сжимаются файлы графических образов, текстовые файлы и файлы данных, для которых степень сжатия может достигать 5-40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей –60-90%. Почти не сжимаются архивные файлы. Объекты сжатия В зависимости от того, в каком объекте размещены данные, подвергаемые сжатию, различают: уплотнение (архивацию) файлов; уплотнение (архивацию) папок; уплотнение дисков. Уплотнение файлов применяют для уменьшения их размеров при подготовке к передаче по каналам электронных сетей или к транспортировке на внешнем носителе малой емкости, например на гибком диске. Уплотнение папок используют как средство архивации данных перед длительным хранением, в частности, при резервном копировании. Уплотнение дисков служит целям повышения эффективности использования их рабочего пространства и, как правило, применяется к дискам, имеющим недостаточную емкость. Несмотря на изобилие алгоритмов сжатия данных, теоретически есть только три способа уменьшения их избыточности. Это либо изменение содержания данных, либо изменение их структуры, либо и то и другое вместе. Если при сжатии данных происходит изменение их содержания, метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления исходной последовательности. Такие методы называют также методами сжатия с регулируемой потерей информации. Они применимы только для тех типов данных, для которых формальная утрата части содержания не приводит к значительному снижению потребительских свойств. В первую очередь, это относится к мультимедийным данным: видеорядам, музыкальным записям, звукозаписям и рисункам. Методы сжатия с потерей информации обычно обеспечивают гораздо более высокую степень сжатия, чем обратимые методы, но их нельзя применять к текстовым документам, базам данных и, тем более, к программному коду. Характерными форматами сжатия с потерей информации являются: JPG для графических данных; .MPG для видеоданных; .МРЗ для звуковых данных. Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим. Из результирующего кода можно восстановить исходный массив путем применения обратного метода. Обратимые методы применяют для сжатия любых типов данных. Характерными форматами сжатия без потери информации являются: .GIF, .TIP, .PCX и многие другие для графических данных; .AVI для видеоданных; .ZIP, .ARJ, .RAR, .LZH, .LH, .CAB и многие другие для любых типов данных. Архиваторы Современные программные средства для создания и обслуживания архивов отличаются большим объемом функциональных возможностей, многие из которых выходят за рамки простого сжатия данных и эффективно дополняют стандартные средства операционной системы. В этом смысле современные средства архивации данных называют диспетчерами архивов. К базовым функциям, которые выполняют современные диспетчеры архивов, относятся: извлечение файлов из архивов, создание новых архивов, добавление файлов в имеющийся архив, создание самораспаковывающихся архивов, создание распределенных архивов на носителях малой емкости, тестирование целостности структуры архивов, полное или частичное восстановление поврежденных архивов, защита архивов от просмотра и несанкционированной модификации. К дополнительным функциям диспетчеров архивов относятся сервисные функции, делающие работу более удобной. Они часто реализуются внешним подключением дополнительных служебных программ и обеспечивают: просмотр файлов различных форматов без извлечения их из архива; поиск файлов и данных внутри архивов; установку программ из архивов без предварительной распаковки; проверку отсутствия компьютерных вирусов в архиве до его распаковки; криптографическую защиту архивной информации; декодирование сообщений электронной почты; «прозрачное» уплотнение исполнимых файлов .ЕХЕ и .DLL; создание самораспаковывающихся многотомных архивов; выбор или настройку коэффициента сжатия информации. Структура окон WinRAR и WinZip типична для приложений Windows. Вид панели инструментов WinRAR приведен на рис. 1.  Рис. 1. Панель инструментов WinRAR Самораспаковывающиеся архивыВ тех случаях, когда архивация производится для передачи документа потребителю, следует предусмотреть наличие у него программного средства, необходимого для извлечения исходных данных из уплотненного архива. Если таких средств у потребителя нет –создают самораспаковывающиеся архивы. Самораспаковывающийся архив готовится на базе обычного архива путем присоединения к нему небольшого программного модуля. Сам архив получает расширение .ЕХЕ, характерное для исполняемых файлов (рис. 2). Потребитель сможет выполнить его запуск как программы, после чего распаковка архива произойдет на его компьютере автоматически. Распределенные архивы В тех случаях, когда предполагается передача большого архива на носителях малой емкости, например на гибких дисках, возможно распределение одного архива в виде малых фрагментов на нескольких носителях. Некоторые диспетчеры (например, WinZip) выполняют разбиение сразу на гибкие диски, а некоторые (например, WinRAR) позволяют выполнить предварительное разбиение архива на фрагменты заданного размера на жестком диске. Впоследствии их можно перенести на внешние носители путем копирования.  Рис. 2. Определение параметров архива При создании распределенных архивов диспетчер WinZip обладает особенностью: каждый том несет файлы с одинаковыми именами. В результате этого нет возможности установить номера томов, хранящихся на каждом из гибких дисков, по названию файла. Поэтому каждый диск следует маркировать пометками на наклейке, а при создании распределенного архива следует быть внимательнее, чтобы не перепутать последовательность немаркированных томов. В случае необходимости узнать номер тома можно не по названию файла, а по метке на диске, хотя эта операция не слишком удобна. Для этого следует открыть окно «Мой компьютер», выбрать значок дисковода, щелкнуть на нем правой кнопкой мыши и выбрать в контекстном меню пункт «Свойства». В диалоговом окне «Свойства: Диск …» на вкладке «Общие» можно узнать номер тома распределенного архива в поле «Метка тома». Консольная версия WinRAR Консольная версия WinRAR поддерживает архивы только в формате RAR, у которых обычно расширение ".rar". ZIP и прочие форматы не поддерживаются. Пользователи Windows могут установить GUI-версию RAR – WinRAR, которая обрабатывает и архивы других типов. Некоторые отличительные особенности RAR: оригинальный высокоэффективный алгоритм сжатия данных; специальные алгоритмы сжатия, оптимизированные для текстовых, аудио- и графических данных, а также для 32- и 64-битовых исполняемых файлов архитектуры Intel; лучшая, чем у аналогичных продуктов, степень сжатия при использовании режима "непрерывного" (solid) архивирования; электронная подпись (только в зарегистрированной версии); самораспаковывающиеся (SFX) архивы и тома; восстановление физически поврежденных архивов; блокировка, шифрование, задание порядка архивирования файлов; сохранение прав доступа к файлам, меток тома и др. Следует отметить, что при создании томов RAR в FAT или FAT32 WinRAR автоматически ограничивает максимальный объем тома до 4 ГБ минус 1 байт, так как эти файловые системы не поддерживают файлы объемом больше 4 ГБ. Работа с WinRAR из консоли |