„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;).