Wielki ścisk

Choć nowoczesne dyski twarde oferują obecnie gigabajty przestrzeni, wciąż warto pamiętać o możliwości kompresji danych. Dobry "paker" przyda się szczególnie osobom często przesyłającym dane przez Internet

Temat kompresji powraca wśród użytkowników komputerów regularnie co kilka lat. Najpierw był czas drogich i niezbyt pojemnych pamięci masowych, więc pakowanie zbiorów interesowało niemal wszystkich. Z czasem dyski staniały, ale jednocześnie upowszechnił się dostęp do Internetu i powstał problem przesyłania plików po łączach o małej przepustowości. W miarę rozwoju Sieci zainteresowanie kompresją znów malało. Dziś coraz częściej korzystamy z szerokopasmo- wych łączy, ale ilość generowanych i przesyłanych danych, np. olbrzymich rozmiarów plików multimedialnych, sprawia, że kompresja znów interesuje coraz więcej osób. Warto też pamiętać, że algorytmy pakujące mogą zostać wykorzystane w poważniejszych celach i usprawnić np. pracę zdalną. To właśnie dzięki kompresji, korzystając z łącza o takiej samej przepustowości, prześlemy i odbierzemy więcej danych w krótszym czasie, co zwykle przekłada się bezpośrednio na koszta.

Kompresja to oczywiście nie tylko świat komputerów, ale też np. telefonia komórkowa czy telewizja cyfrowa. Niezależnie jednak od zastosowań i wykorzystywanych algorytmów podczas pakowania danych zawsze wykorzystywany jest fakt redundancji, czyli nadmiarowości informacji. Z oczywistych względów zajmiemy się jednak tylko tymi aspektami kompresji, ktore związane są z pakowaniem zawartości naszych dysków twardych.

Takie same, ale mniejsze?

Jak to się dzieje, że po przeprowadzeniu kompresji otrzymujemy plik zawierający te same lub niemal te same informacje, ale zajmujący mniej miejsca? Sztuka polega na wykorzystaniu niedokładności naszych zmysłów, dzięki której część informacji może zostać pominięta. Taka kompresja nosi nazwę stratnej i jest stosowana w plikach DivX, MP3 czy JPEG. Z oczywistych przyczyn tej metody nie możemy jednak zastosować, zmniejszając rozmiar zbiorów tekstowych, baz danych czy programów komputerowych. W ich przypadku potrzebny jest algorytm umożliwiający odzyskanie pliku w postaci identycznej z pierwotną. Jest to tzw. kompresja bezstratna. W naszym teście formatów kompresji i w dalszej części artykułu będziemy się zajmowali wyłącznie takim sposobem pakowania danych. W osobnej tabeli na $(LC90866: Wielki ścisk)$ prezentujemy też najpopularniejsze aplikacje kompresujące dane w testowanych przez nas formatach.

Słownik to podstawa

Metody kompresji bezstratnej można podzielić na probabilistyczne, czyli bazujące na częstości występowania poszczególnych znaków w zbiorze, oraz słownikowe, polegające na zastępowaniu powtarzających się bloków danych jedynie wskaźnikami do słownika zawierającego powtarzające się sekwencje symboli. Żaden z biorących udział w teście formatów danych nie wykorzystuje jednak wyłącznie tylko jednego rodzaju algorytmu. Najczęściej stosowane są mechanizmy łączące oba wspomniane sposoby pakowania danych, z tym że jako podstawowa używana jest metoda słownikowa.

Proces „prasowania” plików składa się z dwóch etapów: modelowania i kodowania. Podczas pierwszego kroku wydobywane są informacje o nadmiarowych danych w analizowanym zbiorze i powstaje model wykorzystywany następnie w procesie kodowania. W drugiej fazie pliki są kodowane na podstawie stworzonego wcześniej modelu i zapisywane w dogodnej do przesyłania postaci np. jako ciągi 0 i 1.

A gdzie reszta danych?

Jednym z historycznych przykładów zasad wykorzystywanych podczas kompresji danych jest alfabet Morse’a. Jego twórca zauważył, że pewne litery alfabetu występują częściej niż inne, i na tym spostrzeżeniu oparł swój system kodowania. Zmniejszenie długości przesyłanych tekstów uzyskał poprzez przypisanie częściej występującym znakom krótszych ciągów kodowych. Po przeprowadzeniu badań w drukarni sprawdził, w jakim stopniu zużywane są poszczególne czcionki, i stwierdził, że (w języku angielskim) najczęściej występujące litery to „e” (zakodowane jako „.”) oraz t („-„), a najrzadziej „q” („–.-„) i ” j” („.—„).

