GRY-Online.pl --> Archiwum Forum

Kodowanie Huffmana

17.01.2009
20:43
smile
[1]

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.

17.01.2009
21:02
[2]

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 ;)

17.01.2009
21:05
[3]

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

17.01.2009
21:25
[4]

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ć :)

17.01.2009
22:00
[5]

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. :)

© 2000-2021 GRY-OnLine S.A.