Описание презентации по отдельным слайдам:
Для того чтобы сэкономить место на внешних носителях (винчестерах, флэш‐дисках) и ускорить передачу информации по компьютерным сетям, нужно ее сжать – уменьшить информационный объем, сократить длину двоичного кода. Возможны две ситуации при сжатии: Потеря информации в результате сжатия недопустима; Допустима частичная потеря информации в результате сжатия.
При упаковке данных в файловые архивы производится их сжатие без потери информации. Сжатие с частичной потерей информации производится при сжатии кода изображения (графики, видео) и звука. Сжатие без потери информации: использование неравномерного кода; выявление повторяющихся фрагментов кода.
Сжатие информации Сжатие происходит за счет устранения избыточности кода, например, за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов в виде коэффициента повторения. Важнейшая характеристика процесса сжатия – коэффициент сжатия. Коэффициент сжатия – отношение объема исходного сообщения к объему сжатого.
Алгоритмы сжатия, использование неравномерного кода В основе первого подхода лежит использование неравномерного кода. В восьмиразрядной таблице символьной кодировки (ASCII), каждый символ кодируется восемью битами и, следовательно, занимает в памяти 1 байт. Информационный вес символа тем больше, чем меньше его частота встречаемости. С этим обстоятельством и связана идея сжатия текста в компьютерной памяти: отказаться от одинаковой длины кодов символов.
Алгоритм Хаффмана Алгоритм Хаффмана — адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
Коэффициентом сжатия называют отношение длины кода в байтах после сжатия к его длине до сжатия. Деревом называется графическое представление (граф) структуры связей между элементами некоторой системы. Двоичным деревом называется дерево, в котором любая вершина, имеет не более двух потомков. Корнем дерева называется единственная вершина, не имеющая родительской вершины. Листьями дерева называются вершины, не имеющие потомков.
Алгоритм кода Хаффмана: 1. Символы исходного алфавита образуют вершины. Вес каждой вершины вес равен количеству вхождений данного символа в сжимаемое сообщение. 2. Среди вершин выбираются две с наименьшими весами (если таких пар несколько, выбирается любая из них). 3. Создается следующая вершина графа, из которой выходят две дуги к выбранным вершинам; одна дуга помечается цифрой 0, другая — символом 1. Вес созданной вершины равен сумме весов, выбранных на втором шаге вершин. 4. К новым вершинам применяются шаги 2 и 3 до тех пор, пока не останется одна вершина с весом, равным сумме весов исходных символов.
Для кодирования сообщения, состоящего из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Выберите правильный вариант ответа. 1) для буквы Б – 01 2) это невозможно 3) для буквы В – 01 4) для буквы Г – 01 Задача А9
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 1) 1 2) 1110 3) 111 4) 11 Для самостоятельной работы
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? Задача А9
Список используемой литературы: http://crazycode.net/blog/10-algorithms-and-data-structures/31-huffman http://edu.1september.ru/courses/07/008/01.pdf http://www.lukomor.ru/attach/pages/ege13/A09.pdf?PHPSESSID=9fa7039ee3de232e76b2a13614accbf5 Педагогический университет «Первое сентября», 2008г. И.Г. Семакин «Информатика и ИКТ» 10 класс профильный уровень,2012
Данная презентация предназнача для 10 класса (профильного) на урок информатики по теме "Сжатие двоичного кода.Алгоритм Хаффмана". Особое внимание уделяется на виды сжатия иформации (с потерей и без потери информации). Подробно описывается алгоритм Хаффмана, приводятся примеры, рассчитывается коэффициент сжатия информации; для закрепления даны задачи для самостоятелного решения; также в конце приведены задания по данной теме, которые встречаются в ЕГЭ, первые задачи приведены с решением, затем опять для самостоятельно решения, для закрепления полученных знаний.
Вам будут интересны эти курсы: