„KOMPRESJA DANYCH”

 

Ostatnio siedząc sobie na kibelku robiąc to, co się w kibelkach raczyć robi czytałem fachową literaturę informatyczną. Wertując sobie kartki przypadkiem natknąłem się na tekst poruszający metody kompresji danych oraz ich sposoby. Ponieważ zawsze zastanawiałem się nad tym jak oni to robią przeczytałem go, ale dopiero za drugim razem doszedłem do tego, o co w tym wszystkim chodzi. Postaram się wam w prosty, obrazowy sposób przedstawić proces kompresji danych.

Przyjrzyjmy się ogólnym zasadom kompresji danych. Zapis każdego znaku wymaga 1 bajta, czyli 8 bitów, a zapisanie do pamięci 0 lub 1 wymaga tylko jednego bita. Za przykład posłuży nam prosty ciąg znaków: AABBBCCDDDD. Ciąg ten złożony jest 11 znaków więc do jego zapisania w pamięci potrzebujemy 11*8=88 bitów.. Nic nie stoi nam na przeszkodzie, aby ten sam ciąg zapisać tak: 2A3B2C4D czyli 8*8=64 bity, .co pozwala zaoszczędzić nam 24 bity. Daje nam to w przybliżeniu około 65% stopień kompresji.

Niestety ta metoda kompresji przydatna jest tylko w niektórych typach danych. Przypuśćmy, że mamy następujący ciąg danych: ABDCBBAD. W takim przypadku powyższa metoda nie przyniesie korzyści, a nawet wprost przeciwnie skompresowane dane będą więcej zawierały.. Jak to? Spójrz: Do zapisania tego ciągu potrzeba 8*8=64 bity, a po przekształceniu go na: 1A1B1D1C2B1A1D będziemy potrzebowali 14*8=112 bitów. Jak temu zaradzić? Otóż bardzo często stosuje się tzw. Algorytm Huffmana i jego działanie opiszemy na przykładzie ciągu:: BCBABCACB.

Na samym początku liczymy ilość tych samych znaków w ciągu. Wynik jest następujący:

ZNAK

A

B

C

LICZBA WYSTĄPIEŃ

2

4

3

 

Ustawmy teraz te znaki tak, aby znaki mające najmniejszą liczbę powtórzeń były bliżej środka, a te co mają większą liczbę na bokach:

 

C   A   B

3    2    4

 

Teraz przystępujemy do tworzenia drzewa połączeń sumując najmniejsze liczby połączeń.:

C      A      B               Do otrzymanych sum dodajemy kolejne najmniejsze liczby.

3       2       4

 

 

     5

 


             9

 

Ustawiamy się teraz w węźle 9 i idziemy do góry w kierunku liter C, A, B opisując po drodze przebytą drogę. Jeżeli skręcamy w lewo piszemy 0, a jak w prawo 1. Drogi do naszych znaków są następujące: C=00, A=01, B=1. W ten sposób każdemu z naszych znaków przypisaliśmy ciąg zer i jedynek. Teraz zapisujemy nasz cały ciąg w postaci 0 i1 czyli:

 

B

C

B

A

B

C

A

C

B

1

00

1

01

1

00

01

00

1

Jak już wcześniej wspomniałem do zapisania w pamięci komputera 0 lub 1 potrzeba tylko 1 bita rozmiar po kompresji wynosi 14, a nie 9*8=72 bity !!!. Oczywiście rozmiar takiego archiwum będzie większy, ponieważ będzie trzeba dodać opis drzewa po to, aby możliwe byłoby jego rozpakowanie, ale wynik nadal będzie świetny.

Mam nadzieję, że to zrozumieliście i wiecie, na czym polega kompresja danych. A teraz, na co czekacie? Idźcie pochwalić się waszym kumplom;).

 

7-MAŁY-7 maly7@go2.pl