Algorytmy Kompresji Bezstratnej

Podstawy kompresji bezstratnej

Podstawową właściwością kompresji bezstratnej jest zachowanie informacji. Po kompresji i dekompresji wynik ma dokładnie te same bity co plik źródłowy. Dane nie są tracone, zmieniane ani przestawiane. Taka gwarancja jest wymagana dla dokumentów tekstowych, programów komputerowych, zapisów finansowych i danych naukowych, gdy zmiana pojedynczego bitu może zmienić znaczenie lub poprawność danych.

Skoro żadna informacja nie jest odrzucana, kompresja wykorzystuje nadmiarowość (redundancję). Dane często zawierają wzorce, powtórzenia i przewidywalne struktury. Algorytmy bezstratne rozpoznają te właściwości i zapisują je w zwartej reprezentacji. Trzy często spotykane rodziny to metody statystyczne, takie jak kodowanie Huffmana, metody słownikowe, takie jak LZW, oraz schematy wykorzystujące powtórzenia, takie jak kodowanie długości serii.

Kompresja statystyczna

Redundancja statystyczna wynika z różnej częstości symboli w danych. W dużej próbce pewne symbole lub wartości pojawiają się częściej niż inne. Na przykład w języku polskim samogłoski 'a' i 'i' oraz spółgłoska 'z' są częstsze niż 'ź' czy 'ń'. Standard ASCII definiuje znaki za pomocą 7 bitów, choć w praktycznym zapisie znak często zajmuje 8-bitowy bajt. Stała długość takiego zapisu nie uwzględnia częstości symboli. Metody statystyczne wykorzystują tę różnicę do tworzenia zwartych kodów.

Zasada polega na przypisaniu krótszych kodów binarnych częstym symbolom oraz dłuższych kodów symbolom rzadkim. Średnia liczba bitów na symbol może wtedy się zmniejszyć, co daje kompresję.

Kodowanie Huffmana: klasyczna implementacja

Opracowane przez Davida A. Huffmana w 1952 roku, kodowanie Huffmana jest algorytmem kompresji statystycznej. Dla zadanego alfabetu i częstości symboli konstruuje optymalny kod prefiksowy, czyli kod o najmniejszej średniej długości w tej klasie kodów. Przy jednakowych częstościach możliwe są różne, równoważne tablice kodów. Dekoder musi otrzymać tablicę lub sposób jej odtworzenia. Proces można podzielić na kilka kroków.

Pierwszym krokiem jest odczytanie danych źródłowych i zliczenie liczby wystąpień każdego unikalnego symbolu. Pozwala to określić prawdopodobieństwo lub częstotliwość każdego symbolu. Użyjmy prostego przykładowego ciągu: "ala ma kota".

Analizujemy ciąg i zliczamy znaki (włączając spację):

Następnie, na podstawie tych częstotliwości, konstruujemy specjalne drzewo binarne. Proces jest iteracyjny:

• Utwórz węzeł liściasty dla każdego unikalnego symbolu, oznaczając go symbolem i jego częstotliwością.
• Wielokrotnie znajdź dwa węzły w kolekcji o najniższych częstotliwościach.
• Połącz te dwa węzły w nowy wewnętrzny węzeł nadrzędny. Częstotliwość tego nowego węzła nadrzędnego jest sumą częstotliwości jego dwóch potomków.
• Kontynuuj ten proces, aż wszystkie węzły zostaną połączone w jeden korzeń.

W takiej strukturze symbole o małej częstości zwykle leżą głębiej, a symbole częste bliżej korzenia.

Gdy drzewo jest już zbudowane, przypisujemy kody binarne, przechodząc przez nie. Powszechną konwencją jest oznaczanie każdej lewej gałęzi jako '0', a każdej prawej jako '1'. Kod binarny dla dowolnego symbolu to sekwencja zer i jedynek napotkana na ścieżce od korzenia drzewa do liścia tego symbolu.

Oryginalny ciąg "ala ma kota" jest teraz kodowany poprzez zastąpienie każdego znaku jego nowym kodem binarnym. Centralną cechą kodów Huffmana jest właściwość prefiksowa. Oznacza to, że żaden kod nie jest początkiem (prefiksem) żadnego innego kodu. Na przykład '0' jest kodem dla 'a', i żaden inny kod nie zaczyna się od '0'. Ta właściwość pozwala dekoderowi jednoznacznie analizować skompresowany strumień bitów bez specjalnych separatorów między kodami.

Dekoder odczytuje strumień bitów bit po bicie, przechodząc przez drzewo Huffmana (które musi być wysłane wraz z danymi lub być predefiniowane), aż dotrze do liścia. Po osiągnięciu liścia symbol jest wypisywany, a proces powtarza się od korzenia drzewa.

Kompresja słownikowa: znajdowanie powtarzających się fraz

Metody statystyczne skupiają się na częstości pojedynczych symboli. Większa redundancja może dotyczyć całych słów lub powtarzających się fraz. Metody słownikowe wyszukują takie sekwencje i zastępują je krótkimi odwołaniami.

Algorytm LZW (Lempel-Ziv-Welch)

