Регистрирайте сеРегистрирайте се

Код на Хъфман


 
   Форум за математика Форуми -> Дискретната математика
Предишната тема :: Следващата тема  
Автор Съобщение
pasho_pz
Начинаещ


Регистриран на: 18 Mar 2007
Мнения: 16

Репутация: 8.4Репутация: 8.4Репутация: 8.4Репутация: 8.4Репутация: 8.4Репутация: 8.4Репутация: 8.4Репутация: 8.4

МнениеПуснато на: Tue Mar 10, 2009 5:25 pm    Заглавие: Код на Хъфман

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







Пуснато на:     Заглавие: Реклама

Върнете се в началото
FuckYouAll
Редовен


Регистриран на: 27 Feb 2009
Мнения: 165


гласове: 16

МнениеПуснато на: Tue Mar 10, 2009 8:24 pm    Заглавие:

Много се надявам някой да ти отговори (аз не мога), защото и на мен ми е интересно...
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Mar 10, 2009 11:44 pm    Заглавие:

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

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

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

[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.

Успех.



tree.png
 Description:
 Големина на файла:  57.22 KB
 Видяна:  5968 пъти(s)

tree.png



tree2.png
 Description:
 Големина на файла:  66.29 KB
 Видяна:  5968 пъти(s)

tree2.png



tree3.png
 Description:
 Големина на файла:  15.63 KB
 Видяна:  5968 пъти(s)

tree3.png


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.