kodowanie huffmana

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

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ć

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.

0

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

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