Bezstratová kompresia je trieda kompresných algoritmov, ktorá umožňuje spätnú rekonštrukciu pôvodných údajov z komprimovaných dát bez akejkoľvek straty informácie. Bezstratová kompresia je možná preto, lebo väčšina reálnych údajov vykazuje štatistickú redundanciu. Naproti tomu stratová kompresia umožňuje zrekonštruovať len približnú podobu pôvodných údajov, spravidla však dosahuje výrazne vyšší kompresný pomer (a teda menšiu veľkosť výsledných súborov).

Z holubníkového princípu vyplýva, že žiadny bezstratový kompresný algoritmus nedokáže zmenšiť veľkosť úplne všetkých možných vstupných údajov – niektoré údaje sa po spracovaní predĺžia aspoň o jeden symbol alebo bit.

Kompresné algoritmy sú spravidla účinné pri dokumentoch čitateľných ľuďmi či strojmi a nedokážu zmenšiť veľkosť náhodných údajov, ktoré neobsahujú žiadnu redundanciu. Existuje mnoho rôznych algoritmov, ktoré sú navrhnuté buď pre konkrétny typ vstupných údajov, alebo na základe konkrétnych predpokladov o type redundancie, akú nekomprimované údaje pravdepodobne obsahujú.

Bezstratová kompresia dát sa využíva vo veľkom množstve aplikácií, napríklad vo formáte ZIP alebo v nástroji GNU gzip. Často sa používa aj ako súčasť stratových kompresných technológií (napríklad bezstratové predspracovanie typu mid/side stereo kódovania pri kodéroch formátu MP3 a iných stratových zvukových kodéroch).

Bezstratová kompresia sa používa všade tam, kde je dôležité, aby boli pôvodné a dekomprimované údaje identické, alebo kde by boli akékoľvek odchýlky od originálu nežiaduce. Typickými príkladmi sú spustiteľné programy, textové dokumenty a zdrojové kódy. Niektoré obrázkové formáty, napríklad PNG alebo GIF, používajú výhradne bezstratovú kompresiu, zatiaľ čo iné, napríklad TIFF alebo MNG, môžu využívať aj stratové metódy. Bezstratové zvukové formáty sa najčastejšie používajú na archiváciu alebo pri produkcii zvuku, zatiaľ čo menšie stratové zvukové súbory sa bežne používajú v prenosných prehrávačoch a v prípadoch, kde je úložný priestor obmedzený alebo kde presná reprodukcia zvuku nie je nevyhnutná.

Populárne nástroje využívajúce bezstratovú kompresiu sú okrem formátu ZIP aj pôvodne unixové programy bzip2 a compress, ako aj formáty RAR, StuffIt, 7-Zip a ARJ.

Techniky Väčšina programov na bezstratovú kompresiu postupuje v dvoch krokoch: najprv sa pre vstupné údaje vytvorí štatistický model, a následne sa tento model použije na priradenie vstupných údajov k bitovým postupnostiam tak, aby „pravdepodobné“ (teda často sa vyskytujúce) údaje vytvárali kratší výstup než údaje „nepravdepodobné“.

Hlavnými kódovacími algoritmami používanými na vytváranie bitových postupností sú Huffmanovo kódovanie (používané aj algoritmom Deflate) a aritmetické kódovanie. Aritmetické kódovanie dosahuje kompresný pomer blízky teoretickému optimu pre daný štatistický model, ktoré je určené informačnou entropiou, zatiaľ čo Huffmanovo kódovanie je jednoduchšie a rýchlejšie, no dosahuje horšie výsledky pri modeloch, v ktorých sa pravdepodobnosti niektorých symbolov blížia k 1.

Existujú dva základné spôsoby konštrukcie štatistických modelov. Pri statickom modeli sa údaje najprv analyzujú a zostaví sa model, ktorý sa následne uloží spolu s komprimovanými dátami. Tento prístup je jednoduchý a modulárny, no má nevýhodu v tom, že samotné uloženie modelu môže byť nákladné a že vynucuje použitie jediného modelu pre všetky komprimované údaje, čo vedie k horším výsledkom pri súboroch s heterogénnym obsahom. Adaptívne modely naopak model priebežne aktualizujú počas kompresie. Kodér aj dekodér začínajú s triviálnym modelom, čo spočiatku vedie k slabej kompresii, ale s postupným „učením sa“ o údajoch sa výkon zlepšuje. Väčšina bežne používaných moderných kompresných metód dnes využíva práve adaptívne kodéry.

Bezstratové kompresné metódy možno kategorizovať podľa typu údajov, na kompresiu ktorých sú určené. Hoci v princípe možno akýkoľvek všeobecný bezstratový kompresný algoritmus (teda taký, ktorý akceptuje ľubovoľný bitový reťazec) použiť na ľubovoľný typ údajov, mnohé z nich nedosahujú výraznú kompresiu pri údajoch, ktoré nezodpovedajú forme, pre akú boli navrhnuté. Mnohé kompresné techniky používané pre text pritom fungujú pomerne dobre aj pre obrázky s indexovanou farbou.

Multimédiá Tieto techniky využívajú špecifické vlastnosti obrázkov, napríklad bežný jav súvislých dvojrozmerných oblastí s podobnými tónmi. Každý pixel okrem prvého sa nahradí rozdielom oproti svojmu ľavému susedovi, čím vzniknú malé hodnoty s oveľa vyššou pravdepodobnosťou výskytu než hodnoty veľké. Podobný postup sa často aplikuje aj na zvukové súbory a dokáže dobre komprimovať súbory obsahujúce prevažne nízke frekvencie a nízku hlasitosť. Pri obrázkoch možno tento krok zopakovať výpočtom rozdielu oproti hornému pixelu, a pri videu možno navyše počítať rozdiel oproti zodpovedajúcemu pixelu v nasledujúcej snímke.

Adaptívne kódovanie využíva pravdepodobnosti z predchádzajúcej vzorky pri kódovaní zvuku, z ľavého a horného pixelu pri kódovaní obrazu, a navyše z predchádzajúcej snímky pri kódovaní videa. Pri vlnkovej transformácii sa pravdepodobnosti prenášajú aj naprieč hierarchiou.

Historicko-právne otázky Mnohé z týchto metód sú implementované v otvorených aj proprietárnych nástrojoch, predovšetkým algoritmus LZW a jeho varianty. Niektoré algoritmy sú v Spojených štátoch a v iných krajinách chránené patentmi a ich legálne používanie si vyžaduje licenciu od držiteľa patentu. Pre patenty na určité druhy kompresie LZW a najmä pre licenčnú politiku držiteľa patentu, spoločnosti Unisys, ktorú mnohí vývojári považovali za zneužívajúcu, časť zástancov otvoreného softvéru odporúčala nepoužívať formát GIF na kompresiu statických obrázkov a nahradiť ho formátom PNG, ktorý kombinuje algoritmus Deflate založený na LZ77 so súborom doménovo špecifických predikčných filtrov. Platnosť patentov na LZW však vypršala 20. júna 2003.

Ako už bolo spomenuté, bezstratová kompresia zvuku je pomerne špecializovaná oblasť. Algoritmy na bezstratovú kompresiu zvuku dokážu využiť opakujúce sa vzory vyplývajúce z vlnovej povahy dát – v podstate používajú autoregresné modely na predikciu „nasledujúcej“ hodnoty a kódujú (prípadne malý) rozdiel medzi očakávanou a skutočnou hodnotou. Ak je rozdiel medzi predikovanými a skutočnými údajmi (nazývaný chyba) zvyčajne malý, potom sa určité hodnoty rozdielu (napríklad 0, +1, −1 a podobne) stávajú veľmi častými, čo možno využiť ich zakódovaním do malého počtu výstupných bitov.

Niekedy je výhodné komprimovať len rozdiely medzi dvomi verziami súboru (alebo pri kompresii videa medzi po sebe idúcimi obrázkami v postupnosti). Táto technika sa nazýva deltakódovanie (podľa gréckeho písmena Δ, ktoré v matematike označuje rozdiel), pričom tento pojem sa zvyčajne používa len vtedy, ak majú obe verzie zmysel aj mimo samotnej kompresie a dekompresie.

Metódy Žiadny bezstratový kompresný algoritmus nedokáže efektívne skomprimovať všetky možné údaje (podrobnejšie pozri časť Obmedzenia). Preto existuje mnoho rôznych algoritmov, ktoré sú navrhnuté buď pre konkrétny typ vstupných údajov, alebo na základe konkrétnych predpokladov o type redundancie, akú nekomprimované údaje pravdepodobne obsahujú. Nižšie sú uvedené niektoré z najbežnejšie používaných bezstratových kompresných algoritmov.

Všeobecné použitie ANS – entropické kódovanie používané formátmi LZFSE a Zstandard Aritmetické kódovanie – entropické kódovanie Burrows–Wheelerova transformácia – reverzibilná transformácia zvyšujúca kompresibilitu textových údajov, používaná algoritmom bzip2 Huffmanovo kódovanie – entropické kódovanie, dobre sa kombinuje s inými algoritmami Lempel-Zivova kompresia (LZ77 a LZ78) – slovníkový algoritmus, ktorý tvorí základ mnohých ďalších algoritmov Deflate – kombinuje LZ77 s Huffmanovým kódovaním, používaný formátmi ZIP, gzip, zlib a PNG Brotli – využíva LZ77 s veľkým posuvným oknom (až 16 MiB), Huffmanovo kódovanie a kontextové modelovanie LZ4 – veľmi rýchla kompresia aj dekompresia Lempel–Ziv–Markov (LZMA) – veľmi vysoký kompresný pomer, používaný nástrojmi 7-Zip a xz Lempel–Ziv–Storer–Szymanski (LZSS) – používaný nástrojom WinRAR spolu s Huffmanovým kódovaním Lempel–Ziv–Welch (LZW) – používaný formátom GIF a unixovým nástrojom compress Prediction by Partial Matching (PPM) – optimalizovaný na kompresiu čistého textu Kódovanie s dĺžkou behu (RLE) – jednoduchá schéma poskytujúca dobrú kompresiu údajov s dlhými sériami rovnakej hodnoty

