Реферат на тему Метод кодирования Хаффмана

Содержание:

Введение 3
1. Сущность алгоритма кодирования Хаффмана 5
2. Специфика сжатия данных по алгоритму Хаффмана 8
Заключение 16
Список использованной литературы 17

Введение:

Потребность кодировать информацию, т.е. преобразовывать ее для каких-то специфических целей, люди испытывали и в докомпьютерную эпоху. Письменность есть ни что иное, как способ кодировать сообщения для долговременного хранения, публикации или отправки адресату. То же можно сказать о цифрах, применяемых для вычислений, записи дат. Музыка уже несколько веков записывается с помощью нот.
Со временем появились специальные системы кодирования для передачи информации с помощью радиосигналов (азбука Морзе), для людей с ограниченными возможностями (азбука Брайля для незрячих, азбука жестов для глухонемых). По мере развития науки и техники были внедрены знаковые системы для отдельных отраслей человеческой деятельности. Химики пользуются особыми формулами для записи структуры молекул, астрономы — для обозначения интенсивности блеска и цвета небесных тел, инженеры, создавая чертежи и схемы, применяют стандартизированные условные обозначения. В каждой отрасли человеческой деятельности есть свои особенности общения между специалистами, свой сленг, свои символы.
Современные пользователи довольно часто сталкиваются с проблемой нехватки свободного пространства на жестком диске. Многие, в попытке освободить хоть немного свободного пространства, пытаются удалить с жесткого диска всю ненужную информацию. Более продвинутые пользователи используют для уменьшения объема данных особые алгоритмы сжатия. Несмотря на эффективность этого процесса, многие пользователи никогда о нем даже не слышали.
Все существующие способы сжатия информации можно разделить на две основные категории. Это сжатие без потерь и сжатие с определенными потерями. Первая категория актуальна только тогда, когда есть необходимость восстановить данные с высокой точностью, не потеряв ни одного бита исходной информации. Единственный случай, в котором необходимо использовать именно этот подход, это сжатие текстовых документов. В том случае, если нет особой необходимости в максимально точном восстановлении сжатой информации, необходимо предусмотреть возможность использования алгоритмов с определенными потерями при сжатии.
Данные методы сжатия информации интересуют прежде всего, так как именно они применяются при передаче больших объемов информации по электронной почте, при выдаче выполненной работы заказчику или при создании резервных копий информации, хранящейся на компьютере. Эти методы сжатия информации не допускают потерю информации, поскольку в их основу положено лишь устранение ее избыточности, информация же имеет избыточность практически всегда, если бы последней не было, нечего было бы и сжимать.
Неэффективная кодировка является вторым фактором, характеризующим избыточность. Программы, благодаря которым выполняется сжатие информации, могут вводить свою кодировку, причем она может быть разной для разных файлов, и приписывать ее к сжатому файлу в виде таблицы (словаря), из которой распаковывающая программа будет считывать информацию о том, как в данном файле закодированы те или иные символы или их группы.
Алгоритмы, в основу которых положено перекодирование информации, называются алгоритмами Хаффмана.
Целью данной работы является изучение сущности методов кодирования Хаффмана. 

Заключение:

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

Фрагмент текста работы:

1. Сущность алгоритма кодирования Хаффмана
Изучая теорию информации можно столкнуться с такими ключевыми понятиями информации как кодирование, графы, дерево.
Граф — это средство для наглядного представления состава и структуры системы. Граф состоит из вершин, связанных дугами или ребрами. Существуют графы, не содержащие циклов, или ациклические графы, и связные графы. Одной из разновидностей графов является дерево. Двоичное дерево — дерево, у которого из каждого узла выходит только две дуги. Кодирование — это преобразование сообщений в сигнал. Процесс декодирования — процесс обратный кодированию .
Код Хаффмана — это особый тип оптимального префиксного кода, который обычно используется для сжатия данных без потерь. Он сжимает данные, очень эффективно экономя от 20% до 90% памяти, в зависимости от характеристик сжатых данных. Мы рассматриваем данные как последовательность символов. Жадный алгоритм Хаффмана использует таблицу, показывающую, как часто каждый символ (т.е. его частота) генерирует оптимальный способ представления каждого символа в виде двоичной строки. Код Хаффмана был предложен Дэвидом А. Хаффманом в 1951 году.
Предположим, у нас есть файл данных размером 100 000 символов, который мы хотим сохранить компактно. Мы предполагаем, что в этом файле всего 6 разных символов. Частота символов задается: