Na początku mej pracy pragnę wyjaśnić samo pojęcie kompresja danych oraz jej genezę.
Termin "kompresja danych" pojawił się ponad pół wieku temu wraz z rozwojem nowej gałęzi matematyki - teorii informacji. Badania i doświadczenia prowadzone kilkadziesiąt lat przez wielu naukowców doprowadziły do ustalenia i rozwinięcia wielu standardów. Kompresję danych stosuje się nie tylko w komputerach, ale także w wielu urządzeniach elektronicznych, na przykład telewizji HDTV, cyfrowym wideo czy PhotoDisc. Technologia kompresji danych coraz szerzej wkracza w nasze życie, dlatego warto ją bliżej poznać.
Za twórcę i jednego z pierwszych "wynalazców" kompresji uważa się Claude'a Shannona, który pracował nad komunikacją, informacją oraz sposobami przesyłania i przechowywania danych. Kompresja danych jest technologią, która pozwala na zmniejszenie ich objętości, bez uszczerbku dla zawartej w nich informacji. Możliwe to jest, w uproszczeniu, poprzez odnalezienie powtarzających się znaków lub ich ciągów i odpowiednie ich zakodowanie pozwalające w razie potrzeby odtworzyć poprzednią zawartość.
Kolejnym krokiem jest próba klasyfikacji kompresji, a mianowicie:
Są dwa rodzaje kompresji:
Ilościowa (bezstratna);
Jakościowa.
W pierwszym przypadku wielokrotna kompresja i dekompresja nie powodują utraty żadnej części informacji. Dane są po prostu wiernie zakodowywane i rozkodowywane. Zwykle wykorzystuje się w tym celu częstsze występowanie pewnych kodów w całym lub części pliku. Kody te zapisuje się jako ciągi bitowe o długości odwrotnie proporcjonalnej do częstości występowania.
Kompresję ilościową można realizować w sposób:
Statycznie - dane są przeglądane w całości, po czym w całości są kompresowane lub dekompresowane;
Dynamicznie - dane w miarę nadchodzenia kolejnych bajtów (a raczej bitów) są kompresowane lub dekompresowane.
Kompresja realizowana dynamicznie może mieć gorsze parametry od statycznej, jednak z drugiej strony, może lepiej dostrajać się do fragmentów o innym charakterze danych. Dla przykładu załóżmy, że mamy zbiór danych, w którym częstość występowania każdego kodu jest jednakowa. Jednocześnie może być tak, że zbiór jest posortowany, a poszczególne kody występują wielokrotnie. Wystarczy podzielić zbiór, a okaże się, że otrzymane fragmenty są łatwo kompresowalne. Z tego powodu kompresja dynamiczna jest stosowana znacznie częściej. Kompresja drugiego rodzaju, jakościowa, służy temu samemu celowi, ale dopuszcza zmianę danych. Algorytmy należące do tej grupy pozwalają sobie na utratę szczegółów w zamian za duży stopień upakowania. Takie zjawisko jest dopuszczalne na przykład przy zapisie obrazów lub dźwięków.
Jeśli chodzi o przykłady kompresji ilościowej, najlepszym przykładem będą tutaj wszelkiego rodzaju archiwizatory, programy kompresji aktywnej i kompresji na bieżąco. Powodują one zazwyczaj stworzenie jednego charakterystycznego, skompresowanego pliku, w którym "zawartych" jest wiele plików (np. wykonywalnych, z różnymi danymi). Plik ten zajmuje mniej miejsca niż suma plików przed kompresją.
Istnieje wiele metod kompresji używanych przez programy kompresujące w rodzaju ARJ, ZIP, Stacker, LHARC, PKARC, RAR, itp. Potrafią one w zależności od parametrów pliku wybrać odpowiednią metodę kompresji, głównie kierując się rozmiarem pliku. Stosują takie metody kompresji jak algorytm Huffmana, LZW 77, imploding itp.
Jeśli zaś chodzi o kompresję jakościową, w przypadku pewnych rodzajów informacji, (jeśli zna się ich charakter) można samodzielnie dobrać sposób ich zapisu. Często można pozwolić sobie przy tym na pewne zniekształcenie danych. Takie sposoby są stosowane przy zapisie obrazu, zapisie próbek sygnałów akustycznych (sampli) i innych. Metodę taką zastosowano na przykład w formacie zapisu obrazów JPEG. Podobnie postąpiono w magnetofonie cyfrowym DCC. Konstruktorom udało się skompresować zawartość dźwiękową aż pięciokrotnie, bez zauważalnej utraty jakości słyszalnej. Umożliwiło to zrezygnować z kłopotliwej głowicy wirującej, która jest w magnetofonach RDAT. Rozwiązanie to jest sprzętowe. Dzięki skonstruowaniu odpowiedniego układu scalonego uzyskano wymaganą szybkość pracy.
Innym przykładem kompresji jakościowej jest kompresja z wykorzystaniem teorii fraktali. Już od dawna wiadomo, że za pomocą odpowiednio dobranego wzoru matematycznego można wyrysować skomplikowane obiekty na ekranie, na przykład zbiór Mandelbrota. Generalnie każdy zbiór informacji może zostać zapisany w ten sposób, ale nie można tego zrobić na tyle szybko, by nadawało się to do użycia on line ("w locie"). Jak na razie, nie dopracowano się praktycznie stosowanej metody? Pojawiające się obecnie publikacje posługują się kompresją z utratą jakości. Paradoksalnie, zastosowanie kompresji fraktalnej do obrazów graficznych daje zwykle ich wyostrzenie. Świadczy to jednak o zniekształceniu danych i stąd matematyczna utrata jakości.
Współczynnik kompresji
Współczynnik kompresji jest miarą stosunku rozmiaru pliku pierwotnego do jego rozmiaru po kompresji.
Jeśli plik po kompresji jest dokładnie dwa razy mniejszy od pierwotnego, to współczynnik kompresji wynosi 2:1. Oznacza to innymi słowy, że miejsce potrzebne na jednostkę danych na dysku pomieści po kompresji dwie jednostki danych. Większy współczynnik (np. 3:1) oznacza silniejszą kompresję, a mniejszy (np. 1,5:1) słabszą.
Przyjmuje się, że programy do kompresji całych dysków, na przykład Stacker czy DoubleSpace, mają współczynnik kompresji 2:1, co jest ogólnym średnim rezultatem dla stosowanego algorytmu. Dlatego też dystrybutorzy tych pakietów reklamują je jako "podwajające wielkość dysku". W praktyce niektóre pliki kompresują się lepiej, a niektóre gorzej niż inne. Uzyskany współczynnik może być większy lub mniejszy niż średni 2:1.
Dane na dysku są kompresowane poprzez usunięcie nadmiarowych sekwencji bajtów (metoda jest opisana bardziej szczegółowo dalej). Niektóre pliki są bardziej nadmiarowe. Mogą zdarzyć się także pliki w ogóle bez nadmiaru. Pliki z wieloma powtarzającymi się sekwencjami bajtów, na przykład pliki grafiki bitowej produkowane przez programy graficzne takie jak PaintBrush, kompresują się o wiele efektywniej niż pliki bez takich sekwencji, przykładowo pliki zawierające programy. Nawet, jeśli pliki kompresuje się nadzwyczaj dobrze, maksymalnym współczynnikiem kompresji, zarówno pakietu DoubleSpace, jak i pakietu Stacker, jest 16:1.
Ten limit 16:1 jest w istocie umowny. Oba wyżej wymienione pakiety kompresują i dekompresują pliki "w locie", co oznacza, że operacje de/kompresji zachodzą w czasie odczytu/zapisu pliku z/na dysk. Żadna dodatkowa akcja ze strony czy to użytkownika, czy aplikacji nie jest potrzebna. Aby taki system działał bez nadmiernych opóźnień, de/kompresja musi zachodzić bardzo szybko. Konstruktorzy pakietów poszli, więc na kompromis i nie starali się znaleźć największego możliwego współczynnika kompresji, aby nie wydłużać nadmiernie czasu działania procedur.
Interesującą techniką kompresji sygnału - niezależnie od tego czy to będą dane graficzne, czy dźwiękowe - jest kodowanie pasmowe. Jego połączenie z kwantyzacją nieliniową oraz kodowaniem bezstratnym, na przykład z kodowaniem Huffmana, jest obecnie jedną z najefektywniejszych technik kompresji sygnału. Kompresja sygnału jest potrzebna coraz częściej, choćby ze względu na ciągle zwiększające się wymagania jakościowe - mimo relatywnego spadku cen nośników informacji (twarde dyski, CD) oraz urządzeń komputerowych czy muzycznych. Jeszcze nie tak dawno wydruki komputerowe, prosta grafika, muzyka na kasetach kompaktowych - czyli na kasetach magnetofonowych wynalezionych przez Phillipsa - cieszyły i dawały radość posiadania. Obecnie niektóre gry komputerowe przypominają filmy fabularne, a nagrania muzyczne wypuszcza się na płytach kompaktowych o jakości 20-BIT, firma Sony wypuściła Mini Disc, a Phillips magnetofon cyfrowy DCC do zapisu muzyki. Przystawki MPEG umożliwiają oglądanie filmów i widowisk na ekranie komputera. Jednak wszystkie te zabawki karmią się megabajtami danych, które coraz trudniej "upchać". Tak, więc kompresja informacji jest w tych warunkach niezbędna. Charakterystyczną cechą danych tego typu, czyli danych wizualnych i dźwiękowych, jest (w odróżnieniu na przykład od tekstów czy programów) możliwość zastosowania kompresji ze stratą. Nie sposób skompresować w ten sposób na przykład programu komputerowego, bo strata nawet jednego jedynego bitu może poważnie zmienić działanie całego programu.
Cechą wszystkich zmysłów człowieka jest detekcja zmian oraz uśrednianie dopływającej informacji. Przenosząc te właściwości na inny grunt można przechowywany w jakimś nośniku sygnał zakodować tak, aby zachowane zostały tylko najważniejsze informacje, podczas gdy mniej ważne zostaną pominięte. Systemów kompresji tak działających jest obecnie bardzo dużo. Wycinają one dane, których i tak nie jesteśmy w stanie zauważyć. Jednak mogą też wyciąć o wiele więcej - na przykład, gdy system ma małą przepustowość. Co prawda wówczas różnica pomiędzy oryginałem nie skompresowanym a kopią skompresowaną i zdekompresowaną będzie wyraźna, ale i tak (przy tej samej ilości informacji) o cały rząd wielkości mniejsza niż bez kompresji przesyłanego obrazka. Na przykład przy 300 kB oryginału i 10 kB, które mamy do dyspozycji na przechowanie, korzystając z odpowiedniej metody kompresji obrazek będzie lepiej wyglądał po skompresowaniu z oryginału (np. system JPEG) i późniejszym jego zdekompresowaniu niż gdyby został przesłany w postaci 10 kB (duży raster, mało kolorów). To samo dotyczy muzyki. Dźwięk skompresowany metodami stratnymi do wielkości 10 kB i w czasie trwania 5 sekund będzie o całe niebo lepiej brzmiał niż analogiczny dźwięk zużywający owe 10 kB, ale nie poddany kompresji. Można to łatwo sprawdzić, przykładowo 8 bitów dokładności amplitudowej i pliku 10 kB w ciągu 5 sekund daje tradycyjnie (bez kompresji) częstotliwość próbkowania 2000 Hz, czyli jakość telefoniczna. Natomiast przykładowe kodowanie typu PASC, używane w magnetofonach DCC Philipsa, stosuje kompresję średnio 6:1, znaczy to, że w pliku o wielkości 10 kB możemy "upchać" tym razem dźwięk pięciosekundowy z próbkowaniem 12 kHz albo z poprzednią częstotliwością zarejestrować sygnał o długości pół minuty (przydatne przy zapisywaniu rozmów telefonicznych w komputerze).
Metody kompresji danych są istotne, na przykład dla bazy danych. Dane są zwykle obszerne i jeśli można znaleźć metodę ich upakowania warto to uczynić. Metody ogólnie stosowane, takie jak na przykład kompresja Huffmana, dają dla prawie wszystkich rodzajów danych kompresję rzędu 2:1, nie zapewniają jednak swobodnego dostępu do tych danych, co utrudnia ich stosowanie. Odpowiednia kompresja może przyczynić się do szybszego przesyłania danych. Urządzenia dyskowe i transmisyjne nie są tak szybkie jak pamięć RAM komputera. Jeżeli część operacji wykonamy w pamięci, to mimo ich większej złożoności, możemy zaoszczędzić trochę czasu. Przykładem może być dokonanie kompresji na komputerze przed transmisją, przesłanie ich w takiej postaci, po czym dekompresja w komputerze odbierającym. Modemy realizujące taką kompresję są powszechnie stosowane. Paradoks jednak w tym, że większość przesyłanych danych jest już skompresowana i mechanizm ten nie przynosi żadnego rezultatu.
Programy kompresujące oraz charakterystyka ich pracy
Pierwsze, często jeszcze nieświadome zetknięcie użytkowników z plikami skompresowanymi, następuje najczęściej podczas instalacji licencjonowanego oprogramowania. Trudno na przykład wyobrazić sobie Corela 4.0 (nie mówię o 5.0) w wersji nieskompresowanej, który i tak zajmuje 12 dyskietek 1.44 MB. Na Corelu jednak oprogramowanie przecież nie kończy się. Programy dla DOS-u także mają pokaźne rozmiary, a przecież nie każdego stać na dysk twardy o pojemności 2 GB. Co robić, gdy zaczyna brakować miejsca? Kasować nie wszystko można. Tutaj zaczyna się pole do popisu dla programów kompresujących.
Programy kompresji danych stały się nieodłącznymi towarzyszami wszystkich użytkowników komputerów. Korzysta się z nich na co dzień; nie tylko w celu zmniejszenia powierzchni dysku zajmowanej przez dane, ale również w celu zintegrowania w jednym dużym pliku kilku mniejszych - co ułatwia zarządzanie danymi, ich przesyłanie za pomocą modemu, sporządzanie kopii zapasowej itp.
Upraszczając, kompresja wszelkich danych polega na wykorzystywaniu uporządkowanych sekwencji (bitów lub bajtów) w pliku i ich zastępowaniu w archiwum krótszymi. I tak na przykład plik składający się z 255 jedynek może zostać skompresowany do objętości trzech bajtów: bajtu oznaczającego skompresowaną sekwencję, kodu znaku skompresowanego i liczbę znaków skompresowanych - w tym przypadku 255. Jest to rzecz jasna tylko teoria, bowiem każdy program kompresujący dodaje własne nagłówki, nazwy pakowanych plików i inne dodatkowe informacje, które w archiwach normalnej wielkości zajmują niewielki procent, tu zaś mogą mieć duży wpływ na efekt końcowy. W każdym przypadku programy kompresujące wczytują dane o dużej objętości i mają je zapisać na dysku w postaci pliku o możliwie małej objętości.
Podstawowe kategorie programów kompresujących
Programy archiwizujące (typu PKZIP czy ARJ) - dokonują kompresji plików danych lub programów i następnie zapisują je po przetworzeniu w jednym pliku o specjalnym formacie, którego odtworzenie wymaga ponownego uruchomienia programu archiwizującego.
Programy kompresji aktywnej (typu LZEXE czy PKLITE) - poddają kompresji jedynie pliki z zapisanymi programami (*.exe), lecz w taki sposób, że mimo zmniejszenia objętości nadają się one do dalszego wykorzystywania bez konieczności uprzedniej dekompresji specjalnymi programami. Jest to możliwe dzięki temu, że w tak spreparowanym pliku wykonywalnym znajduje się procedura automatycznie dokonująca dekompresji do pamięci operacyjnej podczas uruchamiania skompresowanego pliku.
Programy kompresji na bieżąco (on line), które dokonują kompresji wszystkich danych znajdujących się na dysku twardym lub dyskietce i zapisują je do jednego pliku. Dane tak spreparowane są udostępniane poprzez specjalny rezydujący w pamięci program obsługi, który automatycznie kompresuje lub dekompresuje dane przy każdej próbie odczytu bądź zapisu na dysk.
Dzięki programom kompresującym na twardym dysku lub dyskietce można zmieścić więcej danych i programów. Pliki, których nie używamy na co dzień, mogą być (po wcześniejszym skompresowaniu) z powodzeniem składowane na dysku. Pozwoli nam to zaoszczędzić sporo miejsca.
Jeśli dane mają być przesyłane za pośrednictwem modemu, ich kompresja jest wręcz nieodzowna. Im mniejsza ilość przesyłanych danych, tym krótsza, a w związku z tym tańsza, jest transmisja. Zmniejsza się ponadto niebezpieczeństwo przerwania połączenia w czasie transmisji, pociągające za sobą konieczność rozpoczęcia całego procesu od nowa. Kompresja przyczynia się również do zwiększenia porządku na twardym dysku. Pliki tego samego rodzaju (na przykład tekstowe) mogą być umieszczone w jednym, skompresowanym zbiorze.
Archiwizacja ułatwia także manipulację plikami. Oczywiste jest, że jeden plik stworzony przy pomocy pakera kopiuje się znacznie szybciej niż sto oddzielnych plików, które znajdują się w tym archiwum.
Kompresja fraktalna
Tradycyjne metody kompresji danych graficznych powodują jedynie kilkukrotną (od 2 do 5 razy) redukcję ich rozmiarów. Wśród profesjonalistów prawdziwą furorę robi nowy sposób kodowania obrazów - tzw. kompresja fraktalna. Dzięki niej można osiągnąć kompresję rzędu 0,0001 stopni kompresji (przy założeniu utraty dokładności informacji).
Pojęcie fraktala pojawiło się w latach siedemdziesiątych. Wprowadził je Benoit Mandelbrot (urodzony w 1924 roku w Warszawie) dla opisu klasy zbiorów, które uzyskał za pomocą komputera podczas badań wahań akcji giełdowych. Nazwę "fraktal" (ang. fractal) utworzono na bazie łacińskiego słowa "fractus" - złamany. Tłumacząc, czym jest fraktal, zazwyczaj daje się przykład liścia paproci albo płatka śniegu. Za tym pojęciem kryje się bowiem twór "podobny do samego siebie", to znaczy taki, że przy jego dowolnym powiększeniu otrzymuje się zawsze podobny obraz.
Listki składowe paproci składają się z pomniejszonych liści, które podobne są do całości. Podobieństwo to opisuje się w formie przekształcenia odwzorowującego cały fraktal na jego część. Fragmenty chmur są podobne do całych obłoków, a gałęzie podobne są do drzew.
Obraz w postaci fraktalnej zajmuje o wiele mniej miejsca niż ten sam rysunek zapisany piksel po pikselu. Poza tym daje się on dowolnie skalować (tak jak grafika wektorowa).
Dekompresja danych zakodowanych fraktalnie jest bardzo prosta. O wiele trudniejsza jest natomiast kompresja. Automatyczne i efektywne wydzielanie z obrazu figur nadających się do zastąpienia fraktalem wydaje się wciąż zadaniem bardzo skomplikowanym.
Mimo "młodego wieku" fraktali i związanego z nimi podejścia do kompresji, na świecie osiągnięto już bardzo zachęcające wyniki w tej dziedzinie. 10000-krotna redukcja danych graficznych jest imponująca. Uzyskanie tak efektywnej kompresji umożliwia z jednej strony przechowywanie większej ilości danych w pamięci komputerów, z drugiej strony, ułatwia ich przesyłanie na odległość. Przewaga tej metody w stosunku do innych polega na osiąganiu wysokiego współczynnika kompresji przy jednoczesnej dobrej jakości obrazu.
Format wykorzystujący kompresję fraktalami to IFS (Iterative Function Systems) firmy Iterative Systems. Sam algorytm oferowany jest za ciężkie pieniądze przez wymienioną wyżej firmę, a z grubsza polega on na podziale obrazu na części i dopasowywaniu do nich funkcji IFS w taki sposób, aby różnica pomiędzy oryginałem a odtworzonym obrazem była jak najmniejsza. Rezultaty są jeszcze lepsze niż w plikach JPEG, ale kompresja trwa dużo dłużej. Dekompresja jest błyskawiczna, a obraz można odtworzyć w dowolnej rozdzielczości bez zauważalnych efektów pikselizacji.Ideą kompresji fraktalnej jest znajdowanie podobieństwa pomiędzy poszczególnymi fragmentami obrazu. Aby wykryć jakiekolwiek podobieństwo, należy podzielić obraz na rozłączne wycinki, tzw. płatki, pokrywające całą jego powierzchnię. Dla każdego wydzielonego płatka poszukuje się transformacji innego fragmentu obrazu, która da w wyniku taki płatek. Gdy znajdziemy transformacje dla wszystkich płatków, będziemy dysponować zbiorem reguł dla całego obrazka, który można wydajnie zapisać.
Samopodobieństwo fragmentów obrazu opisywane jest systemami funkcji iteracyjnych. Systemy takie składają się z pewnej liczby transformacji reprezentujących obrót, przesunięcie i skalowanie. Transformacje są regułami na tworzenie obrazu i wymagają niewielkiej ilości pamięci na ich przechowanie. Przechowywanie reguł tworzenia obrazu zamiast bezwzględnych wartości pikseli pozwala na osiągnięcie wysokiej stopy kompresji.
Na koniec, po charakterystyce zagadnienia kryjącego się pod pojęciem Kompresja Danych pragnę ukazać kilka praktycznych metod kompresji danych.
MH (ang. Modified Huffman) - metoda standardowa ITU-T G3. Linie poziome kompresowane są przez łączenie takich samych punktów w jeden sygnał (np. trzy czarne punkty = jeden sygnał, dwa białe punkty = inny sygnał).
MR (ang. Modified READ) - metoda dla opcji G3 (READ = ang. Relative Element Address Designate coding). W tym systemie co drugą lub co czwartą linię poziomą poddaje się kompresji metodą MH. Każda z pozostałych linii porównywana jest z poprzednią i konwertowane są tylko te ciągi punktów, które są różne.
MMR (ang. Modified MR) - metoda dla opcji G3, podstawowa metoda G3. Za pierwszą linię przyjmuje się linię całkowicie białą. W kolejnych liniach konwersji podlegają tylko punkty, które różnią się od linii poprzedniej. Metoda ta jest znacznie sprawniejsza niż kodowanie metodą MH lub MR, ale jest bardziej podatna na błędy. Aby temu zaradzić, stosuje się zwykle różne formy korekcji błędów.
Prędkość modemu MMR (sek.) MR (sek.) MH (sek.)
28 800 bps (V.34) (3) . .
14 400 bps (V.17) 6 13 20
9 600 bps (V.29) 10 20 30
4 800 bps (V.27ter) 20 40 60
Powyższe dane przedstawiają standardowe czasy transmisji, mierzone przy przesyłaniu pojedynczej strony A4, zeskanowanej w trybie standardowym (bez protokołów uzgodnienia). Rzeczywisty czas transmisji zależy jednak od rozdzielczości skanowania i innych czynników.
JBIG (ang. Join Bi-level Image Experts Group) - metoda opcji G3. Jest to międzynarodowy standard dwupoziomowego kodowania obrazy. Najpierw transmitowany jest z grubsza obraz całego dokumentu. A potem przesyłane są dodatkowe informacje uzupełniające obraz. Metoda ta jest znacznie lepsza od konwencjonalnych metod, szczególnie przy kompresji obrazów z półtonami. W porównaniu z kodowaniem metodą MMR, metoda JBIG może skompresować czarno-biały dokument o gęstości większej o 1,1 do 1,5 raza, a dokument z półtonami o gęstości 2 do 30 razy większej.
JPEG (ang. Joint Photographic Experts Group) - metoda opcji G3. Standardowa metoda kodowania dla obrazów barwnych, mająca zastosowanie przy reprodukcji fotografii lub ilustracji kolorowych. Organizacja i identycznej nazwie, JPEG, jest kooperantem ISO i ITU-T, który pracuje nad standaryzacją metod kodowania nieruchomego obrazu barwnego.
Praca pochodzi z serwisu www.e-sciagi.pl
1