Nieco bardziej współczesną i dobrze obrazującą ideę kompresji danych jest metoda RLE (Run Length Encoding). To bardzo prosty algorytm, sprawdzający się przy kompresji bloków danych, w których powtarza się wiele takich samych znaków obok siebie, jak np. w plikach graficznych. Załóżmy, że we wspomnianym zbiorze dane o wartościach kolorów będą symbolizowane literami A, B i C, a przykładowy ciąg będzie wyglądał tak: AABBBBBCCCBBDDDDDDDD. Blok ma 20 znaków, ale informacja w nim przekazana może być skompresowana do rozmiaru 13 znaków: AA*5B*3CBB8*D, gdzie ciąg *nX oznacza n-krotne wystąpienie znaku X, a znacznik * jest separatorem pomiędzy danymi kodowanymi i niekodowanymi.

Od czego jednak zależy kryterium, które dane kodować? Wystarczy pamiętać, że celem kompresji jest zmniejszenie rozmiaru bloku danych bez utraty jego zawartości, a w opisywanej metodzie nieopłacalne jest kodowanie ciągów od jednego do trzech znaków. Zakodowane A będzie miało postać *1A, w takich przypadkach więc zbiór się powiększy lub co najwyżej pozostanie taki sam. Efektywne jest dopiero kodowanie od 4 następujących po sobie znaków wzwyż.

