Nie istnieje bezstratny kompresor, który zmniejszy każdy możliwy plik
Uniwersalny bezstratny kompresor, który skraca każdy plik i nigdy żadnego nie wydłuża, jest niemożliwy z prostego powodu kombinatorycznego. Dla plików długości n bitów istnieje 2^n różnych wejść. Wszystkich krótszych ciągów bitów — długości 0,1,…,n−1 — jest łącznie tylko 2^n−1. Nie wystarcza ich, aby każdemu n-bitowemu plikowi przypisać inny krótszy kod, a bezstratna dekompresja wymaga jednoznaczności. Jeśli kompresor skraca pewne dane, musi pozostawić inne bez skrócenia lub je powiększyć. Skuteczna kompresja działa dlatego, że realne dane nie są równomiernie losowe i mają regularności, które kodek potrafi wykorzystać.
Liczenie kodów wystarcza do dowodu
Rozważmy wszystkie 2^n plików o długości dokładnie n bitów. Gdyby każdy miał zostać zamieniony na plik krótszy niż n bitów, potrzebowalibyśmy co najmniej 2^n różnych krótszych kodów. Tymczasem liczba wszystkich ciągów o długościach od 0 do n−1 wynosi 1+2+4+…+2^(n−1)=2^n−1. Brakuje choć jednego kodu. To wersja zasady szufladkowej: więcej obiektów niż szuflad oznacza kolizję.
Bezstratność wymaga odwracalności
Jeżeli dwa różne pliki zostałyby skompresowane do identycznego wyniku, dekompresor nie wiedziałby, który z nich odtworzyć. Dlatego mapowanie dla danych, które mają być bezstratnie odzyskane, musi być jednoznaczne. Ten warunek łączy argument o liczbie ciągów bezpośrednio z kompresją: nie możemy „upchnąć” wszystkich n-bitowych wejść w mniejszym zbiorze krótszych kodów.
Dlaczego ZIP jednak zwykle działa
Pliki tworzone przez ludzi i systemy mają strukturę. Tekst zawiera nierówne częstości symboli i powtarzalne słowa; obrazy mają lokalne podobieństwa; logi powtarzają formaty. Kompresor projektuje krótkie reprezentacje dla typowych regularności, płacąc dłuższą reprezentacją dla danych, które do modelu nie pasują. Zysk na użytecznych rozkładach nie przeczy twierdzeniu o wszystkich możliwych ciągach.
Losowo wyglądające dane są trudnym przeciwnikiem
Jeżeli wejście nie zawiera regularności uchwytnych przez dany kodek, nagłówki i metadane mogą sprawić, że wynik będzie nawet większy. Dane już skompresowane lub zaszyfrowane często wyglądają dla ogólnego kompresora blisko losowych, dlatego kolejne kompresowanie nie daje gwarantowanego zysku. Nie jest to wada konkretnego programu, lecz konsekwencja ograniczonej liczby krótszych reprezentacji.
Granica bez zaawansowanej teorii
Ta ciekawostka jest wyjątkowa, bo fundamentalną granicę informatyki można pokazać bez maszyn Turinga, NP-zupełności czy rachunku złożoności. Wystarczy policzyć ciągi bitów. Pokazuje to, że pewne ograniczenia systemów cyfrowych wynikają już z samej informacji i jednoznacznego kodowania.
Dokładny rachunek z zasadą szufladkową
Dla wszystkich n-bitowych plików istnieje dokładnie 2^n możliwych wejść. Ile jest ciągów krótszych niż n bitów? 1+2+4+…+2^(n−1)=2^n−1. Jest ich więc za mało, aby każdemu n-bitowemu wejściu przypisać unikalny krótszy kod. Bezstratny dekompresor musi rozróżniać wszystkie wejścia, więc kody nie mogą się zderzać. Co więcej, jeżeli kompresor skróci choć część n-bitowych plików, inne muszą pozostać długości co najmniej n lub się wydłużyć, gdy uwzględnimy wszystkie możliwe wejścia. To bardzo mocny wynik, bo nie zależy od formatu ZIP, konkretnego algorytmu ani mocy komputera — wynika wyłącznie z liczenia możliwych napisów.
Dlaczego prawdziwe pliki mimo wszystko często się kompresują
Pliki tworzone przez ludzi i urządzenia nie są równomiernie losowane ze zbioru wszystkich możliwych ciągów bitów. Tekst zawiera powtórzenia i nierówne częstości znaków, obrazy mają lokalne korelacje, a dane strukturalne często powtarzają wzorce. Kompresory wykorzystują właśnie te regularności. Twierdzenie o niemożności skracania wszystkiego mówi, że nie można zachować takiego sukcesu na pełnym zbiorze wejść; nie przeczy temu, że dla wybranych, silnie ustrukturyzowanych klas danych oszczędności są ogromne.