Kompresní algoritmy: popis, základní techniky, charakteristiky

Komprese je zvláštní případ kódování, jehož hlavní charakteristikou je, že výsledný kód je menší než původní kód. Proces je založen na nalezení opakování v informačních řadách a následném uložení pouze jednoho vedle počtu opakování. Takže například, pokud se sekvence objeví v souboru jako "AAAAAA", zabírající 6 bajtů, bude uložen jako" 6A", který zabírá pouze 2 bajty, v kompresním algoritmu RLE.

Historie vzniku procesu

Morseova abeceda vynalezená v roce 1838 je prvním známým případem komprese dat. Později, když se v roce 1949 začaly získávat mainframové počítače, vynalezli Claude Shannon a Robert Fano kódování pojmenované podle autorů-Shannon-Fano. Toto šifrování přiřazuje kódy znakům v datovém poli podle teorie pravděpodobnosti.

Teprve v sedmdesátých letech s příchodem internetu a online úložiště byly implementovány plnohodnotné kompresní algoritmy. Huffmanovy kódy byly dynamicky generovány na základě vstupních informací. Klíčovým rozdílem mezi kódováním Shannon-Fano a Huffmanovým kódováním je to, že v prvním byl pravděpodobnostní strom konstruován zdola nahoru, čímž se vytvořil suboptimální výsledek a ve druhém byl vytvořen shora dolů.

V roce 1977 vydali Abraham Lempel a Jacob Ziv svou inovativní metodu LZ77 pomocí modernizovanějšího slovníku. V roce 1978 vydal stejný tým autorů vylepšený kompresní algoritmus LZ78. Který používá nový slovník, který analyzuje vstup a generuje statický slovník, nikoli dynamický jako verze 77.

Formy provedení komprese

Kompresi provádí program, který používá vzorec nebo algoritmus definující, jak snížit velikost dat. Například reprezentovat řetězec bitů s menším řetězcem 0 a 1 pomocí slovníku pro transformace nebo vzorce.

Komprese může být jednoduchá. Například, jak odstranit všechny zbytečných znaků, vložení jednoho opakujícího se kódu pro zadání řetězce opakování a nahrazení menšího bitového řetězce. Algoritmus komprese souborů je schopen snížit textový soubor na 50% nebo podstatně více.

Pro přenos se proces provádí v přenosové jednotce, včetně dat záhlaví. Když jsou informace odesílány nebo přijímány přes internet, mohou být archivovány jednotlivě nebo společně s jinými velkými soubory, mohou být přeneseny do ZIP, GZIP nebo jiného "zmenšený" formát.

Výhoda kompresních algoritmů:

1. Výrazně snižuje paměť. Při kompresním poměru 2: 1 zabere soubor 20 megabajtů (MB) 10 MB prostoru. Výsledkem je, že správci sítě tráví méně peněz a času ukládáním databází.
2. Optimalizuje výkon zálohování.
3. Důležitá metoda redukce dat.
4. Téměř jakýkoli soubor lze komprimovat, ale je důležité vybrat požadovanou technologii pro konkrétní typ souboru. Jinak mohou být soubory "zmenšený", celková velikost se však nezmění.

Používají se metody dvou typů-bezeztrátové kompresní algoritmy a ztrátové. První umožňuje obnovit soubor do původního stavu bez ztráty jednoho bitu informací v nekomprimovaném souboru. Druhý - je to typické přístup ke spustitelným souborům, textovým tabulkám a tabulkám, kde ztráta slov nebo čísel způsobí změnu informací.

Ztrátová komprese trvale odstraňuje datové bity, které jsou nadbytečné, nedůležité nebo nepostřehnutelné. Je užitečné s grafikou, zvukem, videem a obrázky, kde odstranění některých bitů nemá prakticky žádný znatelný vliv na prezentaci obsahu.

Huffmanův kompresní algoritmus

Tento proces lze použít pro "snížení" nebo šifrování.

Je založen na přiřazení kódů různých délek bitů k odpovídajícímu každému opakujícímu se znaku, čím více takových opakování, tím vyšší je kompresní poměr. Chcete-li obnovit zdrojový soubor, musíte znát přiřazený kód a jeho délku v bitech. Podobně, použijte program pro šifrování souborů.

Pořadí vytváření algoritmy komprese dat:

1. Vypočítejte, kolikrát se každý znak opakuje v souboru pro "snížení".
2. Vytvořte propojený seznam s informacemi o symbolech a frekvencích.
3. Proveďte třídění seznamu od nejmenšího po největší v závislosti na frekvenci.
4. Převést každou položku v seznamu do stromu.
5. Kombinujte stromy do jednoho, zatímco první dva tvoří nový.
6. Přidejte frekvence každé větve do nového prvku stromu.
7. Vložte nový na požadované místo v seznamu podle součtu přijatých frekvencí.
8. Přiřaďte každému znaku nový binární kód. Pokud je přijata nulová větev, přidá se do kódu nula a pokud je první větev, přidá se jedna.
9. Soubor je překódován podle nových kódů.
10. Například charakteristiky kompresních algoritmů pro krátký text:"ata la jaca a la estaca"
11. Spočítejte, kolikrát se každý znak objeví a vytvořte propojený seznam:" (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
12. Objednejte podle frekvence od nejnižší po nejvyšší: e (1), j (1), s (1), c (2), l (2), T (2), " (5), a (9)

Jak vidíte, kořenový uzel stromu je vytvořen, poté jsou přiřazeny kódy.

A zbývá jen zabalit bity do skupin po osmi, tj.:

Celkem osm bajtů a původní text byl 23.

Ukázka knihovny LZ77

Zvažte algoritmus LZ77 na příklad textu«howtogeek». Pokud to zopakujete třikrát, změní to takto.

Poté, když chce číst text zpět, nahradí každou instanci (h) výrazem "howtogeek" a vrátí se k původní frázi. To demonstruje algoritmus bezeztrátové komprese dat, protože data, která jsou zadána, jsou stejná jako data, která jsou přijímána.

Toto je ideální příklad, kdy je většina textu komprimována pomocí více znaků. Například slovo " to "bude komprimováno, i když se vyskytuje ve slovech jako "to"," jejich " a "to". S opakovanými slovy lze získat obrovské kompresní poměry. Například text se slovem "howtogeek" opakovaným 100krát má velikost tři kilobajty, při kompresi bude trvat pouze 158 bajtů, tj.% "zmenšování".

To je samozřejmě docela extrémní příklad, ale jasně ukazuje vlastnosti kompresních algoritmů. V obecné praxi je to 30-40% s textovým formátem ZIP. Algoritmus LZ77, platí pro všechna binární data, nejen pro text, i když je snazší komprimovat kvůli opakujícím se slovům.

Diskrétní kosinová transformace obrázků

Komprese videa a zvuku funguje velmi odlišně. Na rozdíl od textu, kde se provádí bezeztrátové kompresní algoritmy a data nebudou ztracena, s obrázky se provádí "zmenšování" se ztrátami a čím více%, tím více ztrát. To vede k těm strašně vypadajícím souborům JPEG, které lidé několikrát nahrávali, vyměňovali a pořizovali snímky obrazovky.

Většina obrázků, fotografií a dalších věcí ukládá seznam čísel, z nichž každý představuje jeden pixel. JPEG je ukládá pomocí algoritmu komprese obrazu zvaného diskrétní kosinová transformace. Je to soubor sinusových vln, které se sčítají s různou intenzitou.

Tato metoda používá 64 různých rovnic, poté Huffmanovo kódování, aby se dále zmenšila velikost souboru. Podobný algoritmus komprese obrazu dává šíleně vysoký kompresní poměr a snižuje jej z několika megabajtů na několik kilobajtů v závislosti na požadované kvalitě. Většina fotografií je komprimována, aby se ušetřila doba načítání, zejména pro mobilní uživatele se špatným přenosem dat.

Video funguje trochu jinak než obrázky. Algoritmy komprese grafických informací obvykle používají to, co se nazývá "komprese mezi snímky", která vypočítává změny mezi jednotlivými snímky a ukládá je. Například, pokud existuje relativně statický snímek, který ve videu trvá několik sekund, bude "zmenšený" v jednom. Komprese mezi snímky poskytuje digitální televizi a webové video. Bez něj by video vážilo stovky gigabajtů, což je větší než průměrná velikost pevného disku v roce 2005.

Komprese zvuku funguje podobně jako komprese textu a obrázků. Pokud JPEG odstraní detaily z obrazu, který lidské oko nevidí, komprese zvuku Ano, totéž pro zvuky. MP3 používá datový tok, v rozsahu od nižší úrovně 48 a 96 kbit/s (dolní limit) do 128 a 240 kbit / s (docela dobrý) do 320 kbit/s (vysoce kvalitní zvuk) a rozdíl lze slyšet pouze u výjimečně dobrých sluchátek. Existují bezztrátové kompresní kodeky pro zvuk, z nichž hlavní je FLAC a používá kódování LZ77 k přenosu bezztrátového zvuku.

