Kompresja bezstratna
Kompresja bezstratna to metoda redukcji rozmiaru danych, która umożliwia pełne odtworzenie oryginalnej informacji. Kluczowym aspektem tej metody jest twierdzenie o zliczaniu, które wskazuje, że każda funkcja kompresji bezstratnej, która zmniejsza rozmiar informacji, musi przynajmniej o 1 bit wydłużyć niektóre dane, chyba że nie kompresuje żadnych informacji.
Twierdzenie o zliczaniu
Nie można stworzyć funkcji, która odwracalnie kompresuje wszelkie informacje, nie wydłużając przynajmniej jednej z nich. Dowód polega na wykazaniu, że gdyby funkcja ta istniała, prowadziłoby to do sprzeczności z ograniczoną liczbą możliwych wiadomości o danej długości.
Algorytmy kompresji bezstratnej
Algorytmy te efektywnie kompresują typowe dane, które zawierają dużą redundancję. Jednak niektóre typy danych są trudne lub niemożliwe do skompresowania, takie jak:
- Strumienie liczb losowych – niemożliwe do skompresowania.
- Strumienie liczb pseudolosowych – trudne do skompresowania.
- Dane już skompresowane – zazwyczaj trudne do dalszej kompresji.
Metody kompresji bezstratnej dzieli się na dwie główne kategorie:
- Metody słownikowe: Wyszukują konkretne ciągi znaków i zastępują je krótszymi reprezentacjami.
- Metody statystyczne: Używają różnych długości kodów w zależności od częstości występowania symboli, uwzględniając kontekst.
Popularne metody kompresji
- Kodowanie Shannona, Shannona-Fano, Huffmana, arytmetyczne.
- LZ77, LZ78 i ich pochodne (LZSS, LZP, LZW, LZMW).
- RLE (Run-Length Encoding).
- PPM (Prediction by Partial Matching).
- Transformata Burrowsa-Wheelera, Move To Front.
