Matematyka.pl

Dla alfabetu {a, b, c, d, e} znajdź kod Huffmana przy założeniu następującego rozkładu prawdopodobieostwa występowania poszczególnych liter w kodowanym ciągu: {0.3, 0.25, 0.2, 0.15, 0.1}

a = 11
b = 10
c = 00
d= 011
e= 010

Jak to się robi krok po kroku ?

Buduje się takie drzewo (



następnie koduje się litery i ich kombinacje binarnie patrząc na to drzewo.

Cos mi tu nei pasuje :/ Nie powinno "a" wyjsc 1-bitowe ?

Nie, tutaj jednobitowe kodowanie a wymusi przynajmniej 2 dodatkowe bity w kodowaniu pozostałych znaków.

Na przykład gdy zwiększymy częstość a do 0,39, a pozostałe znaki pozostawimy w takich proporcjach, w jakich były, wówczas jednobitowe a zacznie się opłacać:

a = 0

b= 10

c = 110

d = 1111

e = 1110

Jeszcze raz może policzę krok po kroku:

\(\displaystyle{ (e+d)=0,25}\)

\(\displaystyle{ (c+(e+d))=0,45}\)

\(\displaystyle{ (b+a)=0,55}\)

\(\displaystyle{ ((c+(e+d))+(b+a))=1}\).

Można inaczej:

\(\displaystyle{ (e+d)=0,25}\)

\(\displaystyle{ (c+b)=0,45}\)

\(\displaystyle{ (a+(e+d))=0.55}\)

\(\displaystyle{ ((a+(e+d))+(c+b))}\)

czyli np.:

a=00

b=11

c=10

d=011

e=010

Teraz juz wiem co robilem zle. Zamiast 0,3+0,25 liczylem 0,45+0,25