Сжатие данных

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.

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

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

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

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

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

Объект- изучение сжатия информации на уроках информатики и ИКТ.

Предмет- технологии по овладению основными методами сжатия информации.

Цель - разработать уроки по «сжатию информации» в рамках изучения темы: текстовая информация.

Задачи:

1. Изучить особенности программ архиваторов

2. Познакомиться с методами сжатия информации

3. Разработать блок уроков по сжатию информации



ГЛАВА I.ТЕОРИТИЧЕСКОЕ ИЗУЧЕНИЕ ТЕМЫ «АРХИВАЦИЯ ДАННЫХ И СЖАТИЕ ИНФОРМАЦИИ»

1.1 Общее понятие архивации

Архиваторы- это программы для создания архивов. Архивы предназначены для хранения данных в удобном компактном виде. В качестве данных обычно выступают файлы и папки. Как правило, данные предварительно подвергаются процедуре сжатия и упаковки. Поэтому почти каждый архиватор одновременно является программой для сжатия данных. С другой стороны, любая программа для сжатия данных может рассматриваться как архиватор. От нее зависит размер создаваемых архивов. Чем меньше архив, тем меньше места требуется для его хранения. Для передачи нужна меньшая пропускная способность канала передачи или затрачивается меньшее время. Преимущества архивов очевидны, если учесть, что данные уменьшаются в размере и в 2 раза, и в 5 раз. Основным недостатком архивов является невозможность прямого доступа к данным. Их сначала необходимо извлечь из архива или распаковать. Операция распаковки, впрочем, как и упаковки, требует некоторых системных ресурсов. Это не мгновенная операция. Поэтому архивы в основном применяют со сравнительно редко используемыми данными. Необходимость в длительном хранении данных - создании архивов- со временем встает перед большинством пользователей (для профессионалов в обязательном порядке). Всякий разумный пользователь должен быть озабочен созданием резервных копий наиболее ценных для него программ и данных. Проблема архивации возникает и тогда, когда жесткий диск компьютера наполнен информацией и требуется освободить на нем место, ничего не удаляя безвозвратно. Удивительно, учитывая емкость современных жестких дисков, сколь часто это происходит. Большие по объему архивные файлы могут быть размещены на нескольких дисках (томах).

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

Так файл, созданный текстовым процессором Word и не содержащий рисунков, может быть сжат при архивации в несколько раз; степень сжатия графических файлов, как правило, существенно меньше. Под степенью сжатия понимают отношение размеров сжатого файла и исходного, выраженное в процентах. Степень сжатия зависит от используемой программы сжатия, метода сжатия и типа исходного файла. Лучше всего сжимаются графические и текстовые файлы, файлы данных, степень сжатия которых может достигать 5 -- 40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей -- 60 -- 90%. Почти не сжимаются архивные файлы[13]. Пример сжатия графической информации (рисунок 1).

Рисунок 1. Сжатие графической информации

Фото сжимаются очень не значительно, т.к. областей состоящих из точек одного цвета очень мало. Пример сжатия текстовой информации (таблица 1).

Таблица 1 Сжатие текстовой информации методом LZ

Исходный текст	Результат сжатия
Алгоритм разработан израильскими математиками Якобом Зивом и Абрахамом Лемпелем	Алгоритм раз1ботан из1ильскими мате4ика5Яко7ом3ив821х68Л10пе11

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

· сжатие некоторых файлов и целых директорий;

· создание самораспаковывающихся (SFX) архивов. То есть для распаковки архива программа-архиватор не требуется;

· изменение содержимого архива;

· шифрование содержимого архива;

· информация для восстановления архива при частичном повреждении и возможность восстановления поврежденных архивов;

· разбивка архива на несколько частей или томов;

· консольная версия программы для работы из командной строки;

· графическая (GUI) версия программы.

Рассмотрим создание SFX архивов, более подробно на примере нескольких архиваторов. Архиватор WinRAR обладает широкими возможностями для создания бесключевых SFX. С его помощью можно создать незаметный (silent) инсталлятор, который распакует содержимое SFX в заданную папку, выполнит заранее указанную команду, а по окончании установки может удалить распакованные файлы. Помимо всего WinRAR умеет добавлять элементы в меню Пуск, помещать ярлыки на Рабочий стол, а также задавать архиву иконку по вашему выбору. Мы рассмотрим только базовые возможности программы. Итак, запустив архиватор, мы переходим в папку, в которой находится административная установка Adobe. Выделяем все файлы (рисунок 2).

Рисунок 2. Папка в которой находится административная установка Adobe

И нажимаем «Добавить» (рисунок 3). Именуем архив по желанию, отмечаем создание SFX и выбираем максимальный уровень сжатия.

Рисунок 3. В этом окне отмечаем создание SFX, в нем же дается имя архива