ProgramZIP (PKZip)RARZIP (WinZip)AceARJ327-ZipGZipBZip2
http://www.pkware.com/www.rarlab.com/www.winzip.com/www.winace.com/www.arjsoft.com/www.7-zip.org/www.gzip.org/sources.redhat.com/bzip2/
Użyta aplikacjaPKZip 6.0.147WinRAR 3.30WinZip 9.0WinAce Archiver 2.5ARJ32 3.117-Zip 3.13linia komend/1.3.5linia komend/1.0.2
Producent/autor i licencjaPKWare (shareware)Eugene Roshal (shareware)Nico Mak (shareware)Marcel Lemke (shareware)Robert Jung (shareware)Igor Pavlov (freeware)Jean-loup Gailly (freeware)Julian Seward (freeware)
Wykorzystywane algorytmy kompresjiLZH, LZW, Shannon-Fano, HuffmanLZSS (wariant LZ77) + HuffmanLZH, LZW, Shannon-Fano, Huffmanzmodyfikowany LZ77 + HuffmanLZSS + HuffmanLZMA (zmodyfiko-wany LZ77)Shannon-Fano, HuffmanBurrows-Wheeler + Huffman
Ocena ogólna (POWER)10098949488868278
Pliki tekstowe (*.RTF, rozmiar 38,63 MB)
Kompresja standardowa/Stopień kompresji10,58 MB/72,6%8,71 MB/77,5%10,94 MB/71,7%8,77 MB/77,3%10,85 MB/71,9%7,99 MB/79,3%10,71 MB/72,3%7,97 MB/79,4%
Kompresja maksymalna/Stopień kompresji10,12 MB/73,8%7,02 MB/81,8%10,23 MB/73,5%8,75 MB/77,4%10,81 MB/72,0%7,70 MB/80,1%10,59 MB/72,6%7,97 MB/79,4%
Czas wykonania standardowej kompresji plików4 s36 s5 s40 s10 s66 s6 s24 s
Czas wykonania maksymalnej kompresji plików8 s30 s21 s44 s15 s120 s11 s32 s
Pliki dźwiękowe (*.WAV, rozmiar 593,18 MB)
Kompresja standardowa/Stopień kompresji571,78 MB/3,61%446,68 MB/24,70%570,62 MB/3,80%442,92 MB/25,33%572,19 MB/3,54%561,83 MB/5,28%570,63 MB/3,80% 567,16 MB/4,39%
Kompresja maksymalna/Stopień kompresji571,79 MB/3,61%446,66 MB/24,70%570,63 MB/3,80%442,92 MB/25,33%572,19 MB/3,54%561,79 MB/5,29%570,63 MB/3,80% 567,16 MB/4,39%
Czas wykonania standardowej kompresji plików100 s260 s118 s312 s140 s913 s465 s791 s
Czas wykonania maksymalnej kompresji plików120 s268 s161 s795 s162 s1294 s465 s931 s
Pliki graficzne (*.BMP, rozmiar 58,71 MB)
Kompresja standardowa/Stopień kompresji8,93 MB/84,78%8,12 MB/86,18%9,37 MB/84,05%7,45 MB/87,31%9,01 MB/84,65%6,92 MB/88,21%9,26 MB/84,23% 7,06 MB/87,97%
Kompresja maksymalna/Stopień kompresji8,61 MB/85,33%8,02 MB/86,34%8,84 MB/84,95%7,48 MB/87,26%8,94 MB/84,78%6,81 MB/88,40%9,13 MB/84,46% 7,05 MB/87,99%
Czas wykonania standardowej kompresji plików4 s20 s5 s32 s10 s37 s23 s62 s
Czas wykonania maksymalnej kompresji plików8 s29 s14 s36 s14 s66 s31 s70 s
Pliki bazy danych (*.MDB, rozmiar 104,76 MB)
Kompresja standardowa/Stopień kompresji21,52 MB/79,46%11,76 MB/88,77%21,82 MB/79,17%12,50 MB/88,06%22,09 MB/78,91%10,44 MB/90,03%21,70 MB/79,29% 16,08 MB/84,65%
Kompresja maksymalna/Stopień kompresji19,73 MB/81,17%11,48 MB/89,04%19,76 MB/81,14%12,48 MB/88,08%22,01 MB/78,99%7,72 MB/92,63%21,50 MB/79,48% 16,04 MB/84,69%
Czas wykonania standardowej kompresji plików10 s52 s11 s59 s20 s88 s46 s83 s
Czas wykonania maksymalnej kompresji plików15 s86 s37 s62 s25 s184 s62 s104 s
Pliki PDF (*.PDF, rozmiar 48,49 MB)
Kompresja standardowa/Stopień kompresji34,12 MB/29,64%33,58 MB/30,75%34,16 MB/29,55%33,59 MB/30,74%34,14 MB/29,59%33,65 MB/30,61%34,12 MB/29,64% 34,13 MB/29,62%
Kompresja maksymalna/Stopień kompresji33,96 MB/29,96%33,55 MB/30,81%33,95 MB/30,00%33,58 MB/30,76%34,13 MB/29,61%27,44 MB/43,41%34,06 MB/29,77% 34,05 MB/29,79%
Czas wykonania standardowej kompresji plików8 s58 s8 s57 s12 s66 s21 s70 s
Czas wykonania maksymalnej kompresji plików8 s74 s10 s57 s12 s92 s22 s75 s
Pliki wykonywalne (rozmiar 38,90 MB)
Kompresja standardowa/Stopień kompresji26,18 MB/32,69%22,67 MB/41,72%26,26 MB/32,48%24,56 MB/36,86%26,24 MB/32,53%23,85 MB/38,68%26,21 MB/32,62% 26,61 MB/31,58%
Kompresja maksymalna/Stopień kompresji26,02 MB/33,11%22,63 MB/41,82%26,06 MB/33,01%24,55 MB/36,88%26,23 MB/32,55%21,43 MB/44,90%26,19 MB/32,67% 26,57 MB/31,68%
Czas wykonania standardowej kompresji plików7 s44 s8 s45 s10 s53 s18 s23 s
Czas wykonania maksymalnej kompresji plików8 s51 s15 s46 s11 s79 s21 s37 s
Różne pliki (4357 plików w 381 folderach, rozmiar 611,73 MB)
Kompresja standardowa/Stopień kompresji348,12 MB/43,09%315,52 MB/48,42%355,85 MB/41,83%326,85 MB/46,57%357,19 MB/41,61%310,84 MB/49,19%356,21 MB/41,77%340,75 MB/44,30%
Kompresja maksymalna/Stopień kompresji344,14 MB/43,74%314,26 MB/48,63%353,23 MB/42,26%323,32 MB/47,15%356,85 MB/41,66%293,14 MB/52,08%355,05 MB/41,96%337,62 MB/44,81%
Czas wykonania standardowej kompresji plików105 s691 s107 s696 s166 s820 s406 s753 s
Czas wykonania maksymalnej kompresji plików151 s939 s265 s897 s179 s1428 s406 s852 s
0
Zamknij

Choć staramy się je ograniczać, wykorzystujemy mechanizmy takie jak ciasteczka, które pozwalają naszym partnerom na śledzenie Twojego zachowania w sieci. Dowiedz się więcej.