15 nejoblíbenějších algoritmů pro kompresi dat

Algoritmy pro kompresi dat lze definovat jako proces zmenšení velikosti souborů při zachování stejných nebo do určité míry podobných dat. To se provádí provedením eliminace nepotřebných dat nebo opětovným vytvořením dat pro vyšší efektivitu.

Při kompresi máte možnost vybrat si ze ztrátových nebo bezeztrátových metod. Pokud hovoříme o ztrátové metodě, dochází při ní k trvalému vymazání dat. Na druhou stranu bezeztrátová se postará o původní data. Typ, který si vyberete, závisí na tom, jak kvalitní soubory požadujete.
V tomto článku najdete směs bezeztrátových algoritmů komprese dat a algoritmů komprese obrazu a videa založených na hlubokém učení.

Bezztrátové algoritmy komprese dat jsou obvykle bytosti používané pro plnění funkce archivu nebo jiných vysoce kvalitních funkcí. Tyto algoritmy komprese dat umožňují provést zmenšení velikosti souboru. Zajišťují také, že soubory lze v případě potřeby plně obnovit.

LZ77

LZ77 byl oznámen v roce 1977 a označován jako základ tolika dalších bezeztrátových kompresních algoritmů. Obvykle používá metodu „posuvného okna“. V této metodice se stará o slovník, který využívá trojice pro reprezentaci:

• Offset- Lze jej označit jako skutečný začátek fráze a začátek souboru.
• Run-length-Definuje se jako množství znaků, které vám pomáhají při vytváření fráze.
• Deviating characters-The are the marketers that indicate a new phrase.

Obsahuje označení, že použitá fráze je zcela shodná s původní frází, a také definuje, zda existuje nějaký odlišný znak.

Když budete analyzovat soubor, slovník se dynamicky aktualizuje pro odraz obsahu komprimovaných dat a také velikosti.

LZR

LZR byl vyvinut a oznámen v roce 1981. Oznámil jej Michael Rodeh, který jej později upravil. Lze jej použít jako primární alternativu ke kompresnímu algoritmu LZ77, ale máte také možnost jej použít pro libovolný offset v rámci souboru. Pokud jej nepoužíváte lineárně, pak potřebuje značné množství paměťového prostoru. Díky této podmínce je LZ77 lepší volbou pro použití. Tento algoritmus komprese dat je jednoduchý na implementaci a při implementaci na hardwaru má potenciál velmi vysokého výkonu.

Jedná se o algoritmus, který je široce používaným kompresním algoritmem unixových nástrojů pro kompresi dat a používá se v obrazovém formátu GIF. Stal se prvním algoritmem komprese dat, který byl široce používán na počítačích. Velký anglický textový soubor lze obvykle zkomprimovat pomocí LZW přibližně na polovinu původní velikosti.

LZSS

LZSS je zkratka pro Lempel Ziv Storer Szymanski a byl vyvinut a oznámen v roce 1982. Jedná se o algoritmus komprese dat, který vylepšuje algoritmus LZ77. Tento proces komprese probíhá tak, že obsahuje metodu, která bude hlídat, zda záměna zmenšuje velikost souboru. Pokud se nezmenší, pak bude vstup ponechán v původní podobě. Také nepreferuje použití odchylných znaků a upřednostňuje pouze použití párů délky posunu.

Tento algoritmus se používá hlavně pro archivaci souborů do různých formátů, jako je RAR nebo ZIP, nebo pro kompresi síťových dat.

Lze jej označit jako techniku slovníkového kódování. LZSS se snaží nahradit řetězec symbolů odkazem na slovníkové umístění stejného řetězce. Hlavní rozdíl mezi LZ77 a LZSS spočívá v tom, že v LZ77 může být odkaz na slovník delší než řetězec, který nahrazuje. V LZSS jsou takové odkazy vynechány, pokud je délka menší než bod „zlomu“.

Deflate

Deflate je formát souboru s bezeztrátovým algoritmem komprese dat, který využívá kombinaci LZSS a Huffmanova kódování. Navrhl jej Phil Katz v roce 1993. Huffmanovo kódování je také algoritmus, který byl vyvinut v roce 1952. Lze jej definovat jako algoritmus entropického kódování, který pomáhá při přiřazování kódu na základě četnosti znaků.