Теперь надо сконфигурировать параметры SFX. Для этого на вкладке «Дополнительно» нажимаем «Параметры SFX». На вкладке «Общие» указываем команду для распаковки (рисунок 3).

Рисунок 3. Вкладка «Общие»

И переходим на вкладку «Режимы» (рисунок 4). Здесь мы указываем распаковку во временную папку (что повлечет за собой автоматическое удаление распакованных файлов по окончании установки), скрытый режим и перезапись всех файлов.

Перейдя на вкладку «Комментарий», мы видим все параметры, которые только что установили через графический интерфейс. Можно было сразу перейти на эту вкладку и напечатать комментарий вручную или загрузить из заранее подготовленного текстового файла.



Рисунок 4. Вкладка «Режимы»

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

Недостатки: Высокая стоимость.

Архиватор 7-Zip, с его помощью можно создавать бесключевые SFX, хотя процесс их создания несколько длиннее, чем у WinRAR.

Для начала нужно запаковать содержимое нашей папки в 7-Zip архив. Сделать это можно через 7-Zip файл-менеджер. Запустив его, мы переходим в папку, в которой находится административная установка Adobe. В эту же папку нужно положить файл StartX.exe, его назначение мы объясним ниже. Выделяем все файлы (рисунок 5).



Рисунок 5. Папка в которой находится административная установка Adobe и файл StartX.exe

И нажимаем вкладку «Добавить» (рисунок 6).

Рисунок 6. Вкладка «Добавить»



Именуем архив по желанию, выбираем формат 7-Zip, максимальный уровень сжатия и нажимаем «ОК». На выходе получаем файл, из которого нам предстоит сделать SFX.

Теперь нужно создать конфигурационный файл для SFX. Его можно сделать в Блокноте. Единственное, но обязательное условие - он должен быть в кодировке UTF-8. Первая и последние строки обозначают начало и конец конфигурационного файла. Средняя строка - команда, которая будет выполнена после распаковки архива. Утилита StartX.exe является эквивалентом консольной команды START и поддерживает такие же ключи. Ее наличие необходимо для установки MSI пакета, извлеченного из 7-Zip SFX. Сохраняем конфигурационный файл в ту же папку, куда и сохраняли файл из которого предстояло сделать SFX архив и переходим к завершающей стадии создания SFX. Из инсталляционной папки 7-Zip нужно взять SFX модуль и скопировать его к остальным файлам. Теперь, когда в одной папке собраны все три файла, нужно из командной строки выполнить следующую команду: «COPY /b 7zs.sfx + config.txt + adobe7.7z adobe7.exe».

Через мгновение в папке появится файл. Это и есть наш SFX. Его запуск инициализирует распаковку архива во временную папку, запуск команды из конфигурационного файла, и удаление распакованных файлов по окончании установки.

Модифицированный SFX модуль для 7-Zip. Оригинальный 7-Zip SFX модуль не дает возможности сделать распаковку абсолютно незаметной. В процессе распаковки пользователь видит диалоговое окно (рисунок 7).

Рисунок 7. Диалоговое окно



Пользователь даже может прервать установку нажатием на кнопку «Cancel». Этой проблемы можно избежать, воспользовавшись SFX модулем. Мы можем загрузить модифицированный модуль, где мы также найдем справку и исходный код. В справке описаны все новые функции и примеры использования. Для модифицированного модуля StartX не нужна.

Любопытно, что в данном случае 7-Zip продемонстрировал лучшее сжатие, чем WinRAR. Размер 7-Zip SFX (даже с утилитой StartX.exe) оказался 20893 КБ против 23825 КБ у WinRAR SFX. Oднако, недостатком родного SFX модуля 7-Zip является невозможность сконфигурировать бесключевую распаковку SFX в заданную папку.

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

Недостатки: нет возможности выбора иконки для архива.

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

Возможности программы SFX Creator:

· поддержка практически всех переменных системных/пользовательских директорий;

· выбор типа сжатия (LZMA - данный тип компрессии применяется в архиваторе 7-Zip), BZIP2, ZLIB;

· создание ярлыков для файлов;

· импорт REG-файлов после распаковки файлов;

· выполнение приложений до и после распаковки ваших файлов;

· выполнение операций в реестре (запись/удаление параметров, удаление разделов);

· выполнение файловых операций (копирование/удаление файлов, создание/удаление директорий);

· возможность создать программу удаления (с удобным добавлением информации в апплет "Установка и удаление программ");

· возможность установить свою иконку на SFX архив;

· возможность добавить информацию о версии файла;

· возможность выполнить собственные функции, написанные на языке NSIS перед и после распаковки файлов;

