ALG)4

294 Rozdział 13. Kodowanie i kompresja danych

jednak w przypadku zwykłych tekstów, zawierających komunikaty w języku polskim, musimy koniecznie używać kosztownego kodowania ^-bitowego? Język polski nie zawiera przecież aż 2^=256 znaków! Załóżmy, że dla typowych tekstów ograniczymy się do następującego alfabetu:

'A'... ‘Z’    =    26 znaków

‘ '(spacja) , ; . -    =    5 znaków

Ą, Ć, Ę, L, Ń, Ó, Ź, Ż    =    8 znaków

RAZEM:    39 znaków.

Do zakodowania 39 znaków w zupełności wystarczy 6 bitów (A=00 0(100, B=O0 000/, C- ...), czyli komunikat „kurczy” nam się z 400 do 300 bitów³!

Łatwo zauważyć, że znajomość przesyłanego alfabetu pozwala, przy umiejętnym doborze kodu, znacznie zmniejszyć długość przesyłanego komunikatu, bez utraty informacji w nim zawartej. Istnieje mnogość kodów, bardziej skomplikowanych niż prymitywne kody „tabelkowe” typu ASCII, nie jest jednakże moim zamiarem zamienienie tego rozdziału w mini-podręcznik teorii kodowania i informacji. Bez wnikania w szczegóły, warto być może wspomnieć, że istnieją dwie podstawowe grupy kodów: równomierne (o stałej długości słow'a kodowego) i nierównomierne (o zmiennej długości słowa kodowego). W obu przypadkach można do zakodowanej informacji dołączyć pewne dodatkowe bity kontrolne, ułatwiające odtworzenie informacji, nawet w przypadku częściowego uszkodzenia przesyłanego komunikatu (uzyskujemy wówczas tzw. kody nadmiarowe). Nie chciałbym jednak zbyt szeroko omawiać tych zagadnień, gdyż są one związane bardziej z transmisją sygnałów (fizyczna transmisja danych; sens przesyłanej informacji nie jest istotny), niż z informatyką w czystej postaci (aplikacje użytkownika; sens przesyłanej informacji ma kluczowe znaczenie).

W dalszej części rozdziału omówimy szczegółowo popularny system kodowania z tzw. kluczem publicznym oraz kod Huffmana, który jest znakomitym i nieskomplikowanym przykładem uniwersalnego algorytmu kompresji danych.

13.1.Kodowanie danych i arytmetyka dużych liczb

Kodowanie danych (lub jak kto woli: szyfrowanie wiadomości) ma miejsce wszędzie tam, gdzie z pewnych względów chcemy utajnić zawartość przesyłanej informacji, tak aby jej treść nie dostała się w niepowołane ręce i nie mogła być wykorzystana w niemiłych nam celach. Może ono dotyczyć prywatnej korespon-

Zyskujcmy 25 % pierwotnej długości tekstu!