Katz také navrhl původní algoritmus, který se používá ke konstrukci proudů Deflate. Jak bylo uvedeno v dokumentu RFC, algoritmus vytvářející soubory Deflate byl obecně považován za implementovatelný způsobem, na který se nevztahovaly patenty. To vedlo k jeho širokému používání, kromě formátu souborů ZIP, který byl hlavním účelem Katzova návrhu. Patent již není k dispozici.

LZMA

LZMA je zkratka pro algoritmus Lempel Ziv Markovova řetězce a byl navržen a vydán v roce 1998. Lze o něm také říci, že je modifikací algoritmu LZ77. Tato modifikace byla provedena pro archivátor -Zip s formátem .7z. Používá se metoda řetězové komprese, která implementuje modifikovaný LZ77 spíše na úrovni bitů než bajtů. Výstupní výskyt bude dále zpracován pomocí aritmetického kódování pro provedení další komprese.

Výkon dalších kroků komprese závisí na přesné implementaci. Tento algoritmus komprese dat používá slovníkové kompresní schéma poněkud velmi podobné algoritmu LZ77, který publikovali Abraham Lempel a Jacob Ziv v roce 1977. Rovněž se vyznačuje vysokým kompresním poměrem a proměnlivou velikostí kompresního slovníku. Přitom si stále zachovává rychlost dekomprese velmi podobnou ostatním běžně používaným kompresním algoritmům.

LZMA2

LZMA2 byl navržen a vydán v roce 2009. Lze jej také definovat jako modifikaci LZMA. Zlepšuje LZMA tím, že zvyšuje jeho výkon díky větším možnostem vícevláknového zpracování. LZMA2 také poskytuje lepší práci s nestlačitelnými daty. Jedná se o jednoduchý kontejnerový formát, který může obsahovat jak nekomprimovaná data, tak data LZMA, a to i s více různými parametry kódování LZMA.

LZMA2 podporuje libovolně škálovatelnou vícevláknovou kompresi a dekompresi a účinnou kompresi dat, která jsou částečně nekomprimovatelná. Může však mít určité problémy se zabezpečením a může být nebezpečný a méně účinný než LZMA. Zjednodušeně řečeno, může být pro vás užitečný, ale ano, ve srovnání s LZMA není tak bezpečný.

Komprese založená na vícevrstvém perceptronu (MLP)

MLP lze definovat jako technologii, která používá více neuronových vrstev pro vstup, zpracování a poskytování výstupních dat. Lze ji implementovat pro úlohy zmenšování rozměrů a také pro kompresi dat. Algoritmus založený na MLP byl poprvé vyvinut v roce 1988 a připojuje se k již existujícím procesům:

• Binární kódování – standardní dvousymbolové kódování.
• Kvantování – problémy vstupu ze spojité množiny na diskrétní množinu.
• Transformace prostorové oblasti – změny dat po jednotlivých pixelech.

Pro určení optimálního binárního kódu využívá algoritmus MLP výstupy z výše uvedených procesů do rozkladné neuronové sítě.

Dále byl tento algoritmus modifikován intuitivními technikami, které umožnily přesnou aproximaci dat zcela na základě sousedních dat prostřednictvím zpětného šíření. Může vám být velmi užitečný při kompresi obrazových a video dat.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder je definován jako rámec založený na konvoluční neuronové síti (CNN). Díky tomu představuje alternativu k těm technikám komprese videa, které jsme tak dlouho používali. Pro prediktivní a zbytkové signály přináší tento model různé konvoluční neuronové sítě (CNN).

Provádí kódování map příznaků do binárního toku pomocí skalární kvantizace a velmi starého a tradičního algoritmu komprese souborů zvaného Huffmanovo kódování. Tvrdí se, že tento model je schopen poskytnout vynikající výkon ve srovnání se známým standardem kódování videa H.264/AVC.

Konvoluční neuronová síť (CNN) – komprese založená na

CNN jsou definovány jako neuronové sítě různých vrstev. Používají se hlavně k rozpoznávání obrazů a detekci prvků. V okamžiku, kdy ji použijete pro kompresi, využívají tyto sítě konvoluci pro výpočet spojení mezi sousedními pixely. Pokud je porovnáme s algoritmy založenými na MLP, vykazují sítě CNN lepší výsledky komprese než ony.

Také vám poskytují lepší výkon superrozlišení a redukci artefaktů. Kromě toho algoritmy komprese dat založené na CNN umožňují zlepšení kvality obrázků JPEG. Děje se tak díky snížení poměru špičkového signálu k šumu a strukturální podobnosti.

Komprese na bázi CNN si také může rozumět s výkonem standardu High-Efficiency Video Coding. To se provádí pomocí odhadu entropie. Může být také velmi užitečný při provádění komprese souborů.

Komprese založená na generativních adverzních sítích (GAN)

GAN lze definovat jako alternativu neuronových sítí, která využívá dvě sítě, které si konkurují. To se provádí za účelem tvorby přesnějších analýz a předpovědí. V roce 2017 byly poprvé vyvinuty algoritmy založené na GAN. Tyto algoritmy pro kompresi dat mohou komprimovat soubory více než dvaapůlkrát menší ve srovnání s tradičními běžně používanými metodami, jako je JPEG nebo WebP.

Algoritmy založené na GAN lze použít pro kompresi v reálném čase s tím, že se společně používá paralelní zpracování. Tento algoritmus funguje tak, že komprimuje obrázky kompletně na základě nejvíce odpovídajících rysů.

Při dekódování se na základě předpovědí, které byly provedeny pomocí těchto rysů, rekonstruují obrazy. Pokud ji porovnáme s kompresí založenou na CNN, Komprese založená na GAN pro vás vytvoří velmi kvalitní obrazy díky eliminaci nepříznivých ztrát.

Predikce částečnou shodou (PPM)

PPM je adaptivní statistická technika komprese dat založená na kontextovém modelování a predikci. Tyto modely využívají sadu předchozích symbolů v nekomprimovaném proudu symbolů k předpovědi dalšího symbolu v proudu. Algoritmy PPM lze také použít ke shlukování dat do předpovídaných skupin při shlukové analýze.
Počet předchozích symbolů, n, určuje pořadí modelu PPM, který se označuje jako PPM(n).

Existují také neomezené varianty, kde kontext nemá žádná délková omezení, a označují se jako PPM. Pokud nelze provést predikci na základě všech n kontextových symbolů, je proveden pokus o predikci pomocí n – 1 symbolu. Tento proces se opakuje, dokud není nalezena shoda nebo dokud v kontextu nezbývají žádné další symboly. V tomto okamžiku je provedena pevná predikce.
Implementace komprese PPPM se značně liší v dalších detailech. Vlastní výběr symbolů se obvykle zaznamenává pomocí aritmetického kódování, i když je možné použít také Huffmanovo kódování nebo dokonce nějaký typ techniky slovníkového kódování.

Kódování délky běhu (RLE)

RLW je forma bezeztrátové komprese dat, při které se běhy dat (sekvence, v nichž se stejná hodnota dat vyskytuje v mnoha po sobě jdoucích datových prvcích) ukládají jako jedna hodnota dat a počet, nikoli jako původní běh. To je nejužitečnější u dat, která obsahují mnoho takových průběhů.

Například jednoduché grafické obrázky, jako jsou ikony, čárové kresby, Conwayova hra na život a animace. Není užitečná u souborů, které neobsahují mnoho běhů, protože by mohla značně zvětšit velikost souboru.

RLE lze také použít pro označení raného formátu grafických souborů podporovaného společností CompuServe pro kompresi černobílých obrázků, který však byl široce vytlačen jejich pozdějším formátem Graphics Interchange Format (GIF). RLE také odkazuje na málo používaný formát obrázků v systému Windows 3.x s příponou rule, což je Run Length Encoded Bitmap, používaný ke kompresi úvodní obrazovky systému Windows 3.x.

bzip2

bzip2 je svobodný a open-source program pro kompresi dat, který používá Burrows-Wheelerův algoritmus. Komprimuje pouze jednotlivé soubory a není archivátorem souborů. Jeho autorem je Julian Seward a správcem Federico Mena. Seward poprvé veřejně vydal bzip2 ve verzi 0.15 v červenci 1996. Stabilita a popularita kompresoru během několika následujících let rostla a koncem roku 2000 Seward vydal verzi 1.0.

Po devítileté přestávce v aktualizacích projektu od roku 2010. Dne 4. června 2019 přijal Federico Mena funkci správce projektu bzip2. bzip2 komprimuje data v blocích o velikosti 100 až 900 kB.

Používá Burrows-Wheelerovu transformaci k převodu často se opakujících posloupností znaků na řetězce stejných písmen. Poté použije transformaci move-to-front a Huffmanovo kódování. bzip2 předchůdce bzip používal aritmetické kódování místo Huffmanova. Změna byla provedena kvůli omezení softwarového patentu.

Huffmanovo kódování

Huffmanův kód je zvláštní typ optimálního prefixového kódu, který se běžně používá pro bezeztrátovou kompresi dat. Proces nalezení nebo použití takového kódu probíhá tak, že se využije Huffmanovo kódování, algoritmus vyvinutý Davidem A. Huffmanem v době, kdy byl studentem doktorského studia na MIT, a publikovaný v roce 1952 v článku „A Method for the Construction of Minimum-Redundancy Codes“.

Výstup Huffmanova algoritmu lze považovat za kódovou tabulku proměnné délky pro kódování zdrojového symbolu (například znaku v souboru). Algoritmus odvozuje tuto tabulku z odhadované pravděpodobnosti nebo četnosti výskytu (váhy) pro každou možnou hodnotu zdrojového symbolu.

Stejně jako v jiných metodách entropického kódování jsou častější symboly obecně reprezentovány pomocí menšího počtu bitů než méně časté symboly. Huffmanovu metodu lze efektivně implementovat. Nalezení kódu v čase lineárním k počtu vstupních vah, pokud jsou tyto váhy seřazeny.

ZStandard

Zstandard (nebo zstd) je algoritmus bezeztrátové komprese dat, který vyvinul Yann Collet ve společnosti Facebook. Zstd je referenční implementace v jazyce C. Verze 1 této implementace byla uvolněna jako svobodný software 31. srpna 2016.
Zstandard byl navržen tak, aby poskytoval kompresní poměr srovnatelný s algoritmem DEFLATE (vyvinutým v roce 1991 a použitým v původních programech ZIP a gzip), ale rychlejší, zejména při dekompresi. Je laditelný s úrovněmi komprese od záporných 5 (nejrychlejší) do 22 (nejpomalejší rychlost komprese, ale nejlepší kompresní poměr).

Zstd při maximální úrovni komprese poskytuje kompresní poměr blízký LZMA, LZAHM a PPM. Je výkonnější než LZA nebo bzip2. Zstandard dosahuje současné Paretovy hranice, protože dekomprimuje rychleji než jakýkoli jiný v současnosti dostupný algoritmus s podobným nebo lepším kompresním poměrem

Slovníky mohou mít velký vliv na kompresní poměr malých souborů, takže Zstandard může používat kompresní slovník zadaný uživatelem. Nabízí také tréninkový režim, který dokáže generovat slovník ze sady vzorků.

Závěr

Tyto algoritmy komprese dat vám pomohou optimalizovat velikost souboru. Různé typy algoritmů komprese dat vám poskytnou různé výsledky. Pokud zde však nenajdete ten správný algoritmus, můžete se podívat do tohoto průvodce a upřesnit své hledání. Algoritmů není málo, ale při hledání správného algoritmu pro váš projekt musíte být konkrétní.

Doufám, že tento článek byl pro vás užitečný při výběru nejlepšího algoritmu komprese dat podle vašich potřeb. Děkujeme vám za přečtení tohoto článku. Můžete se také podívat na článek Nejlepší šifrovací a hashovací algoritmy.

Zůstaňte naladěni

.