Кодер та декодер із використанням алгоритму Хаффмана

РЕФЕРАТ[pic 1]

Пояснювальна записка до курсової роботи складається з: 40 ст., 8 рис., 7 джерел посилання, 1 дод.

Предмет дослідження: структури даних, робота з файлами, використання алгоритмів для стиснення даних та архівізації.

Мета курсової роботи: закріплення отриманих знань з програмування із використанням алгоритмічної мови С++ на прикладі  програмної реалізації кодування Хаффмана.

Методи дослідження: вивчення літературних джерел, створення та відлагодження програм на комп'ютері, аналіз результатів роботи програми.

У роботі розроблена програма для  програмної реалізації кодування Хаффмана. В додатку реалізовано приклад кодування Хаффмана, описана архітектура та алгоритми роботи.

КЛЮЧОВІ СЛОВА: ФАЙЛ, ТИП, СТИСНЕННЯ, АРХІВАТОР, ДАНІ,АЛГОРИТМ, АНАЛІЗ, АРХІВ, ХАФФМАН

                ЗМІСТ

ВСТУП        7

1 ОСНОВНІ ВІДОМОСТІ ЩОДО КОДУВАННЯ ХАФФМАНА        11

1.1 Призначення        11

1.2 Опис кодування        13

1.3 Застосування кодування Хаффмана        15

2 АЛГОРИТМ ХАФФМАНА НА С++        22

2.1Принцип роботи         22

2.2Переповнення        23

2.3 Масштабування ваг вузлів дерева Хаффмана…………………………..23

3 ОПИС ПРОГРАМНОЇ РЕАЛІЗАЦІЇ АЛГОРИТМУ ХАФФМАНА        25

3.1 Загальні відомості        25

3.2 Функціональне призначення        30

ВИСНОВКИ        42

ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАННЯ        43

ДОДАТОК А        44

ВСТУП

Задача мого курсового проекту написати кодер та декодер із використанням алгоритму Хаффмана. Для прикладу роботи програми я вибрала мову програмування С++. Для кодування була вибрана фраза “ it is my striiiiing!!!!”. Закодована вона була в таку послідовність бітів 11010100111011.

  10000[pic 2]

! 00

g 10100

I 11

m 10100

n 01110

r 01111

s 1011

t 010

y 0110

Щоб не плутатись з бітами набагато зручніше здійснити спуск по дереву (починаючи з кореня) за таким правилом:

 1. Вихідна точка – корінь дерева.

 2. Прочитати новий біт.  Якщо він нуль, то пройти гілкою, поміченою нулем, інакше — одиницею.

 3. Якщо точка, в яку ми потрапили, кінцева, то ми визначили кодовий символ, який слід записати та повернутися до пункту 1. Інакше слід повторити пункт 2

Розглянемо приклад дерева та подивимось на блок схему заданого алгоритму.

[pic 3]

Рис1. Приклад дерева за даними

Тепер подивимось на приклад блок схеми алгоритму Хаффмана.

[pic 4]

Рис.2 блок схема алгоритма генерації кода Хаффмана по довжині кода

На малюнку 2 прийняті такі позначення:

 MD - масив довжин кодів

 MK-масив кодів Хаффмана

 с – поточний хід Хаффмана

 s– поточна довжина коду Хаффмана

 k– індекс масиву довжин

 == - одно

 != - Нерівно

 = привласнити

 ← - збільшити масив на один елемент праворуч та додати на це місце вказане значення

 ++ - збільшити на одиницю

 <<= - зрушити значення вліво на вказану величину з додаванням нулів праворуч.

        Таким чином, службова інформація це список символів алфавіту, що кодується, плюс список довжин кодів.  Проте декодер можна передавати не сам список довжин, а список лічильників довжин, Тобто список кількості появ кожної довжини від довжини рівної 1 до максимальної довжини.

1 ОСНОВНІ ВІДОМОСТІ ЩОДО КОДУВАННЯ ХАФФМАНА

1.1 Призначення

Метод стиснення інформації на основі двійкових дерев, що кодують, був запропонований Д. А. Хаффманом в 1952 році задовго до появи сучасного цифрового комп'ютера. Маючи високу ефективність, він та його численні адаптивні версії лежать в основі багатьох методів, що використовуються в сучасних алгоритмах кодування. Код Хаффмана рідко використовується окремо, частіше працюючи у зв'язці з іншими алгоритмами кодування. Метод Хаффмана є прикладом побудови кодів змінної довжини, мають мінімальну середню довжину. Цей метод робить ідеальне стиснення, тобто стискає дані до їхньої ентропії, якщо ймовірності символів точно дорівнюють негативним ступеням числа 2.