Witam!
Zastanawiam się jak są kompresowane pliki, czy są jakieś ogólnodostępne algorytmy do kompresowania? Czy są one skomplikowane?
Pozdrawiam,
Frubi
0
0
0
bzip i gzip są otwarte, ale też, jak dla mnie, skomplikowane
0
Ja może jakoś sformułuję wypowiedź:
- jak są kompresowane?
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
- czy są ogólnodostępne algorytmy?
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.
0
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
0
Swojego czasu na wiki czytałem arta "kompresja fraktalna".
0
z "dziwactw" dodam jeszcze falki
0
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ś.
0
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? :)
0
czyli wyszstko opiera sie do przetworzenia informacji w inna :0
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).
0
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:
- lz77, lzss, lzw i inne: zastępowanie 'spójnego' ciągu znaków, który już wystąpił wcześniej w danych wejściowych specjalnym kodem (np: indeks łańcucha w słowniku lub referencja do wcześniejszego miejsca w buforze wejściowym),
- ppm: szacowanie prawdopodobieństwa znaków na podstawie statystyk w akutalnym n- znakowym kontekście (kontekst to znaki ściśle poprzedzające aktualnie kodowany znak). gdy statystyki w aktualnym kontekście są niewystarczające, enkoder może wypuścić kod ucieczki i kodować używając krótszego kontekstu,
- lzp: może być bazowany na poprzednich dwóch rodzinach. lzp przetrzymuje informacje o ostatnim znaku (lub indeksie) w danym kontekście. oszczędność uzyskuje się poprzez możliwość opuszczenia przesyłania indeksu (lz77) lub lepszemu dopasowaniu statystyk (ppm),
- bwt: transformata burrowsa- wheelera - polega na utworzeniu macierzy z ciągu wejściowego (macierz ma rozmiar kwadratowy względem rozmiaru ciągu wejściowego). poszczególne wiersze są zbudowane z ciągu wejściowego obróconego o ileś znaków (każdy wiersz o iiną ilość znaków). potem macierz jest sortowana leksykograficznie i wypuszczana jest ostatnia kolumna. na tym etapie nie ma jeszcze żadnej kompresji, ale wypuszczony ciąg zawiera dużo sekwencji powtarzających się znaków, które można łatwo skompresować za pomocą rle (run length encoding),
- i inne, wliczając kodeki specjalizwane do obsługi multimediów (kodeki audio, wideo, obrazu, etc),