Jak funguje komprese souborů?

Softwaroví inženýři vždy vyvíjeli nové způsoby instalace velkého množství dat do malého prostoru. Bylo to pravdivé, když byly naše pevné disky malinké a příchod internetu právě zesílil kritiku. Komprese souborů hraje velkou roli v návaznosti na to, že nám umožňuje posílat méně dat po řádku, abychom mohli mít rychlejší stahování a více zapojení do zaneprázdněných sítí.

Tak jak to funguje?

Odpověď na tuto otázku by zahrnovala vysvětlení některé velmi složité matematiky, jistě víc, než můžeme v tomto článku pokrýt, ale nemusíte přesně porozumět tomu, jak matematicky funguje, abyste pochopili základy.

Nejpopulárnější knihovny pro kompresi textu se spoléhají na dva kompresní algoritmy, přičemž současně používají obě pro dosažení velmi vysokých poměrů komprese. Tyto dva algoritmy jsou "LZ77" a "Huffman kódování." Huffman kódování je docela komplikované, a my tu nebudeme dělat podrobnosti. Používá se nejprve nějaké fantazijní matematiky k přiřazení kratších binární kódy na jednotlivé písmena, zmenšení velikosti souborů v procesu. Chcete-li se o tom dozvědět více, podívejte se na tento článek o tom, jak tento kód funguje, nebo tento vysvětlující program pomocí souboru Computerphile.

LZ77, na druhé straně, je poměrně jednoduché a o tom budeme hovořit. Snaží se odstranit duplicitní slova a nahradit je menším "klíčem", který představuje slovo.

Vezměte si tento krátký text například:

Algoritmus LZ77 by se na tento text podíval, uvědomil si, že třikrát opakuje "howtogeek" a změnil jej na toto:

Pak, když chce přečíst text zpět, nahradí každou instanci (h) "howtogeek", přivede nás zpět k původní větě.

Říkáme kompresi, jako je tato "bezztrátová" - data, která jste vložili, jsou shodná s údaji, které se dostanou ven. Nic není ztraceno.

Ve skutečnosti LZ77 nepoužívá seznam klíčů, místo toho nahrazuje druhý a třetí výskyt odkazem zpět do paměti:

Takže teď, když se dostane do (h), bude se vrátit k "howtogeek" a číst, že místo toho.

Máte-li zájem o podrobnější vysvětlení, toto video z Computerphile je docela užitečné.

Nyní je to idealizovaný příklad. Ve skutečnosti je většina textu komprimována klávesami, která jsou malá, jako jen několik znaků. Například slovo "the" by bylo komprimováno i tehdy, když se objeví slovy "tam", "their" a "then". S opakovaným textem můžete získat některé bláznivé poměry komprese. Vezměte tento textový soubor se slovem "howtogeek" 100 krát. Původní textový soubor má velikost 3 kilobyty. Když je však komprimován, zabírá pouze 158 bajtů. To je skoro 95% komprese.

Nyní je zřejmé, že je to docela extrémní příklad, protože jsme se znovu a znovu opakovali stejné slovo. V obecné praxi se pravděpodobně dostane přibližně 30-40% komprese pomocí formátu komprese, jako je ZIP, v souboru, který je převážně textový.

Tento algoritmus LZ77 se mimochodem vztahuje na všechna binární data, a nikoliv jen na text, ačkoli text je obecně jednodušší ke kompresi vzhledem k tomu, kolik opakovaných slov používá většina jazyků. Jazyk, jako je například čínština, může být o něco těžší stlačit než angličtina.

Jak funguje komprese obrazu a videa?

Komprese videa a zvuku funguje velmi odlišně. Na rozdíl od textu, kde můžete mít bezztrátovou kompresi a žádné ztráty dat, s obrázky máme to, co se nazývá "ztrátová komprese", kde ztratíte nějaké údaje. A čím víc komprimujete, tím více ztratíte.

To je to, co vede k těm strašně vypadajícím obrázkům ve formátu JPEG, které lidé nahráli, sdíleli a vyfotografovali několikrát. Pokaždé, když se obraz komprimuje, ztratí nějaká data.

Zde je příklad. Toto je snímek, který jsem vzal, který nebyl vůbec komprimován.

Poté jsem si vzal tento snímek a spustil ho přes Photoshop několikrát, vždy když ho exportoval jako nekvalitní JPEG. Zde je výsledek.

Vypadá to docela špatně, správně?

No, je to jen nejhorší scénář, exportovat vždy při 0% JPEG kvalitě. Pro srovnání, zde je 50% kvalitní JPEG, který je téměř nerozlišitelný od zdrojového PNG obrazu, pokud jej nevyfukujete a nepřehlédnete.

PNG pro tento obrázek byl 200 KB, ale tento 50% kvalita JPEG je pouze 28 KB.

Jak ušetří tolik prostoru? Dobře, algoritmus JPEG je výkon inženýrství. Většina snímků ukládá seznam čísel, přičemž každé číslo představuje jeden pixel.

JPEG nic z toho. Místo toho ukládá obrazy pomocí něčeho nazvaného Diskrétní kosinová transformace, což je sbírka sinusových vln spojených s různou intenzitou. Používá 64 různých rovnic, ale většina z nich se nepoužívá. To je to, co dělá kvalitní posuvník JPEG ve Photoshopu a dalších obrázkových aplikacích - zvolte kolik rovnic použijete. Aplikace pak používají kódování Huffman, aby ještě více zmenšily velikost souboru.

To dává JPEGs insanely vysoký poměr komprese, který může snížit soubor, který by byl více megabajtů až na pár kilobajtů, v závislosti na kvalitě. Samozřejmě, pokud používáte příliš mnoho, skončíte tímto:

Ten snímek je strašný. Ale menší množství komprese JPEG může mít významný dopad na velikost souboru a tím je JPEG velmi užitečné pro kompresi obrazu na webových stránkách. Většina obrázků, které vidíte online, je komprimovaná, aby ušetřila časy stahování, zejména pro mobilní uživatele se špatným datovým připojením. Ve skutečnosti byly všechny obrázky na stránce How-To Geek komprimovány, aby se stránka načítala rychleji a pravděpodobně jste si nikdy nevšimli.

Komprese videa

Video funguje trochu jinak než obrázky. Myslíte si, že by prostě komprimovali každý snímek videa pomocí JPEG a určitě to dělají, ale existuje lepší metoda pro video.

Používáme něco nazývaného "interframe compression", které vypočítává změny mezi jednotlivými snímky a ukládá je pouze. Takže například pokud máte relativně pořádný záběr, který ve videosekvenci trvá několik sekund, ušetří se spousta místa, protože kompresní algoritmus nemusí ukládat všechny věci ve scéně, která se nemění. Interní komprese je hlavním důvodem, proč máme digitální televizní a webové video vůbec. Bez něj by videa byla stovky gigabajtů, což je více než průměrná velikost pevného disku v roce 2005, kdy byla služba YouTube spuštěna.

Také, protože interframe komprese funguje nejlépe s většinou stacionární video, to je důvod, proč confetti ničí kvalitu videa.

Poznámka: GIF to nedělá, což je důvod, proč animované GIF jsou často velmi krátké a malé, ale stále mají velkou velikost souboru.

Další věc, kterou je třeba pamatovat na video, je jeho bitrate - množství dat povolených každou sekundu. Pokud je váš datový tok přibližně 200 kb / s, vaše video bude vypadat hodně špatně. Kvalita vzrůstá, jakmile vzroste bitová rychlost, ale po několika megabajtech za sekundu dochází k poklesu výnosů.

Toto je zvětšený snímek pořízený z videa medúzy. Ten vlevo je 3Mb / s a ​​ten vpravo je 100Mb / s.

30x nárůst velikosti souboru, ale ani značné zvýšení kvality. Obecně platí, že videa YouTube se pohybují v rozmezí 2 až 10 Mb / s v závislosti na vašem připojení, protože by se nic víc neztratilo.

Toto demo funguje lépe se skutečným videem, takže pokud se chcete podívat na to sami, můžete si stáhnout tytéž videosoubory pro testování datové rychlosti, které se zde používají.

Komprese zvuku

Komprese zvuku funguje velmi podobně jako komprese textu a obrazu. Tam, kde JPEG odstraňuje detaily z obrázku, který se nezobrazuje, komprese zvuku se u zvuků liší. Možná nebudete muset slyšet praskání kytarového výběru na struně, pokud je skutečná kytara hodně, mnohem hlasitěji.

MP3 také používá bitovou rychlost, od dolního konce 48 a 96 kbps (dolní konec) až 128 a 240 kbps (docela dobré) až 320 kb / s (high-end audio), a pravděpodobně slyšíte pouze rozdíl s výjimečně dobrými sluchátky a uší).

K dispozici jsou také bezztrátové kompresní kodeky pro zvuk - hlavní je FLAC, který používá kódování LZ77 k dodávání úplně bezzvukového zvuku. Někteří lidé přísahou perfektní kvalitu zvuku FLAC, ale s převahou MP3, zdá se, že většina lidí buď nemůže říct nebo nevadí rozdíl.