ЗМІСТ
Введення
1. Рішення завдання
. Програмна реалізація
. Алгоритм програми
. Аналіз трудомісткості алгоритму
Висновок
Список використаних джерел
ВСТУП
Дана робота представляє собою опис програми, що реалізує алгоритм Хаффмана, а саме, дозволяє закодувати текст двійковим кодом так, щоб обсяг інформації був мінімальний, а також оцінку обчислювальної складності даної програми.
1. Рішення завдання
Існує кілька алгоритмів кодування інформації двійковим кодом, але для вирішення поставленого завдання найбільш підходить алгоритм Хаффмана кодування інформації.
Ідея методу - часто повторювані символи потрібно кодувати більш короткими ланцюжками бітів, ніж ланцюжки рідкісних символів. Будується двійкове дерево, листя відповідають кодованим символам, код символу представляється послідовністю значень ребер (ці значення в двійковому дереві суть 1 і 0), провідних від кореня до листа. Листя символів з високою ймовірністю появи знаходяться ближче до кореня, ніж листя малоймовірних символів. p align="justify"> Це дозволяє закодувати інформацію (текст) двійковим кодом, причому обсяг інформації буде мінімальний. Однак, для розкодування тексту нам буде потрібно алфавіт, а саме В«дерево ХаффманаВ», яке було побудовано при кодуванні. Вирішення цієї проблеми не включено до рішення поставленого завдання, тому що при невеликих обсягах інформації алфавіт може займати більшу кількість пам'яті, ніж сама інформація (текст).
2. Програмна реалізація
Програма реалізована на мові C + +. Вона зчитує вхідний файл і записує його двійкове подання у вихідний файл. Потрібно зауважити, що, теоретично, вхідний файл може бути абсолютно будь-яким, будь то текстовий файл, картинка або відеофайл, тому що читання файлу відбувається по байтах. Але правильність роботи перевірялася тільки на текстових файлах. p align="justify"> Програма виводить на частоту появи символу в тексті, код кожного символу після кодування, і початковий текст у двійковому поданні.
Текст програми:
# include
# include
# include
# include
# include "Windows.h" namespace std; Tree
{: symbol; weight; * left_son; * right_son;
}; Symbol_class
{: symbol;// символ
int amount;// його частота в тексті
vector code;// код символу
}; symbol_vector;// список всіх символів Tree_vector;// дерево Хаффмана
vector code;// бінарний код символів * main_...
