Курсовая работа по дисциплине «Информатика» на тему: «Алгоритм Хаффмана» Автор: Пятко Наталья. - презентация

1 Курсовая работа по дисциплине «Информатика» на тему: «Алгоритм Хаффмана» Автор: Пятко Наталья

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

3 Любое событие или явление может быть выражено по-разному, разными способами, разным алфавитом. Чтобы информацию более точно и экономно передать по каналам связи, ее надо соответственно закодировать. Целью данной курсовой работы является реализация алгоритма Хаффмана, то есть алгоритма оптимального префиксного кодирования. Алгоритм Хаффмана

4 В рамках данной курсовой работы рассмотрены принципы алфавитного кодирования, разделимые схемы кодирования, префиксные коды, частотная таблица алфавитов естественных языков. В курсовой работе говорится о задаче оптимального кодирования, а также рассматривается прямой и обратный ход алгоритм Хаффмана, доказательство оптимальности и полноты кодов Хаффмана. Алгоритм Хаффмана

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

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

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

8 Алгоритм состоит в следующем: выбираются два свободных узла дерева с наименьшими весами; создается их родитель с весом, равным их суммарному весу; родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка; одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой бит 0; шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева. Алгоритм Хаффмана

9 Алгоритм Хаффмана дает самый короткий код среди всех кодов, представляющих каждый символ сообщения фиксированной последовательностью бит. Доказательство этого факта строится на следующем свойстве оптимального кода - этот код может быть преобразован так, что два наиболее редких символа A и B будут представлены самыми длинными кодами, причем эти коды будут отличаться лишь младшим битом. Достоинства алгоритма:

10 Первая связана с хранением значений счетчиков символов, при кодировании длинных последовательностей. Дело в том, что языки высокого уровня, обычно, оперируют с числами максимум в 32 бит, в которых можно записывать числа от 0 до , т.е. можно работать с файлами размером 4Гб. Но иногда этих значений недостаточно и приходится вырабатывать дополнительные меры по предотвращению переполнения счетчиков символов. Вторая особенность связана с постоянным перестроением дерева Хаффмана, что влияет на скорость работы алгоритма. Вместе с тем можно заметить, что при считывании очередного символа из входного потока, дерево Хаффмана может остаться прежним и его перестраивать не имеет смысла. Это бывает, когда новое значение счетчика символа не влияет на его местоположении в дереве Хаффмана. Недостатки алгоритма:

11 С тех пор, как Д. А. Хаффман опубликовал в 1952 году свою работу «Метод построения кодов с минимальной избыточностью», его алгоритм кодирования стал базой для огромного количества дальнейших исследований в этой области. Кодирование Хаффмана используется в коммерческих программах сжатия (например в PKZIP и LHA), встроено в некоторые телефаксы и даже используется в алгоритме JPEG сжатия графических изображений с потерями. Алгоритм Хаффмана

12 Основная литература: 1. Абрамова М.И.: Информатика. - Белгород: НИУ БелГУ, Громов, Ю.Ю. Информационная безопасность и защита информации: Учебное пособие / Ю.Ю. Громов, В.О. Драчев, О.Г. Иванова. - Ст. Оскол: ТНТ, Партыка, Т.Л. Информационная безопасность: Учебное пособие / Т.Л. Партыка, И.И. Попов. - М.: Форум, Петров, С.В. Информационная безопасность: Учебное пособие / С.В. Петров, И.П. Слинькова, В.В. Гафнер. - М.: АРТА, Шаньгин, В.Ф. Информационная безопасность компьютерных систем и сетей: Учебное пособие / В.Ф. Шаньгин. - М.: ИД ФОРУМ, НИЦ ИНФРА-М, 2013 Дополнительная литература: 1. Васильков А. В. Информационные системы и их безопасность / А. В. Васильков, А. А. Васильков, И. А. Васильков - М.: Форум, Гуда А. Н., Колесников В. И. Информатика и программирование: компьютерный практикум - М.: Дашков и К, 2010 Список используемой литературы

13 Спасибо за внимание!