Jak działa kompresja plików

W naszym poprzednim przykładzie wybraliśmy wszystkie powtarzające się słowa i umieściliśmy je w słowniku. Dla nas jest to najbardziej oczywisty sposób pisania słownika. Ale program kompresujący widzi to zupełnie inaczej: Nie ma on pojęcia oddzielnych słów – szuka tylko wzorców. A żeby maksymalnie zmniejszyć rozmiar pliku, starannie wybiera, które wzorce włączyć do słownika.

Jeśli podejdziemy do zdania z tej perspektywy, otrzymamy zupełnie inny słownik.

Jeśli program kompresujący przeskanowałby zdanie Kennedy’ego, pierwsza nadmiarowość, na jaką by się natknął, miałaby zaledwie kilka liter. W „ask not what your” powtarza się litera „t”, po której następuje spacja – w „not” i „what”. Gdyby program kompresujący zapisał to do słownika, mógłby zapisać „1” za każdym razem, gdy po „t” następowałaby spacja. Ale w tym krótkim zdaniu ten wzorzec nie występuje na tyle często, by uczynić z niego warte uwagi hasło, więc program w końcu by je nadpisał.

Kolejną rzeczą, na którą program mógłby zwrócić uwagę, jest „ou”, które pojawia się zarówno w „twój”, jak i „kraj”. Gdyby to był dłuższy dokument, zapisanie tego wzorca do słownika mogłoby zaoszczędzić sporo miejsca – „ou” jest dość częstą kombinacją w języku angielskim. Ale w miarę jak program kompresujący pracowałby nad tym zdaniem, szybko odkryłby lepszy wybór na hasło słownikowe: Nie tylko „ou” jest powtórzone, ale całe słowa „your” i „country” są powtórzone, a właściwie są powtórzone razem, jako fraza „your country”. W tym przypadku program nadpisałby wpis słownikowy dla „ou” wpisem dla „twojego kraju.”

Fraza „can do for” również się powtarza, raz po „your” i raz po „you”, dając nam powtarzający się wzór „can do for you”. To pozwala nam napisać 15 znaków (w tym spacji) z jedną wartością liczbową, podczas gdy „twój kraj” pozwala nam napisać tylko 13 znaków (ze spacjami) z jedną wartością liczbową, więc program nadpisze wpis „twój kraj” jako po prostu „r kraj”, a następnie napisze osobny wpis dla „może zrobić dla Ciebie”. Program postępuje w ten sposób, zbierając wszystkie powtarzające się fragmenty informacji, a następnie oblicza, które wzory powinien zapisać do słownika. Ta zdolność do przepisywania słownika jest „adaptacyjną” częścią algorytmu LZ opartego na słowniku adaptacyjnym. Sposób, w jaki program faktycznie to robi, jest dość skomplikowany, o czym można się przekonać, czytając dyskusje na Data-Compression.com.

Niezależnie od tego, jakiej konkretnie metody użyjesz, ten system dogłębnego przeszukiwania pozwala skompresować plik znacznie wydajniej, niż można by to zrobić, wybierając tylko słowa. Używając wzorców, które wybraliśmy powyżej, i dodając „__” dla spacji, otrzymujemy taki oto większy słownik:

A to mniejsze zdanie: „1not__2345__–__12354”

Zdanie zajmuje teraz 18 jednostek pamięci, a nasz słownik zajmuje 41 jednostek. Tak więc skompresowaliśmy całkowity rozmiar pliku z 79 jednostek do 59 jednostek! Jest to tylko jeden ze sposobów kompresji zdania, niekoniecznie najbardziej efektywny. (Sprawdź, czy możesz znaleźć lepszy sposób!)

Jak dobry jest ten system? Współczynnik redukcji plików zależy od wielu czynników, w tym od typu pliku, jego rozmiaru i schematu kompresji.

W większości języków świata pewne litery i słowa często występują razem w tym samym wzorze. Ze względu na ten wysoki stopień redundancji pliki tekstowe kompresuje się bardzo dobrze. Redukcja o 50 procent lub więcej jest typowa dla plików tekstowych o dobrym rozmiarze. Większość języków programowania jest również bardzo redundantna, ponieważ używa stosunkowo niewielkiego zbioru poleceń, które często występują razem w ustalonym wzorze. Pliki, które zawierają wiele unikalnych informacji, takie jak grafika czy pliki MP3, nie mogą być skompresowane w tym systemie, ponieważ nie powtarzają wielu wzorców (więcej na ten temat w następnej sekcji).

Jeżeli plik ma wiele powtarzających się wzorców, stopień redukcji zazwyczaj wzrasta wraz z rozmiarem pliku. Można to zauważyć, patrząc na nasz przykład – gdybyśmy mieli więcej przemówień Kennedy’ego, moglibyśmy częściej odwoływać się do wzorców w naszym słowniku, a tym samym uzyskać więcej miejsca w pliku na każde hasło. Ponadto, w dłuższej pracy mogą pojawić się bardziej wszechobecne wzorce, co pozwoli nam stworzyć bardziej wydajny słownik.

Wydajność ta zależy również od konkretnego algorytmu używanego przez program kompresujący. Niektóre programy są szczególnie przystosowane do wyłapywania wzorców w pewnych typach plików, więc mogą je skompresować w sposób bardziej zwięzły. Inne posiadają słowniki w słownikach, które mogą kompresować wydajnie większe pliki, ale nie mniejsze. Podczas gdy wszystkie programy kompresujące tego typu działają w oparciu o ten sam podstawowy pomysł, w rzeczywistości istnieje wiele różnic w sposobie ich wykonania. Programiści zawsze starają się zbudować lepszy system.