[kod huffmana]

iveldion · Post autor: **iveldion** » 23 lut 2011, o 11:02

Skonstruuj kod Huffmana dla następujących ciągów znaków ( spacja _ też jest znakiem)

LIS_ALI_I_AS_LILI

kompletnie nie wiem jak się za to zabrać, mamy niby częstotliwość taką:
\(\displaystyle{ L=(04)\\
I=(05)\\
S=(02)\\
A=(02)\\
\_ =(04)}\)
mógłby mi to ktoś wytłumaczyć?

wawek91 · Post autor: **wawek91** » 23 lut 2011, o 19:10

A wiesz wogóle na czym polega algorytm Huffmana? Po polsku mówiąc wybierasz 2 najmniejsze liczmy i sumujesz, krok ten powtarzasz do momentu pozostania 2 liczb. Potem cofając się z rekursji budujesz drzewo zastępując sumę jej składnikami. Kiedy już wszystko rozłożysz możesz kodować na zasadzie: lewie ramie 0, prawe ramie 1. Dzięki temu otrzymasz swoje szukane kodowanie. W razie czego pisz, służę pomocą.

iveldion · Post autor: **iveldion** » 23 lut 2011, o 19:40

no ale jakie liczby ? ja koduje litery, wiec mogę sobie przypisać liczby te które wypisałem ? [częstotliwośc?]

będzie wtedy 4 i 13ście ;>
musiałbym to zobaczyć bo przeczytałem to na wikipedii ale kompletnie nie rozumie jak to zrealizować więc twoja pomoc będzie niezbędna

wawek91 · Post autor: **wawek91** » 23 lut 2011, o 20:03

Hm ... to jest tak masz zbiór liczb \(\displaystyle{ 4, 5, 2, 2, 4}\)(Twoj przykład)
W kolejnym kroku masz \(\displaystyle{ 4,4,5,4}\)
W kolejnym \(\displaystyle{ 8,5,4}\)
W ostatnim \(\displaystyle{ 9, 8}\)
Teraz rysujesz drzewo gdzie korzeń nie ma żadnej wartości a jego dzieci mają wartości \(\displaystyle{ 9}\) i \(\displaystyle{ 8}\). Następnie rozbijasz \(\displaystyle{ 9}\) na jej składniki czyli \(\displaystyle{ 5}\) i \(\displaystyle{ 4}\), potem rozbijasz \(\displaystyle{ 8}\) na \(\displaystyle{ 4}\) i \(\displaystyle{ 4}\), aż w końcu, \(\displaystyle{ 4}\) (dowolną bo wszystkie są na tym samym poziomie) na \(\displaystyle{ 2}\) i \(\displaystyle{ 2}\).
Teraz wystarczy już jedynie założyć, że Twoje kodowanie będzie wyglądało następująco: jeśli 'idziemy' do lewego dziecka to \(\displaystyle{ 0}\) jeśli do prawego to \(\displaystyle{ 1}\). I w taki sposób otrzymamy optymalne kodowanie binarne.

iveldion · Post autor: **iveldion** » 23 lut 2011, o 20:40

ale ten zbiór sam wyliczyłem z częstotliwości liczb, dobrze zrobiłem ?
więc tak graf będzie wyglądał ;>

wiec kodowanie będzie

Kod: Zaznacz cały

i tj koniec ?

wawek91 · Post autor: **wawek91** » 23 lut 2011, o 23:05

Graf jest ok ale kodowanie wygląda tak:

Kod: Zaznacz cały

L - 01
I - 00
S - 111
A - 110
_ - 10

Oczywiście to jest przykładowe, bo możemy np zamienić kodowanie liter S i A. Mam nadzieję, że wogóle o to chodziło, ale to odrazu mi się skojarzyło kiedy powiedziałeś o kodowaniu liter algorytmem Huffmana. W taki sposób robiliśmy to na ćwiczeniach. To się bodajże nazywa kodowanie prefixowe.

iveldion · Post autor: **iveldion** » 23 lut 2011, o 23:28

hmm ale skąd ci się wzięły akurat takie wyniki ?
tzn jak to zakodowałeś ;>
bo ja logiki nie widze, to nie są binarne odpowiedniki danych liczb, więc nie mam pojęcia

wawek91 · Post autor: **wawek91** » 24 lut 2011, o 10:38

Kodowałem to w taki sposób jak Ci mówiłem. Idąc po lewym ramieniu do lewego dziecka wypisuje \(\displaystyle{ 0}\) a jeśli po prawym ramieniu do prawego dziecka to \(\displaystyle{ 1}\). Dla przykładu do Twojej \(\displaystyle{ 5}\)-tki czyli liczby wystąpień litery \(\displaystyle{ I}\) idę od korzenia po lewym ramieniu (tam gdzie wcześniej byla \(\displaystyle{ 9}\)) a potem (od tej byłej \(\displaystyle{ 9}\)) znowu po lewym ramieniu do \(\displaystyle{ 5}\). Zatem \(\displaystyle{ 00}\).

iveldion · Post autor: **iveldion** » 24 lut 2011, o 15:46

zrozumiałem, dziękuje !