Jaka jest koncepcja kompresji zip?

Question

Jaka jest koncepcja kompresji zip? Rozumiem koncepcję usuwania pustej przestrzeni itp., Ale przypuszczalnie trzeba dodać coś, aby powiedzieć, ile/gdzie ta wolna przestrzeń musi zostać dodana z powrotem podczas dekompresji?

Jaki jest podstawowy proces kompresji strumienia bajtów?

Answer 1

Dobrym miejscem na rozpoczęcie byłoby odszukanie schematu kompresji Huffman. Podstawową ideą huffman jest to, że w danym pliku niektóre bajty pojawiają się częściej niż inne (w pliku tekstowym wiele bajtów nie pojawi się w ogóle). Zamiast tego spędź 8 bitów, aby zakodować każdy bajt, czemu nie użyć krótszej sekwencji bitów do kodowania najczęstszych znaków i dłuższych sekwencji do kodowania mniej popularnych znaków (sekwencje te są określane przez utworzenie drzewa huffman).

Po uzyskać uchwyt na użyciu tych drzew do kodowania/pliki dekodowania na podstawie częstości znaków, wyobraź sobie, że wtedy zacząć pracować na częstotliwości słowa - zamiast kodowania „oni” jako ciąg 4 znaków, to dlaczego nie uznać go być pojedynczym bohaterem ze względu na jego częstotliwość, dzięki czemu można mu przypisać własny liść w drzewie Huffmana. Jest to mniej więcej podstawa kompresji ZIP i innych kompresji bezstratnej - szukają wspólnych "słów" (sekwencji bajtów) w pliku (w tym sekwencji o długości 1 bajta, jeśli są dość powszechne) i używają drzewa do ich kodowania. Plik zip musi wtedy zawierać informacje o drzewie (kopię każdej sekwencji i ile razy się pojawi), aby umożliwić odtworzenie drzewa i zdekodowanie reszty pliku.

Kontynuacja:

Aby lepiej odpowiedzieć na oryginalne pytanie, idea bezstratnej kompresji nie jest tak dużo, aby usunąć pustą przestrzeń, ale usunąć redundent informacji.

Jeśli utworzyłeś bazę danych do przechowywania tekstów muzycznych, możesz znaleźć dużo miejsca do przechowywania refrenu, który powtarza się kilka razy. Zamiast używać całej tej przestrzeni, możesz po prostu umieścić słowo CHORUS przed pierwszym wystąpieniem linii chóru, a następnie za każdym razem, gdy refren ma się powtarzać, po prostu użyj CHORUSA jako miejsca na miejsce (w rzeczywistości jest to raczej pomysł za kompresją LZW - w LZW każda linia utworu miała numer pokazany przed nim.Jeśli linia powtarza się później w utworze, a następnie wypisać całą linię, pokazany jest tylko numer)

Answer 2

Pojęcie kompresji to zasadniczo statystyczny. Jeśli masz serię bajtów, szansa na to, że bajt N jest X w praktyce, zależy od rozkładu wartości poprzednich bajtów 0..N-1. Bez kompresji można przydzielić 8 bitów dla każdej możliwej wartości X. Przy kompresji ilość bajtów przydzielonych dla każdej wartości X zależy od szacowanej szansy p (N, X).

Na przykład, biorąc pod uwagę sekwencję "aaaa", algorytm kompresji może przypisać wysoką wartość do p (5, a) i niższe wartości do p (5, b). Gdy p (X) jest wysokie, łańcuch bitowy przypisany do X będzie krótki, gdy p (X) jest niski, używany jest długi łańcuch bitowy. W ten sposób, jeśli p (N, X) jest dobrym oszacowaniem, średnia długość łańcucha bitowego będzie mniejsza niż 8 bitów.

Answer 3

Podstawowa koncepcja polega na tym, że zamiast używać ośmiu bitów do reprezentowania każdego bajtu, używa się krótszych reprezentacji dla częstszego występowania bajtów lub sekwencji bajtów.

Na przykład, jeśli plik składa się wyłącznie z 0x41 bajtów (A) powtarzające się szesnaście razy, a następnie zamiast reprezentujący go jako sekwencja 8-bitowym 01000001 skrócić to do sekwencji 1-bitowym 0. Następnie plik może być reprezentowany przez 0000000000000000 (szesnaście 0 s).Tak więc plik z bajtem 0x41 powtórzony szesnaście razy może być reprezentowany przez plik składający się z bajtu 0x00 powtórzonego dwukrotnie.

Więc co mamy tutaj jest to, że dla tego pliku (0x41 powtarzane szesnaście razy) bity 01000001 nie przenoszą żadnych dodatkowych informacji na bit 0. Tak więc w tym przypadku wyrzucamy obce bity, aby uzyskać krótszą reprezentację.

To jest podstawowa idea kompresji.

Jako inny przykład, rozważmy wzór o osiem bajta

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

i teraz go powtórzyć 2048 razy. Jednym ze sposobów podejścia powyżej jest przedstawienie bajtów za pomocą trzech bitów.

000 0x41 
001 0x42 
010 0x43 
011 0x44 
100 0x45 
101 0x46 
110 0x47 
111 0x48 

Teraz możemy reprezentować powyższy wzór bajtu przez 00000101 00111001 01110111 (jest to wzór trzy-bajtowy 0x05 0x39 0x77) powtarzane 2048 razy.

Ale jeszcze lepszym rozwiązaniem jest reprezentują wzorzec bajta

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

przez pojedynczy bit 0. Następnie możemy przedstawić powyższy wzór bajtu przez 0 powtórzony 2048 razy, który staje się bajtem 0x00 powtórzonym 256 razy. Teraz musimy tylko do przechowywania słownika

0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

a wzór bajtowy 0x00 powtarzane 256 razy i skompresowany plik z 16384 bajtów (modulo słownika) 256 bajtów.

To, w dużym skrócie, to, jak działa kompresja. Cała sprawa sprowadza się do znalezienia krótkich, wydajnych reprezentacji sekwencji bajtów i bajtów w danym pliku. To prosty pomysł, ale szczegóły (znalezienie reprezentacji) mogą być dość trudne.

Patrz na przykład:

1. Data compression
2. Run length encoding
3. Huffman compression
4. Shannon-Fano coding
5. LZW