Jak działa kompresja plików?

Inżynierowie oprogramowania zawsze opracowali nowe sposoby dopasowania dużej ilości danych do małej przestrzeni. To prawda, gdy nasze dyski twarde były niewielkie, a pojawienie się Internetu właśnie sprawiło, że stało się to bardziej krytyczne. Kompresja plików odgrywa dużą rolę w łączeniu nas, pozwalając nam przesyłać mniej danych w dół, dzięki czemu możemy mieć szybsze pobieranie i dopasowywać więcej połączeń do obciążonych sieci.

Więc jak to działa?

Odpowiedź na to pytanie wymagałaby wyjaśnienia bardzo skomplikowanej matematyki, z pewnością więcej niż możemy opisać w tym artykule, ale nie musisz dokładnie rozumieć, jak to działa matematycznie, aby zrozumieć podstawy.

Najpopularniejsze biblioteki do kompresji tekstu opierają się na dwóch algorytmach kompresji, wykorzystując obie jednocześnie, aby osiągnąć bardzo wysokie współczynniki kompresji. Te dwa algorytmy to "LZ77" i "kodowanie Huffmana". Kodowanie Huffmana jest dość skomplikowane i nie będziemy tutaj szczegółowo omawiać tego. Przede wszystkim używa trochę wyszukanej matematyki, aby przypisać krótszą kody binarne do pojedynczych liter, zmniejszając rozmiary plików w procesie. Jeśli chcesz dowiedzieć się więcej na ten temat, zapoznaj się z tym artykułem o tym, jak działa kod, lub o tym wyjaśniającym w Computerphile.

Z kolei LZ77 jest względnie prosty i o tym tutaj będziemy rozmawiać. Dąży do usunięcia zduplikowanych słów i zastąpienia ich mniejszym "kluczem", który reprezentuje słowo.

Weź ten krótki fragment tekstu, na przykład:

Algorytm LZ77 przyjrzałby się temu tekstowi, zdał sobie sprawę, że trzy razy powtarza "howtogeek" i zmienia go na:

Następnie, gdy chce przeczytać tekst z powrotem, zastąpi on każdą instancję (h) "howtogeek", przywracając nas do pierwotnej frazy.

Tę kompresję nazywamy "bezstratną" - dane, które umieszczasz, są takie same, jak dane, które dostajesz. Nic nie jest stracone.

W rzeczywistości LZ77 nie używa listy kluczy, ale zastępuje drugie i trzecie wystąpienie linkiem z powrotem w pamięci:

Tak więc teraz, gdy dojdzie do (h), będzie to wyglądać z powrotem do "howtogeek" i zamiast tego czytać.

Jeśli jesteś zainteresowany bardziej szczegółowym wyjaśnieniem, to wideo z Computerphile jest bardzo pomocne.

To jest wyidealizowany przykład. W rzeczywistości większość tekstu jest skompresowana za pomocą klawiszy tak małych, jak tylko kilka znaków. Na przykład słowo "the" zostanie skompresowane nawet wtedy, gdy pojawi się w słowach takich jak "tam", "ich" i "wtedy". Przy powtarzającym się tekście można uzyskać szalone współczynniki kompresji. Weź ten plik tekstowy ze słowem "howtogeek" powtórzonym 100 razy. Oryginalny plik tekstowy ma trzy kilobajty. Po skompresowaniu zajmuje to tylko 158 bajtów. To prawie 95% kompresja.

Oczywiście, jest to dość ekstremalny przykład, ponieważ powtarzaliśmy to samo słowo w kółko. Ogólnie rzecz biorąc, prawdopodobnie uzyskasz około 30-40% kompresji przy użyciu formatu kompresji, takiego jak ZIP, w pliku, który zawiera głównie tekst.

Algorytm LZ77 odnosi się do wszystkich danych binarnych, nawiasem mówiąc, a nie tylko tekstu, choć tekst jest na ogół łatwiejszy do skompresowania ze względu na liczbę powtarzających się słów, których używa większość języków. Język taki jak chiński może być nieco trudniejszy do skompresowania niż angielski, na przykład.

Jak działa kompresja obrazu i wideo?

Kompresja wideo i audio działa bardzo różnie. W przeciwieństwie do tekstu, w którym można uzyskać kompresję bezstratną, a żadne dane nie są tracone, obrazy mają tzw. "Kompresję stratną", w której tracimy dane. Im bardziej kompresujesz, tym więcej tracisz danych.

To właśnie prowadzi do tych okropnie wyglądających plików JPEG, które ludzie wielokrotnie przesłali, udostępnili i zrzutu ekranu. Za każdym razem, gdy obraz jest kompresowany, traci część danych.

Oto przykład. To jest zrzut ekranu, który nie został skompresowany.

Następnie wziąłem ten zrzut ekranu i wielokrotnie przeprowadzałem go w Photoshopie, za każdym razem eksportując go jako JPEG o niskiej jakości. Oto wynik.

Wygląda całkiem źle, prawda?

Cóż, jest to tylko najgorszy scenariusz, eksportując przy 0% jakości JPEG za każdym razem. Dla porównania, jest to JPEG o jakości 50%, który jest prawie nie do odróżnienia od źródłowego obrazu PNG, chyba że wysadzisz go i przyjrzysz się bliżej.

