Algorytm Huffmana

Kompresja algorytmem Huffmana rozpoczyna się od zebrania statystyk występowania poszczególnych elementów w zbiorze. Następny etap polega na zbudowaniu drzewa binarnego, w którym znaki są umieszczane jako ***8222;liście" wg zasady: występujące najczęściej na zewnątrz grafu, a najrzadziej w jego środku. Wygenerowanie kodu dla każdego ze znaków następuje w wyniku przejścia drogi od wierzchołka do odpowiedniego liścia.

Zaraz zapodam skan z CHIPa gdzie byl pokazany przyklad ;) Poczekaj ;)

Tylko tam jest opisany kolejny specjalny przypadek drzewa binarnego - pelne drzewo binarne (czyli ze wszystkie posrednie poziomy sa wypelnione, a ostani poziom jest wypelniany od lewej). W ogolnosci nie musi ono tak "ladnie" wygladac.

Wiec ... stworzyles pelne drzewo binarne, a nie BST (binary search tree)

A tak wyglada "ladne" drzewo BST:

http://forum.cdrinfo.pl/attachment.p...chmentid=21233

A tak wyglada brzydkie drzewo BST:

http://forum.cdrinfo.pl/attachment.p...chmentid=21234

(NULLi sie zwykle nie rysuje, ale tutaj narysowalem zebys widzial jak to wyglada, gdyby w pierwszym rysunku dorysowywac NULLe to trzeba by bylo stworzyc nowy poziom i od kazdego liscia - wezla na ostatnim pociagnac krawedz do dwoch synow - NULLi)

Dzięki wszystkim!!!!

o drzewach cos tu znalazlem jeszcze takze poczytam...
http://www.i-lo.tarnow.pl/edu/inf/alg/sort/pages/05.htm

Z tą kompresją tez wydaje mi sie ze 50% bo plik zmalal 2 krotnie



1) http://beta.xlo.poznan.pl//upload_files/drzewo.GIF
Dobrze?

Co do szyfru Cezara, wygląda on tak, że chcąc zakodować dany wyraz przesuwamy każdą literę o taką samą, ustaloną wartość.

Dla przykładu chcemy zakodować wyraz DOM, nasza wartość niech wynosi 3. Po zakodowaniu wychodzi GRP (każdą literę zastępujemy literą znajdującą się 3 miejsca dalej w alfabecie).

Słabą stroną tego szyfru jest to iż jest on bardzo prosty do odgadnięcia. Mając zakodowany dłuższy tekst wystarczy rozszyfrować jeden wyraz i już mamy klucz.

Zad 1 mozna zrobic na kilka sposobow. Chodzi tu o drzewo BST, a takich z danego ciagu liczb mozna zrobic duzo. Ogolnie chodzi o to zeby wszystkie elementy po lewej stronie byly mniejsze od korzenia a te po prawej wieksze od korzenia. Oprocz prawy i lewy syn powinni tworzyc podrzewa bedace drzewami BST.

Szczegolnym przypadkiem BST jest AVL i to jest bardzo ladna struktura jezeli chodzi o teoretyczne wlasnosci, lecz niestety sie dosc trudno koduje i dlatego zamiast tego uzywa sie jeszcze innej struktury - drzewa SPLAY.

Wiec mozna z tego zrobic po prostu drzewo wygladajace jak lista: zaczynasz od najmniejszego i po prawej przypinasz kolejny element i tak dalej. Niestety glebokosc bedzie bardzo niekorzystna - tyle co elementow.

Zad 2 - poszukaj jak sie to liczy albo sciagnij np. IzaRC i tam zobacz jak wyswietla ...

Zad 3 - np. mp3, - stratna bo sie obcina zeby uzyskac wieksza oszczednosc miejsca..

Zad 4 - powinienem wiedziec, ale nie pamietam juz tego.

Zad 5 - nie powinienem tego wiedziec i nie wiem, ale pewnie jest w sieci ...

Zad 6 - jak wyzej.

Ogolnie:

drzewa binarne to drzewa gdzie kazdy wierzcholek ma dwoch synow - lewego i prawego.

metody porzadkowania - no sortowanie to glowne zagadnienie inf :) zobacz selection sort, insertion sort, bubble sort, bucket sort, merge sort, quick sort, heap sort, - tu jest cos, strona wolno dziala ale jest dosc duzo - znalazlem to przed chwila http://www.i-lo.tarnow.pl/edu/inf/al...s/contents.htm

Z kodowaniem to musisz czegos poszukac ... ale RSA to dosc popularny problem :)

w/g mnie 50 % kompresja

wg. mnie 1/2

2) Na chłopski rozum:
stosunek 2048 do 4096 * 100%
3) http://pl.wikipedia.org/wiki/Kompresja_stratna
przykład MP3, JPEG, DivX, RMVB, OGG

Zagadnienia z informatyki.
 

W poneidzialek mam sprawdzian, szukalem info na ten temat, ale nie moge znalezc satysfakcjonujacej mnie odpowiedzi.
Potrzebuje zeby ktos mi wytlumaczyl tak na "chlopski rozum" bo nie potrafie skumac tych zadan :D
Dlatego kieruje prosbe do Was o wyjasnienei

Oto zagadnienia:
-drzewa binarne
-metody porządkowania
-kod morsa i hufmana
-kryptologia metody szyfrowania
-szyfry podstawieniowy, przestawieniowy, asymetryczne(rsa, pgp), i vigenera

i zadania...

1) z ciągu liczb zbudój binarne drzewa poszukiwań określ wys. tego drzewa 5,2,1,10,11,8,4
2) Plik przed kompresją miał 4096kb po 2048kb podaj st. kompresji
3) Co to jest kompresja stratn podaj przykłady.
4) Dany jest alfabet A={A,B,C,D,E} oraz częstotliwość wyst. liter A=2,5 B=3 C=1,5 D=1,5 E=0,5 Zbuduj drzewo kodu Huffmana dla tego alfabetu, oblicz śr. dł. tego kodu, podaj reprezentacje kodu ADA
5) Co to jest szyfr symetryczny, rozszyfruj tekst zaszyfrowany szyfrem cezara którego klucz to <2-6>
MOMNCHYYNUVMNCHY
podaj wadę met. cezara
6) utwórz szyfr poli alfabetyczny dla łacińskiego alfabetu dla klucza OMNI i zaszyfruj NOSCE TE IPSUM