Bezeztrátová komprese

Bezeztrátová komprese (bezeztrátová komprimace, též neztrátová, bezztrátová) je jeden ze dvou základních přístupů ke kompresi dat. Jedná se o algoritmy, které dovolují přesnou zpětnou rekonstrukci komprimovaných dat, na rozdíl od ztrátové komprese, kde se to záměrně neděje. Bezeztrátová komprese se používá všude tam, kde je důležité, aby se originální data a data po kompresi a následné dekompresi zcela shodovala – např. texty nebo audiovizuální data, u kterých uživatel nechce ani sebemenší ztrátu kvality.

Existuje mnoho různých formátů pro bezeztrátovou kompresi obecných dat. Například velmi populární je ZIP, se kterým lze pracovat téměř na jakékoli platformě. Dalším oblíbeným formátem je RAR, který je komerční – existují pro něj komerční nástroje na většině platforem, ale svobodné nástroje pro vytváření archivů RAR neexistují. Mezi open source komunitami jsou oblíbeny formáty gzip a bzip2, jejichž algoritmy mají tu výhodu, že nejsou patentované. Dalším méně známým, ale velice výkonným kompresním algoritmem je LZMA, který je užíván například programem 7-Zip.

Jednotlivé algoritmy můžeme rozdělit podle typů dat, pro které jsou určeny (text, obraz, zvuk, video, obecná data). Algoritmy pro obecná data v praxi obvykle nejsou schopny docílit tak vysokého kompresního poměru (poměru velikosti dat před a po komprimaci) jako specializované algoritmy. Například zvukový soubor nebude příliš úspěšně komprimovaný algoritmem určeným pro textové soubory.

Většina bezeztrátových komprimačních programů nepoužívá jen jeden algoritmus, ale hned několik najednou. U některých komprimačních programů jsou data napřed transformována a až poté komprimována, přičemž transformace slouží k dosažení lepších kompresních poměrů.

Tyto algoritmy ve skutečnosti nic nekomprimují, pouze upravují data tak, aby se dala lépe zkomprimovat. Je také podmínkou, že ke každé transformaci musí existovat transformace inverzní, která bude schopna obnovit původní data.

• Burrowsova-Wheelerova transformace (BWT)
• Move-to-front transformace (MTF I a MTF II)
• Weighted frequency count (WFC)
• Distance coding (DC)
• Inverse frequency coding (IF)

Algoritmy v této skupině vytvářejí v průběhu komprimace slovník na základě dat již zkomprimovaných, v němž se pak snaží najít data, která se teprve mají komprimovat. Pokud jsou data nalezena ve slovníku, algoritmus zapíše pozici dat ve slovníku místo samotných dat.

• Lempel-Ziv 77 (LZ77)
• Lempel-Ziv 78 (LZ78)
• Lempel-Ziv-Welch (LZW) – podobný LZ78, byl velmi populární, ale také byl patentovaný
• LZMA

Snaží se určitým způsobem předvídat, jaké znaky budou v souboru dat následovat. Pro znaky s vyšší pravděpodobností výskytu vyhradí algoritmus kratší informaci pro jejich zapsání, pro znaky s nižší pravděpodobností výskytu vyhradí naopak delší informaci pro jejich zapsání.

Statistické metody dále dělíme na metody se statickým modelem (model slouží pro vypočítávání pravděpodobnosti výskytu znaků) a metody s adaptivním modelem. Metody se statickým modelem vytvoří před komprimací dat určitý model a podle něho zkomprimují celý soubor dat, zatímco metody s adaptivním modelem průběžně model aktualizují.

Obecně lze říci, že metody se statickým modelem bývají dvouprůchodové a metody s adaptivním modelem jednoprůchodové.

• Shannonovo-Fanovo kódování
• Huffmanovo kódování
• Aritmetické kódování
• Range coding (RC)
• ACB
• Prediction by partial match (PPM)

• Run-length encoding (RLE)
• Potlačení nul
• Bitové mapy
• Půlbajtové kódování

• Apple Lossless – ALAC (Apple Lossless Audio Codec)
• Direct Stream Transfer – DST
• Free Lossless Audio Codec – FLAC
• Meridian Lossless Packing – MLP
• Monkey's Audio – Monkey's Audio APE
• RealPlayer – RealAudio Lossless
• Shorten – SHN
• TTA – True Audio Lossless
• WavPack – WavPack lossless/"hybrid"
• WMA Lossless – Windows Media Lossless
• TAK – Tom's Audio-Kompressor

• FLIF – primárně bezeztrátový
• ABO (Adaptive Binary Optimization)
• GIF – vždy bezeztrátový, avšak omezený limitem 256 různých barev v jednom rámci
• JBIG2 v bezeztrátové variantě
• JPEG 2000 v bezeztrátové variantě
• JPEG-LS – bezeztrátový / téměř bezeztrátový kompresní standard
• JPEG XL v bezeztrátové variantě
• PNG – vždy bezeztrátový
• TIFF v bezeztrátových variantách
• WebP v bezeztrátové variantě

• AV1 v bezeztrátové variantě
• Huffyuv
• SheerVideo
• CorePNG
• MSU Lossless Video Codec
• LCL
• Animation codec
• Lagarith
• H.264 / AVC v bezeztrátové variantě
• H.265 / HEVC v bezeztrátové variantě

• David A. Huffman
• Ztrátová komprese

• Bezztrátová komprese obrázků (online nástroj)
• Jak správně optimalizovat obrázky pro web