Kompresja bezstratna

Algorytmy bezstratnej kompresji danych nie mogą zagwarantować kompresji dla wszystkich zbiorów danych wejściowych. Innymi słowy, dla każdego algorytmu bezstratnej kompresji danych, będzie istniał zbiór danych wejściowych, który nie zmniejszy się podczas przetwarzania przez algorytm, a dla każdego algorytmu bezstratnej kompresji danych, który zmniejszy co najmniej jeden plik, będzie istniał co najmniej jeden plik, który powiększy. Można to łatwo udowodnić za pomocą elementarnej matematyki, używając argumentu liczenia, jak poniżej:

• Załóżmy, że każdy plik jest reprezentowany jako ciąg bitów o dowolnej długości.
• Załóżmy, że istnieje algorytm kompresji, który przekształca każdy plik w plik wyjściowy, który nie jest dłuższy niż oryginalny plik, i że co najmniej jeden plik zostanie skompresowany do pliku wyjściowego, który jest krótszy niż oryginalny plik.
• Niech M będzie najmniejszą liczbą taką, że istnieje plik F o długości M bitów, który kompresuje się do czegoś krótszego. Niech N będzie długością (w bitach) skompresowanej wersji pliku F.
• Ponieważ N<M, każdy plik o długości N zachowuje swój rozmiar podczas kompresji. Możliwych jest 2N takich plików. Razem z F, daje to 2N+1 plików, które wszystkie kompresują się do jednego z 2N plików o długości N.
• Ale 2N jest mniejsze niż 2N+1, więc zgodnie z zasadą gołębiej dziury musi istnieć jakiś plik o długości N, który jest jednocześnie wyjściem funkcji kompresji na dwóch różnych wejściach. Ten plik nie może być zdekompresowany w sposób wiarygodny (który z dwóch oryginałów powinien dać wynik?), co zaprzecza założeniu, że algorytm był bezstratny.
• Musimy zatem stwierdzić, że nasza pierwotna hipoteza (że funkcja kompresji nie wydłuża żadnego pliku) jest z konieczności nieprawdziwa.

Każdy algorytm bezstratnej kompresji, który skraca niektóre pliki, musi z konieczności wydłużać niektóre pliki, ale nie jest konieczne, aby te pliki stały się bardzo długie. Większość praktycznych algorytmów kompresji zapewnia możliwość „ucieczki”, która może wyłączyć normalne kodowanie dla plików, które stałyby się dłuższe przez zakodowanie. W teorii, tylko jeden dodatkowy bit jest wymagany by powiedzieć dekoderowi że normalne kodowanie zostało wyłączone dla całego wejścia; jednak większość algorytmów kodujących używa do tego celu co najmniej jednego pełnego bajtu (a zwykle więcej niż jednego). Na przykład, pliki skompresowane deflate nigdy nie muszą rosnąć o więcej niż 5 bajtów na 65 535 bajtów danych wejściowych.

W rzeczywistości, jeśli rozważamy pliki o długości N, jeśli wszystkie pliki byłyby równie prawdopodobne, to dla każdej bezstratnej kompresji, która zmniejsza rozmiar jakiegoś pliku, oczekiwana długość skompresowanego pliku (uśredniona dla wszystkich możliwych plików o długości N) musi być koniecznie większa niż N. Więc jeśli nie wiemy nic o właściwościach danych, które kompresujemy, równie dobrze możemy ich w ogóle nie kompresować. Algorytm kompresji bezstratnej jest użyteczny tylko wtedy, gdy istnieje większe prawdopodobieństwo, że będziemy kompresować pewne typy plików niż inne; wtedy algorytm może być zaprojektowany tak, by kompresować te typy danych lepiej.

Więc główną lekcją płynącą z tego argumentu nie jest to, że ryzykujemy duże straty, ale po prostu to, że nie zawsze możemy wygrać. Wybór algorytmu zawsze oznacza implicite wybór podzbioru wszystkich plików, które staną się użytecznie krótsze. Jest to teoretyczny powód, dla którego musimy mieć różne algorytmy kompresji dla różnych rodzajów plików: nie może być jednego algorytmu, który jest dobry dla wszystkich rodzajów danych.

„Sztuczka”, która pozwala algorytmom kompresji bezstratnej, używanym na typach danych, dla których zostały zaprojektowane, konsekwentnie kompresować takie pliki do krótszej formy, polega na tym, że pliki, na które algorytmy są zaprojektowane, mają jakąś formę łatwo modelowanej nadmiarowości, którą algorytm ma usunąć, a zatem należą do podzbioru plików, które algorytm może skrócić, podczas gdy inne pliki nie zostaną skompresowane lub nawet staną się większe. Algorytmy są zazwyczaj dość specyficznie dostrojone do konkretnego typu pliku: na przykład programy do bezstratnej kompresji audio nie działają dobrze na plikach tekstowych i vice versa.

W szczególności, pliki z losowymi danymi nie mogą być konsekwentnie kompresowane przez żaden możliwy do pomyślenia algorytm bezstratnej kompresji danych: w rzeczy samej, ten wynik jest używany do zdefiniowania pojęcia losowości w teorii złożoności algorytmów.

