Wybór rodzaju kompresji danych
Kompresja danych zmniejsza rozmiar plików, ogranicza zajętość nośnika i skraca czas transmisji. Przy wyborze metody trzeba określić wymagania dotyczące rekonstrukcji: czy po dekompresji dane muszą zachować każdy bit, czy dopuszczalne jest przybliżenie? Odpowiedź rozdziela techniki kompresji na dwie kategorie: kompresję bezstratną i stratną. Obie kategorie mogą korzystać z transformacji, modeli statystycznych i kodowania entropijnego, lecz różnią się etapem, w którym ustala się wynik rekonstrukcji.
Różnica między tymi kategoriami wpływa na współczynnik kompresji i wynik dekompresji. Kompresja bezstratna gwarantuje kopię bitową. Kompresja stratna pozwala zmniejszyć plik bardziej, kosztem trwałej zmiany części danych. Właściwy wybór zależy od typu danych, wymaganej dokładności i sposobu użycia pliku. Dla tekstu i kodu różnica pojedynczego znaku może mieć znaczenie semantyczne, a dla obrazu lub dźwięku ocenia się również jakość percepcyjną.
: rekonstrukcja bitowa
Kompresja bezstratna opisuje dane w zwartej postaci, zachowując każdą informację. Dekompresja odtwarza dokładnie tę samą sekwencję bitów, dzięki czemu plik wynikowy jest równoważny plikowi źródłowemu. Odtworzenie obejmuje także kolejność bajtów, znaki sterujące i wartości binarne, jeżeli należą do danych wejściowych.
Zasada podstawowa: wykorzystanie redundancji
Kompresja bezstratna rozpoznaje i zwarto koduje (redundancję). Może ona wynikać z powtarzających się sekwencji albo z różnej częstości symboli. Jeżeli fragment można odtworzyć na podstawie pozostałej części danych, można zastąpić go krótszym opisem. Dekoder musi znać reguły interpretacji takiego opisu, aby odtworzyć oryginalną sekwencję. Algorytmy bezstratne analizują dane pod kątem dwóch głównych typów redundancji:
- Powtarzające się Sekwencje: Dane często zawierają powtarzające się sekwencje znaków lub bajtów. Zamiast przechowywać sekwencję za każdym razem, gdy się pojawia, algorytm bezstratny może przechować ją raz, a następnie użyć krótkiego wskaźnika lub odwołania dla kolejnych wystąpień.
- Przewidywalność Statystyczna:Niektóre symbole lub wartości pojawiają się znacznie częściej niż inne. W języku polskim samogłoska 'a' jest częsta, a 'ź' rzadka. Algorytmy bezstratne wykorzystują tę różnicę, przypisując krótsze kody binarne częstym symbolom i dłuższe kody rzadkim symbolom, co skraca średnią długość kodu wiadomości.
Typowe techniki bezstratne
Kilka kluczowych metod stanowi podstawę większości algorytmów kompresji bezstratnej:
To prosta technika kompresji. Zastępuje długą serię identycznych danych pojedynczą wartością i licznikiem. W obrazie pozioma linia złożona z 200 białych pikseli może być zapisana jako "200 białych pikseli", zamiast przechowywania każdego piksela osobno. Metoda sprawdza się w prostych grafikach, ikonach i diagramach z dużymi obszarami jednolitego koloru. Licznik musi mieć ustalony zakres i sposób zapisu, dlatego krótkie serie mogą nie dawać oszczędności. Dla fotografii, w których długie serie identycznych pikseli są rzadkie, zysk jest mniejszy.
Algorytmy z rodziny Lempel-Ziv są używane w wielu formatach. DEFLATE, który łączy LZ77 z kodowaniem Huffmana, jest stosowany w ZIP, GZIP i PNG. LZW, używany w formatach GIF i TIFF, buduje powtarzających się ciągów znaków lub wzorców bajtów podczas przetwarzania danych. Gdy algorytm napotyka znaną sekwencję, zapisuje krótkie odwołanie do wpisu zamiast całej sekwencji. Odwołanie może opisywać indeks, długość i odległość w strumieniu, zależnie od wariantu algorytmu. W zdaniu "Jakżeż ja się uspokoję, jakżeż ja się uspokoję" fragment "jakżeż ja się uspokoję" występuje dwukrotnie. Algorytm może zapisać ten fragment raz, a przy drugim wystąpieniu użyć wskaźnika.
Metody te analizują częstotliwość symboli w danych i przypisują im kody o zmiennej długości. Najczęstsze symbole otrzymują krótsze kody binarne, a rzadsze symbole dłuższe kody. to klasyczny przykład. Jeśli litera 'A' pojawia się najczęściej, może otrzymać kod '0', podczas gdy rzadka litera 'Ź' może otrzymać '1110101'. Krótsze kody częstych symboli zmniejszają średnią długość całego zapisu. Kodowanie arytmetyczne reprezentuje wiadomość jako przedział w zakresie [0,1) i zapisuje jego położenie słowem bitowym. Średnia liczba bitów przypadająca na symbol może być wtedy ułamkowa.
Zastosowania kompresji bezstratnej
Kompresja bezstratna jest właściwa w zastosowaniach, w których wymagana jest integralność danych. Zmieniony bit może uczynić plik nieużytecznym, zmienić jego znaczenie albo zafałszować wynik odczytu. W takich zastosowaniach sprawdza się również sumy kontrolne i mechanizmy wykrywania błędów, lecz nie zastępują one zachowania danych.
- Tekst i Dokumenty: Dokument prawny, powieść lub prosty e-mail muszą być odtworzone dokładnie. Zmiana jednego znaku mogłaby zmienić znaczenie umowy lub wiadomości.
- Kod Komputerowy i Pliki Wykonywalne: W programie zmiana jednego bitu kodu źródłowego lub pliku wykonywalnego może zmienić działanie programu, spowodować błąd albo wpłynąć na wynik.
- Bazy Danych i Arkusze Kalkulacyjne: Zapisy finansowe, dane naukowe i każda forma ustrukturyzowanych danych wymagają dokładnych wartości. Mały błąd mógłby mieć poważne konsekwencje finansowe lub badawcze.
- Obrazowanie Medyczne i Naukowe: Część zastosowań medycznych dopuszcza specjalistyczne techniki stratne. W archiwizacji zdjęć rentgenowskich, skanów MRI i danych genomowych często wybiera się kompresję bezstratną, aby zachować dane do dalszej analizy.
: przybliżona rekonstrukcja
Kompresja stratna trwale zmienia część danych, aby uzyskać mniejszy plik. W multimediach parametry kodera dobiera się tak, aby różnica była akceptowalna dla odbiorcy i zastosowania. Dekoder odtwarza sygnał na podstawie zachowanych składowych, więc wynik zależy od kodeka, przepływności i treści.
Podstawowa zasada: wykorzystanie ludzkiej percepcji
Kompresja stratna wykorzystuje właściwości ludzkiego wzroku i słuchu. Za pomocą i algorytmy określają, które składowe można uprościć przy wybranym poziomie jakości. Modele są przybliżeniami zależnymi od materiału i nie gwarantują jednakowej oceny dla każdego odbiorcy.
- Dla Obrazów: Ludzkie oko jest bardziej wrażliwe na zmiany jasności (luminancji) niż na zmiany koloru (chrominancji). Algorytmy takie jak JPEG mogą przechowywać kolor w niższej rozdzielczości niż jasność, stosując podpróbkowanie chrominancji. Mogą też ograniczać drobne, wysokoczęstotliwościowe detale, zwłaszcza w złożonych częściach obrazu. Widoczne artefakty zależą od krawędzi, tekstur, kontrastu i poziomu kwantyzacji.
- Dla Dźwięku: Stratne formaty audio, takie jak MP3 i AAC, używają modeli psychoakustycznych do wskazania składników maskowanych. Głośny dźwięk może utrudniać usłyszenie cichszego dźwięku o zbliżonej częstotliwości. Koder może wtedy ograniczyć opis tego składnika, a efekt zależy od materiału i ustawień. Przy niskiej przepływności uproszczenia mogą stać się słyszalne w postaci szumu lub zniekształceń.
Wyjaśnienie powszechnych technik stratnych
Kompresja stratna to zazwyczaj wieloetapowy proces obejmujący transformację, kwantyzację i kodowanie entropijne.
Zamiast pracować bezpośrednio na pikselach, algorytmy takie jak JPEG i MPEG najpierw stosują transformację matematyczną, często . W modelu matematycznym transformacja jest odwracalna i reorganizuje dane. Blok pikseli staje się blokiem współczynników częstotliwości, które opisują składowe nisko- i wysokoczęstotliwościowe. W typowych obrazach duża część energii jest skupiona w kilku współczynnikach niskoczęstotliwościowych.
Kwantyzacja jest etapem, w którym dane są trwale upraszczane. Współczynniki częstotliwości dzieli się przez wartości z tabeli kwantyzacji, a wyniki zaokrągla do liczb całkowitych. W typowych tabelach JPEG większe wartości dotyczą wysokich częstotliwości, więc część tych współczynników przyjmuje zero. Parametr "jakości" kodera zwykle skaluje tabelę kwantyzacji. Wyższa wartość zachowuje więcej szczegółów i tworzy większy plik, a niższa upraszcza więcej współczynników.
Po kwantyzacji wynikowe dane zawierają wiele zer i uproszczonych współczynników. Następnie stosuje się kodowanie bezstratne. W bazowym kodowaniu JPEG używa się kodów Huffmana, natomiast standard JPEG definiuje także warianty z kodowaniem arytmetycznym.
Główne zastosowania kompresji stratnej
Kompresja stratna jest stosowana w multimediach, gdy ograniczenie przepływności lub rozmiaru ma większe znaczenie niż zachowanie każdego bitu. Standardy obrazów, dźwięku i wideo określają własne modele, transformacje, kwantyzację oraz sposoby kodowania strumienia.
- Fotografia Cyfrowa: JPEG jest powszechnym standardem przechowywania zdjęć. Pozwala przechowywać obrazy o wybranej jakości w ułamku rozmiaru nieskompresowanych danych, co ułatwia zapis w aparatach i udostępnianie zdjęć.
- Wideo online i streaming: Serwisy takie jak YouTube, Netflix oraz wideokonferencje wykorzystują kodeki wideo H.264 i H.265 do dostarczania strumieni przy ograniczonej przepływności łącza. Parametry kodowania dobiera się do rozdzielczości, liczby klatek i dostępnego bitrate.
- Muzyka cyfrowa: Format MP3 zmniejsza przepływność zapisu audio, co ułatwia przechowywanie bibliotek muzycznych na urządzeniach przenośnych i przesyłanie plików przez internet. Jakość zależy między innymi od przepływności i charakteru nagrania.
Warto uwzględnić stratę pokoleniową. Ponowne zapisanie pliku w formacie stratnym może odrzucić kolejne dane i zwiększyć degradację. Przy wielokrotnych edycjach wygodnie jest zachować wersję źródłową lub bezstratną, a format stratny utworzyć przy eksporcie. Każde ponowne kodowanie operuje na już przybliżonym wyniku, dlatego artefakty mogą się kumulować.
Porównanie kompresji bezstratnej i stratnej
Poniższa tabela zestawia podstawowe właściwości obu metod. Podane współczynniki są wartościami orientacyjnymi i zależą od danych, kodeka oraz ustawień. Współczynnik 2:1 oznacza dwukrotnie mniejszy zapis względem danych wejściowych, przy tej samej definicji rozmiaru. Przy krótkich plikach na zmierzony współczynnik wpływają również nagłówki i metadane. Słowniki, dane modelu oraz dopełnienie bitowe mogą zwiększać końcowy zapis.
| Cecha | Kompresja Bezstratna | Kompresja Stratna |
|---|---|---|
| Integralność Danych | Idealna rekonstrukcja bit po bicie. Oryginał = Zdekompresowany. | Niedoskonała rekonstrukcja. Oryginał ≈ Zdekompresowany. |
| Odwracalność | Proces w pełni odwracalny. | Proces nieodwracalny. Odrzuconych danych nie można odzyskać. |
| Współczynnik Kompresji | Umiarkowany (np. 2:1 do 3:1 dla części danych). Zależny od zawartości danych. | Wysoki lub większy (np. 10:1 do 100:1+). Regulowany przez kodek i jego parametry. |
| Kluczowa Zasada | Eliminuje nadmiarowość statystyczną. | Eliminuje informacje nieistotne percepcyjnie. |
| Główne Zastosowania | Tekst, programy, archiwa, bazy danych, dane medyczne. | Obrazy, audio, wideo (multimedia). |