Wprowadzenie do Kompresji

Potrzeba kompresji danych

Urządzenia i usługi cyfrowe generują, przesyłają i przechowują duże ilości danych. Smartfon może przechowywać tysiące zdjęć i filmów w wysokiej rozdzielczości. Serwisy takie jak Netflix, Disney+ i YouTube przesyłają wideo, a strony internetowe łączą tekst, obrazy i kod.

Surowe dane tych treści zajmują dużo miejsca. Minuta nieskompresowanego wideo w wysokiej rozdzielczości może zajmować gigabajty. Przesłanie takiego pliku przez typowe łącze mogłoby trwać godziny, a kilka filmów mogłoby zapełnić dysk. Bez zmniejszenia rozmiaru danych część usług byłaby niepraktyczna lub kosztowna.

Kompresja danych koduje informację za pomocą mniejszej liczby bitów niż reprezentacja początkowa. W kompresji bezstratnej dane można odtworzyć dokładnie, a w stratnej część informacji jest odrzucana. Celem jest ograniczenie miejsca potrzebnego do przechowywania i czasu transmisji. Mniejsze pliki zajmują mniej miejsca na dyskach, serwerach i kartach pamięci oraz szybciej przechodzą przez sieci, od LAN po internet.

Kompresja zmienia reprezentację informacji źródłowej. W trybie stratnym zmienia także część zachowanych danych. Skuteczność zależy od danych. Powtarzalne symbole i przewidywalne próbki dają się kodować krócej, natomiast dane losowe mogą nie ulec skróceniu. Format pliku może łączyć kilka etapów, na przykład modelowanie, transformację i kodowanie entropijne. Dobór metody musi uwzględniać także czas kodowania, wymagania dekodera i dopuszczalną utratę jakości. Kodek opisuje procedurę kodowania, a kontener określa sposób pakowania strumieni i metadanych.

Podstawy teoretyczne: Claude Shannon i teoria informacji

Teoretyczne podstawy kompresji powstały w połowie XX wieku w pracach amerykańskiego matematyka i inżyniera Claude'a E. Shannona. Jego badania dostarczyły modelu matematycznego potrzebnego do opisu granic i możliwości kodowania źródłowego.

W pracy z 1948 roku, "Matematyczna teoria komunikacji," Shannon wprowadził pojęcia używane w analizie informacji:

• Bit jako jednostka informacji: Sformalizował bit jako podstawową jednostkę informacji, reprezentującą odpowiedź na jedno pytanie typu tak/nie.
• Entropia informacyjna: Shannon wprowadził pojęcie entropii do ilościowego określenia średniej informacji w wiadomości ze źródła danych. Entropia opisuje niepewność źródła. Losowy, trudny do przewidzenia strumień ma wysoką entropię, a strumień powtarzalny ma niską entropię.
• Twierdzenie o kodowaniu źródłowym: Twierdzenie określa asymptotyczną granicę bezstratnej kompresji dla długich ciągów symboli z ustalonego modelu źródła. Średnia liczba bitów na symbol nie może zejść poniżej entropii, a stawki powyżej entropii są osiągalne przy odpowiednim kodowaniu.

W późniejszej pracy z 1951 roku, "Przewidywanie i entropia drukowanego języka angielskiego," przeanalizował statystyczne właściwości języka. Wykazał, że litery i ich połączenia mają różne częstości, na przykład litera 'e' jest częsta, a po 'q' w języku angielskim zwykle występuje 'u'. Taka redundancja pozwala kompresować tekst. Identyfikacja i redukcja nadmiarowości jest zasadą wielu technik kompresji.

Model komunikacji Shannona

Shannon zaproponował ogólny model systemu komunikacyjnego, który można odnieść do transmisji skompresowanych danych:

1. Źródło wiadomości: Początek wiadomości (np. osoba mówiąca).
2. Nadajnik (Koder): Przekształca wiadomość w sygnał odpowiedni do transmisji. W naszym kontekście jest to algorytm kompresji.
3. Kanał: Medium, którym sygnał jest przesyłany (np. kabel internetowy, fale radiowe). W kanale mogą pojawić się szumy i zakłócenia, które uszkadzają sygnał.
4. Odbiornik (Dekoder): Przekształca odebrany sygnał z powrotem w wiadomość dla odbiorcy. Jest to algorytm dekompresji.
5. Cel informacji: Ostateczny odbiorca wiadomości (np. osoba słuchająca na drugim końcu linii).

Kompresor i dekompresor realizują kodowanie źródłowe. Ich zadaniem jest zmiana reprezentacji przy zachowaniu wymaganego poziomu informacji. Kodowanie kanałowe pełni inną funkcję. Dodaje kontrolowaną redundancję, aby wykrywać lub korygować błędy transmisji.

Co kompresujemy? Zastosowania dla różnych typów danych

Kompresja obejmuje wiele rodzajów danych cyfrowych i ogranicza rozmiar ich reprezentacji.

• Wideo: Nieskompresowane wideo wymaga dużo miejsca. Kodeki i standardy takie jak H.264/AVC, H.265/HEVC i AV1 umożliwiają strumieniowanie (YouTube, Netflix) oraz wideokonferencje. H.264/AVC i H.265/HEVC są używane także na płytach Blu-ray.
• Obrazy: JPEG służy do kompresji fotografii, zwykle z utratą części informacji. PNG i GIF stosuje się między innymi do grafik, diagramów i obrazów z ostrymi krawędziami.
• Audio i muzyka: Formaty takie jak MP3 i AAC wykorzystują kodowanie percepcyjne do pomijania składowych dźwięku, które mogą być słabo słyszalne. Zmniejsza to rozmiar plików używanych w odtwarzaczach i serwisach streamingowych, takich jak Spotify czy Apple Music.
• Mowa: W telefonii komórkowej (GSM, VoLTE) i aplikacjach VoIP (Skype, Zoom) specjalizowane kodeki mowy kompresują ludzki głos, aby wykorzystać minimalną przepustowość sieci.
• Tekst i archiwa: Pliki tekstowe są małe, lecz duże zbiory mogą korzystać z kompresji. Formaty archiwów, takie jak ZIP, RAR i 7z, kompresują tekst oraz inne pliki, zmniejszając rozmiar pobieranych programów i kopii zapasowych.

W praktyce format określa algorytm oraz sposób przechowywania nagłówków, parametrów i danych pomocniczych. Ten narzut wpływa na wynik dla małych plików. Dla długich strumieni większe znaczenie ma model źródła oraz zależności między kolejnymi symbolami.

Przykładowo Deflate łączy wyszukiwanie powtórzeń metodą LZ77 z kodowaniem Huffmana. ZIP jest kontenerem archiwum, który może przechowywać dane skompresowane Deflate, nagłówki i informacje o plikach.

Zalety i wady kompresji

Kompresja zmniejsza wymagania dotyczące przechowywania i transmisji, lecz wymaga czasu obliczeń oraz może zmieniać dane.

Zalety

• Mniejsze wymagania pamięci masowej: Mniej miejsca na dysku pozwala przechowywać więcej plików na urządzeniach i w chmurze.
• Szybsza transmisja danych: Mniejsze pliki mogą szybciej przechodzić przez sieć, co skraca pobieranie i transmisję strumieniową.
• Wykorzystanie przepustowości: Kompresja pozwala większej liczbie użytkowników lub usług współdzielić połączenie sieciowe.
• Niższe koszty: Mniejsze zapotrzebowanie na pamięć masową i przepustowość może obniżyć koszty centrów danych, dostawców sieci i transferu danych.

Wady

• Narzut obliczeniowy: Kompresja i dekompresja wymagają mocy obliczeniowej. Złożone algorytmy mogą obciążać baterię urządzeń mobilnych i sprzęt używany do kodowania wideo w czasie rzeczywistym.
• Utrata jakości w kompresji stratnej: Wybrane dane są trwale odrzucane. Przy wysokim stopniu kompresji mogą pojawić się artefakty obrazu lub zniekształcenia dźwięku.
• Wrażliwość na błędy: W skompresowanym strumieniu błąd bitu może uszkodzić większy fragment, gdy dekoder wykorzystuje zależności między danymi. Skala zależy od formatu i zastosowanej ochrony. W pliku nieskompresowanym ten sam błąd może dotyczyć tylko jednego piksela lub próbki dźwięku.

Podział: kompresja bezstratna i stratna

Podstawowy podział metod kompresji wynika z odwracalności procesu. Wyróżnia się kompresję bezstratną i stratną.

Wybór między kompresją bezstratną a stratną zależy od zastosowania. Archiwizacja ważnych dokumentów wymaga kompresji bezstratnej. Przy udostępnianiu zdjęć w internecie kompresja stratna może ograniczyć rozmiar pliku do poziomu wygodnego dla transmisji. To podstawowe rozróżnienie w nauce o kompresji danych.