Читать курсовая по Отсутствует: "Статический алгоритм Хаффмана" Страница 1

(Назад) (Cкачать работу)

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Ивановский государственный энергетический университет

имени В.И. Ленина»

Кафедра ПОКС

Курсовая работа

по дисциплине: Структуры и алгоритмы обработки данных

«Статический алгоритм Хаффмана»

Выполнили: студенты гр. III-42

Сенченко А.А.

Петров Т.С.

Проверил: д.т.н. Пантелеев Е.Р.

Иваново2012

ОглавлениеПостановка задачи

Исходные данные

Описание алгоритма

Алгоритм построения дерева Хаффмана

Детали реализации

Результат работы программы

Используемые АТД

Структура программы

Оценка эффективности

Вывод

Список литературы

Написать кодер и декодер с использованием статического алгоритма Хаффмана. Исследовать эффективность (степень сжатия) в зависимости от типа и размера сжимаемых файлов.

Для демонстрации работы алгоритма мы использовали по 2 файла 3 типов разных размеров: doc, bmp, jpeg. После компрессии появляется файл в том же каталоге с именем дополненным суффиксом “.hfm” в конце. После декомпрессии программа создаёт файл, убирая расширение “.hfm”из конца имени файла.

Вся программа представляет собой Windows Forms приложение на языке C#.

Метод Хаффмана является исторически первым методом группы частотных алгоритмов. Оригинальная работа была опубликована в 1952 г. под названием "A Method for The Construction of Minimum Redundancy Codes".

В основе метода лежит модель кодирования в виде бинарного дерева с минимальной длиной взвешенных путей.

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

Вершина бинарного дерева, полу степень захода которой равна нулю, называется корнем. Для остальных вершин дерева полу степень захода равна единице.

Вершина m-дерева, полустепень исхода которой равна нулю, называется листом. Для остальных вершин полу степень исхода составляет 1 или 2.

Пусть T - бинарное дерево, А = (0,1) - двоичный алфавит, и каждому ребру Т- дерева приписана одна из букв алфавита таким образом, что все ребра, исходящие из одной вершины, помечены различными буквами. Тогда любому листу T - дерева можно приписать уникальное кодовое слово, образованное из букв, которыми помечены ребра, встречающиеся при движении от корня к соответствующему листу.

Особенность описанного способа кодирования в том, что полученные коды являются префиксными. Очевидно, что стоимость хранения информации, закодированной при помощи T - дерева, равна сумме длин путей из корня к каждому листу дерева, взвешенных частотой соответствующего кодового слова, или длиной взвешенных путей: Σwili, где wi- частота кодового слова длины li во входном потоке.

Рассмотрим в качестве примера кодировку символов в стандарте ASCII. Здесь каждый символ представляет собой кодовое слово фиксированной (8 бит) длины, поэтому стоимость хранения определится выражением 8Σwi = 8W, где W - количество кодовых слов во входном потоке. Поэтому стоимость хранения 39 кодовых слов в кодировке ASCII равна 312, независимо от относительной

Похожие работы