· возможность перед распаковкой ваших файлов проверить наличие установленного ПО и выполнить определённые действия, если вас не устраивает результат проверки (например если версия ПО ниже необходимой, можно прекратить установку и/или показать сообщение пользователю);

· возможность распаковать ваши файлы в каталог, который указан в каком-либо ключе реестра;

· регистрация библиотек при распаковке файлов (и возможность отменить регистрацию при удалении приложения);

· возможность при запуске/завершении показать пользователю информационное сообщение;

· вы можете создавать распаковщик (практически уже пакет инсталлятора) с графическим интерфейсом. Вам предлагается использовать 2 типа интерфейса на выбор;

· возможность показа вашего изображения перед запуском процесса распаковки файлов;

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

архивация сжатие информация



Рисунок 8. SFX Creator

В данный момент существует много архиваторов. Они имеют разную распространенность и эффективность[11]. Познакомимся с основными идеями, лежащими в основе сжатия файлов. Сама возможность архивации связана с избыточностью современных форматов записи данных по отношению к объему информации, что обеспечивает их быструю обработку соответствующими программами[14]. Существует две группы алгоритмов сжатия данных: сжатие без потерь, при котором путем обратного действия (разархивации) данные восстанавливаются полностью без каких- либо изменений, и сжатие с потерями, когда удаляется информация, не влияющая на суть данных или не воспринимаемая человеком (в основном это возможно при архивации звука и изображений). Для сжатия без потерь в основном используют два классических метода: метод Хаффмана и метод Лемпеля- Зива. Метод Хаффмана основан на том, что практически в любом тексте, составленном из стандартного 256- символьного набора, некоторые символы встречаются чаще, а некоторые реже[1]. Архивируемый текст предварительно просматривается программой- архиватором, и составляется таблица частотности использования символов (рисунок 9).

Рисунок 9. Частота употребления букв русского языка

Затем при записи самых распространенных в данном тексте символов используются максимально короткие двоичные последовательности, для менее распространенных- более длинные и т.д. К примеру, пусть в некотором тексте (на русском языке) буква «И» по использованию оказалась на первом месте, буква «А» на втором и буква «П» на третьем. Тогда можно, в процессе архивации, заменить обычный 8-ми битный код «И» на 0, буквы «А» на 1 и буквы «П» на 10- экономия очевидна и велика. К перекодированному таким образом тексту при его хранении присоединяется таблица кодировки, которая позволяет при разархивировании восстановить исходный текст. Еще проще идея алгоритма Лемпеля- Зива (называемого также алгоритмом LZ77). В потоке данных анализируются последовательности байт, и если некоторая последовательность уже встречалась, и если запись о ее длине и смещении от текущей позиции короче, чем сама эта последовательность, то в создаваемый архивный файл записывается не сама последовательность, а ссылка на нее (ссылка включает смещение и длину). Например, фраза: «Лето просто пролетает», при архивации таким образом предстанет в следующем виде: «Лето_прос(-7,2)_(-7,3)_(-15,3)а(-18,2)[10]. Более подробно остановимся на терминах которые наиболее часто используются в архивации (таблица 2 приложение1).



1.2 Архивирование и разархивирование

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

· имя файла;

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

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

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

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

Рисунок 10. Архивный файл

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

Извлечение файлов из архива. Современные программные средства для создания и обслуживания архивов отличаются большим объемом функциональных возможностей, многие из которых выходят далеко за рамки простого сжатия данных эффективно дополняют стандартные средства операционной системы (рисунок 11). В этом смысле современные средства архивации называют диспетчерами архивов. К базовым функциям, которые выполняют большинство современных диспетчеров архивов, относятся:

· извлечение файлов из архивов;

· создание новых архивов;

· добавление файлов в имеющийся архив;

· создание самораспаковывающихся архивов;

· создание распределенных архивов на носителях малой емкости;

· тестирование целостности структуры архивов[8].

Рисунок 11. Извлечение файла из архива

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

Распределенные архивы. В тех случаях, когда предполагается передача большого архива на носителях малой емкости, например на гибких дисках, возможно распределение одного архива в виде малых фрагментов на нескольких носителях. Современные диспетчеры архивов способны выполнить предварительное разбиение архива на фрагменты заданного размера на жестком диске[4]. В последствии, их можно перенести на внешние носители путем копирования. Все файлы распределенного архива получают разные имена, и поэтому их последующее упорядочение не вызывает проблем. Гибкие диски являются крайне ненадежными носителями, поэтому архивы, сформированные на жестком диске, должны хранится до получения подтверждения от потребителя о том, что распределенный архив поступил к нему в неповрежденном виде и прошел распаковку. Правилом «хорошего тона» считается создание двух копий при передаче материалов на гибких дисках. Оптимальный режим работы с распределенными архивами следующий:

· создание набора файлов распределенного архива в папке на жестком диске;

· копирование файлов распределенного архива на отдельные сменные носители (обычно гибкие диски);

· перенос (перевозка) сменных носителей в место назначения;

· копирование файлов распределенного архива со сменных носителей в одну папку на конечном жестком диске;

· распаковка распределенного архива[15].

Защита архивов. В большинстве случаев защиту архивов выполняют с помощью пароля, который запрашивается при попытке просмотреть, распаковать или изменить архив. Теоретически, защита с помощью пароля считается неудовлетворительной и не рекомендуется для особо важной информации. В то же время необходимо отметить, что основные программные средства, используемые для восстановления пароля (или взлома закрытой информации, что, по сути, тоже самое), используют методы прямого перебора. Пароли на базе не только букв английского алфавита и цифр действительно снимаются очень быстро. Однако даже незначительное увеличение числа используемых символов за счет знаком препинания многократно увеличивает криптостойкость защиты, а использование также и символов русского алфавита может полностью опровергнуть попытки снять пароль путем перебора, сделав сроки работы неприемлемыми[5]. Криптостойкость -- криптографическая стойкость (или криптостойкость) способность криптографического алгоритма противостоять возможным атакам на него. Криптографический алгоритм - алгоритм преобразования данных:

· либо являющийся полностью или частично секретным;

· либо использующий при работе набор секретных параметров.

1.3 Методы сжатия

Разработано большое количество разнообразных методов, их модификаций и подвидов для сжатия данных. Современные архиваторы, как правило, одновременно используют несколько методов сжатия[7]. Можно выделить некоторые основные.

Кодирование длин серий (RLE- сокращение от run- length encoding- кодирование длин серий). Последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений. Широко используется как дополнительный, так и промежуточный метод. Программные реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но в среднем обеспечивают недостаточное сжатие[16].

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

Словарный метод (LZ- сокращение от Lempel Ziv -имена авторов). Наиболее распространенный метод. Используется словарь, состоящий из последовательностей данных или слов. При сжатии эти слова заменяются на их коды из словаря. В наиболее распространенном варианте реализации в качестве словаря выступает сам исходный блок данных. Основным параметром словарного метода является размер словаря. Чем больше словарь, тем больше эффективность. Однако для неоднородных данных чрезмерно большой размер может быть вреден, так как при резком изменении типа данных словарь будет заполнен неактуальными словами. Для эффективности работы данного метода при сжатии требуется дополнительная память. Приблизительно на порядок больше, чем нужно для исходных данных словаря. Существенным преимуществом словарного метода является простая и быстрая процедура распаковки. Дополнительная память при этом не требуется. Такая особенность особенно важна, если необходим оперативный доступ к данным[16].

Энтропийный метод (Huffman- кодирование Хаффмана, Arithmetic coding- арифметическое кодирование). В основе этого метода лежит кодирование не байтами, а битовыми группами:

· Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов;

· Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность);

· Образующая в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.

В связи с тем, что к сжатому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хаффмана малоэффективен. Практика также показывает, что его эффективность зависит и от заданной предельной длины кода (размера словаря). В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит). Широко используется как дополнительный метод. В качестве самостоятельного метода применяется, например, в графическом формате JPG.

Метод контекстного моделирования (CM- сокращение от context modeling- контекстное моделирование). В этом методе строится модель исходных данных. При сжатии очередного элемента данных эта модель выдает свое предсказание или вероятность. Согласно этой вероятности, элемент данных кодируется энтропийным методом. Чем точнее модель будет соответствовать исходным данным, тем точнее она будет выдавать предсказания, и тем короче будут кодироваться элементы данных. Для построения эффективной модели требуется много памяти. При распаковке приходится строить точно такую же модель. Поэтому скорость и требования к объему оперативной памяти для упаковки и распаковки почти одинаковы. В данный момент методы контекстного моделирования позволяют получить наилучшую степень сжатия, но отличаются чрезвычайно низкой скоростью.

PPM (PPM- Prediction by Partial Matching- предсказание по частичному совпадению). Это особый подвид контекстного моделирования. Предсказания выполняется на основании определенного количества предыдущих элементов данных. Основным параметром является порядок модели, который задает это количество элементов. Чем больше порядок модели, тем выше степень сжатия, но требуется больше оперативной памяти для хранения данных модели. Если оперативной памяти недостаточно, то такая модель с большим порядком показывает низкие результаты. Метод PPM особенно эффективен для сжатия тестовых данных.

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

