ŖpPOPAKUJMY...Ŗ0 Ŗ1ŗ0czyli nieco teoriiŖ0ŗ0 W zapisanym tekōcie powtarzjā siė wielokrotnie te same sīowa, pewne litery alfabetu wystėpujā o wiele czėōciej niū pozostaīe... Nawet bardzo rozbudowane programy "pakerskie" bazujā na tych oczywistych faktach! Teoria kompresji - dyscypliny z pograniczna matematyki i informatyki - jest stosunkowo mīoda. Prace Huffmana czy Shannona siėgajā lat 60-tych. Popularne dziō pakery korzystajā z algorytmów opracowanych pod koniec lat 70-tych. Obecnie znanych jest kilka zasadnicznych metod kompresji danych. Kaūda z nich moūe byź jednak realizowana na wiele sposobów i doōź znacznie róūniź siė w szczegóīach - stād spora iloōź programów sīuūācych kompresji i spore (niekiedy) róūnice w ich efektywnoōci. ŗ1Najprostszā metodā kompresji jest RLE (Run Lenght Encoding).ŗ0 Jeōli w pakownaym pliku zdarzajā siė ciāgi identycznych bajtów, wtedy zamiast zapisywaź je dosīownie wystarczy podaź iloōź powtorzeļ i "powiedzieź" co siė powtarza. Np. ciāg bajtów "AAAAA" moūna zastāpiė symbolem "5A". Metoda ta jest bardzo nieefektywna w stosunku do tekstów - jedyne co siė tam w miarė czėsto powtarza to spacje. Natomiast moūe to przynieōź efekty w np. odniesieniu do rysunków (szczególnie w nieduūej palecie kolorów), gdzie np. niebo to 1500 kolejnych pixeli w kolorze niebieskim... w takim wypadku moūemy uzyskaź nawet zaskakujāco duūy procent kompresji. ŗ1Innym popularnym algorytmem jest algorytym Huffmana.ŗ0 Wykorzystuje on fakt róūnej czėstoōci wystėpowania poszczególnych znaków. W typowym angielskim tekōcie gīoska "e" pojawwa siė blisko 60 x (!) czėōciej niū "z". Litery wielkie wystėpujā rzadziej niū maīe, zaō cyfry spotyka siė sporadycznie. Normalnie jednej literze odpowiada bajt, czyli 8 bitów (wbrew rewelacjom pana Pampucha, który odkryī bajty 16-bitowe...). Spróbujmy jednak zapisaź je na grupach 5-cio bitowych. Poniewaū za pomocā 5 bitów moūemy zapisaź 32 róūne symbole, tylko czėōź liter uda siė zapisaź za pomocā jednej grupy. Jednā z kombinacji bitów musimy zarezerwowaź jako znak specjalny. Posīuūy do zakodowania pozostaīych liter (jako "prefiks"), które w ten sposób otrzymajā kodu dwu- a nawet trójgrupowe. Jeōli jednak litera "e" otrzyma kod krótszy, zaō "z" dīuūszy róūnica w czėstoōci ich wystėpowania sprawi, ūe zapis bėdzie duūo krótszy. ŗ1Bardzo dobre wyniki daje tzw. kodowanie arytmetyczne.ŗ0 Spróbujmy spojrzeź na otrzymywany skompresowany plik jak na bezpostaciowy ciāg bitów. Jeōli wyobrazimy sobie, ūe kaūdy bit oznacza cyfrė (dwójkowā) po przecinku, to caīy plik stanie siė liczbā rzeczywistā z zakresu od 0 do 1. Zamiast zapamiėtywaź caīā liczbė zapamiėtujemy przedziaī, w którym siė znajduje. Kolejne znaki czytane z wejōcia powodujā dopisywanie na wyjōciu bitów (cyfr) precyzujācych granicė przedziaīu. Im wiėksze jest prawdopodobieļstwo wystėpowania czytanego symbolu, tym mniej bitów dopisujemy na wyjōciu. Choź metoda ta moūe byź efektywna, to trudno jednak stworzyź ogólny algortym pakujācy równie dobrze kaūdy rodzaj danych. Tak czy siak dziaīaīby on bardzo wolno i wymagaī ogromnej pamiėci. Dlatego rzadko siė go stosuje. ŗ1Kilka innych pakerów opiera siė na zastėpowaniu powtarzajācych siė ciāgów bajtów ich "wskazaniem" w specjalnym sīowniku.ŗ0 Algorytmy te znane sā pod nazwami LZ77 lub LZ78 (lub ogólnie LZ). Nazwa pochodzi od nazwisk programistów: Lempel-Ziv, zaō numer oznacza rok w jakim zostaī stworzony. Ulepszony algortym nosi nazwė LZW (Lepmpel-Ziv-Wlech). Ogolna zasada algorytmu LZ78 wyglāda (mniej wiėcej) nastėpujāco: kaūdā napotkanā nowā frazė wprowadza siė do specjalnego sīownika. Jeōli fraza zostanie napotkana ponownie wówczas zamiast niej zapisuje siė jej indeks. Przykīadowo skompresujmy tekst: ŗ1Kurwa, ja ciė zajebiėŗ0 ŗ2 1 / 2/ 3/ 4/ 5ŗ0 Teraz nastėpne zdanie, np. ŗ1Kurwa, którā ja widzė, lubi ciė ŗ0 bėdzie wyglādaī nastėpujāco: ŗ21\2\ŗ1którā\ŗ23\ŗ1widzė\ŗ22\ŗ1lubi\ŗ24 6 7 8ŗ0 czyli w sumie otrzymamy ciāg: ŗ21\2\6\3\7\2\8\4ŗ0 itd. (pominėliōmy tu spacje) Widaaź sporā redukcjė iloōci zapisanych bajtów, nieprawdaū? Jak juū wspomniano ŗ1wiėkszoōź popularnych packerów stosuje rozmaite wersje algorytmu LZ77.ŗ0 Jest on bardzo zbliūony do LZ78, z tym ūe stosuje on "sīownik" zakīadany nie dla caīego pliku a dla "okienka", którego wielkoōź zwykle waha siė w granicach 4-64 Kb. Dane w nim zawarte tworzā sīownik. Jeōli ciāg bajtow wystāpi ponownie, zamiast niego zapisuje siė bieūācā pozycjė w sīowniku i dīugoōź powtarzajācej siė frazy. Duūā zaletā metody jest bardzo īatwe i stosunkowo szybkie depakowanie danych. ŗ2Ogólnie naleūy pamiėtaź, ūe nie ma uniwersalnych pakerówŗ0, równie dobrze radzācych sobie z kaūdym rodzajem danych. Zatem naleūaīoby stosowaź rozmaite algorytmy w odniesieniu do rozmaitych typów danych. ŗ2Program, który ōwietnie pakuje np. tekst moūe caīkowicie zawodziź przy grafice czy muzyce...ŗ0 Ogólnie jeōli np. tekst udaje siė spakowaź o 40-45% a program o 20-30-50% to moūemy juū byź zadowoleni ze stosowanego pakera (choź trafia siė czasem sytuacja, w której np. udaje siė spakowaź jakiō plik o 90% lub teū pakuje siė o 5 czy 10% to sā raczej wyjātki od reguīy). Wiele alogrytmow ma wrėcz ustalony max. stopieļ kompresji, wyūej którego "nie podskoczy" ale na szczėōcie nie istnieje teoretyczna górna granica spakowania danych (choź ofcoz raczej nie siėgnie ona 100% :-)). ŗ2Natomiast nie da siė w ogóle skompresowaź szumu lub innych danych o rozkīadzie losowym.ŗ0 Ŗ1ŗ0 - na podst. GW - MassaŖ0ŗ0 Ps. Wklepujācy nie odpowiadajā za poprawnoōź informacji zawartych w tym tekōcie!