Formáty "snížení" textu

Rozsah knihoven pro text se skládá hlavně z algoritmu bezeztrátové komprese dat, s výjimkou extrémních případů pro data s plovoucí desetinnou čárkou. Většina kompresorových kodeků zahrnuje "zmenšování" LZ77, Huffman a aritmetické kódování. Používají se po jiných nástrojích, aby vytlačily několik dalších procentních bodů komprese.

Běhy hodnot jsou kódovány jako symbol následovaný délkou běhu. Je možno správně obnovit původní proud. Pokud je délka série<= 2 znaky, má smysl nechat je beze změny, například jako na konci proudu s "bb".

V některých vzácných případech získají další úspory použitím transformace pomocí ztrátových kompresních algoritmů na části obsahu před použitím metody bez ztráty. Protože v těchto transformacích nelze soubory obnovit do původního stavu, jsou tyto "procesy" vyhrazeno pro textové dokumenty. Které netrpí ztrátou informací, například zkrácením číslic s plovoucí desetinnou čárkou pouze na dvě významná desetinná místa.

Dnes většina systémů komprese textu funguje kombinací různých transformací dat, aby se dosáhlo maximálního výsledku. Smyslem každé fáze systému je provést převést tak, aby další fáze mohla pokračovat v efektivní kompresi. Sečtením těchto kroků získáte malý soubor, který lze bezeztrátově Obnovit. Existují doslova stovky formátů a kompresních systémů, z nichž každý má své výhody a nevýhody ve vztahu k různým typům dat.

Schémata HTTP: DEFLATE a GZIP

Dnes web používá dva široce používané algoritmy komprese textu HTTP: DEFLATE a GZIP.

DEFLATE - obvykle kombinující data, s použitím LZ77, Huffmanova kódování. Soubor gzip používá DEFLATE uvnitř, spolu s některými zajímavými zámky, heuristikou filtrování, záhlaví a kontrolním součtem. Celkově lze říci, že další blokování a heuristika používající GZIP poskytují kvalitativní kompresní poměry než jen jeden DEFLATE.

Datové protokoly nové generace-SPDY a HTTP2.0, podporují kompresi záhlaví pomocí GZIP, takže většina webového zásobníku ji bude používat i v budoucnu.

Většina vývojářů Jednoduše nahraje nekomprimovaný obsah a spoléhá se na webový server "snížení" data za běhu. To poskytuje skvělé výsledky a snadno použitelný algoritmus komprese grafických obrázků. Ve výchozím nastavení je mnoho serverů nastaveno na gzip s úrovní 6, jejíž nejvyšší úroveň je 9. To se provádí záměrně, což umožňuje serverům rychleji komprimovat data na úkor většího výstupního souboru.

Formáty BZIP2 a LZMA, které vytvářejí kompaktnější tvary než GZIP, které se při tom dekomprimují rychleji.

LZMA lze považovat za vzdáleného příbuzného GZIP. Oba začínají populární slovník Lz následovaný statistickým kódovacím systémem. Vylepšená LZMA-schopnost komprimovat malé soubory však spočívá v jeho " pokročilých algoritmech mapování a oken LZ.

Předběžné zpracování dokumentu

Pro vysoce kvalitní kompresi se provádí dvoustupňový proces:

• fáze minimalizace;
• fáze bez ztráty.

Minifikace je zmenšení velikosti dat tak, aby mohla být použita bez zpracování, vymazáním mnoha zbytečných věcí v souboru, aniž by je syntakticky upravovala. Takže je bezpečné odstranit většinu mezer z Jscript, snížení velikosti beze změn syntaxe. Minifikace se provádí během procesu montáže. Buď jako ruční krok, nebo jako součást automatizovaného montážního řetězce.

Existuje mnoho programů, které provádějí základní kompresní algoritmy, mezi nimi:

1. Winzip je bezztrátový formát úložiště široce používaný pro dokumenty, obrázky nebo aplikace. Jedná se o poměrně jednoduchý program, který komprimuje každý ze souborů jednotlivě, což vám umožní obnovit každý, aniž byste museli číst zbytek. Tím se zvyšuje výkon procesu.
2. 7zip je bezplatný manažer pro velmi výkonný a nejjednodušší algoritmus komprese informací. Díky formátu souborů 7z, který vylepšuje standard ZIP o 50%. Podporuje ostatní nejběžnější jsou formáty jako RAR, ZIP, CAB, GZIP a ARJ proto nepředstavují problém pro použití s jakýmkoli komprimovaným souborem a integrují se do kontextové nabídky ve Windows.
3. GZIP je jedním z nejznámějších kompresorů určených pro Linux. Vzhledem k úspěchu na této platformě byl vylepšen pro Windows. Jednou z hlavních výhod gzip je, že používá algoritmus DEFLATE (kombinace kódování LZ77 a Huffman).
4. WinRAR-kompresorový program a multifunkční dekompresor dat. Jedná se o nepostradatelný nástroj pro úsporu místa na disku a doby přenosu při odesílání a přijímání souborů přes internet nebo při zálohování. Slouží ke kompresi všech typů dokumentů nebo programů tak, aby zabíraly méně místa na disku a mohly být rychleji ukládány nebo přenášeny po síti. Toto je první kompresor, který implementuje 64bitovou správu souborů, což umožňuje zpracování velkých objemů omezených pouze na operační systém.

Minifikátory CSS

Existuje mnoho minifikátorů CSS. Mezi Dostupné možnosti patří:

• online CSS Minifier;
• freeformatter.com/css-minifier;
• cleancss.com/css-minify;
• cnvyr.io;
• minifier.org;
• css-minifier.com.

Hlavní rozdíl mezi těmito nástroji závisí na hloubce jejich minifikačních procesů. Zjednodušená optimalizace tedy filtruje text, aby odstranila zbytečné mezery a pole. Pokročilá optimalizace zahrnuje nahrazení "AntiqueWhite" výrazem "# FAEBD7", protože hexadecimální forma v souboru je kratší a vynucení znaku malého registru gzip.

Agresivnější způsoby CSS šetří místo, ale mohou porušit požadavky CSS. Většina z nich tedy nemá schopnost být automatizována a vývojáři si vybírají mezi velikostí nebo stupněm rizika.

Ve skutečnosti existuje nový trend vytváření dalších verzí z jazyků CSS, které pomáhají autorovi kódu efektivněji jako další výhoda, což umožňuje kompilátoru produkovat menší kód CSS.

Výhody a nevýhody komprese

Hlavními výhodami komprese jsou snížení hardwaru úložiště, doby přenosu dat a šířky pásma komunikace.

Takový soubor vyžaduje méně paměti a použití metody vede ke snížení nákladů na disk nebo SSD. Vyžaduje méně času na přenos při nízké šířce pásma sítě.

Hlavní nevýhodou komprese je dopad na výkon v důsledku využití prostředků CPU a paměti pro proces a následné dekomprese.

Mnoho výrobců vyvinulo systémy, aby se pokusilo minimalizovat dopad výpočetní techniky náročné na zdroje související s kompresí. Pokud se provádí před zápisem dat na disk, může systém proces uvolnit a uložit systémové prostředky. Například IBM používá samostatnou hardwarovou akcelerační kartu ke zpracování komprese v některých podnikových úložných systémech.

Pokud jsou data komprimována po jejich zápisu na disk nebo po zpracování, provede se na pozadí, aby se snížil dopad na výkon stroje. Ačkoli komprese po zpracování snižuje dobu odezvy pro každý vstup a výstup( I / O), stále spotřebovává paměť a cykly procesoru a ovlivňuje počet operací, které úložný systém zpracovává. Navíc, protože data musí být nativně zapsána na disk nebo flash disky nekomprimovaným způsobem, úspory fyzické paměti nejsou tak velké jako u vestavěné paměti "zmenšování".

Budoucnost není nikdy definována, ale na základě současných trendů je možné předpovědět, co se může stát s technologií komprese dat. Algoritmy míchání kontextu, jako je PAQ a jeho varianty, začaly získávat popularitu a mají tendenci dosahovat nejvyšších poměrů "snížení". I když jsou obvykle pomalé.

S exponenciálním zvýšením hardwarové rychlosti podle Mooreova zákona budou procesy míchání kontextu pravděpodobně vzkvétat. Protože náklady na rychlost jsou překonány rychlým hardwarem kvůli vysokému kompresnímu poměru. Algoritmus, který se PAQ snažil vylepšit, se nazývá "Predikce parciálních mapovacích cest". Nebo PPM.

A konečně, Lempel-Ziva-Markovův Řetězový algoritmus (LZMA) trvale vykazuje vynikající kompromis mezi rychlostí a vysokým kompresním poměrem a pravděpodobně v budoucnu vytvoří více nových možností. Povede to, protože již bylo přijato v mnoha konkurenčních formátech komprese, například v programu 7-Zip.

Dalším potenciálním vývojem je použití komprese pomocí výčtu podřetězců (CSE), což je slibná technologie a dosud nemá mnoho softwarových implementací.