Метод сортировки блока данных (BWT- сокращение от Burrows Wheeler Transform- по имени авторов). Это особый вид или группа преобразований, в основе которых лежит сортировка. Такому преобразованию можно подвергать почти любые данные. Сортировка производится над блоками, поэтому данные предварительно разбиваются на части. Основным параметром являются размер блока, который подвергается сортировке. Для распаковки данных необходимо проделать почти те же действия, что и при упаковке. Поэтому скорость и требования к оперативной памяти почти одинаковы. Архиваторы, которые используют данный метод, обычно показывают высокую скорость и степень сжатия для текстовых данных.

Непрерывные блоки или непрерывный режим (Solid mode- непрерывный режим). Во многих методах сжатия начальный участок данных или файла кодируется плохо. Например, в словарном методе словарь пуст. В методе контекстного моделирования модель не построена. Когда количество файлов большое, а их размер маленький, общая степень значительно ухудшается за счет этих начальных участков. Чтобы этого не происходило при переходе на следующий файл, используется информация, полученная исходя из предыдущих файлов. Аналогичного эффекта можно добиться простым представлением исходных файлов в виде одного непрерывного файла. Этот метод используется во многих архиваторах и имеет существенный недостаток. Для распаковки произвольного файла необходимо распаковать и файлы, которые оказались в начале архива. Это необходимо для правильного заполнения словаря и построения модели. Существует и промежуточный вариант, когда используются непрерывные блоки фиксированного размера. Потери сжатия получаются минимальными, но для извлечения одного файла, который находится в конце большого архива, необходимо распаковать только один непрерывный блок, а не весь архив[5].

Сегментирование. Во всех методах сжатия при изменении типа данных собственно сам переход кодируется очень плохо. Словарь становится не актуальным, модель настроена на другие данные. В этих случаях применяется сегментирование. Это предварительная разбивка на однородные части. Затем эти части кодируются по отдельности или группами.

Программные средства сжатия данных.«Классическими» форматами сжатия данных, широко используемыми в повседневной работе с компьютером, являются форматы .ZIP, .RAR и .ARJ. В связи с широким распространением нескольких форматов сжатия многие программные средства для сжатия данных начинают приобретать универсальный характер, позволяя упаковывать и распаковывать сжатые архивы разных типов. Программные средства для WINDOWS обычно имеют один «предпочтительный» тип архива, но также справляются с распаковкой данных при работе с архивами других типов. Наиболее распространен формат .ZIP, который является стандартом для архивов, распространяемых через Интернет. Немаловажную роль в этом играет открытость этого формата. Этот формат является полностью открытым- его использование не требует никаких лицензионных отчислений. Операционная система Windows XP позволяет рассматривать ZIP- архивы как сжатые папки. Это предлагает полностью прозрачную работу с такими архивами- все файловые операции можно выполнять в сжатой папке так же, как в обычной. Однако специализированные средства работы с архивами обеспечивают более широкий набор функций. Формат архивного файла, а следовательно, и его расширение зависят от выбранного архиватора[21]. Примеры популярных архивов и их расширение представлены в таблице 3.

Таблица 3 Примеры архиваторов

Название архиватора	Расширение архивного файла
LHA	.lzh
RAR	.rar
ARJ	.arj
PKZIP/PKUNZIP	.zip

Некоторые архиваторы поддерживают создание самораспаковывающихся архиваторов. Такие архиваторы имеют расширение .exe и распаковываются при запуске этого файла[19].

Существует два режима работы с архиваторами: режим командной строки и диалоговый с использованием интерфейса программы. Среди приведенных выше архиваторов диалоговый режим поддерживает, например, архиватор RAR. При работе в режиме командной строки каждая команда вводится клавишей <Enter>. Для вывода на экран справки о командах архиватора обычно достаточно набрать в командной строке имя архиватора, символ «/» и «?». Например: arj/? Или rar/?. В ОС Windows программы- архиваторы устанавливаются в систему. Их можно автоматически вызвать по контекстному меню (правая клавиша мыши при выделении файла или группы файлов). Программа- архиватор WinRar (рисунок 12).



Рисунок12. Архиватор WinRAR

WinRAR - это 32-разрядная версия архиватора RAR для Windows, мощного средства создания архивов и управления ими. Существует несколько версий RAR для разных операционных систем. Количество файлов, которое можно добавить в архив, зависит от объёма доступной памяти и длины имён файлов. Для добавления одного файла в архив RAR требуется ориентировочно 128 байт памяти. Максимальный размер архива RAR, равно как и любого файла в архиве RAR, практически не ограничен - он составляет 8 эксабайт (что равнозначно 8 589 934 591 Гбайт или 9 223 372 036 854 775 807 байт). В целом архивный формат RAR значительно лучше оптимизирован для сложных задач с использованием большого количества файлов и гигабайтных дисковых пространств. Меню WinRAR содержит следующие пункты: «Файл», «Команды», «Избранное», «Параметры» и «?».

