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ż.
| Program | ZIP (PKZip) | RAR | ZIP (WinZip) | Ace | ARJ32 | 7-Zip | GZip | BZip2 |
| 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 aplikacja | PKZip 6.0.147 | WinRAR 3.30 | WinZip 9.0 | WinAce Archiver 2.5 | ARJ32 3.11 | 7-Zip 3.13 | linia komend/1.3.5 | linia komend/1.0.2 |
| Producent/autor i licencja | PKWare (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 kompresji | LZH, LZW, Shannon-Fano, Huffman | LZSS (wariant LZ77) + Huffman | LZH, LZW, Shannon-Fano, Huffman | zmodyfikowany LZ77 + Huffman | LZSS + Huffman | LZMA (zmodyfiko-wany LZ77) | Shannon-Fano, Huffman | Burrows-Wheeler + Huffman |
| Ocena ogólna (POWER) | 100 | 98 | 94 | 94 | 88 | 86 | 82 | 78 |
| Pliki tekstowe (*.RTF, rozmiar 38,63 MB) | ||||||||
| Kompresja standardowa/Stopień kompresji | 10,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ń kompresji | 10,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ów | 4 s | 36 s | 5 s | 40 s | 10 s | 66 s | 6 s | 24 s |
| Czas wykonania maksymalnej kompresji plików | 8 s | 30 s | 21 s | 44 s | 15 s | 120 s | 11 s | 32 s |
| Pliki dźwiękowe (*.WAV, rozmiar 593,18 MB) | ||||||||
| Kompresja standardowa/Stopień kompresji | 571,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ń kompresji | 571,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ów | 100 s | 260 s | 118 s | 312 s | 140 s | 913 s | 465 s | 791 s |
| Czas wykonania maksymalnej kompresji plików | 120 s | 268 s | 161 s | 795 s | 162 s | 1294 s | 465 s | 931 s |
| Pliki graficzne (*.BMP, rozmiar 58,71 MB) | ||||||||
| Kompresja standardowa/Stopień kompresji | 8,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ń kompresji | 8,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ów | 4 s | 20 s | 5 s | 32 s | 10 s | 37 s | 23 s | 62 s |
| Czas wykonania maksymalnej kompresji plików | 8 s | 29 s | 14 s | 36 s | 14 s | 66 s | 31 s | 70 s |
| Pliki bazy danych (*.MDB, rozmiar 104,76 MB) | ||||||||
| Kompresja standardowa/Stopień kompresji | 21,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ń kompresji | 19,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ów | 10 s | 52 s | 11 s | 59 s | 20 s | 88 s | 46 s | 83 s |
| Czas wykonania maksymalnej kompresji plików | 15 s | 86 s | 37 s | 62 s | 25 s | 184 s | 62 s | 104 s |
| Pliki PDF (*.PDF, rozmiar 48,49 MB) | ||||||||
| Kompresja standardowa/Stopień kompresji | 34,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ń kompresji | 33,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ów | 8 s | 58 s | 8 s | 57 s | 12 s | 66 s | 21 s | 70 s |
| Czas wykonania maksymalnej kompresji plików | 8 s | 74 s | 10 s | 57 s | 12 s | 92 s | 22 s | 75 s |
| Pliki wykonywalne (rozmiar 38,90 MB) | ||||||||
| Kompresja standardowa/Stopień kompresji | 26,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ń kompresji | 26,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ów | 7 s | 44 s | 8 s | 45 s | 10 s | 53 s | 18 s | 23 s |
| Czas wykonania maksymalnej kompresji plików | 8 s | 51 s | 15 s | 46 s | 11 s | 79 s | 21 s | 37 s |
| Różne pliki (4357 plików w 381 folderach, rozmiar 611,73 MB) | ||||||||
| Kompresja standardowa/Stopień kompresji | 348,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ń kompresji | 344,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ów | 105 s | 691 s | 107 s | 696 s | 166 s | 820 s | 406 s | 753 s |
| Czas wykonania maksymalnej kompresji plików | 151 s | 939 s | 265 s | 897 s | 179 s | 1428 s | 406 s | 852 s |
