Адаптація алгоритму Хаффмана для кодування та декодування інформації

Мiнiстерство освiти i науки Укра"iни

Кафедра комп'ютерних наук

Секцiя iнформацiйний та комунiкацiйних технологiй

Обов’язкове домашнє завдання

з дисциплiни " Алгоритми і структурі данних"

Тема: "Адаптація алгоритму Хаффмана для кодування та декодування інформації"

Виконав                                                                      студент групи 

Перевiрив                                                                        

Зміст

Вступ        3

Алгоритм рішення        4

Теоритична частина        5

Код програми        7

Тестові приклади        13

Порівняльний аналіз        15

Асимптотична оцінка        15

Висновок        16

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

Вступ

Коди Хаффмана - дуже ефективний метод стиснення даних, який, в залежності від характеристик цих даних, зазвичай дозволяє заощадити від 20 до 90% обсягу. Ми розглядаємо дані, що представляють собою послідовність символів. У жадібному алгоритмі Хаффмана використовується таблиця, що містить частоти появи тих чи інших символів. За допомогою цієї таблиці визначається оптимальне представлення кожного символу у вигляді бінарного рядка.

Припустимо, що є файл даних, що складається з 100 тисяч символів, який потрібно стиснути. Символи в цьому файлі зустрічаються з частотою,. Таким чином, всього файл містить шість різних символів, а, наприклад, символ а зустрічається в ньому 45 тисяч раз.

. Завдання про кодування послідовності символів. Файл даних містить тільки символи а-f з зазначеними частотами. Якщо призначити кожному символу трехбітовое кодове слово, файл можна закодувати за допомогою 300 тисяч бітів. При використанні показаних кодових слів змінної довжини файл кодується тільки 224 тисячами бітів.

Існує безліч способів уявити подібний файл даних.Розглянемо завдання по розробці бінарного символьного коду , в якому кожен символ представляється унікальним бінарної рядком. Якщо використовується код фіксованої довжини, або рівномірний код, в якому кожен символ представлений унікальним бінарної рядком, то для подання шести символів знадобиться три біта: а = 000, 6 = 001, ..., / = 101. При використанні такого методу для кодування всього файлу знадобиться 300 тисяч бітів. Чи можна домогтися кращих результатів?

За допомогою коду змінної довжини, або нерівномірного коду, вдається отримати значно кращі результати, ніж за допомогою коду фіксованої довжини. Це досягається за рахунок того, що частоти, що зустрічаються асоціюються  символам і зіставляються короткі кодові слова, а менш часто  зустрічающимся довгі.

Для подання файла за допомогою цього коду буде потрібно

(45.1 + 13-3 + 12.3 + 16.3 + 9.4 + 5-4). 1000 = 224000 бітів.

Завдяки цьому економиться 25% обсягу.

Алгоритм рішення

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