kodowanie huffmana

Odpowiedz Nowy wątek
2011-09-07 10:04
poczatkujacy
0

http://pl.wikipedia.org/wiki/Kodowanie_Huffmana

Czy tak jak, tam w przykladzie kodują litery ABCD i dołączają element o częstości 0,3 jest po prawej to jest taka reguła, że mniejsze bądź równe po prawej a wększę bądź równe po lewej? Czy to bez znaczenia.

Pozdrawiam!

Prosze o sprawdzenie tego zakodowania

http://www.przeklej.pl/plik/waga-krawedzi-docx-002cga4rq1dc

Pozostało 580 znaków

2011-09-07 12:29
0

Na wikipedii jest błąd. W książce Cormen'a "Algorytmy i struktury danych" było pokazane, że mniejsze bądź równe po lewej (chociaż tutaj nie ma to różnicy, ważne, żeby było konsekwentnie wykonywane) ale na wikipedii raz jest po lewej mniejsze (A i B) a raz po lewej jest większe (A+B+C).
user image
Ale mogę się mylić


Gdy się nie wie, co się robi, to dzieją się takie rzeczy, że się nie wie, co się dzieje ;-)

Pozostało 580 znaków

2011-09-07 12:59
0

A niby czemu ważne aby było konsekwentnie? W każdym kroku łączymy dwa najlżejsze węzły, obojętne który będzie lewy. Zmienią się tylko kody, ale długość będzie zachowana oraz wszystkie własności kodu Huffmana. Konstrukcja może prowadzić do różnych długości kodów jeżeli np w jakimś momencie są co najmniej trzy węzły o minimalnej wadze. Ale mimo, że kody mogą być różne, to jeśli są kodami Huffmana, to zawsze są optymalne.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-09-07 13:18
0

Racja, przy ostatnim łączeniu to nie ma znaczenia. Tutaj jest gif z angielskiej wikipedii
user image


Gdy się nie wie, co się robi, to dzieją się takie rzeczy, że się nie wie, co się dzieje ;-)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0