Kodowanie hoffmana

[ogre]

Jesli ma ktos jakis dobry link na ten temat to bylbym wdzieczny za udostepnienie.

[elceef]

Pewnie miałeś na myśli kodowanie Huffmana

[ogre]

No tak... Ci informatycy z liceum... Dlatego nie mogłem praktycznie nic znaleźć :|

[ogre]

Niestety, nadal nie wiem jak to zrobić.

Mam wyraz "abra kadabra".

1. Nie wiem, czy spacja też się liczy
2. Umiem wyliczyć [L] z http://pl.wikipedia.org/wiki/Kodowanie_Huffmana, ale [E] nie - ponieważ nie znam jeszcze logarytmów.
3. Nie wiem jak to rozkodować, i czy da się to rozkodować bez wyliczania E, żeby policzyć efektywność - jak to jest w wikipedii.

4. Czy w ogóle to co napisałem, czyli liczenie tej efektywności jest potrzebne do odkodowania?
5. Jak to odkodować?

Mógłby mnie ktoś naprowadzić na dobry trop? Patrzyłem na kilku stronach poza wikipedią, ale też mają niekompletne wzory, lub dane, nie jest napisane jak to obliczyć, czy spacja też się liczy.

Często są napisane same litery kody i wystąpienia:
http://4programmers.net/Algorytmy/Ko...ana,_kodowanie, tak jak tutaj, to:
1. Które dwa najmniejsze wierzchołki mam wybrać, skoro W i E mają po 3 wystąpienia?

--------------------------------------------------------------------------------------------

Ogólnie, jeśli komuś nie chce się odpowiadać na to wszystko, chodzi mi po prostu o to, żeby ktoś mi to wyjaśnił na rzetelnym przykładzie. Rysunki można pominąć.

Chcę uwzględnić to w mojej krótkiej prezentacji o szyfrach, ponieważ 'nauczyciel' mi tak polecił. Nie znam logarytmów, nie wiem jak to obliczyć i jak rozkodować

Proszę o pomoc.

[Nikow]

O ile dobrze zrozumiałem, chodzi o to że na początku robimy listę powtarzających się bajtów występujących w danych. Dla przykładu mamy plik który zawiera cyfry. Zliczamy na początku wszystkie cyfry, ile razy każda z nich występuje. Załóżmy że najczęściej występuje cyfra 5, dlatego ją dajemy na początek naszego "drzewa" (kod 0). Drugą najczęściej występującą w naszym pliku cyfrą jest 6. Dlatego stawiamy go na drugim stopniu naszego drzewa, dlatego ma kod 10. Później może być cyfra 3 i dajemy jej kod 110. Mówiąc inaczej, liczba zapalonych bitów (1) oznacza głębokość w naszym drzewie, a zgaszony bit (0) to separator.

Drzewko dla tabeli "5637428190powinno być mniej więcej takie:

/////////////////
/5-0-\1//////////
//6-0-\1/////////
///3-0-\1////////
////7-0-\1///////
/////4-0-\1//////
//////2-0-\1/////
///////8-0-\1////
////////1-0-\1///
/////////9-0-\1//
//////////0-0-\1/
/////////////////

Schodzisz w dół drzewka, tylko jeśli masz 1, jeśli 0 bierzesz wartość znaku. Dlatego dla kodu 1111110 bierzesz wartość 8. Tak, niektóre znaki będą kodowane na dłuższy sposób, ale według kodowania huffmana to się zwraca. Dlatego tutaj jest takie ważne policzenie występowania każdego znaku i jakieś posortowanie tego. Tutaj się przydają struktury 2 polowe (znak,liczba wystąpień). Bajt przyjmuje maksymalnie 256 wartości, dlatego do wydedukowania największej liczby możemy użyć sortowania bombelkowego.

Jak dalej nie kapujesz o co chodzi, zapraszam na IRC.