Ещё один элемент интерфейса - панель инструментов. Она находится ниже меню и выше списка файлов. Кнопки на панели инструментов повторяют пункты из меню «Команды» (у всех пунктов в этом меню есть «горячие клавиши» для быстрого доступа). Во время просмотра содержимого архива некоторые кнопки могут быть отключены, если их функции неприменимы к архиву. Под панелью инструментов находится маленькая кнопка со стрелкой вверх и строка списка дисков. При нажатии кнопки «Вверх» происходит переход в родительскую папку. Список дисков служит для выбора текущего диска или, например, сети. Этот список также можно открыть нажатием клавиши <F4>. При желании кнопку «Вверх» и список дисков можно перетащить в правый угол панели инструментов. Текущий диск также можно изменить нажатием сочетания клавиш <Ctrl+D> или щелчком мыши на маленьком значке диска в строке состояния. Ниже панели инструментов расположено файловое окно. В нём отображается содержимое текущей папки или, если в WinRAR открыт архив, содержимое архива. Эти режимы называются режимом управления файлами и режимом управления архивами. Для каждого файла выводится следующая информация: имя, размер, тип и дата изменения. Для файлов в архиве показываются ещё два параметра - упакованный размер и значение CRC32. CRC32 - это особая контрольная сумма, вычисляемая на основании данных файла, с помощью неё можно сразу определить, одинаковы ли упакованные в архиве файлы, не прибегая к их распаковке. Файлы с одинаковым содержимым всегда имеют одинаковые CRC32. Все параметры представлены в виде колонок. Порядок сортировки файлов можно поменять щелчком на заголовке колонки (там же синей стрелкой указывается направление сортировки). Кроме того, можно изменить ширину колонок, перетаскивая мышью разделители заголовков колонок. Несколько дополнительных параметров списка можно изменить в диалоге «Список файлов». Если находящийся в архиве файл зашифрован, то после его имени будет стоять звездочка («*»). Если файл продолжается в следующем томе, то после его имени будут стоять символы «-->». Если файл продолжается из предыдущего тома, то после имени будут стоять символы «<--«. А если файл продолжается из предыдущего и переходит на следующий том, то после его имени будут стоять символы «<->».

Следующие комбинации клавиш можно использовать для навигации по списку файлов. Чтобы перейти в родительскую папку, необходимо нажать клавиши <BackSpace> (BS), <Ctrl+PgUp> или дважды щелкнуть мышью на папке «..» в списке файлов. Если сделать это в корневой папке архива, то этим закроется архив и осуществится переход в ту папку на диске, где он находится. Для перехода в другую папку можно нажать <Enter>, <Ctrl+PgDn> или дважды щелкнуть левой кнопкой мыши на этой папке. То же действие на файле архива приведет к открытию архива. Для перехода в корневую папку служит комбинация клавиш <Ctrl+\>. Если щелкнуть правой кнопкой мыши на списке файлов, то появится меню с командами интерфейса и управления файлами. Эти команды доступны также из обычных меню WinRAR, с панели инструментов и с помощью сочетаний клавиш, поэтому можно использовать наиболее удобный для себя способ. Если включена опция «Показывать комментарий» в диалоге общих параметров, а в открытом архиве есть комментарий, он будет показан в специальном окне справа от списка файлов. Ширину окна комментария можно изменять, перетаскивая мышью его левый край. Внизу окна WinRAR (под списком файлов) находится строка состояния. В её левой части расположены два маленьких значка: «диск» и «ключ». Щелчком по значку «диск» можно изменить текущий диск, а щелчком по «ключу» - текущий пароль. Две соответствующие команды также есть в меню «Файл». По умолчанию значок «ключ» жёлтого цвета, но если введён пароль, то он становится красным. В средней части строки состояния выводится информация об общем размере выделенных файлов или о текущем состоянии. В правой части строки состояния отображаются общее количество файлов в текущей папке и их размер. Оболочка WinRAR имеет два основных режима: режим управления файлами и режим управления архивами. В режиме управления файлами в окне WinRAR отображается список файлов и папок в текущей папке. Можно выделить эти файлы и папки, как обычно в Windows, с помощью мыши или клавиатуры, и произвести с выделенными файлами различные операции, например, заархивировать их или удалить. В этом режиме также можно протестировать группу архивов и извлечь из них файлы. В режиме управления архивами в окне WinRAR отображается список файлов и папок в открытом архиве. Здесь также можно выделить файлы и папки и выполнить с ними различные действия, специфичные для архива, например, распаковать, протестировать или добавить комментарий. В обоих режимах можно изменить текущую папку (на диске или в архиве). Для перехода в родительскую папку необходимо нажать клавишу <BackSpace> (BS) или <Ctrl+PgUp>, либо дважды щелкнуть мышью на папке «..» в списке файлов. Если сделать это в корневой папке архива, то закроется архив и осуществится переход в ту папку на диске, в которой он находится. Для перехода в другую папку необходимо нажать <Enter>, <Ctrl+PgDn> или дважды щелкнуть мышью на этой папке. Аналогичное действие на файле архива приведет к открытию архива. Для перехода в корневую папку диска служит комбинация клавиш <Ctrl+\>. Для входа в режим управления файлами запускается WinRAR двойным щелчком на его значке или вводится в командной строке «WinRAR» без параметров. Для входа в режим управления архивами запускается WinRAR в режиме управления файлами, помещается курсор на выбранный архив и нажимается <Enter> (это же действие выполняется при выборе пункта «Открыть архив» в меню «Файл» или при двойном щелчке мышью на имени архива). Кроме того, вход в режим управления архивами происходит при нажатии на архиве <Enter> или двойном щелчке мышью в оболочке Windows (в Проводнике или на Рабочем столе), но только в том случае, если WinRAR ассоциирован с архивами (что делается по умолчанию во время установки). Связать WinRAR с архивами несложно и после установки - для этого служит диалог «Параметры интеграции»[20].