Plik PNG tego obrazu miał rozmiar 200 KB, ale ten JPEG o jakości 50% ma tylko 28 KB.

Jak więc oszczędzić tak dużo miejsca? Cóż, algorytm JPEG to wyczyn inżynierii. Większość obrazów zapisuje listę numerów, przy czym każda liczba reprezentuje pojedynczy piksel.

JPEG tego nie robi. Zamiast tego przechowuje obrazy przy użyciu czegoś, co nazywa się Discrete Cosine Transform, która jest zbiorem fal sinusoidalnych połączonych ze sobą w różnym natężeniu. Używa 64 różnych równań, ale większość z nich się nie wykorzystuje. Oto, jaki jest suwak jakości dla JPEG w Photoshopie i innych aplikacjach graficznych - wybierz ile równań użyć. Następnie aplikacje używają kodowania Huffmana, aby jeszcze bardziej zmniejszyć rozmiar pliku.

Daje to JPEG'om niesamowicie wysoki współczynnik kompresji, co może zmniejszyć plik, który w zależności od jakości może zmniejszyć liczbę megabajtów do kilku kilobajtów. Oczywiście, jeśli użyjesz go za dużo, otrzymasz to:

Ten obraz jest okropny. Jednak niewielkie rozmiary kompresji JPEG mogą mieć znaczny wpływ na rozmiar pliku, a to sprawia, że ​​JPEG jest bardzo przydatny do kompresji obrazu na stronach internetowych. Większość zdjęć, które widzisz w Internecie, jest skompresowanych, aby zaoszczędzić na czasach pobierania, szczególnie dla użytkowników mobilnych, którzy mają słabe połączenia transmisji danych. W rzeczywistości wszystkie obrazy w How-To Geek zostały skompresowane, aby ładowanie strony było szybsze i prawdopodobnie nigdy nie zauważyłeś.

Kompresja wideo

Wideo działa trochę inaczej niż obrazy. Można by pomyśleć, że po prostu kompresują każdą klatkę wideo za pomocą JPEG i na pewno to robią, ale jest lepsza metoda dla wideo.

Używamy czegoś, co nazywa się "kompresją międzyramkową", która oblicza zmiany między każdą klatką i przechowuje je tylko. Na przykład, jeśli masz stosunkowo mało ujęcia, które zajmuje kilka sekund w filmie, dużo miejsca zostanie zapisane, ponieważ algorytm kompresji nie musi przechowywać wszystkich rzeczy w scenie, które się nie zmieniają. Kompresja międzyramkowa jest głównym powodem, dla którego w ogóle mamy telewizję cyfrową i wideo sieciowe. Bez tego filmy byłyby setkami gigabajtów, czyli więcej niż przeciętny rozmiar dysku twardego w 2005 roku, kiedy YouTube zaczął.

Ponadto, ponieważ kompresja międzyramkowa działa najlepiej w przypadku głównie wideo stacjonarnego, dlatego konfetti niszczy jakość wideo.

Uwaga: GIF tego nie robi, dlatego animowane GIF-y są często bardzo krótkie i małe, ale wciąż mają dość duży rozmiar pliku.

Inną rzeczą, o której należy pamiętać o wideo, jest jego bitrate - ilość danych dozwolona w każdej sekundzie. Jeśli na przykład Twoja szybkość transmisji bitowej wynosi 200 kb / s, wideo będzie wyglądało dość źle. Jakość rośnie wraz ze wzrostem przepływności, ale po kilku megabajtach na sekundę uzyskuje się coraz mniejsze zyski.

Jest to powiększona ramka zaczerpnięta z filmu meduzy. Ten po lewej stronie ma 3 Mb / s, a ten po prawej 100 Mb / s.

30-krotny wzrost rozmiaru pliku, ale nie wzrost jakości. Ogólnie rzecz biorąc, filmy z YouTube mieszczą się w granicach 2-10 Mb / s, w zależności od połączenia, ponieważ nic więcej nie zostanie zauważone.

To demo działa lepiej z rzeczywistym filmem, więc jeśli chcesz to sprawdzić, możesz pobrać te same filmy testowe, które są tutaj używane.

Kompresja dźwięku

Kompresja dźwięku działa bardzo podobnie do kompresji tekstu i obrazu. Gdzie JPEG usuwa szczegóły z obrazu, którego nie zobaczysz, kompresja audio robi to samo dla dźwięków. Być może nie będziesz musiał słyszeć skrzypienia gitary na strunie, jeśli rzeczywista gitara jest dużo, dużo głośniejsza.

MP3 używa również bitrate, począwszy od niskiego końca 48 i 96 kb / s (low end) do 128 i 240 kb / s (całkiem nieźle) do 320 kb / s (high-end audio), a usłyszysz różnicę tylko dzięki wyjątkowo dobrym słuchawkom ( i uszy).

Istnieją również bezstratne kodeki kompresji audio - z których najważniejszym jest FLAC - który używa kodowania LZ77, aby dostarczyć całkowicie bezstratny dźwięk. Niektórzy ludzie przeklinają doskonałą jakość dźwięku FLAC, ale z przewagą MP3, wydaje się, że większość ludzi albo nie może powiedzieć, albo nie ma nic przeciwko różnicy.