--> Archiwum Forum
Jam Jest Pawian [ Busted In The Hood ]
Kodowanie Huffmana
Witam, zakładam ten wątek z nadzieją że ktoś z was miał coś wspólnego z kodowanie huffmana, i wyjaśni mi moją wątpliwość, spowodowaną różnicą moich "obliczeń" z wynikiem ze skryptu. Chodzi o zakodowanie wyrazu YAAABAAADAAABAAADOOOO :D
Dla poszczególnych liter wychodzą mi następujące kody:
A - 1
O - 01
B - 001
D - 0001
Y - 0000
A w skrypcie wyniki mam takie:
A - 1
O - 00
B - 010
D - 0111
Y - 0110
Pytanie. Które z powyższych rozwiązań jest prawidłowe. Z góry dzięki za pomoc.
wuluk [ blind in darkness ]
Kodować Huffmanem można na dwa sposoby z tego co pamiętam - od góry i od doły. Twój kod jest równie dobry jak ze skryptu, więc albo zrobiłeś drugą metodą albo trafiłeś to przypadkiem ;)
Moby7777 [ Generaďż˝ ]
Ja to w sumie miałem wieki temu ale z tego co mi się przypomina (i z tego co patrzę na wiki i Twoje wyniki) to algorytm kodowania Huffmana nie jest jednoznaczny. Znaczy, że dla tak prostych przykładów jesteś w stanie wygenerować wiele równoważnych kodów. Zwróć uwagę na fakt, iż nie wykorzystujesz ledwie 1/4 przestrzeni czterech bitów... Czyli na moje oko obydwa wyniki są w sumie poprawne.
Ale jak mówiłem: dawno to miałem i mogę się mylić.
Jam Jest Pawian [ Busted In The Hood ]
Ja opierałem się na drzewach binarnych tak, jak jest to na polskiej wiki. Dzięki za wspomnienie o niejednoznaczności, dopiero teraz o tym doczytuje w sieci, a prowadzący zapomniał nam na ćwiczeniach o tym wspomnieć :)
Moby7777 [ Generaďż˝ ]
@Pawian: nie sugeruj się informacjami od prowadzących - zwłaszcza na ćwiczeniach. :) Ćwiczeniowcy to jakby nie patrzeć zazwyczaj doktoranci czyli ludzie niewiele starsi od Ciebie. Oni też mogą się pomylić albo o czymś zapomnieć. A co do kodowań to zawsze możesz popatrzeć zdroworozsądkowo na zasadzie "czy mój sposób jest gorszy? czy pojawia się niejednoznaczność? czy jest nadmiarowy?" Jak odpowiedzi będą negatywne to szukaj info w necie. :)