Учебник Информатика. Базовый курс. Симонович С.В.. С. В. Симоновичаинформатикабазовый курс2е издание
 Скачать 17.96 Mb.
|
|
Алгоритм Хаффмана В основе этого алгоритма лежит кодирование не байтами, а битовыми группами. • Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов. • Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность). • Образующаяся в результате кодирования иерархическая структура приклады- вается к сжатому документу в качестве таблицы соответствия. Пример кодирования символов русского алфавита представлен на рис. 14.1. Как видно из схемы, представленной на рис. используя 16 бит, можно закоди- ровать до 256 различных символов. Однако ничто не мешает использовать и после- Программные средства сжатия данных 379 Рис. Пример кодирования русского алфавита по алгоритму Хафмана довательности длиной до 20 бит — тогда можно закодировать до лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова). В связи тем, что к сжатому архиву необходимо прикладывать таблицу соответ- ствия, на файлах малых размеров алгоритм Хаффмана малоэффективен. Практика также показывает, что его эффективность и от заданной предельной длины кода (размера словаря). В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 доЮ24 единиц (длина кода до 18-20 бит). Синтетические алгоритмы Рассмотренные выше алгоритмы в «чистом виде» на практике не применяют из-за того, что эффективность каждого из них сильно зависит от начальных условий. В связи с этим современные средства архивации данных используют более слож- ные алгоритмы, основанные на комбинации нескольких теоретических методов. Общим принципом в работе таких «синтетических» алгоритмов является предва- рительный просмотр и анализ исходных данных для индивидуальной настройки алгоритма на особенности обрабатываемого материала. Программные средства сжатия данных «Классическими» форматами сжатия данных, широко используемыми в повседнев- ной работе с компьютером, являются форматы и .ARJ. Программные сред- ства, предназначенные для создания и обслуживания архивов, выполненных в данных форматах, приведены в табл. 14.2. Несмотря на то что средства архивации, предназначенные для операционной системы MS-DOS, вполне могут работать под управлением Windows, пользоваться ими не реко- мендуется. В первую очередь это связано с тем, что при обработке файлов происходит утрата «длинных имен» файлов и подмена их именами MS-DOS по спецификации 8.3. Это может создать потребителю документа определенные неудобства, а в случаях, когда архивация производится с целью резервного копирования, утрата «длинных имен» вообще недопустима. 380 Глава Приемы и методы работы со сжатыми данными Таблица 14.2. Средства архивации файлов Операционная система MS-DOS Windows Формат сжатия .ARJ Средство архивации EXE Средство разархивирования PKUNZIP.EXE UNRAR.EXE EXE WinZip, сжатые WinRAR WinRAR WinArj WinArj, WinRAR Стоит отметить, что в связи с широким распространением нескольких сжатия многие программные средства для сжатия данных начинают приобретать универсальный характер, позволяя упаковывать и распаковывать сжатые архивы разных типов. Программные средства для Windows обычно имеют один «предпоч- тительный» тип архива, но также справляются с распаковкой данных при работе с архивами других типов. Наиболее распространен формат который является стандартом де-факто для архивов, распространяемых через Интернет. Немаловажную роль в этом играет открытость этого формата. Этот формат является полностью открытым — его использование не требует никаких лицензионных отчислений. Операционная система Windows позволяет рассматривать как сжа- тые папки. Это предполагает полностью «прозрачную» работу с такими архивами — все файловые операции можно выполнять в сжатой папке так же, как в обычной. Однако специализированные средства работы с архивами обеспечивают более широкий набор функций. При использовании файловой системы NTFS возможно внутреннее сжатие при записи на диск для экономии пространства. С точки зрения всех файловых операций такие файлы не рассматриваются как упакованные. При их копировании на носитель с дру- гой файловой системой они автоматически распаковываются. Базовые требования к диспетчерам архивов Современные программные средства для создания и обслуживания архивов отли- чаются большим объемом функциональных возможностей, многие из которых выходят далеко за рамки простого сжатия данных и эффективно дополняют стан- дартные средства операционной системы. В этом смысле современные средства архивации данных называют диспетчерами архивов. К базовым функциям, которые выполняют большинство современных диспетче- ров архивов, относятся: • извлечение файлов из архивов; • создание новых архивов; • добавление файлов в имеющийся архив; • создание самораспаковывающихся архивов; Программные средства сжатия данных • создание распределенных архивов на носителях малой емкости; • тестирование целостности структуры архивов; • полное или частичное восстановление поврежденных архивов; • защита архивов от просмотра и несанкционированной модификации. Самораспаковывающиеся архивы. В тех случаях, когда архивация производится для передачи документа потребителю, следует предусмотреть наличие у него программ- ного средства, необходимого для извлечения исходных данных из уплотненного архива. Если таких средств у потребителя нет или нет оснований предполагать их наличие, создают самораспаковывающиеся архивы. Самораспаковывающийся архив готовится на базе обычного архива путем присоединения к нему небольшого программного модуля. Сам архив получает расширение имени характерное для исполнимых файлов. Потребитель сможет выполнить его запуск как программы, после чего распаковка архива произойдет на его компьютере автоматически. Распределенные архивы. В тех случаях, когда предполагается передача большого архива на носителях малой емкости, например на гибких дисках, возможно рас- пределение одного архива в виде малых фрагментов на нескольких носителях. Современные диспетчеры архивов способны выполнить предварительное разбиение архива на фрагменты заданного размера на жестком диске. Впоследствии их можно перенести на внешние носители путем копирования. Все файлы распределенного архива получают разные имена, и поэтому их последующее упорядочение не вызы- вает проблем. Оптимальный режим работы с распределенными архивами следующий: • создание набора файлов распределенного архива в папке на жестком диске; • копирование файлов распределенного архива на отдельные сменные носители (обычно гибкие диски); • перенос (перевозка) сменных носителей в место назначения; • копирование файлов распределенного архива со сменных носителей в одну папку на конечном жестком диске; • распаковка распределенного архива. Гибкие диски являются крайне ненадежными носителями, поэтому архивы, сфор- мированные на жестком диске, должны храниться до получения подтверждения от потребителя о том, что распределенный архив поступил к нему в неповрежден- ном виде и прошел распаковку. Правилом «хорошего тона» считается создание двух копий при передаче материалов на гибких дисках. Защита архивов. В большинстве случаев защиту архивов выполняют с помощью пароля, который запрашивается при попытке просмотреть, распаковать или изме- нить архив. Теоретически, защита с помощью пароля считается неудовлетвори- тельной и не рекомендуется для особо важной информации. В то же время необходимо отметить, что основные программные средства, используемые для вос- становления утраченного пароля (или взлома закрытой информации, что, по сути, 3 8 2 Глава Приемы и методы работы со сжатыми данными то же самое), используют методы прямого перебора. Работу этих средств можно существенно затруднить и замедлить, если расширить область перебора. Пароли на базе только букв английского алфавита и цифр действительно снимаются очень быстро. Однако даже незначительное увеличение числа используемых символов за счет знаков препинания многократно увеличивает криптостойкость защиты, а использование также и символов русского алфавита может полностью опроверг- нуть попытки снять пароль путем перебора, сделав сроки работы неприемлемыми. Дополнительные требования к диспетчерам архивов К дополнительным функциям диспетчеров архивов относятся сервисные функ- ции, делающие работу более удобной. Они часто реализуются внешним подклю- чением дополнительных служебных программ и обеспечивают: • просмотр файлов различных форматов без извлечения их из архива; • поиск файлов и данных внутри архивов; • установку программ из архивов без предварительной распаковки; • проверку отсутствия компьютерных вирусов в архиве до его распаковки; • криптографическую защиту архивной информации; • декодирование сообщений электронной почты; • «прозрачное» уплотнение исполнимых файлов и • создание самораспаковывающихся многотомных архивов; • выбор или настройку коэффициента сжатия информации. Программные средства уплотнения носителей Теоретические основы В основе уплотнения носителей (например, дисков) также лежит принцип сжатия данных за счет уменьшения избыточности путем изменения структуры, но при этом надо иметь в виду ряд особенностей: • процесс уплотнения носителей является относительным, то есть никакого физического увеличения емкости носителя не происходит, а вместо этого про- исходит сжатие записываемых данных, что вызывает эффект кажущегося уве- личения емкости носителя; • процесс сжатия данных происходит под управлением программ, работающих автоматически в фоновом режиме, и, тем самым, он «прозрачен» для пользова- теля, который никак не ощущает разницы в работе с обычным и уплотненным носителем, но может констатировать факт размещения на диске большего объе- ма данных, чем физическая емкость диска; • степень сжатия данных зависит, как мы знаем, от типа данных, поэтому наблю- даемое приращение емкости носителя не является величиной постоянной и непрерывно меняется в зависимости от того, какой тип данных добавляется на носитель; Программные средства уплотнения носителей 3 8 3 • размер свободного пространства на сжатом томе определяется как произведе- ние реального свободного пространства и предполагаемого (или среднего) ко- эффициента сжатия и поэтому является приближенной величиной, причем часто такое приближение оказывается очень грубым. Из вышесказанного вытекает, в частности, что в основе алгоритмов сжатия дан- ных, используемых для уплотнения носителей, не могут лежать необратимые методы. Это ясно уже потому, что заранее неизвестен тип данных, который будет записан, а некоторые типы данных (например, код) не допускают потери данных ни в малейшей степени. Практическая реализация концепции уплотнения дисков 1. На физическом диске создается скрытый файл, предназначенный для записи сжатых данных. Данный файл называют файлом сжатого а физический диск, на котором он размещен, называют несущим диском. 2. На уровне операционной системы происходит объявление файла сжатого тома в качестве нового уплотненного диска. которые записываются на уплот- ненный диск, на самом деле заносятся в файл сжатого тома, расположенный на несущем диске. 3. Если файл сжатого тома занимает весь несущий диск, то несущий диск делается скрытым и его место в операционной системе занимает уплотненный диск. 4. Весь обмен информацией с уплотненным диском происходит не под управлением стандартных средств операционной системы, а под управлением специальной программы — драйвера сжатого тома, которая интегрируется в операционную систему и организует ее взаимодействие с нестандартной файловой системой, созданной внутри файла сжатого тома. «Присоединение» уплотненного диска Термин присоединение диска {mounting — монтаж) возник еще в те годы, когда прикладные программисты работали за терминалами больших ЭВМ и были полно- стью оторваны от аппаратных средств компьютера. Если им требовалось программ- ное обеспечение, расположенное на известном им магнитном диске (магнитном барабане, магнитной ленте), то приходилось лично или по телефону обращаться в группу технического обеспечения с просьбой установить носитель на нужное уст- ройство чтения. Поскольку машинное время пользователям в те годы выделялось малыми порциями по утвержденному расписанию, иногда приходилось даже пода- вать предварительную заявку на установку носителей в определенные часы. С персональной вычислительной техникой так не работают, но термин остался, хотя стал виртуальным. При присоединении уплотненного диска, конечно же, не происходит никаких монтажных работ, однако если в компьютерной системе име- ется уплотненный диск, то со стороны операционной системы возможен двойной взгляд на его структуру. Во-первых, операционная система может рассматривать его как обычный несущий диск, на котором расположен файл сжатого тома (самый обычный файл, только 3 8 4 Глава Приемы и методы работы со сжатыми данными очень большой). С другой стороны, операционная система может рассматривать тот же диск через посредство драйвера сжатого тома, и тогда она «не видит» файла сжатого тома на несущем диске, но наблюдает как бы дополнительный диск, име- ющийся в компьютерной системе. Оба подхода имеют равные права на существование, переход от первого пред- ставления ко второму и называется присоединением уплотненного диска. Обрат- ная операция, соответственно, называется отсоединением. Целесообразность уплотнения носителей Идея уплотнения носителей возникла тогда, когда жесткий диск был ценным доро- гостоящим агрегатом, несмотря на то что его емкость оставалась не столь уж боль- шой. В 80-е годы и в начале 90-х годов количество компьютерных систем, имеющих недостаточную емкость жестких дисков, но нуждающихся в хранении (хотя бы и временном) больших объемов данных, было весьма велико. Однако в последние годы удельная стоимость хранения единицы данных падает столь стремительно, что актуальность уплотнения жестких дисков значительно снизилась. Оценивая возможность уплотнения носителей, следует иметь в виду, что наличие такого носителя в компьютерной системе затрудняет ее обслуживание и заметно снижает надежность, в первую очередь в связи с особой сложностью восстановле- ния информации в случае неожиданных повреждений аппаратного или программ- ного обеспечения. По этим причинам необходимость использования сжатых дисков возникает все реже и реже, и в последних версиях операционных систем средства работы со сжа- тыми носителями постепенно исчезают. Например, в ранних версиях Windows име- лась полная поддержка работы со сжатыми дисками, затем осталась поддержка на уровне совместимости (возможность использования существующих сжатых томов, но не создание новых). В Windows поддержка сжатых томов уже вообще отсут- ствует — вместо этого предполагается использование «прозрачного» сжатия фай- лов, обеспечиваемого файловой системой NTFS. Практическое занятие Упражнение Просмотр архивного файла в формате мин 1. Запустите диспетчер архивов WinZip 8.1 командой Пуск • Программы • WinZip • 2. Вставьте гибкий диск, содержащий архивный файл в формате ZIP, дисковод А:. 3. Дайте команду File • Open Archive (Файл • Открыть архив). 4. В диалоговом окне Open Archive (Открытие архива) воспользуйтесь раскрываю- щей кнопкой в списке Папка, разыщите и откройте Диск 3,5 (А:), выделите зна- чок файла в формате и щелкните на командной кнопке Открыть. В окне программы WinZip откроется список файлов, входящих в архив (рис. 14.2). Практическое занятие 385 Панель инструментов Имена файлов, в архив Размер файла в архиве Процент экономии Исходный размер файла Рис. 14.2, Просмотр содержимого архива с помощью программы WinZip 5. Выделите значок файла, который желаете просмотреть, например readme.txt. Дважды щелкните на этом значке, и файл откроется в окне ассоциированной программы. По умолчанию в операционной системе Windows с файлами типа ассоциирована программа Блокнот. 6. Если нужно просмотреть файл в другой программе, выделите его значок и вос- пользуйтесь командой Actions • View (Действия • Просмотр). По этой команде откроется диалоговое окно View (Просмотр), в котором можно самостоятельно указать, какую программу следует использовать в качестве средства просмотра для файлов данного типа. 7. Выделите для просмотра файл с иным расширением имени, например Этот тип файлов не имеет ассоциированной программы просмотра. средство WinZip умолчанию использует программу Блокнот и для просмотра файлов, для которых отсутствует явное на программу просмотра. (О том, как в ХР назначить средство просмотра произвольному типу файлов, рассказано в упражнении 6.4.) научились просматривать файлы, находящиеся внутри архива, без распаковки архива и, соответственно, без извлечения файлов. Это важно, поскольку далеко не все архивы, поступающие на компьютер, особенно из Интернета, стоит распаковывать. Предварительный просмотр позволяет убедиться в том, что архив содержит действи- тельно необходимые данные, а также получить предварительную информацию о том, как лучше распорядиться его содержимым. Упражнение 14.2. Извлечение файлов мин 1. Предварительно определите папку, в которую будут помещены файлы, извле- из архива. Если никаких предпочтений нет, создайте временную папку, например папку С:\Мои 386 Глава Приемы и методы работы со сжатыми данными 2. Запустите диспетчер архивов и откройте размещенный на гибком диске А:. . 3. Выделите файлы, которые желаете извлечь. групповом выделении пользуйтесь левой кнопкой мыши совместно с клавишами CTRL и SHIFT. 4. Дайте команду Actions • Extract (Действия • Извлечь) — откроется диалоговое окно Extract (Извлечение), представленное Кнопка запуска процесса Папка для размещения извлекаемых файлов Переключатели для выбора файлов Средства настройки режима обновления Панель выбора папки для размещения извлекаемых файлов Рис. 14.3. Управление извлечением файлов из архива 5. На левой панели диалогового окна установите необходимые переключатели. 6. На правой панели откройте папку-приемник, в которую произойдет извлечение выделенных файлов. Работа на правой панели аналогична работе с Проводни- ком Windows. 7. Запустите процесс извлечения файлов щелчком на командной кнопке Extract (Извлечь). 8. По окончании процесса закройте диалоговое окно щелчком на кнопке Cancel (Отмена) или на закрывающей кнопке в правом верхнем углу окна и завершите работу с программой WinZip командой File • Exit • Выход). 9. С помощью Проводника (Пуск • Программы • Проводник) убедитесь в том, что файлы, извлеченные из архива, действительно поступили в заданную папку. 10. Удалите экспериментальную папку \Zip_Test. Мы научились извлекать файлы из архива в заданную папку. При этом у нас есть сле- дующие возможности выбора: • какие файлы извлекать, а нет; • в какую папку производить запись. |