Zvuk Adaptive Transform Acoustic Coding (ATRAC) Apple Lossless (ALAC) Audio Lossless Coding (MPEG-4 ALS) Direct Stream Transfer (DST) Dolby TrueHD DTS-HD Master Audio Free Lossless Audio Codec (FLAC) Meridian Lossless Packing (MLP) Monkey's Audio (APE) MPEG-4 SLS (HD-AAC) OptimFROG Original Sound Quality (OSQ) RealAudio Lossless Shorten (SHN) TTA (True Audio Lossless) WavPack Windows Media Audio 9 Lossless (WMA Lossless)

Rastrová grafika Výhradne bezstratové kódovanie: BMP PNG – Portable Network Graphics GIF – Graphics Interchange Format

Formáty umožňujúce stratové aj bezstratové kódovanie: AVIF – AV1 Image File Format FLIF – Free Lossless Image Format HEIF – High Efficiency Image File Format (na báze HEVC) ILBM – kódovanie RLE pre obrázky vo formáte Amiga IFF JBIG2 – kompresia čiernobielych obrázkov JPEG 2000 – prostredníctvom reverzibilnej celočíselnej vlnkovej transformácie Le Gall–Tabatabai 5/3 JPEG-LS JPEG XL JPEG XR – pôvodne WMPhoto a HD Photo LDCT – na báze diskrétnej kosínusovej transformácie PCX – PiCture eXchange QOI – Quite OK Image Format TGA – Truevision TGA TIFF – Tag Image File Format WebP

3D grafika OpenCTM – bezstratová kompresia 3D trojuholníkových sietí

Video Pozri zoznam bezstratových video kodekov.

Kryptografia Kryptosystémy často pred šifrovaním komprimujú údaje („otvorený text“) s cieľom zvýšiť bezpečnosť. Pri správnej implementácii kompresia výrazne zvyšuje tzv. unicity distance tým, že odstraňuje vzory, ktoré by mohli uľahčiť kryptoanalýzu. Mnohé bežné bezstratové kompresné algoritmy však vytvárajú hlavičky, obálky, tabuľky alebo iný predvídateľný výstup, ktorý môže kryptoanalýzu naopak uľahčiť. Kryptosystémy preto musia využívať také kompresné algoritmy, ktorých výstup takéto predvídateľné vzory neobsahuje.

Genetika a genomika Algoritmy kompresie genetických údajov (nezamieňať s genetickými algoritmami) predstavujú najnovšiu generáciu bezstratových algoritmov, ktoré komprimujú údaje (spravidla postupnosti nukleotidov) kombináciou konvenčných kompresných algoritmov a špecifických algoritmov prispôsobených genetickým údajom. V roku 2012 tím vedcov z Univerzity Johna Hopkinsa publikoval prvý algoritmus genetickej kompresie, ktorý nevyžaduje na kompresiu externé genetické databázy. Algoritmus HAPZIPPER bol navrhnutý pre údaje projektu HapMap a dosahuje viac ako 20-násobnú kompresiu (zmenšenie veľkosti súboru o 95 %), pričom poskytuje 2- až 4-násobne lepšiu kompresiu a je výrazne rýchlejší než popredné všeobecné kompresné nástroje.

Algoritmy na kompresiu genómových sekvencií, nazývané aj kompresory DNA sekvencií, využívajú charakteristické vlastnosti DNA sekvencií, napríklad invertované repetície. Medzi najúspešnejšie kompresory patria XM a GeCo. Pri eukaryotoch dosahuje o niečo lepší kompresný pomer algoritmus XM, no pri sekvenciách väčších než 100 MB sú jeho výpočtové nároky nepraktické.

Spustiteľné súbory Samorozbaľovacie spustiteľné súbory obsahujú komprimovanú aplikáciu a dekompresor. Pri spustení dekompresor transparentne dekomprimuje a spustí pôvodnú aplikáciu. Táto technika sa často využíva pri tvorbe tzv. dema, kde sa organizujú súťaže o čo najmenšie demo s prísnymi limitmi veľkosti, niekedy len 1 kilobajt. Tento typ kompresie nie je obmedzený len na binárne spustiteľné súbory, ale možno ho aplikovať aj na skripty, napríklad v jazyku JavaScript.

Dokumenty