Witam!
Zastanawiam się jak są kompresowane pliki, czy są jakieś ogólnodostępne algorytmy do kompresowania? Czy są one skomplikowane?
Pozdrawiam,
Frubi
Witam!
Zastanawiam się jak są kompresowane pliki, czy są jakieś ogólnodostępne algorytmy do kompresowania? Czy są one skomplikowane?
Pozdrawiam,
Frubi
bzip i gzip są otwarte, ale też, jak dla mnie, skomplikowane
Ja może jakoś sformułuję wypowiedź:
Ogólnie metody polegają na wyeliminowaniu nadmiaru informacji z pliku. Opierają się na przykład na zastępowaniu najczęstszych znaków (na przykład bajtów, ale nie koniecznie) najkrótszymi ciągami bitów [kompresja Huffmana], eliminowaniu wielu powtarzających się symboli zapisem <ilość, symbol> [kompresja RLE], zastępowaniu kombinacji symboli, której już wystąpiły symbolami zarezerwowanymi [kompresja LZW] itp. Wiele metod kompresji wykorzystuje informacje statystyczne lub tak zwaną geometrię informacji - jeśli w pliku zapisane są tylko 124 bajty o wartościach od 32 do 160, to zamiast tracić [8 bitów * 124 = 992 bity =.. ] 124 bajty w pliku, można zapisać dane na 7 bitach (od 0 do 128) i dopisać 1 bajt informujący o przesunięciu, czyli [7 bitów * 124 bajty + 8 bitów * 1 bajt = 876 bitów =.. ] 110 bajtów; 14 bajtów zysku
Tak. W zależności od rodzaju plików rozróżnia się kompresje stratne i bezstratne. Jak wynika z nazwy, skompresowany bezstratnie plik da się odtworzyć do postaci oryginalnej. Kompresja stratna dotyczy konkretnych formatów - na przykład usuwanie z dźwięku tonów lub zmian niesłyszalnych dla niewprawnego ucha, czy też zapisywanie fragmentów obrazu w postaci informacji o harmonicznych zmianach koloru, co pozwala pominąć skrajne częstotliwości, czyli obciąć informację [kompresja użyta w jpg]. Pliki binarne, ze względu na formę i wagę informacji kompresuje się zawsze bezstratnie.
Zachęcam do przejrzenia powyższych linków oraz Wikipedii.
jeszcze jest takie cos jak kwadratowanie :P np. masz podobne kolory w jakims kwadracie ktory jest dosc duzy zamiast uzywac np. 16 kolorow do opisania uzywasz 4 wartosci int lub byte
Swojego czasu na wiki czytałem arta "kompresja fraktalna".
z "dziwactw" dodam jeszcze falki
To jak już dokładamy dziwactwa to istnieje jeszcze kompresja złożona, bazująca na probabilistycznej estymacji ciągów i dużych liczb. Metodę tą wykorzystuje rodzina programów PAQ/PAsQDa/PAQAR. To najlepsze kompresory świata (przy czym ten 2 jest polską wersją) - oczywiście jakość kompresji kosztem zajętości pamięci i czasu. Coś za coś.
Szczawik napisał(a)
...bazująca na probabilistycznej estymacji ciągów i dużych liczb...
o konfuzji ambiwalencji z trendem do eskalacji redundancji mówisz? :):)
a coś konkretniej? możesz? :)
czyli wyszstko opiera sie do przetworzenia informacji w inna :0
Ogólny mechanizm polega na utworzeniu równoległych potoków przetwarzających, które w różny sposób estymują (szacują) na bazie prawdopodobieństwa i historii, jaki ciąg bitów teraz wystąpi. Dobrane są tak, aby każdy z możliwych wariantów mógł zaistnieć (zwykle ostatni estymator po prostu zwraca dane wejściowe). Na wyjście zapisywany jest numer estymatora, który ocenił prawidłowo oraz ewentualny jego zwrócony wynik.
Przy dekompresji pobierany jest numer estymatora oraz ewentualny argument i na podstawie historii jest oceniane (w sposób analogiczny jak przy kompresji), co powinno być na wyjściu. Oczywiście generacja losowa nie wchodzi w rachubę - to kompresja bezstratna.
Im więcej modeli tym łatwiej znaleźć takie, które szacując zgadną możliwie najdłuższy ciąg, ale również większy przyrost pliku, gdy słabo zgadują i trzeba do pliku zapisywać dłuższe numery estymatorów i wartości ich wyjść (zwykle jedno, przy dużej ilości dwu bajtowe).
zasada działania pakerów z rodziny paq to generalnie obliczanie prawdopodobieństwa, że nastepny bit danych będzie równy jeden (ustawiony). gdy już obliczymy tą wartość, to bit jest kodowany przez koder arytmetyczny. do obliczania prawdopodobieństwa używanych jest wiele modeli (każdy specjalizwany do konketnych typów danych, np: tekst, jpeg, rekordy, multimedia, etc), a potem wyniki są miksowane (w nowszych wersjach paq przez sieć neuronową). ogólnie ta metoda jest znana pod nazwą 'context mixing'. zajrzyj do źródeł paq8. na początku w komentarzu jest opisany pobieżnie algorytm.
tu: <url>cs.fit.edu/~mmahoney/compression/text.html</url> są benchamrki różnych pakerów. przy każdym jest kolumna opisująca używany algorytm.
jeden z prostszych pakerów opartych na idei 'context mixing' to px: <url>geocities.com/netstore101/Downloads/px.zip</url> . bazowany na pierwszej wersji paq.
oprócz cm jest jeszcze: