Jak działa kompresja plików?

Więc zdałem sobie sprawę, że kompresję plików uważam za oczywistą. Możliwość łączenia kilku plików w jeden i sprawienia, by był mniejszy niż którykolwiek z nich, jest czymś, co akceptuję jako fakt, ale jak to działa?

Mam ograniczoną wiedzę na ten temat, która ma coś wspólnego z zastąpieniem wszystkich duplikatów wpisów wskaźnikami, aby zmniejszyć się w ten sposób, ale poza tym nie mam pojęcia!

Ponieważ zawsze jestem otwarty na nową wiedzę, jak wyobrażam sobie, że większość z nas tutaj jest, pomyślałem, że zapytam. Więc, SuperUser, jak działa kompresja tak właściwie praca?

compression archiving Phoshi
źródło

The Artykuł w Wikipedii to dobry początek, ale byłoby miło mieć bardziej szczegółowe wyjaśnienia. Dobre pytanie (choć byłem pewien, że już takie pytanie mamy, ale wydaje się, że nie).

Gnoupi

@Gououpi: Rzeczywiście, pierwszą rzeczą, jaką zrobiłem, było przeszukanie, ponieważ byłem pewien, że tutaj jest jeden. Najwyraźniej nie, więc starałem się to naprawić: P

Phoshi

mamy tag „co-jest”, gdy wysyłasz zdjęcia i „wot izzit ??”; zauważyłem potrzebę tagu „jak to działa”, ale to za długo i „jak to działa” brzmi głupio. „wyjaśnij” może to zrobić.

quack quixote

@ quack quack: Ah, dzięki. Szukałem w autouzupełnieniu tagu typu „plz-send-the-explanation”, ale nie mogłem go znaleźć.

Phoshi

zbliżyłem się do tworzenia tagu „jak” kilka razy ... ale „wyjaśnij” jest prawdopodobnie lepsze. „samouczek” i „howto” oraz „początkujący” są częściowo stosowane, ale nie do końca pasują.

quack quixote

Odpowiedzi:

Kompresja bezstratna

Bezstratna kompresja nie powoduje utraty danych. Wszystko, co jest wprowadzane, można uzyskać idealnie. Działa to dobrze w przypadku plików tekstowych lub binarnych, w których zostanie zauważony najmniejszy błąd.

Kompresja plików polega na pobieraniu plików i skanowaniu wzorców oraz przekładaniu tych wzorców na coś, co zajmuje mniej miejsca.

Na przykład „AAAAAAAA” można przekształcić w „8A”.

Przyznaje, że nie tak to działa dokładnie, ponieważ wtedy masz problem, co jeśli „8A” było w jawnym tekście. Zdekompresujesz plik i byłoby źle. Dobrym miejscem do rozpoczęcia jest Wikipedia lub Algorytm kompresji danych LZW .

Poniżej został skopiowany prosty kod pseudo-kod:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

Cała kompresja wykorzystuje słownik wyszukiwania, który służy do kompresji i dekompresji pliku. Im większy słownik, tym bardziej możesz go skompresować, chociaż trafisz na Prawo malejących zwrotów .

Warto również zauważyć, że kompresja nie zawsze daje mniejszy plik. Są sytuacje (z małymi plikami lub podczas kompresji danych losowych ) to zrobisz nie uzyskać mniejszy plik po kompresji. Było trochę zabawy wyzwania odnoszące się do możliwości kompresji losowych danych.

"Kompresja stratna

Powyższe dotyczy głównie kompresja bezstratna . Inne typy kompresji używane w aplikacjach wideo / audio, takich jak MP3, JPG i h.264, są przykładami Kompresja stratna .

Kompresja stratna polega na odrzuceniu najmniej prawdopodobnych danych. W audio brzmi to około 30 000 Hz i poniżej 100 Hz, wraz z innymi różnymi rzeczami. W obrazie (statycznym) usuwa różne rzeczy i łączy piksele razem, a także odrzuca dane.

Kompresja stratna jest formą kodowanie transformacji . Uśrednia dane w celu zmniejszenia ogólnego rozmiaru. Na przykład blok 10 pikseli w obrazie, wszystkie nieco inne kolory mogą zostać połączone w jeden kolor, a tym samym skompresowane.

W kompresji wideo często umieszczane są instrukcje dotyczące tylko przerysowywania pikseli, które zmieniły się od ostatniej klatki, lub klatka kluczowa .

Josh K
źródło

Należy zauważyć, że jest to wyjaśnienie wyłącznie kompresji bezstratnej, rodzaju, dla którego można odzyskać dokładne dane początkowe (najprawdopodobniej używane przez programy do archiwizacji). Istnieją inne rodzaje kompresji, w których tracisz jakość przy mniejszym rozmiarze, na przykład w JPG, MP3 itp.

Gnoupi

Pierwszy przykład Josha jest formą prawdziwej metody kompresji o nazwie Kodowanie Run-Length, a „8A” zostałoby skompresowane do „181A”. Oczywiście jego ostatni akapit ma tu zastosowanie; RLE działa najlepiej na danych z wieloma duplikatami.

Dour High Arch

Dodałem tytuły bezstratne / stratne i dopracowałem trochę więcej. Warto zauważyć, że najlepszym sposobem na dalsze zrozumienie tego jest po prostu przeczytanie artykułu w wikipedii.

Josh K

Kompresja polega na znajdowaniu wzorców w danych, a następnie zastępowaniu tych wzorców specjalnymi mniejszymi wzorami. Dekompresja jest odwrotnością: znajdź specjalne wzory i zastąp je większymi wzorami, które reprezentują. Ważna jest wiedza na temat możliwych wzorców; na przykład wzorce znalezione w tekście mogą być zupełnie inne niż w obrazach. Niektóre techniki kompresji są stratne; nie gwarantują, że rozszerzenie dokładnie odzyska dane wejściowe. Zwykle jest to dobre dla danych analogowych, takich jak muzyka i obrazy, jeśli strata jest wystarczająco mała. Ale dane takie jak tekst muszą być skompresowane za pomocą bezstratnych technik.

Ważne jest, aby uświadomić sobie, że niemożliwe jest skompresowanie, bez strat, losowych danych nawet o jeden bit. Rozważmy plik z N bitami danych binarnych. Są 2 ^ N możliwych plików. Jeśli kompresujesz któryś z tych plików pojedynczym bitem, więc skompresowany plik ma rozmiar N-1 bitów, są tylko 2 ^ (N-1) możliwe skompresowane reprezentacje. Innymi słowy, każdy możliwy skompresowany plik musi reprezentować więcej niż jeden możliwy nieskompresowany plik. Bez unikalnej skompresowanej reprezentacji algorytm dekompresji nie może zagwarantować bezstratnej dekompresji.

Fred
źródło

plik może być nieskompresowany (przymiotnik), ale nie można go zdekompresować (czasownik). zamiast tego jest zdekompresowany .

quack quixote