Algorytm LZW jest klasyczną techniką słownikową, stosowaną między innymi w formacie GIF. Podczas kompresji buduje słownik ciągów znaków na podstawie przetwarzanych danych.

Skompresujmy ciąg "TATATAKNIETAK".

1. Inicjalizacja: Słownik zaczyna od wszystkich pojedynczych znaków. Powiedzmy: T=1, A=2, K=3, N=4, I=5, E=6.
2. Krok 1:
   • Kompresor czyta 'T'. Jest w słowniku.
   • Czyta następny znak 'A'. Ciąg "TA" NIE jest w słowniku.
   • Wypisuje kod dla 'T' (czyli 1).
   • Dodaje "TA" do słownika z nowym kodem (np. 7).
   • Bieżącym ciągiem staje się 'A'.
3. Krok 2:
   • Bieżący ciąg to 'A'. Następny znak to 'T'. "AT" NIE jest w słowniku.
   • Wypisuje kod dla 'A' (czyli 2).
   • Dodaje "AT" do słownika (kod 8).
   • Bieżącym ciągiem staje się 'T'.
4. Krok 3:
   • Bieżący ciąg to 'T'. Następny to 'A'. "TA" JEST w słowniku (właśnie go dodaliśmy, kod 7).
   • Kontynuuje. Bieżący ciąg to "TA". Następny znak to 'T'. "TAT" NIE jest w słowniku.
   • Wypisuje kod dla "TA" (czyli 7).
   • Dodaje "TAT" do słownika (kod 9).
   • Bieżącym ciągiem staje się 'T'.
5. Kontynuacja...Proces jest kontynuowany aż do końca ciągu. W tym przebiegu do słownika trafiają także sekwencje "TA" i "TAK".
6. Wynik: Oryginalny ciąg jest kodowany jako sekwencja kodów numerycznych. W tym przykładzie taka sekwencja może zajmować mniej bitów niż zapis pojedynczych znaków, zależnie od szerokości kodów i narzutów formatu. Dekompresor odtwarza ten sam słownik podczas odczytu, jeśli zna początkowy słownik i reguły kodowania. Znajomość tych elementów eliminuje potrzebę przesyłania pełnej listy wpisów.

Ta technika sprawdza się w danych z wieloma powtarzającymi się sekwencjami, takich jak tekst, kod komputerowy i niektóre obrazy. Format GIF wykorzystuje tę metodę do kodowania powtarzalnych wzorów w wierszach obrazu.

Kodowanie długości serii (RLE)

Kodowanie długości serii (Run-Length Encoding) zapisuje powtórzenia tej samej wartości jako parę obejmującą wartość i długość serii. Metoda jest przeznaczona dla danych z długimi, ciągłymi seriami.

Zasada RLE

Zamiast przechowywać każdy symbol w powtarzalnej sekwencji, RLE przechowuje tylko dwie informacje: sam symbol i liczbę jego powtórzeń.

Interaktywny schemat pokazuje, jak RLE zamienia powtarzane piksele lub znaki w pary licznik/wartość oraz jak zmienia się liczba bajtów.

Przykładową pojedynczą linię czarno-białego obrazu reprezentuje sekwencja (B=biały, C=czarny):

Surowa reprezentacja wymagałaby 22 jednostek danych. Używając RLE, możemy to zakodować jako:

Ta reprezentacja zawiera 8 pól (4 liczniki i 4 wartości), więc dla tego przykładu jest krótsza przed uwzględnieniem sposobu zapisu pól w pliku.

Kiedy stosować RLE

RLE jest skuteczne dla danych z dużymi, jednolitymi obszarami. Można je stosować między innymi do:

• Grafik komputerowych, takich jak ikony, logotypy i wykresy.
• Prostych animacji.
• Wyników niektórych procesów analizy obrazu, gdzie regiony są segmentowane według koloru.

Przy krótkich seriach, typowych dla fotografii i danych zaszumionych, RLE może powiększyć zapis zamiast go zmniejszyć. Warianty RLE są używane między innymi w formatach PCX, BMP i TIFF.

Połączenie metod: DEFLATE

Wiele formatów łączy kilka metod bezstratnych. Przykładem jest DEFLATE, używany w formatach archiwów ZIP i GZIP oraz w strumieniu kompresji PNG. DEFLATE łączy algorytm słownikowy LZ77 z kodowaniem Huffmana. LZ77 zastępuje powtarzające się ciągi odwołaniami opisanymi długością i odległością, a pozostałe bajty pozostawia jako literały. Następnie literały oraz odwołania są kodowane za pomocą drzew Huffmana. Połączenie obu etapów pozwala zapisać powtórzenia i różną częstość symboli w jednym strumieniu. DEFLATE dzieli dane na bloki i może używać stałych albo dynamicznych drzew Huffmana. Skuteczność zależy od zawartości danych i ustawień kodera.

Strumień DEFLATE zawiera również nagłówki bloków, a blok dynamiczny opis własnych drzew Huffmana. Te bity metadanych należą do zapisu skompresowanego, dlatego przy krótkim wejściu rozmiar może pozostać podobny albo wzrosnąć po kodowaniu.