Dlaczego skompresowanie skompresowanego pliku nie zmniejsza jego rozmiaru?

Opierając się na pomyśle, że spakowany plik jest nowym plikiem binarnym, dlaczego nie mogę zmniejszyć rozmiaru Zipa przez spakowanie go raz za razem - aż do bardzo małego pliku wynikowego?

Opierając się na pomyśle, że spakowany plik jest nowym plikiem binnary, dlaczego nie mogę zmniejszyć jego rozmiaru poprzez spakowanie go ponownie i sukcesywnie do bardzo małego pliku?

Ponieważ kompresja działa na podstawie wyszukiwania wzorców i zmniejszania podobnych danych.

Na przykład RLE (Run-length Encoding) to prosta metoda kompresji, w której dane są badane, a przebiegi podobnych danych są kompresowane w następujący sposób:

AAABCEEEJFFYYYYYYYYYYOOAAAAGGGGGAAA

becomes

3ABC3EJ2F10YOO4A5G3A

Jak widać, zastępując powtarzane dane tylko danymi i liczbą ich wystąpienia, można zmniejszyć ten konkretny przykład z 35 bajtów do 20 bajtów. To nie jest duża redukcja, ale wciąż jest o 42% mniejsza. Co więcej, jest to mały, wymyślony przykład; większe, rzeczywiste przykłady mogłyby mieć jeszcze lepszą kompresję. ( OOZostał sam, ponieważ zastąpienie go 2Onie uratuje niczego.)

Pliki tekstowe często kompresują się naprawdę dobrze, ponieważ mają wiele wzorów, które można skompresować. Na przykład słowo to jest bardzo popularne w języku angielskim, więc można usunąć każde wystąpienie tego słowa z identyfikatorem, który jest tylko jednym bajtem (lub nawet mniej). Można również skompresować więcej z części słów, które są podobne jak cAKE, bAKE, shAKE, undertAKE, i tak dalej.

Dlaczego więc nie możesz skompresować pliku, który już został skompresowany? Ponieważ podczas wstępnej kompresji usunięto wzorce .

Spójrz na skompresowany przykład RLE. Jak możesz to jeszcze bardziej skompresować? Nie ma serii identycznych danych do kompresji. W rzeczywistości często, gdy próbujesz skompresować plik, który jest już skompresowany, możesz skończyć z większym plikiem. Na przykład, jeśli zmusiłeś powyższy przykład do ponownego zakodowania, możesz otrzymać coś takiego:

131A1B1C131E1J121F11101Y2O141A151G131A

Teraz dane kompresji (liczby uruchomień) same są traktowane jak dane, więc otrzymujesz większy plik niż początkowo.

Co mogłoby spróbować jest użycie innego algorytmu kompresji, ponieważ możliwe jest, że wyjście jednego algorytmu kompresji mogłaby być podstawowym dla innego algorytmu, jednak jest to zwykle dość mało prawdopodobne.

Oczywiście chodzi tu o kompresję bezstratną, w której zdekompresowane dane muszą być dokładnie identyczne z danymi oryginalnymi. Z kompresji stratnej , zazwyczaj można usunąć więcej danych, ale jakość idzie w dół. Ponadto kompresja stratna zwykle używa pewnego rodzaju schematu opartego na wzorcach (nie tylko odrzuca dane), więc w końcu osiągniesz punkt, w którym po prostu nie ma wzorców do znalezienia.

Jeśli wszystkie skompresowane pliki po ponownej kompresji zmniejszą swoje rozmiary (lub mają rozmiary nie większe niż ich rodzic), to w pewnym momencie rozmiar wyniesie 0, co nie może być prawdą. Jeśli to prawda, prawie wcale nie potrzebujemy przechowywania plików.

Bezstratne algorytmy kompresji danych nie mogą gwarantować kompresji dla wszystkich zestawów danych wejściowych . Innymi słowy, dla każdego bezstratnego algorytmu kompresji danych będzie istniał zestaw danych wejściowych, który nie zmniejsza się, gdy jest przetwarzany przez algorytm, a dla każdego bezstratnego algorytmu kompresji danych, który czyni co najmniej jeden plik mniejszym, będzie co najmniej jeden plik, który powiększa. Można to łatwo udowodnić za pomocą matematyki elementarnej, używając następującego argumentu liczącego:

• 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ż plik oryginalny, i że co najmniej jeden plik zostanie skompresowany do pliku wyjściowego, który jest krótszy niż plik oryginalny.
• Niech M będzie najmniejszą liczbą, tak aby istniał 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 F.
• Ponieważ N <M, każdy plik o długości N zachowuje swój rozmiar podczas kompresji. Istnieją 2 ^N takich plików. Razem z F tworzy to 2 ^N +1 plików, które wszystkie są kompresowane do jednego z 2 ^N plików o długości N.
• Ale 2 ^N jest mniejsze niż 2 ^N +1, więc zgodnie z zasadą szuflady musi istnieć plik o długości N, który jest jednocześnie wynikiem funkcji kompresji na dwóch różnych wejściach. Pliku tego nie można rozpakować w wiarygodny sposób (który z dwóch oryginałów powinien dać?), Co jest sprzeczne z założeniem, że algorytm był bezstratny.
• Musimy zatem dojść do wniosku, że nasza pierwotna hipoteza (że funkcja kompresji nie powoduje już przechowywania pliku) jest z konieczności nieprawdziwa.

https://en.wikipedia.org/wiki/Lossless_compression#Limitations

Plik, który został optymalnie skompresowany, nie będzie zawierał żadnych wzorców ani niczego, co można by zmniejszyć.

Wyobraźmy sobie prosty plik, który to zawiera.

AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCC

Jeśli go skompresujemy, możemy powiedzieć, że jest to 20 A, nowa linia, a następnie 20 B, nowa linia, a następnie 20 C. Lub coś w tym rodzaju 20xA\n20xB\n20xC\n. Po wykonaniu pierwszej kompresji nie ma nowych wzorów do kompresji. W każdym razie, jeśli informacja jest unikalna.

Powiedziałbym, że nie można w dużym stopniu kompresować dowolnych plików binarnych - pomyśl o obrazach JPEG, filmach x264 itd. Zwłaszcza, że ​​chcesz dokładnie odtworzyć oryginalny plik (tzn. Krok po kroku), potrzebujesz kompresji bezstratnej . ¹

Przyczynę tej ograniczonej kompresji podano w tym artykule Wikipedii na temat Entropy, który określa oczekiwaną wartość informacji zawartych w komunikacie :

Entropia skutecznie ogranicza wydajność najsilniejszej bezstratnej (lub prawie bezstratnej) kompresji, która może być zrealizowana teoretycznie przy użyciu typowego zestawu lub w praktyce przy użyciu Huffmana, Lempela-Ziva lub kodowania arytmetycznego. (...)

¹ Bardzo silna „kompresja” obrazów JPEG jest możliwa tylko dlatego, że niektóre informacje są odrzucane (w taki sposób, że ludzkie oko nie może ich rozpoznać na pierwszy rzut oka; kompresja stratna ).