Программа- архиватор ARJ (рисунок 13).



Рисунок 13. Архиватор ARJ

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

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

· создавать архивные файлы из отдельных или всех файлов текущего каталога и его подкаталогов, загружая в один архив до 32000 файлов;

· добавлять и заменять файлы в архиве;

· извлекать и удалять файлы из архива;

· просматривать содержимое архива;

· создавать многотомный архив;

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

· получать помощь по работе на 3 международных языках;

· вводить в архив комментарии к файлам;

· запоминать в архиве пути к файлам;

· сохранять в архиве несколько поколений (версий) одного и того же файла;

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

· осуществлять поиск строк в архивированных файлах;

· восстанавливать файлы из разрушенных архивов;

· создавать самораспаковывающиеся архивы как на одном томе, так и на нескольких томах;

· просматривать содержимое текстовых файлов, содержащихся в архиве;

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

Для получения на экране краткой помощи по работе достаточно в командной строке ввести имя программы: arj. Для получения развернутой помощи и примеров задания команд следует ввести: «arj -?» или «arj /?» Для загрузки программы и выполнения ею необходимых функций используется формат командной строки, где имя программы и параметры разделяются пробелами

arj <команда> [-<кл1> [-<кл2>...]] <имя_архива> [<список_имен_файлов>]

Обязательные параметры командной строки -- это два параметра: <команда> и <имя_архива>

В качестве списка имен файлов можно использовать шаблон (маску). Параметр <команда> записывается в виде одного символа вслед за именем программы и задает функцию архивации. Параметр <имя_архива> задает имя архивного файла и записывается по общим правилам MS DOS, но без указания расширения, которое при создании нового файла присваивается автоматически. Имя архива может быть записано с указанием пути к файлу. Архиватор по умолчанию обрабатывает архивные файлы, имеющие расширение .arj. Самораспаковывающийся архивный файл создается с расширением .exe. Такой файл содержит в себе программный модуль распаковки, и для извлечения из него файлов не требуется программа arj. Ключи уточняют действие команды архивации, и их может быть несколько. Каждый ключ начинается с символа "-" и может быть помещен в любом месте командной строки после команды. Признаком ключа кроме символа "-" может быть символ "/"[20].

Программа- архиватор ZIP(рисунок 14).

Рисунок 14. Архиватор ZIP

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

Существует два основных файла программы :

· PKZIP- программа помещающая файлы в архив;

· PKUNZIP- программа извлекающая файлы из архива.

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

При помещении файла в архив используется следующий формат:

«PKZIP режимы имя архива (имена файлов)»

Режимы- указываются с предшествующим знаком “-” или “/”, они задают или уточняют требуемые от программы архивации действия;

Имена файлов- задают файлы, включаемые в архив. При задании имен файлов можно использовать символы * и ?. Если имена файлов не заданы, то подразумевается все файлы из текущего каталога. После ввода команды программы-упаковщики начинают выполнять запрошенные действия. На экране изображаются имена помещаемых в архив файлов. При сжатии каждого файла выводиться процент обработанной части файла. После окончания сжатия каждого файла напротив его имени сообщается о степени сжатия. Например, при упаковке файла pkzip.exe на экране появляется надпись: «Adding: PKZIP.EXE Deflating (36%), done.» По умолчанию программа PKZIP обеспечивает достаточно большую скорость работы и близкую к максимальной степень сжатия. Но при желании можно получить максимальную (на несколько процентов большую) и наименьшую (быструю) степень сжатия. С ключом максимальной степени сжатия программа работает медленнее обычной, а при ключе наименьшей степени сжатия файлов наоборот, быстрее.

Ключи:

· “-ex” - максимальная степень;

· “-en” - средняя (обычная) степень;

· “-es” - наименьшая степень.

Программа PKZIP имеет три основных режима помещения файлов в архив:

· Add - добавление в архив всех файлов;

· Update - добавление в архив новых файлов;

· Freshen - добавление новых версий имеющихся в архиве файлов.

Эти режимы имеют следующие особенности:

в режиме добавления (Add) в архивный файл добавляются все указанные в команде файлы;

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

в режиме обновления версий файлов (Freshen) в архив добавляются новые версии тех файлов, которые уже имеются в архиве. Иначе говоря, в архив добавляются те файлы, копии которых уже находятся в архиве, но имеют более раннюю дату, чем у соответствующего файла на диске. Этот режим позволяет добиться того, чтобы архивный файл содержал наиболее свежие версии своих файлов. Как упоминалось ранее, для извлечения файлов из архивов, созданных программой PKZIP, используется программа PKUNZIP. После ввода команды программы архивации начинают извлечение файлов из архива. На экране изображаются имена извлекаемых из архива файлов. При извлечении файлов из архива может возникнуть ситуация, когда в том каталоге, в который извлекается файл, уже имеется файл с таким же именем. По умолчанию программа PKUNZIP при этом выполняет следующие действия: на экран выводиться запрос: «PKUNZIP: (W18) Warning! PKUNZIP.EXE already exists. Overwrite (y/n/a/r)? (Файл существует. Перезаписать?)». При нажатии на одну из клавиш : Y -- заместить имеющийся файл на диске, N -- не извлекать файл из архива, A -- всегда замещать имеющиеся на диске файлы(больше запросов не будет), R -- присвоить извлекаемому из архива файлу другое имя. Здесь извлечение новой версии файла - ситуация, когда для извлекаемого из архива файла в том каталоге, куда он должен быть помещен, имеется файл с тем же именем, но файл в архиве имеет более позднюю дату последней модификации, чем файл с тем же именем на диске; извлечение нового файла- ситуация, когда для извлекаемого из архива файла в том каталоге, куда он должен быть помещен, нет файла с тем же именем; запрос- запрос - предупреждение, делаемый перед “затиранием” файла на диске. Для каждого файла из архива в оглавлении архива запоминается его код циклического контроля (СRC). Этот код - специальная функция всего содержимого файла, составленная таким образом, что изменить файл так, чтобы его код циклического контроля остался неизменным, практически невозможно. Наличие кода циклического контроля позволяет проверить целостность архивного файла. При извлечении файлов из архива вычисляется код циклического контроля для каждого файла и сообщают пользователю, если этот код не совпадает с записанным в оглавлении архива. Проверить целостность архива можно с помощью команды тестирования: «Pkunzip -t имя-архива». Хранение информации в архиве более надежно из-за того, что данные хранятся в сжатом виде, меньше вероятность их случайного повреждения, например из-за дефектов магнитного покрытия диска. Но в некоторых случаях архивные файлы с большой вероятностью могут быть повреждены. Вот наиболее типичные из таких ситуаций:

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

· передача архива по телефонной сети через модем;

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

Если программы PKZIP или PKUNZIP обнаруживают, что оглавление архива повреждено, они выводят на экран сообщение: «имя-архива: Error in ZIP, use PKZipFix». Формат вызова: «PKZIPFIX имя- архивного- файла» . Эта программа создает в текущем каталоге архивный файл PKFIXED.ZIP , содержащий всю информацию, которую удалось восстановить из исходного архивного файла[20].



ГЛАВА II. МЕТОДИЧЕСКИЕ ОСНОВЫ ИЗУЧЕНИЯ ТЕМЫ «СЖАТИЕ ИНФОРМАЦИИ» НА УРОКАХ ИНФОРМАТИКИ И ИКТ В БАЗОВОМ КУРСЕ

2.1 Методика изучения темы «Сжатие информации» на уроках информатики и ИКТ

Прежде чем приступить к разработке конспектов по теме «Методы сжатия информации», мы изучили 7 учебно-методических комплекта по информатике - Н.В. Макаровой; А. Г. Гейна; И. Г. Семакина; Н. Д. Угриновича; А. Г. Кушниренко; Е. Н. Босовой; А. П. Ершова.

Мы выяснили, что в учебно- методические комплекты Е. Н. Босовой, А. П. Н. Ершова, А. Г. Кушниренко, Н. В. Макаровой тема «Сжатие информации» не входит; данная тема содержится в УМК Семакина И. Г., Угриновича Н. Д., Гейна А. Г. Проведя сравнительный анализ данных комплектов, мы пришли к выводу, что раскрытие темы «Сжатие информации» идёт в соответствии с федеральным государственным образовательным стандартом (таблица 4).