Изучение темы по информатике "Архивация данных"

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

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

Как хранение, так и передача информации обходятся участникам информационного процесса недешево. Зная стоимость носителя и его емкость (Мбайт, Гбайт), нетрудно подсчитать, во что обходится хранение единицы информации, а зная пропускную способность канала связи (Мбит/с) и стоимость его аренды, можно определить затраты на передачу единицы информации (если не без лимитный тариф). Полученные результаты обычно составляют вполне значимые величины как для корпоративных пользователей, так и для индивидуальных. В связи с этим, регулярно возникает необходимость сжимать данные перед тем, как размещать их в архивах или передавать по каналам связи. Соответственно, существует и обратная необходимость восстановления данных из предварительно уплотненных архивов.

Из выше изложенного, очевидно, что при изучении информационных технологий тема «Сжатие (архивация) данных» достаточно важна.

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

Но что происходит с данными при работе программы - архиватора остается неизвестным.

На уроках по теме «Архивация данных» мы знакомимся с одним из первых алгоритмов эффективного кодиро­вания информации, который был предложен Д. А. Хаффманом в 1952 году.

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

Классический алгоритм Хаффмана на входе полу­чает таблицу частот встречаемости символов в сооб­щении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н - дерево). Алгоритм построения Н - дерева прост и элегантен.

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количест­ву вхождений символа в сжимаемое сообщение.

2. Выбираются два свободных узла дерева с наи­меньшими весами.

3. Создается их родитель с весом, равным их сум­марному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной ветви дерева, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Весь материал – смотрите документ.

Петраков Евгений Витальевич, учитель информатики, гимназия №14, г. Красноярск

Изучение темы «Архивация данных»

в 10-11 классах

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

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

Как хранение, так и передача информации обходятся участникам информационного процесса недешево. Зная стоимость носителя и его емкость (Мбайт, Гбайт), нетрудно подсчитать, во что обходится хранение единицы информации, а зная пропускную способность канала связи (Мбит/с) и стоимость его аренды, можно определить затраты на передачу единицы информации (если не без лимитный тариф). Полученные результаты обычно составляют вполне значимые величины как для корпоративных пользователей, так и для индивидуальных. В связи с этим, регулярно возникает необходимость сжимать данные перед тем, как размещать их в архивах или передавать по каналам связи. Соответственно, существует и обратная необходимость восстановления данных из предварительно уплотненных архивов.

Из выше изложенного, очевидно, что при изучении информационных технологий тема «Сжатие (архивация) данных» достаточно важна.

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

Но что происходит с данными при работе программы-архиватора остается неизвестным.

На уроках по теме «Архивация данных» мы знакомимся с одним из первых алгоритмов эффективного кодиро­вания информации, который был предложен Д.А.Хаффманом в 1952 году.

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

Классический алгоритм Хаффмана на входе полу­чает таблицу частот встречаемости символов в сооб­щении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количест­ву вхождений символа в сжимаемое сообщение.

2. Выбираются два свободных узла дерева с наи­меньшими весами.

3. Создается их родитель с весом, равным их сум­марному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной ветви дерева, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавлива­ется в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дере­во кодирования выглядит так, как показано на рис. 1.

рис.1

На следующем шаге «наилегчайшей» парой оказы­ваются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответст­вует ветви 0 родителя, Г/Д — ветви 1.

На последнем шаге в списке свободных осталось толь­ко два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

рис.2

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 2.

Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последо­вательность битов является кодом данного символа, записанным в обратном порядке.

Для данной таблицы символов коды Хаффмана бу­дут выглядеть следующим образом.

A - 0 Б – 100 В – 101 Г – 110 Д – 111

Поскольку ни один из полученных кодов не являет­ся префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством битов, а наиболее редкий символ Д — наибольшим.

Классический алгоритм Хаффмана имеет один су­щественный недостаток. Для восстановления содер­жимого сжатого сообщения декодер должен знать таб­лицу частот, которой пользовался кодер. Следова­тельно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость на­личия полной частотной статистики перед началом собственно кодирования требует двух проходов по со­общению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования.

После изучения теории переходим к практике. Моим учеником Петраковым И.Е. в рамках работы по НОУ бала разработана «VISYAFF» - программа– визуализатор сжатия данных по методу Хаффмана.

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

В строку «Текст» вводим или копируем текст для сжатия (рис.3)

рис.3

При нажатии на кнопку «Далее» последовательно заполняются окна данными, необходимыми для построения Н-дерева и сам код Хаффмана (рис.4)

«VISYAFF» может построить Н-дерево (рис.5), а также учитывать размер дерева (размер кодовой таблицы), который влияет на реальный размер файла архива.

рис.5

Программа успешно используется на уроках информатики и если

Вы заинтересовались, пишите petrakov63@rambler.ru