Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 33.81 Kb.
|
| Урок 7. Оптимальное кодирование информации. Код Хаффмана Цель урока: научиться применять результаты теории информации при решении проблем сжатия информации, освоить префиксное кодирование информации по Хаф-фману. Форма организации урока: диалог (обсуждение), практическая работа. Особенности изложения содержания темы урока В начале урока необходимо проверить и разобрать домашнее задание к уроку 6. Эффектно завершить повторение материала предыдущего урока можно разбором примера 8, описывающем оптимальную стратегию всем известной игры «Поле чудес». Удивительно, но теория информации может прийти на помощь и здесь, причем не только в виде таблицы информационных весов символов русского алфавита. Далее следует показать школьникам роль формулы Шеннона при оптимальном кодировании информации. Эта формула действительно дает нижнюю границу сжатия файлов с одинаковыми частотными характеристиками входящих в них символов, но только в том случае, когда мы будем использовать для одного и того же символа один и тот же код во всех файлах. Если при этом количество бит, используемых для кодирования любого символа, совпадает с его информационным весом, то кодирование является оптимальным. Правда, на практике осуществить такое кодирование практически нереально. Необходимым условием оптимального кодирования является целочисленность информационного веса каждого символа, а это возможно лишь тогда, когда вероятность появления любого символа представляет собой целую отрицательную степень двойки. Но, даже если мы построим оптимальный или близкий к оптимальному код для символов того или иного алфавита, на практике он не всегда будет применим для однозначного кодирования. Так как у подобных кодов разные символы кодируются последовательностями различной длины, то возникает проблема: как понять, где кончился код одного символа и начался код другого? Эта проблема может быть решена, если код обладает следующим свойством: код одного символа не может быть началом кода другого символа. Код, удовлетворяющий этому условию, называется префиксным. На примере 9 из учебника можно показать смысл подобного кодирования, а затем дать строгое определение. В примере 9 префиксный код был фактически угадан. Тем не менее для произвольного алфавита существует конструктивный алгоритм построения максимально близкого к оптимальному префиксного кода. Он известен как алгоритм Хаффмана. Он уже упоминался в главе 2 учебника. Поэтому можно ограничиться повторением нерекурсивного способа построения дерева Хаффмана. Соответствующий рекурсивный алгоритм без помощи компьютера понять сложнее, однако именно он конструктивно доказывает префиксность кода. Программировать данный алгоритм также легче рекурсивно. Фактически рекурсивное построение кода распадается на две фазы: «склеивание» символов (рекурсивный спуск) и приписывание кодов символам (рекурсивный подъем). Продемонстрировать обе фазы школьникам можно на примере 10 из учебника. Это удобно сделать в виде таблицы (заполнение левого столбца производится сверху вниз, а правого — снизу вверх):  После того как пример подробно разобран, можно перейти к практической работе. Каждому школьнику выдается алфавит с известными частотными характеристиками символов. В зависимости от силы учащихся алфавит может содержать от 4-х (задание 2) до 6-ти символов. От школьников требуется построить близкий к оптимальному префиксный код для заданного алфавита, а затем сравнить сжатие, которое дает полученный код в перерасчете на один символ, с энтропией распределения. Напомним, что энтропией распределения называется средний информационный вес символов алфавита. Далее можно обсудить со школьниками способы записи информации в файл с использованием кодирования по Хаффману. Используя уже имеющиеся коды, можно оценить размер получаемого при этом файла. При наличии доступа в компьютерный класс или хотя бы одного демонстрационного компьютера следует создать файл с соответствующими ASCII-символами (см. комментарии к заданию 4), сжать его с помощью одного из широко распространенных архиваторов (rar, zip, arj и т. п.) и сравнить длину полученного файла с результатом возможного сжатия по Хаффману. Полученную, вероятно существенную, разницу в результатах сжатия необходимо объяснить. Возможно, школьники сами смогут высказать некоторые предположения. В этой заключительной части урока следует обсудить некоторые подходы к сжатию информации, используемые современными архиваторами (см. материалы главы 2), и связать эти подходы с теорией информации. Важную роль здесь играет понятие сложности информации. При сравнительном анализе двух приведенных в тексте учебника последовательностей 01010101010101 и 1001110000 следует обратить внимание учащихся на то, что предложенный способ сокращения первой из последовательностей 7(01) = 1112(01) не обязательно даст эффект. Для того чтобы просчитать действительную сложность этой последовательности, необходимо ввести двоичное кодирование и для скобок (или способ отделения количества повторений от повторяемой части), что на практике может привести даже к удлинению, а не сокращению последовательности. Домашняя работа Задания 1, 3, 5 § 5.6. Подготовка к контрольной работе по теме «Основы теории информации». |
Добавить документ в свой блог или на сайт
