Хъфманово кодиране

Проект по Функционално програмиране,

СУ, ФМИ зимен семестър 2021/2022

Ана Илиева, фак. № 82303

Съдържание

Идея

Структура

Инструкции за употреба

Обобщение на реализацията

Идея

Целта на проекта е да бъде реализиран алгоритъмът на Хъфман за кодиране на информация – алгоритъм за компресия без загуба на данни, работещ в 4 стъпки:

1. Генериране на списък от вида ' ( (x, y) …), където x е елемент на оригиналните данни, а y – броя срещания на x
2. Създаване на Хъфманово дърво, обединявайки по-малки поддървета, съответстващи на списъка от стъпка 1
3. Намиране на кодовете на отделните елементи – на всяко ребро в дървото от стъпка 2 се съпоставя 0, ако е ребро към лявото поддърво, или 1, ако е към дясното
4. Кодиране – всеки елемент на оригиналния списък се замества със своя код от стъпка 3

Използван е функционалният език за програмиране Scheme. В решението са реализирани двете основни функции - за кодиране и декодиране. Постигната е основната идея на проекта - след кодиране и декодиране на даден файл резултатът съвпада с оригинала. Данните са представени като списък от произволен тип елементи.

Структура

Проектът е разделен на малки функции, изпълняващи отделни подзадачи, които обединени съставят двете основни функции:

• Функцията encode – приема предикат за сравнение на отделните елементи — напр. eq? или equal?, и данните, представени чрез списък и връща конструираното Хъфманово дърво и компресираните данни. Използва в себе си функциите:
• make-huffman-tree – съставя Хъфмановото дърво по подадения списък
• encoding – съставя кодираните данни
• Функцията decode - приема предикат за сравнение на отделните елементи — напр. eq? или equal?, Хъфмановото дърво и компресираните данни и връща оригиналния списък от елементи. Използва в себе си помощна функция за успоредно обхождане на дървото и кодираните елементи

Инструкции за употреба

С проекта се работи изключително лесно. За извикване на фукнцията за кодиране: (encode equality list), където equality е предикатът за сравнение на елементите, а list е списъкът с данните.

Пример:

Резултат:

За извикване на функцията за декодиране: (decode equality tree encoding), където equality е предикатът за сравнение на елементите, tree е Хъфмановото дърво, a encoding е кодираната информация.

Пример:

Резултат:

Обобщение на реализацията

Проектът покрива базовите изисквания, като част от основните функции за работа с дървета са реализирани с помощта на написания код на лекции и упражнения.