To jest prowdopodobnie niemożliwe, aby stworzyć algorytm, który może bezstratnie kompresować dowolne dane. Chociaż przez lata pojawiło się wiele twierdzeń o firmach osiągających „doskonałą kompresję”, gdzie arbitralna liczba N losowych bitów może być zawsze skompresowana do N – 1 bitów, tego rodzaju twierdzenia można bezpiecznie odrzucić, nawet nie patrząc na jakiekolwiek dalsze szczegóły dotyczące rzekomego schematu kompresji. Taki algorytm jest sprzeczny z podstawowymi prawami matematyki, ponieważ, gdyby istniał, mógłby być stosowany wielokrotnie w celu bezstratnej redukcji dowolnego pliku do długości 0. Rzekomo „doskonałe” algorytmy kompresji są często drwiąco nazywane „magicznymi” algorytmami kompresji z tego powodu.

Z drugiej strony, zostało również udowodnione, że nie istnieje algorytm określający, czy plik jest nieściśliwy w sensie złożoności Kołmogorowa. Stąd możliwe jest, że każdy konkretny plik, nawet jeśli wydaje się przypadkowy, może być znacznie skompresowany, nawet z uwzględnieniem rozmiaru dekompresora. Przykładem są cyfry stałej matematycznej pi, które wydają się losowe, ale mogą być wygenerowane przez bardzo mały program. Jednakże, nawet jeśli nie można określić, czy dany plik jest niekompresowalny, proste twierdzenie o niekompresowalnych łańcuchach pokazuje, że ponad 99% plików o dowolnej długości nie może być skompresowanych o więcej niż jeden bajt (włączając w to rozmiar dekompresora).

Tło matematyczneEdit

Abstrakcyjnie, algorytm kompresji może być postrzegany jako funkcja na sekwencjach (zwykle oktetach). Kompresja jest udana, jeśli wynikowa sekwencja jest krótsza niż oryginalna sekwencja (i instrukcje dla mapy dekompresji). Aby algorytm kompresji był bezstratny, mapa kompresji musi tworzyć iniekcję z „zwykłych” do „skompresowanych” sekwencji bitowych.

Zasada pigeonhole zabrania bijection między kolekcją sekwencji o długości N i dowolnym podzbiorem kolekcji sekwencji o długości N-1. Dlatego nie jest możliwe wyprodukowanie algorytmu bezstratnego, który zmniejsza rozmiar każdej możliwej sekwencji wejściowej.

Punkty zastosowania w teorii kompresji rzeczywistejEdit

Projektanci algorytmów kompresji rzeczywistej akceptują fakt, że strumienie o wysokiej entropii informacji nie mogą być skompresowane, a zatem zawierają obiekty do wykrywania i obsługi tego stanu. Oczywistym sposobem wykrywania jest zastosowanie surowego algorytmu kompresji i sprawdzenie, czy jego wyjście jest mniejsze niż wejście. Czasami, wykrywanie jest dokonywane przez heurystykę; na przykład, aplikacja kompresująca może uznać pliki, których nazwy kończą się na „.zip”, „.arj” lub „.lha” za niekompresowalne bez bardziej wyrafinowanego wykrywania. Powszechnym sposobem radzenia sobie z taką sytuacją jest cytowanie danych wejściowych lub niekompresowalnych części danych wejściowych na wyjściu, co minimalizuje narzut kompresji. Na przykład, format danych zip określa 'metodę kompresji’ jako 'Stored’ dla plików wejściowych, które zostały skopiowane do archiwum dosłownie.

The Million Random Digit ChallengeEdit

Mark Nelson, w odpowiedzi na twierdzenia o magicznych algorytmach kompresji pojawiające się w comp.compression, skonstruował 415,241 bajtowy plik binarny o wysoce entropicznej zawartości i rzucił publiczne wyzwanie o wartości 100 dolarów każdemu, kto napisze program, który wraz z danymi wejściowymi będzie mniejszy niż dostarczone przez niego dane binarne, a jednocześnie będzie w stanie odtworzyć je bezbłędnie.

FAQ dla grupy dyskusyjnej comp.compression zawiera wyzwanie Mike’a Goldmana oferującego 5,000 dolarów za program, który potrafi kompresować losowe dane. Patrick Craig podjął wyzwanie, ale zamiast kompresować dane, podzielił je na osobne pliki, z których wszystkie kończyły się cyfrą 5, która nie była przechowywana jako część pliku. Pominięcie tego znaku sprawiło, że pliki wynikowe (plus, zgodnie z zasadami, rozmiar programu, który je ponownie złożył) były mniejsze niż plik oryginalny. Nie doszło jednak do faktycznej kompresji, a informacje zapisane w nazwach plików były niezbędne do ponownego złożenia ich w odpowiedniej kolejności w pliku oryginalnym i nie były one brane pod uwagę przy porównywaniu wielkości plików. Same pliki nie są zatem wystarczające do odtworzenia oryginalnego pliku; konieczne są również nazwy plików. Patrick Craig zgodził się, że nie miała miejsca żadna znacząca kompresja, ale argumentował, że sformułowanie wyzwania w rzeczywistości tego nie wymagało. Pełna historia tego wydarzenia, w tym dyskusja na temat tego, czy wyzwanie zostało technicznie spełnione, czy też nie, znajduje się na stronie Patricka Craiga.