To pytanie, które rozpala umysły archiwistów i entuzjastów cyfrowego porządku! W świecie kompresji bezstratnej, gdzie kluczowe jest to, by po rozpakowaniu plik był identyczny z oryginałem, walka o każdy zaoszczędzony bit jest zacięta.

Odpowiedź na to, jaka jest najsilniejsza metoda, zależy od tego, co rozumiemy przez "siłę" — czy chodzi o absolutnie najwyższy stopień kompresji (nawet kosztem czasu i zasobów), czy o najlepszy kompromis między kompresją a szybkością.

Teoretyczny mistrz: Algorytmy PAQ (Context Mixing)

Jeśli szukamy metody, która wyciśnie z pliku absolutnie najwięcej, bez względu na to, ile czasu to zajmie, zwycięzcą jest klasa algorytmów CM (Context Mixing), której najbardziej znanym przedstawicielem jest PAQ (szczególnie wersje takie jak PAQ8).

Co to jest PAQ i dlaczego jest tak silny?

Algorytmy PAQ działają na zasadzie mieszania kontekstów. Zamiast używać jednego modelu do przewidywania kolejnego symbolu (znaku, bajtu), używają wielu różnych modeli jednocześnie. Każdy z tych modeli analizuje dane pod innym kątem (np. jeden szuka powtórzeń, drugi analizuje strukturę słów, trzeci bada statystykę występowania symboli).

Wyniki przewidywań z tych wielu modeli są następnie "mieszane" (stąd nazwa Context Mixing) w celu uzyskania jak najdokładniejszego przewidywania. Im lepsze przewidywanie, tym efektywniejsze jest późniejsze kodowanie entropijne (zazwyczaj kodowanie arytmetyczne), co skutkuje mniejszym rozmiarem pliku.

Wielkie "ale":

Algorytmy PAQ osiągają jedne z najwyższych stopni kompresji, ale ich cena jest bardzo wysoka:

• Wysokie wymagania pamięciowe: Liczone w setkach megabajtów.
• Ekstremalnie niska prędkość kompresji: Kompresja dużego pliku może trwać bardzo długo (w skrajnych, eksperymentalnych przypadkach, nawet dekady!).

Z tego powodu PAQ jest raczej ciekawostką akademicką i narzędziem dla entuzjastów, którzy chcą osiągnąć rekordowy stopień kompresji, a nie praktycznym rozwiązaniem do codziennego użytku.

Praktyczni giganci: LZMA i PPM

W codziennej archiwizacji, gdzie liczy się zarówno siła kompresji, jak i rozsądny czas, królują inne algorytmy.

1. LZMA (Lempel-Ziv-Markov chain Algorithm)

Obecnie to jeden z najczęściej wskazywanych algorytmów, jeśli chodzi o najwyższy stopień kompresji przy zachowaniu akceptowalnej prędkości. Jest on sercem formatu 7z (używanego przez program 7-Zip), który jest powszechnie uznawany za jeden z najefektywniejszych archiwizatorów.

• Zasada działania: Łączy w sobie najlepsze cechy algorytmów słownikowych (jak popularny LZ77, używany w ZIP i GZIP) z kodowaniem łańcuchów Markowa i kodowaniem entropijnym (kodowanie zakresowe/arytmetyczne).
• Zastosowanie: Jest to standardowy wybór dla osób, które chcą zarchiwizować duże zbiory danych (dokumenty, kod źródłowy, nieskompresowane obrazy) i uzyskać najlepszy możliwy stopień kompresji.

2. PPM (Prediction by Partial Matching)

Algorytmy PPM również oferują bardzo wysoki stopień kompresji, często zbliżony do LZMA.

• Zasada działania: PPM wykorzystuje kontekst (ciąg poprzedzających symboli) do przewidzenia następnego symbolu. Im dłuższy kontekst, tym lepsze przewidywanie, a co za tym idzie, lepsza kompresja.
• Zastosowanie: Algorytm ten znalazł praktyczne zastosowanie w znanych archiwizerach, takich jak WinRAR i WinZip, szczególnie w trybach wysokiej kompresji.

3. Bzip2/Bzip3

Warto też wspomnieć o algorytmie Bzip2, który jest oparty na sprytnej metodzie zwanej transformacją Burrowsa-Wheelera (BWT), a następnie kodowaniu Huffmana.

• Zasada działania: BWT nie kompresuje danych bezpośrednio, ale przekształca je w taki sposób, że powtarzające się ciągi znaków stają się zebrane w bloki, co znacznie ułatwia późniejszą kompresję przez inne algorytmy.
• Zastosowanie: Jest bardzo efektywny, zwłaszcza w kompresji plików tekstowych i danych o dużej nadmiarowości. Nowsze wersje, takie jak Bzip3, również robią wrażenie, ale wymagają sporo mocy obliczeniowej.

Podsumowanie: Najsilniejsza metoda kompresji bezstratnej

Jeśli więc szukasz najsilniejszej, ale praktycznej metody, postaw na format 7z i algorytm LZMA. Jeśli natomiast masz czas i zasoby, a chcesz zobaczyć, jak mały może być Twój plik, spróbuj eksperymentów z algorytmami z rodziny PAQ.