Код на Хъфман

[pasho_pz]

Помогнете за кодирането на "Георги Стоянов Пашалиев 0702491005" с метод на Хъфман...
Трябва да се направи Хъфманово дърво, търсих из интернет наини, но без резултат...

[Реклама]

[FuckYouAll]

Много се надявам някой да ти отговори (аз не мога), защото и на мен ми е интересно...

[nikko1]

За да се създаде Хъфманово дърво трябва да имаш таблица със симовли и съответните вероятности за тяхната поява. Създаването на такава таблица и написването на код на Хъфман, както и съответното Хъфманово дърво ще останат като упражнение за теб.

Целта е от произволен източник да бъде създаден префиксен код, в който най-често срещаните символи да са кодирани в най-кратки думи.

Ще дам пример за двоичен код на Хъфман. Да речем че в даден източник на текст се срещат символи със следната честота и вероятности:

[tex]\begin{array}{|c|c|c|}\hline\cyr{simvol}&\cyr{chestota}&\cyr{veroyatnost}\\\hline A&4&0.4\\\hline E&2&0.2\\\hline B&1&0.1\\\hline C&1&0.1\\\hline D&1&0.1\\\hline F&1&0.1\\\hline\end{array}[/tex]

Започваме с редукция на двата символа с най-малка вероятност, т.е. D и F, които ще се групират в един символ с вероятност 0.2. Трябва да сложим новия символ между A и E или между E и B. Нека да изберем да е между E и B и продължаваме с този процес на редукция, резултатът е показан на Фигура 1. Накрая получаваме два символа съответно с вероятности 0.6 и 0.4, който ще кодираме със символите 0 и 1. Сега трябва да се върнем отзад - напред като "разделяме" всяка кодова дума [tex]w,[/tex] поставена като сума от две вероятности на две думи [tex]w0[/tex] и [tex]w1.[/tex] Виж Фигура 2.
Така се получава следният код на Хъфман:
[tex]\begin{array}{cccccc}A&E&B&C&D&F\\00&11&010&011&100&101\end{array}[/tex]

От него създаваме двоично дърво като левия наследник ще е 0, а десния 1. За нашия пример това дърво е на фигура 3.

Успех.