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

Типове

Дърво

data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Show, Read)

Функции

encode

Реализирана на няколко етапа:

getFrequencyList - което приема String и връща списък с наредени двойки (<буква>, <брой срещания>)

> getFrequencyList "aabccd"
[("a",2),("b",1),("c",2),("d",1)]

всяка наредена двойка става листо
getHuffmanTree - рекурсивно "слива" два върха в един клон докато се получи дърво
чрез дървото и функцията encodeInner се получават наредени двойки (<буква>, <код>)
кодираната дума се получава като всяка буква от думата заместим с кода ѝ

Крайният резултат от функцията е наредена двойка от дървото и кода на думата.

decode

Реализирана чрез:

getSymbol - рекурсивно "слиза" надолу по дървото докато стигне до листо. Когато стигне до листо връща символа на листото и дълбоината, на която е намерено. Символа трябва, защото все пак декодираме, а дълбочината трябва, за да знаем колко символа сме декодирали наведнъж. След като сме декодирали един символ, прескачаме толкова пъти, колкото е дълбочината на намерения символ и декодираме наново.

Интерфейс

При извикване на main функцията се показва въпрос "какво да правим". Потребителя може да избере или да кодира, или да декодира като съответно напише e/encode или d/decode (главни и малки букви нямат значение)

Encode - при желание за кодиране от потребителя се иска път до файл, в който е записана информацията за кодиране. Файлът се изчита и съдържанието му се подава на функцията encode. След успешно кодиране на информацията, от потребителя се иска път до файл, в който ще бъде записана кодираната информация - дървото и самия код.
Decode - при желание за декодиране от потребителя се иска път до файл, в който е записана кодирана информация - дърво и код. Файлът се изчита и съдържанието му се подава на функцията decode.
При въвеждане на каквото и да е друго програмата приключва.

Забележки

Функциите encode и decode приемат последен параметър оператор за сравнение на елементи. При използване на main функцията потребителят няма контролн над това кой оператор се подава - по подразбиране е (==)